Computable isomorphism

In computability theory two sets A ; B ⊆ N of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function f : N → N with f ( A ) = B . By the Myhill isomorphism theorem, the relation of computable isomorphism coincides with the relation of one-one reduction.

Two numberings ν and μ are called computably isomorphic if there exists a computable bijection f so that ν = μ ∘ f

Computably isomorphic numberings induce the same notion of computability on a set.