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 formal 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, 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  formula_1 is a surjective partial function from formula_2 to "S" (Ershov 1999:477). The value of a numbering "ν" at a number "i" (if defined) is often written "ν" instead of the usual formula_3. Examples of numberings include: 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 formula_11 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 formula_12 and formula_13 be two numberings. Then formula_14 is reducible to formula_15, written formula_16, if If formula_16 and formula_19 then formula_14 is equivalent to formula_15; this is written formula_22. 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 formula_2 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.