Initial segments of the lattice of π01 classes

Journal of Symbolic Logic 66 (4):1749 - 1765 (2001)
Abstract
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
Options
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 31,396
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
Added to PP index
2009-01-28

Total downloads
17 ( #320,076 of 2,225,995 )

Recent downloads (6 months)
1 ( #428,365 of 2,225,995 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature