Computable isomorphism

In computability theory two sets $A;B\subseteq \mathbb{\mathbb{N}}$ of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function $f:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{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 $\nu$ and $\mu$ are called computably isomorphic if there exists a computable bijection $f$ so that $\nu =\mu \circ f$

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

References

• Theory of recursive functions and effective computability (2nd ed.), Cambridge, MA: MIT Press, 1987, ISBN 0-262-68052-1 .