Initial segments of the lattice of Π10 classes

Journal of Symbolic Logic 66 (4):1749-1765 (2001)

We show that in the lattice E Π of Π 0 1 classes there are initial segments [ $\emptyset$ , P] = 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 Π 0 1 class P such that L is isomorphic to the lattice L(P)*, which is 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 Π 0 1 class P constructed, P has a single, non-computable limit point and 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 L(P) is shown to be decidable. A Π 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 L(P)* is always a Boolean algebra. We show that if P is a decidable Π 0 1 class and L(P) is not a Boolean algebra, then the theory of L(P)interprets the theory of arithmetic and is therefore undecidable
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2694972
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,066
Through your library

References found in this work BETA

Countable Thin Π01 Classes.Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 59 (2):79-139.
Maximal Theories.R. G. Downey - 1987 - Annals of Pure and Applied Logic 33 (3):245-282.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Initial Segments of the Lattice of $\Pi^0_1$ Classes.Douglas Cenzer & Andre Nies - 2001 - Journal of Symbolic Logic 66 (4):1749-1765.
Lattice Initial Segments of the Hyperdegrees.Richard A. Shore & Bjørn Kjos-Hanssen - 2010 - Journal of Symbolic Logic 75 (1):103-130.
Density of the Medvedev Lattice of Π0 1 Classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
Intermediate Logics and Factors of the Medvedev Lattice.Andrea Sorbi & Sebastiaan A. Terwijn - 2008 - Annals of Pure and Applied Logic 155 (2):69-85.
Initial Segments of the Lattice of Ideals of R.E. Degrees.Frank P. Weber - 1994 - Journal of Symbolic Logic 59 (4):1326-1350.
Local Initial Segments of the Turing Degrees.Bjørn Kjos-Hanssen - 2003 - Bulletin of Symbolic Logic 9 (1):26-36.
Degrees of Difficulty of Generalized R.E. Separating Classes.Douglas Cenzer & Peter G. Hinman - 2008 - Archive for Mathematical Logic 46 (7-8):629-647.
A Mathematical Analysis of Pānini’s Śivasūtras.Wiebke Petersen - 2004 - Journal of Logic, Language and Information 13 (4):471-489.
The Structure of the Honest Polynomial M-Degrees.Rod Downey, William Gasarch & Michael Moses - 1994 - Annals of Pure and Applied Logic 70 (2):113-139.


Added to PP index

Total views
23 ( #348,951 of 2,236,459 )

Recent downloads (6 months)
2 ( #768,614 of 2,236,459 )

How can I increase my downloads?


Sorry, there are not enough data points to plot this chart.

My notes

Sign in to use this feature