Cylindric numbering

Short description: Special kind of numbering first introduced by Yuri L. Ershov in 1973

In computability theory a cylindric numbering is a special kind of numbering first introduced by Yuri L. Ershov in 1973.

If a numbering [math]\displaystyle{ \nu }[/math] is reducible to [math]\displaystyle{ \mu }[/math] then there exists a computable function [math]\displaystyle{ f }[/math] with [math]\displaystyle{ \nu = \mu \circ f }[/math]. Usually [math]\displaystyle{ f }[/math] is not injective, but if [math]\displaystyle{ \mu }[/math] is a cylindric numbering we can always find an injective [math]\displaystyle{ f }[/math].

Definition

A numbering [math]\displaystyle{ \nu }[/math] is called cylindric if

[math]\displaystyle{ \nu \equiv_1 c(\nu). }[/math]

That is if it is one-equivalent to its cylindrification

A set [math]\displaystyle{ S }[/math] is called cylindric if its indicator function

[math]\displaystyle{ 1_S: \mathbb{N} \to \{0,1\} }[/math]

is a cylindric numbering.

Examples

• Every Gödel numbering is cylindric

Properties

• Cylindric numberings are idempotent: [math]\displaystyle{ \nu \circ \nu = \nu }[/math]

References

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