# 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^{[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.

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 **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.

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).