Numbering (computability theory)

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.

Definition

A numbering of a set

S

is a partial surjective function

\nu: \subseteq \mathbb{N} \to S

$\nu$ is called a total numbering if $\nu$ is a total function. The value of $\nu$ at $i$ (if defined) is often written $\nu_i$ instead of the usual $\nu(i)$ .

Examples

Given a Gödel numbering $\varphi_i$ we can define a numbering of the recursively enumerable sets by $W(i):=\mathrm{domain}(\varphi_i)$

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 exsists an equivalent total numbering.

Comparison of numberings

Using computable function we can define a partial ordering on the set of all numberings. Given two numberings

\nu_1: \subseteq \mathbb{N} \to S_1

and

\nu_2: \subseteq \mathbb{N} \to S_2

we say

\nu_1

is reducible to

\nu_2

and write

\nu_1 \le \nu_2

\exists f \in \mathbf{P}^{(1)} \, \forall i \in \mathrm{Domain}(\nu_1) : \nu_1(i) = \nu_2 \circ f(i).

If $\nu_1 \le \nu_2$ and $\nu_1 \ge \nu_2$ then we say $\nu_1$ is equivalent to $\nu_2$ and write $\nu_1 \equiv \nu_2$ .

Gourt Home::Gourt :: Numbering (computability theory)

Definition

Examples

Properties

Comparison of numberings

See also