Initial Segments of the Lattice of $\Pi^0_1$ Classes
Cenzer, Douglas ; Nies, Andre
J. Symbolic Logic, Tome 66 (2001) no. 1, p. 1749-1765 / Harvested from Project Euclid
We show that in the lattice $\mathscr{E}_{\Pi}$ of $\Pi^0_1$ classes there are initial segments [$\emptyset$, P] = $\mathscr{L}$(P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a $\Pi^0_1$ class P such that L is isomorphic to the lattice $\mathscr{L}$(P)*, which is $\mathscr{L}$(P), modulo finite differences. For the 2-element lattice, we obtain a minimal class, first constructed by Cenzer, Downey, Jockusch and Shore in 1993. For the simplest new $\Pi^0_1$ class P constructed, P has a single, non-computable limit point and $\mathscr{L}$(P)* has three elements, corresponding to $\emptyset$, P and a minimal class P$_0 \subset$ P. The element corresponding to $P_0$ has no complement in the lattice. On the other hand, the theory of $\mathscr{L}$(P) is shown to be decidable. A $\Pi^0_1$ class P is said to be decidable if it is the set of paths through a computable tree with no dead ends. We show that if P is decidable and has only finitely many limit points, then $\mathscr{L}$(P)* is always a Boolean algebra. We show that if P is a decidable $\Pi^0_1$ class and $\mathscr{L}$(P) is not a Boolean algebra, then the theory of $\mathscr{L}$(P)interprets the theory of arithmetic and is therefore undecidable.
Publié le : 2001-12-14
Classification: 
@article{1183746622,
     author = {Cenzer, Douglas and Nies, Andre},
     title = {Initial Segments of the Lattice of $\Pi^0\_1$ Classes},
     journal = {J. Symbolic Logic},
     volume = {66},
     number = {1},
     year = {2001},
     pages = { 1749-1765},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746622}
}
Cenzer, Douglas; Nies, Andre. Initial Segments of the Lattice of $\Pi^0_1$ Classes. J. Symbolic Logic, Tome 66 (2001) no. 1, pp.  1749-1765. http://gdmltest.u-ga.fr/item/1183746622/