David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
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)|
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
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Alasdair Urquhart (1981). Distributive Lattices with a Dual Homomorphic Operation. II. Studia Logica 40 (4):391 - 404.
Lars Hansen (2005). On an Algebra of Lattice-Valued Logic. Journal of Symbolic Logic 70 (1):282 - 318.
C. J. Ash & R. G. Downey (1984). Decidable Subspaces and Recursively Enumerable Subspaces. Journal of Symbolic Logic 49 (4):1137-1145.
K. Adaricheva, R. Mckenzie, E. R. Zenk, M. Mar´ti & J. B. Nation (2006). The Jónsson-Kiefer Property. Studia Logica 83 (1-3):111 - 131.
C. J. van Alten (2006). On Varieties of Biresiduation Algebras. Studia Logica 83 (1-3):425-445.
Giangiacomo Gerla (1987). Decidability, Partial Decidability and Sharpness Relation for L-Subsets. Studia Logica 46 (3):227 - 238.
Wlesław Dziobiak (1982). Concerning Axiomatizability of the Quasivariety Generated by a Finite Heyting or Topological Boolean Algebra. Studia Logica 41 (4):415 - 428.
C. J. Van Alten (2006). On Varieties of Biresiduation Algebras. Studia Logica 83 (1/3):425 - 445.
Hector Gramaglia & Diego Vaggione (1996). Birkhoff-Like Sheaf Representation for Varieties of Lattice Expansions. Studia Logica 56 (1-2):111 - 131.
Added to index2009-01-28
Total downloads5 ( #237,821 of 1,102,136 )
Recent downloads (6 months)4 ( #91,808 of 1,102,136 )
How can I increase my downloads?