Numbering (computability theory)

Definition and examples

A numbering of a set S is a surjective partial function from N to S (Ershov 1999:477). The value of a numbering ν at a number i (if defined) is often written ν_i instead of the usual ν ( i ) .

For example, the set of all finite subsets of N has a numbering γ in which γ ( ∅ ) = 0 and γ ( { a 0 , … , a k } ) = ∑ i ≤ k 2 a i (Ershov 1999:477).

As a second example, a fixed Gödel numbering φ i of the computable partial functions can be used to define a numbering W of the recursively enumerable sets, by letting by W(i) be the domain of φ_i.

Types of numberings

A numbering is total if it is a total function. If the domain of a partial numbering is recursively enumerable then there always exists an equivalent total numbering (equivalence of numberings is defined below).

A numbering η is decidable if the set { ( x , y ) : η ( x ) = η ( y ) } is a decidable set.

A numbering η is single-valued if η(x) = η(y) if and only if x=y; in other words if η is an injective function. A single-valued numbering of the set of partial computable functions is called a Friedberg numbering.

Comparison of numberings

There is a partial ordering on the set of all numberings. Let

and

be two numbering. Then ν 1 is reducible to ν 2 , written ν 1 ≤ ν 2 , if

If ν 1 ≤ ν 2 and ν 1 ≥ ν 2 then ν 1 is equivalent to ν 2 ; this is written ν 1 ≡ ν 2 .

Computable numberings

When the objects of the set S are sufficiently "constructive", it is common to look at numberings that can be effectively decoded (Ershov 1999:486). For example, if S consists of recursively enumerable sets, the numbering η is computable if the set of pairs (x,y) where y∈η(x) is recursively enumerable. Similarly, a numbering g of partial functions is computable if the relation R(x,y,z) = "[g(x)](y) = z" is partial recursive (Ershov 1999:487).

A computable numbering is called principal if every computable numbering of the same set is reducible to it. Both the set of all r.e. subsets of N and the set of all partial computable functions have principle numberings (Ershov 1999:487). A principle numbering of the set of partial recursive functions is known as an admissible numbering in the literature.