Cylindrification

From Wikipedia, the free encyclopedia

In computability theory a cylindrification is a construction which associates a cylindric numbering to each numbering. The concept was first introduced by Yuri L. Ershov in 1973.

[edit] Definition

Given a numbering $ν$ the cyclindrification $c (ν)$ is defined as

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

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

where $\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 relaton 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.