|
This article is cited in 12 scientific papers (total in 12 papers)
Initial Segments in Rogers Semilattices of $\Sigma^0_n$-Computable Numberings
S. Yu. Podzorov Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
S. Goncharov and S. Badaev showed that for $n\geqslant 2$, there exist infinite families whose Rogers semilattices contain ideals without minimal elements. In this connection, the question was posed as to whether there are examples of families that lack this property. We answer this question in the negative. It is proved that independently of a family chosen, the class of semilattices that are principal ideals of the Rogers semilattice of that family is rather wide: it includes both a factor lattice of the lattice of recursively enumerable sets modulo finite sets and a family of initial segments in the semilattice of $m$-degrees generated by immune sets.
Keywords:
Rogers semilattice, recursively enumerable set, immune set, $m$-degree.
Received: 19.03.2001
Citation:
S. Yu. Podzorov, “Initial Segments in Rogers Semilattices of $\Sigma^0_n$-Computable Numberings”, Algebra Logika, 42:2 (2003), 211–226; Algebra and Logic, 42:2 (2003), 121–129
Linking options:
https://www.mathnet.ru/eng/al26 https://www.mathnet.ru/eng/al/v42/i2/p211
|
Statistics & downloads: |
Abstract page: | 492 | Full-text PDF : | 145 | References: | 87 | First page: | 1 |
|