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 ...

a cylindric numbering is a special kind of

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 ...

first introduced by Yuri L. Ershov in 1973. If a numbering

\nu

is reducible to

\mu

then there exists a computable function

f

with

\nu = \mu \circ f

. Usually

f

is not

injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...

, but if

\mu

is a cylindric numbering we can always find an injective

f

Definition

A numbering

\nu

is called cylindric if :

\nu \equiv_1 c(\nu).

That is if it is one-equivalent to its

cylindrification In computability theory a cylindrification is a construction that associates a cylindric numbering to each numbering. The concept was first introduced by Yuri L. Ershov in 1973. Definition Given a numbering \nu, the cylindrification c(\nu) is ...

A set

S

is called cylindric if its

indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...

1_S: \mathbb \to \{0,1\}

is a cylindric numbering.

Examples

* Every

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 ...

is cylindric

Properties

* Cylindric numberings are

idempotent Idempotence (, ) is the property of certain operation (mathematics), operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence ...

\nu \circ \nu = \nu

References

* Yu. L. Ershov, "Theorie der Numerierungen I." Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19, 289-388 (1973). Theory of computation