Cylindrification Explained

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 defined asDomain (c(\nu)) : = \{\langle n, k \rangle | n \in Domain (\nu)\} c(\nu)\langle n, k \rangle : = \nu(n) where \langle n, k \rangle is the Cantor pairing function.

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

Properties

• Given two numberings

\nu and \mu then \nu \le \mu \Leftrightarrow c(\nu) \le _{1} c(\mu) \nu \le _{1} c(\nu)

References

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