Intervals of the Lattice of Computably Enumerable Sets and Effective Boolean Algebras | Zendy

Nies André | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

Accelerating Research