Computable isomorphism

In computability theory two sets A ; B ⊆ N {displaystyle A;Bsubseteq mathbb {N} } of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function f : N → N {displaystyle fcolon mathbb {N} o mathbb {N} } with f ( A ) = B {displaystyle f(A)=B} . By the Myhill isomorphism theorem, the relation of computable isomorphism coincides with the relation of one-one reduction. In computability theory two sets A ; B ⊆ N {displaystyle A;Bsubseteq mathbb {N} } of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function f : N → N {displaystyle fcolon mathbb {N} o mathbb {N} } with f ( A ) = B {displaystyle f(A)=B} . By the Myhill isomorphism theorem, the relation of computable isomorphism coincides with the relation of one-one reduction. Two numberings ν {displaystyle u } and μ {displaystyle mu } are called computably isomorphic if there exists a computable bijection f {displaystyle f} so that ν = μ ∘ f {displaystyle u =mu circ f}