Recursively Enumerable Set - Equivalent Formulations

Equivalent Formulations

The following are all equivalent properties of a set S of natural numbers:

Semidecidability:

• The set S is recursively enumerable. That is, S is the domain (co-range) of a partial recursive function.
• There is a partial recursive function f such that:

Enumerability:

• The set S is the range of a partial recursive function.
• The set S is the range of a total recursive function or empty. If S is infinite, the function can be chosen to be injective.
• The set S is the range of a primitive recursive function or empty. Even if S is infinite, repetition of values may be necessary in this case.

Diophantine:

• There is a polynomial p with integer coefficients and variables x, a, b, c, d, e, f, g, h, i ranging over the natural numbers such that

• There is a polynomial from the integers to the integers such that the set S contains exactly the non-negative numbers in its range.

The equivalence of semidecidability and enumerability can be obtained by the technique of dovetailing.

The Diophantine characterizations of a recursively enumerable set, while not as straightforward or intuitive as the first definitions, were found by Yuri Matiyasevich as part of the negative solution to Hilbert's Tenth Problem. Diophantine sets predate recursion theory and are therefore historically the first way to describe these sets (although this equivalence was only remarked more than three decades after the introduction of recursively enumerable sets). The number of bound variables in the above definition of the Diophantine set is the best known so far; it might be that a lower number can be used to define all diophantine sets.