Numbering (computability theory)


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 language. A numbering can be used to transfer the idea of computability 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 and admissible numberings of the set of partial computable functions.

Definition and examples

A numbering of a set is a surjective partial function from to S. The value of a numbering ν at a number i is often written νi instead of the usual.
Examples of numberings include:
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.
A numbering η is decidable if the set is a decidable set.
A numbering η is single-valued if η = η 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 numberings. Then is reducible to, written,
if
If and then is equivalent to ; this is written.

Computable numberings

When the objects of the set S are sufficiently "constructive", it is common to look at numberings that can be effectively decoded. For example, if S consists of recursively enumerable sets, the numbering η is computable if the set of pairs where y∈η is recursively enumerable. Similarly, a numbering g of partial functions is computable if the relation R = " = z" is partial recursive.
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 and the set of all partial computable functions have principle numberings. A principle numbering of the set of partial recursive functions is known as an admissible numbering in the literature.