RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2003 Volume 42, Number 2, Pages 211–226 (Mi al26)

This article is cited 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.

UDC: 510.5

Received: 19.03.2001


 English version:
Algebra and Logic, 2003, 42:2, 121–129

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024