Numbering (computability theory)
From Wikipedia, the free encyclopedia
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 computability concept, which is 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.
Contents |
[edit] Definition
A numbering of a set 
is a partial surjective function
The value of 
at 
(if defined) is often written 
instead of the usual 
. is called a total numbering if is a total function.
If is a set of natural numbers, then is required to be a partial recursive function. If is a set of subsets of the natural numbers, then the set 
(using the Cantor pairing function) is required to be recursively enumerable.
[edit] Examples
- Given a Gödel numbering
we can define a numbering of the recursively enumerable sets by 
[edit] 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.
[edit] Comparison of numberings
Using computable function we can define a partial ordering on the set of all numberings. Given two numberings
and
we say ν1 is reducible to ν2 and write
if
If 
and 
then we say ν1 is equivalent to ν2 and write 
.
