Premium
Intervals of the Lattice of Computably Enumerable Sets and Effective Boolean Algebras
Author(s) -
Nies André
Publication year - 1997
Publication title -
bulletin of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.396
H-Index - 48
eISSN - 1469-2120
pISSN - 0024-6093
DOI - 10.1112/s0024609397003548
Subject(s) - mathematics , undecidable problem , recursively enumerable set , recursively enumerable language , lattice (music) , arithmetic function , mathematics subject classification , discrete mathematics , complete boolean algebra , ideal (ethics) , algebra over a field , pure mathematics , two element boolean algebra , decidability , algebra representation , philosophy , physics , epistemology , acoustics
We prove that each interval of the lattice E of c.e. sets under inclusion is either a boolean algebra or has an undecidable theory. This solves an open problem of Maass and Stob [ 11 ]. We develop a method to prove undecidability by interpreting ideal lattices, which can also be applied to degree structures from complexity theory. We also answer a question left open in [ 7 ] by giving an example of a non‐definable subclass of E * which has an arithmetical index set and is invariant under automorphisms. 1991 Mathematics Subject Classification 03D25, 03D35, 03C57.