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.
Given a numbering
ν
the cylindrification
c
(
ν
)
is defined as
D
o
m
a
i
n
(
c
(
ν
)
)
:=
{
⟨
n
,
k
⟩
|
n
∈
D
o
m
a
i
n
(
ν
)
}
c
(
ν
)
⟨
n
,
k
⟩
:=
ν
(
i
)
where
⟨
n
,
k
⟩
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.
Given two numberings
ν
and
μ
then
ν
≤
μ
⇔
c
(
ν
)
≤
1
c
(
μ
)
ν
≤
1
c
(
ν
)
