Intervals of the Lattice of Computably Enumerable Sets and Effective Boolean Algebras
André Nies · Bulletin of the London Mathematical Society · 1997
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.