Cylindrification

Template:Short descriptionIn 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 as

$\mathrm{D}\mathrm{o}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}(c(\nu )):=\{⟨n,k⟩|n\in \mathrm{D}\mathrm{o}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}(\nu )\}$

$c(\nu )⟨n,k⟩:=\nu (n)$

where $⟨n,k⟩$ 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 \iff 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).