Cylindric numbering explained

In computability theory a cylindric numbering is a special kind of numbering 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, 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

A set

1 _{S:} N \to \{ 0 , 1 \} is a cylindric numbering.

Examples

• Every Gödel numbering is cylindric

Properties

• Cylindric numberings are idempotent:

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