Computable isomorphism

In computability theory two sets ${\displaystyle A,B}$ of natural numbers are computably isomorphic or recursively isomorphic if there exists a total computable and bijective function ${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$ such that the image of ${\displaystyle f}$ restricted to ${\displaystyle A\subseteq \mathbb {N} }$ equals ${\displaystyle B\subseteq \mathbb {N} }$, i.e. ${\displaystyle f(A)=B}$.

Further, two numberings ${\displaystyle \nu }$ and ${\displaystyle \mu }$ are called computably isomorphic if there exists a computable bijection ${\displaystyle f}$ so that ${\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 computable isomorphism coincides with the relation of mutual one-one reducibility.^[1]