Initial segments of the lattice of π01 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
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 23,674
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
R. G. Downey (1987). Maximal Theories. 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

Monthly downloads

Added to index


Total downloads

16 ( #280,474 of 1,903,117 )

Recent downloads (6 months)

1 ( #446,023 of 1,903,117 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.