In computability theory a numbering is an 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 S {\displaystyle S} is a surjective partial function from N {\displaystyle \mathbb {N} } to S (Ershov 1999:477). The value of a numbering ν {\displaystyle \nu } at a number i (if defined) is often written ν i {\displaystyle \nu _{i}} instead of the usual ν ( i ) {\displaystyle \nu (i)} . Examples of numberings include:
The set of all finite subsets of N {\displaystyle \mathbb {N} } has a numbering γ {\displaystyle \gamma } , defined so that γ ( 0 ) = ∅ {\displaystyle \gamma (0)=\emptyset } and so that, for each finite nonempty set A = { a 0 , … , a k } {\displaystyle A=\{a_{0},\ldots ,a_{k}\}} , γ ( n A ) = A {\displaystyle \gamma (n_{A})=A} where n A = ∑ i ≤ k 2 a i {\displaystyle n_{A}=\sum _{i\leq k}2^{a_{i}}} (Ershov 1999:477). This numbering is an injection. A fixed Gödel numbering φ i {\displaystyle \varphi _{i}} of the computable partial functions can be used to define a numbering W of the computably enumerable sets, by letting by W(i) be the domain of φ i {\displaystyle \varphi _{i}} . This numbering will be surjective (like all numberings) but not injective: there will be distinct numbers that map to the same computably 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 computably 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 ) } {\displaystyle \{(x,y):\eta (x)=\eta (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 ν 1 : N ⇀ S {\displaystyle \nu _{1}:\mathbb {N} \rightharpoonup S} and ν 2 : N ⇀ S {\displaystyle \nu _{2}:\mathbb {N} \rightharpoonup S} be two numberings. Then ν 1 {\displaystyle \nu _{1}} is reducible to ν 2 {\displaystyle \nu _{2}} , written ν 1 ≤ ν 2 {\displaystyle \nu _{1}\leq \nu _{2}} , if
∃ f ∈ P ( 1 ) ∀ i ∈ D o m a i n ( ν 1 ) : ν 1 ( i ) = ν 2 ∘ f ( i ) . {\displaystyle \exists f\in \mathbf {P} ^{(1)}\,\forall i\in \mathrm {Domain} (\nu _{1}):\nu _{1}(i)=\nu _{2}\circ f(i).}
… excerpt ends here. Continue reading the full article.
