Computable isomorphism

Recursive isomorphism is in computability theory 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.

Numbering of (at most) countable set called recursively isomorphic if there is a similar bijection with.

The figure is then called recursive isomorphism.

Properties

• Recursive isomorphism is an equivalence relation on the power set of the natural numbers. In particular, it is transitive.

• These are also down standing set exactly the RE -complete sets.

Isomorphism theorem of Myhill

The following sentence from John Myhill provides a characterization of the notion of recursive isomorphism:

Be again sets of natural numbers, then:

Two sets are exactly then recursively isomorphic if they are one-one equivalent.

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

In the theory of Turing degrees can be calculated using the Isomorphiesatzes another important equivalence conclude:

Two quantities are then exactly the same Turing degree when their respective Turing jumps are recursively isomorphic.