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
C. J. Van Alten (2006). On Varieties of Biresiduation Algebras. Studia Logica 83 (1/3):425 - 445.
Wlesław Dziobiak (1982). Concerning Axiomatizability of the Quasivariety Generated by a Finite Heyting or Topological Boolean Algebra. Studia Logica 41 (4):415 - 428.
Giangiacomo Gerla (1987). Decidability, Partial Decidability and Sharpness Relation for L-Subsets. Studia Logica 46 (3):227 - 238.
C. J. van Alten (2006). On Varieties of Biresiduation Algebras. Studia Logica 83 (1-3):425-445.
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. Ash & R. G. Downey (1984). Decidable Subspaces and Recursively Enumerable Subspaces. Journal of Symbolic Logic 49 (4):1137-1145.
Lars Hansen (2005). On an Algebra of Lattice-Valued Logic. Journal of Symbolic Logic 70 (1):282 - 318.
Alasdair Urquhart (1981). Distributive Lattices with a Dual Homomorphic Operation. II. Studia Logica 40 (4):391 - 404.
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 downloads11 ( #194,277 of 1,696,561 )
Recent downloads (6 months)6 ( #94,197 of 1,696,561 )
How can I increase my downloads?