Numbering (computability theory)

In computability theory a numbering is the assignment of natural numbers to a set of objects like rational numbers, graphs or words in some language. A numbering can be used to transfer the idea of computability and related concepts, which are strictly defined on the natural numbers using computable functions, to different objects.

Important numberings are the Gödel numbering of the terms in first-order predicate calculus and numberings of the set of computable functions which can be used to apply results of computability theory on the set of computable functions itself.

Definition

A numbering of a set $S \!$ is a partial surjective function

$\nu: \subseteq \mathbb{N} \to S.$

The value of $\nu \!$ at $i \!$ (if defined) is often written $\nu_i \!$ instead of the usual $\nu(i) \!$. $\nu \!$ is called a total numbering if $\nu \!$ is a total function.

If $S \!$ is a set of natural numbers, then $\nu \!$ is required to be a partial recursive function. If $S \!$ is a set of subsets of the natural numbers, then the set $\{\langle i,j \rangle : j \in \nu_i \}$ (using the Cantor pairing function) is required to be recursively enumerable.

Examples

• Given a Gödel numbering $\varphi_i$ we can define a numbering of the recursively enumerable sets by $W(i):=\mathrm{domain}(\varphi_i)$

Properties

It is often more convenient to work with a total numbering than with a partial one. If the domain of a partial numbering is recursively enumerable then there always exists an equivalent total numbering.

Comparison of numberings

Using computable function we can define a partial ordering on the set of all numberings. Given two numberings

$\nu_1: \subseteq \mathbb{N} \to S_1$

and

$\nu_2: \subseteq \mathbb{N} \to S_2$

we say $\nu_1$ is reducible to $\nu_2$ and write

$\nu_1 \le \nu_2$

if

$\exists f \in \mathbf{P}^{(1)} \, \forall i \in \mathrm{Domain}(\nu_1) : \nu_1(i) = \nu_2 \circ f(i).$

If $\nu_1 \le \nu_2$ and $\nu_1 \ge \nu_2$ then we say $\nu_1$ is equivalent to $\nu_2$ and write $\nu_1 \equiv \nu_2$.

See also

• Gödel numbering
• complete numbering
• cylindrification

References

• V.A. Uspenskiĭ, A.L. Semenov Algorithms: Main Ideas and Applications (1993 Springer) pp. 98ff.