# Complete numbering

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Complete_numbering
> Markdown URL: https://mediated.wiki/source/Complete_numbering.md
> Source: https://en.wikipedia.org/wiki/Complete_numbering
> Source revision: 1019576317
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [computability theory](/source/computability_theory) '''complete numberings''' are generalizations of [Gödel numbering](/source/Numbering_(computability_theory)) first introduced by [A.I. Mal'tsev](/source/A.I._Mal'tsev) in 1963. They are studied because several important results like the [Kleene's recursion theorem](/source/Kleene's_recursion_theorem) and [Rice's theorem](/source/Rice's_theorem), which were originally proven for the Gödel-numbered set of [computable function](/source/computable_function)s, still hold for arbitrary sets with complete numberings.

== Definition ==

A [numbering](/source/numbering_(computability_theory)) <math>\nu</math> of a set <math>A</math> is called '''complete''' (with respect to an element <math>a \in A</math>) if for every [partial computable function](/source/partial_computable_function) <math>f</math> there exists a [total computable function](/source/total_computable_function) <math>h</math> so that (Ershov&nbsp;1999:482):
:<math> \nu \circ h(i) = 
\begin{cases} 
\nu \circ f(i) & \mbox{if} ~ i \in \operatorname{dom}(f), \\
a & \mbox{otherwise}.
\end{cases}
</math>

Ershov refers to the element ''a'' as a "special" element for the numbering.  A numbering <math>\nu</math> is called '''precomplete''' if the weaker property holds:
:<math> \nu \circ f(i) = \nu \circ h(i) \qquad i \in \operatorname{dom}(f).</math>

== Examples ==

* Any numbering of a [singleton set](/source/singleton_set) is complete
* The [identity function](/source/identity_function) on the natural numbers is ''not'' complete
* A [Gödel numbering](/source/Numbering_(computability_theory)) is precomplete

== References ==
* [Y.L. Ershov](/source/Yuri_Ershov) (1999), "Theory of numberings", ''Handbook of Computability Theory'', E.R. Griffor (ed.), Elsevier, pp.&nbsp;473&ndash;506. {{ISBN|978-0-444-89882-1}}
* A.I. Mal'tsev, ''Sets with complete numberings''. [Algebra i Logika](/source/Algebra_i_Logika), 1963, vol. 2, no. 2, 4-29 (Russian)

Category:Computability theory

---
Adapted from the Wikipedia article [Complete numbering](https://en.wikipedia.org/wiki/Complete_numbering) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Complete_numbering?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.