Topological divisor of zero: Difference between revisions
Jump to navigation
Jump to search
en>Qetuth m more specific stub type |
en>Addbot m Bot: Migrating 1 interwiki links, now provided by Wikidata on d:q2443467 |
||
| Line 1: | Line 1: | ||
In [[computability theory]] a '''cylindrification''' is a construction which associates a [[cylindric numbering]] to each [[numbering (computability theory)|numbering]]. The concept was first introduced by [[Yuri L. Ershov]] in 1973. | |||
== Definition == | |||
Given a numbering <math>\nu</math> the '''cyclindrification''' <math>c(\nu)</math> is defined as | |||
:<math>\mathrm{Domain}(c(\nu)) := \{\langle n, k \rangle | n \in \mathrm{Domain}(\nu)\}</math> | |||
:<math>c(\nu)\langle n, k \rangle := \nu(i)</math> | |||
where <math>\langle n, k \rangle</math> 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 == | |||
* Given two numberings <math>\nu</math> and <math>\mu</math> then <math>\nu \le \mu \Leftrightarrow c(\nu) \le_1 c(\mu)</math> | |||
* <math>\nu \le_1 c(\nu)</math> | |||
== References == | |||
* Yu. L. Ershov, "Theorie der Numerierungen I." Zeitschrift für mathematische Logik und Grundlagen der Mathematik '''19''', 289-388 (1973). | |||
[[Category:Theory of computation]] | |||
Latest revision as of 17:18, 14 March 2013
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.
Definition
Given a numbering the cyclindrification is defined as
where 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
- Given two numberings and then
References
- Yu. L. Ershov, "Theorie der Numerierungen I." Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19, 289-388 (1973).