Some undecidability results for lattices in recursion theory
Jeffrey S. Carroll · Pacific Journal of Mathematics · 1986
A major open question from recursion theory had been whether 6% 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. The lattice of r. e. equivalence relations.DEFINITION.Say that η is a recursively enumerable (r.e.) equivalence relation if η is an equivalence relation over 9Ϊ and {(x, y)\xηy} is an r.e.set.We will prefer to think of η as a subset of 9ϊ 2 and the notation "(x, y) G Ϊ)" will be used.R.e. equivalence relations have been used as a tool for recursion theorists, particulary with respect to strong reducibilities (see [Od] for a survey) but it was Ershov [Er] who introduced the lattice of r.e.equivalence relations (therein called "positive equivalences").The lattice has not been examined as closely as the r.e.substructure lattices of other recursive objects such as vector spaces, Boolean algebras, and fields ([NRl] provides a comprehensive survey of this work).Some recursion theoretic properties for the lattice of r.e.equivalence relations have been studied in [Ca 1,2,3] and the relationship between r.e.equivalence relations and provability in Peano arithmetic has been considered in [Be, BeS, Mo].We begin this study of the lattice of r.e.equivalence relations by reviewing the basic definitions from [Er] (although we use a different terminology).