Cylindrification

Short description: Concept in computability theory, a field of mathematics

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 [math]\displaystyle{ \nu }[/math], the cylindrification [math]\displaystyle{ c(\nu) }[/math] is defined as

[math]\displaystyle{ \mathrm{Domain}(c(\nu)) := \{\langle n, k \rangle | n \in \mathrm{Domain}(\nu)\} }[/math]

[math]\displaystyle{ c(\nu)\langle n, k \rangle := \nu(n) }[/math]

where [math]\displaystyle{ \langle n, k \rangle }[/math] is the Cantor pairing function.

Note that the cylindrification operation increases the input arity by 1.

Properties

• Given two numberings [math]\displaystyle{ \nu }[/math] and [math]\displaystyle{ \mu }[/math] then [math]\displaystyle{ \nu \le \mu \Leftrightarrow c(\nu) \le_1 c(\mu) }[/math]
• [math]\displaystyle{ \nu \le_1 c(\nu) }[/math]

References

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