Numbering (computability theory)

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (November 2006) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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.

Contents 1 Definition 2 Examples 3 Properties 4 Comparison of numberings 5 See also

[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 ν₁ is reducible to ν₂ and write

if

If and then we say ν₁ is equivalent to ν₂ and write .

[edit] See also

• Gödel numbering
• complete numbering
• cylindrification