Cylindrification

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

Given a numbering \nu the cyclindrification c(\nu) 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 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[edit]

  • Given two numberings \nu and \mu then \nu \le \mu \Leftrightarrow c(\nu) \le_1 c(\mu)
  • \nu \le_1 c(\nu)

References[edit]

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