computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...

complete numberings are generalizations of

Gödel numbering In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was developed by Kurt Gödel for the proof of his ...

first introduced by A.I. Mal'tsev in 1963. They are studied because several important results like the

Kleene's recursion theorem In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 b ...

and

Rice's theorem In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a synta ...

, which were originally proven for the Gödel-numbered set of

computable function Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...

s, still hold for arbitrary sets with complete numberings.

Definition

numbering There are many different numbering schemes for assigning nominal numbers to entities. These generally require an agreed set of rules, or a central coordinator. The schemes can be considered to be examples of a primary key of a database management s ...

\nu

of a set

A

is called complete (with respect to an element

a \in A

) if for every

partial computable function Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...

f

there exists a

total computable function Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...

h

so that (Ershov 1999:482): :

\nu \circ h(i) = 
\begin 
\nu \circ f(i) & \mbox ~ i \in \operatorname(f), \\
a & \mbox.
\end

Ershov refers to the element ''a'' as a "special" element for the numbering. A numbering

\nu

is called precomplete if the weaker property holds: :

\nu \circ f(i) = \nu \circ h(i) \qquad i \in \operatorname(f).

Examples

* Any numbering of a

singleton set In mathematics, a singleton, also known as a unit set or one-point set, is a set with exactly one element. For example, the set \ is a singleton whose single element is 0. Properties Within the framework of Zermelo–Fraenkel set theory, the ...

is complete * The

identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...

on the natural numbers is ''not'' complete * A

is precomplete

References

* Y.L. Ershov (1999), "Theory of numberings", ''Handbook of Computability Theory'', E.R. Griffor (ed.), Elsevier, pp. 473–506. {{ISBN, 978-0-444-89882-1 * A.I. Mal'tsev, ''Sets with complete numberings''. Algebra i Logika, 1963, vol. 2, no. 2, 4-29 (Russian) Computability theory