A major open question from
recursion theory had been whether ℰ, the lattice of recursively enumerable (r.e.)
sets, was undecidable. Recently, Harrington and, independently, Herrmann
have announced that the lattice is indeed undecidable. Previous to this,
Nerode and Smith showed that the lattice of r.e. subspaces of the (canonical)
recursive vector space V∞ is undecidable. Their proof involved powerful
techniques of recursive algebra. This paper presents two more undecidability
results for lattices of r.e. substructures but no advanced recursion theoretic
techniques will be required. The primary result of the first section is the
undecidability of the lattice of r.e. equivalence relations. Recursive Boolean algebras
have been more widely examined and, in the second section, for any infinite
recursive Boolean algebra, the lattice of its r.e. subalgebras is shown to be
undedicable.
