Cylindrification

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 as
:$\mathrm(c(\nu)) := \{\langle n, k \rangle , n \in \mathrm{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).

Theory of computation