Some undecidability results for lattices in recursion theory (Q762063)

A major open question from recursion theory had been whether \({\mathcal E}\), 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_{\infty}\) 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 undecidable.