Recursive isomorphism

In computability theory, recursive isomorphism is an equivalence relation on sets of natural numbers .

definition

Sets of natural numbers are called recursively isomorphic if there is a total computable bijection such that . ${\displaystyle A;B\subseteq \mathbb {N} }$ ${\displaystyle A\equiv B}$ ${\displaystyle i\colon \mathbb {N} \to \mathbb {N} }$ ${\displaystyle i(A)=B}$

Numbering of a (at most) countable set is called recursively isomorphic if there is such a bijection with . ${\displaystyle \mu ;\nu \colon \mathbb {N} \to M}$ ${\displaystyle M}$ ${\displaystyle i\colon \mathbb {N} \to \mathbb {N} }$ ${\displaystyle \mu =\nu \circ i}$

The mapping is then called recursive isomorphism . ${\displaystyle i}$

properties

• Recursive isomorphism is an equivalence relation on the power set of the natural numbers. ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$
  • In particular, it is transitive .
• If there is a recursive isomorphism, its inverse function must also be computable. ${\displaystyle i\colon \mathbb {N} \to \mathbb {N} }$ ${\displaystyle i^{-1}}$
• A set is recursively isomorphic to the holding problem if and only if it is creative . ${\displaystyle H}$
  • In addition, according to the sentence below , these are exactly the RE - complete sets.

Myhill's isomorphism theorem

The following theorem by John Myhill provides a characterization of the concept of recursive isomorphism:

If again be sets of natural numbers, then: ${\displaystyle A;B\subseteq \mathbb {N} }$

${\displaystyle A\equiv B\Leftrightarrow A\preceq _{1}B\land B\preceq _{1}A}$

So two sets are recursively isomorphic if and only if they are one-one-equivalent .

The proof of this theorem is an effective variant of the proof of the Schröder-Bernstein theorem .

In the theory of Turing degrees , another important equivalence can be deduced with the help of the isomorphism theorem:

${\displaystyle A\equiv _{T}B\Leftrightarrow A'\equiv B'}$

Two sets are in the same Turing degree if and only if their respective Turing jumps are recursively isomorphic.

literature

• J. Myhill: Creative Sets . In: Journal for Mathematical Logic and Fundamentals of Mathematics Vol. 1 (1955), pp. 97-108.
• H. Rogers: Theory of recursive function and effective computability (2nd ed.). 1987, MIT Press, Cambridge, MA.