From Wikipedia, the free encyclopedia
Concept in computability theory, a field of mathematics
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
, the cylindrification
is defined as
![{\displaystyle \mathrm {Domain} (c(\nu )):=\{\langle n,k\rangle |n\in \mathrm {Domain} (\nu )\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9942e5efdf4f8ac1b86d11d602bf977c7d967e7c)
![{\displaystyle c(\nu )\langle n,k\rangle :=\nu (n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af441ac8608dbe21afa8350e3771766976014e13)
where
is the Cantor pairing function.
Note that the cylindrification operation increases the input arity by 1.
Properties[edit]
- Given two numberings
and
then ![{\displaystyle \nu \leq \mu \Leftrightarrow c(\nu )\leq _{1}c(\mu )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d1bbd0d88560aaca637b1bb8f42d76b9f948a7a)
![{\displaystyle \nu \leq _{1}c(\nu )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8de2dfb4d147d42d1c0422622b989df5f8103f78)
References[edit]
- Yu. L. Ershov, "Theorie der Numerierungen I." Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19, 289-388 (1973).