z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here