Numbering (computability theory) explained

In computability theory a numbering is the assignment of natural numbers to a set of objects such as functions, rational numbers, graphs, or words in some formal language. A numbering can be used to transfer the idea of computability^[1] and related concepts, which are originally defined on the natural numbers using computable functions, to these different types of objects.

Common examples of numberings include Gödel numberings in first-order logic, the description numbers that arise from universal Turing machines and admissible numberings of the set of partial computable functions.

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 \nu(i) .

Examples of numberings include:

• The set of all finite subsets of

N has a numbering \gamma , defined so that \gamma( 0 ) = \emptyset and so that, for each finite nonempty set A = \{a _{0,} \ldots, a _{k\}} , \gamma(n _{A)} = A where n _{A} = \sum _{i} 2 ^{a _{i}} (Ershov 1999:477). This numbering is a (partial) bijection.

• A fixed Gödel numbering

\varphi _{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. This numbering will be surjective (like all numberings) but not injective: there will be distinct numbers that map to the same recursively enumerable set under W.

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 preorder on the set of all numberings. Let

\nu _{1:} N \rightharpoonup S and \nu _{2:} N \rightharpoonup S be two numberings. Then \nu _{1} is reducible to \nu _{2} , written \nu _{1} \le \nu _{2} , if \exists f \in P ^{(1)} \forall i \in Domain (\nu _{1)} : \nu _{1(i)} = \nu _{2} \circ f(i).

If

\nu _{1} \le \nu _{2} and \nu _{1} \ge \nu _{2} then \nu _{1} is equivalent to \nu _{2} ; this is written \nu _{1} \equiv \nu _{2} .

Computable numberings

When the objects of the set S being numbered 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 recursively enumerable 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.

See also

• Complete numbering
• Cylindrification
• Gödel numbering
• Description number

References

• Y.L. Ershov (1999), "Theory of numberings", Handbook of Computability Theory, Elsevier, pp. 473 - 506.
• V.A. Uspenskiĭ, A.L. Semenov (1993), Algorithms: Main Ideas and Applications, Springer.

Notes and References

1. Web site: Computability Theory - an overview ScienceDirect Topics. 2021-01-19. www.sciencedirect.com.