Computable isomorphism

In computability theory two sets $A;B \subseteq \N$ of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function $f \colon \N \to \N$ with $f(A) = B$. By the theorem of Myhill,^[1] 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

1. ↑ Theorem 7.VI, Hartley Rogers, Jr., Theory of recursive functions and effective computability

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