In computability theory two sets A , B {\displaystyle A,B} of natural numbers are computably isomorphic or recursively isomorphic if there exists a total computable and bijective function f : N → N {\displaystyle f\colon \mathbb {N} \to \mathbb {N} } such that the image of f {\displaystyle f} restricted to A ⊆ N {\displaystyle A\subseteq \mathbb {N} } equals B ⊆ N {\displaystyle B\subseteq \mathbb {N} } , i.e. f ( A ) = B {\displaystyle f(A)=B} . Further, two numberings ν {\displaystyle \nu } and μ {\displaystyle \mu } (of the same set of objects) are called computably isomorphic if there exists a computable bijection f {\displaystyle f} so that ν = μ ∘ f {\displaystyle \nu =\mu \circ f} . Computably isomorphic numberings induce the same notion of computability on a set.
Theorems By the Myhill isomorphism theorem, the relation of computably isomorphic coincides with the relation of mutual one-one reducibility.
References
Rogers, Hartley Jr. (1987), Theory of recursive functions and effective computability (2nd ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, MR 0886890.