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 ${\displaystyle \nu }$ the cylindrification ${\displaystyle c(\nu )}$ is defined as

${\displaystyle \mathrm {Domain} (c(\nu )):=\{\langle n,k\rangle |n\in \mathrm {Domain} (\nu )\}}$

${\displaystyle c(\nu )\langle n,k\rangle :=\nu (i)}$

where ${\displaystyle \langle n,k\rangle }$ is the Cantor pairing function. The cylindrification operation takes a relation as input of arity k and outputs a relation of arity k + 1 as follows : Given a relation R of arity K, its cylindrification denoted by c(R), is the following set {(a1,...,ak,a)|(a1,...,ak) belongs to R and a belongs to A}. Note that the cylindrification operation increases the arity of an input by 1.

Properties

• Given two numberings ${\displaystyle \nu }$ and ${\displaystyle \mu }$ then ${\displaystyle \nu \leq \mu \Leftrightarrow c(\nu )\leq _{1}c(\mu )}$
• ${\displaystyle \nu \leq _{1}c(\nu )}$

References

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