Misplaced Pages

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Cylindric numbering" – news · newspapers · books · scholar · JSTOR (October 2010) (Learn how and when to remove this message)

In computability theory a cylindric numbering is a special kind of numbering first introduced by Yuri L. Ershov in 1973.

If a numbering ${\displaystyle \nu }$ is reducible to ${\displaystyle \mu }$ then there exists a computable function ${\displaystyle f}$ with ${\displaystyle \nu =\mu \circ f}$. Usually ${\displaystyle f}$ is not injective, but if ${\displaystyle \mu }$ is a cylindric numbering we can always find an injective ${\displaystyle f}$.

Definition

A numbering ${\displaystyle \nu }$ is called cylindric if

${\displaystyle \nu \equiv _{1}c(\nu ).}$

That is if it is one-equivalent to its cylindrification

A set ${\displaystyle S}$ is called cylindric if its indicator function

${\displaystyle 1_{S}:\mathbb {N} \to \{0,1\}}$

is a cylindric numbering.

Examples

• Every Gödel numbering is cylindric

Properties

• Cylindric numberings are idempotent: ${\displaystyle \nu \circ \nu =\nu }$

References

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

• Theory of computation