Recursively enumerable set

The lattice of recursively enumerable sets

The set of all recursively enumerable subsets of the natural numbers can be made into a poset under set inclusion; this poset is a lattice. The theory of this lattice is known to be an undecidable problem. Similarly, the set of all computably enumerable vector spaces also forms a lattice. In fact, one can generalize this even further to the lattice L(Q), which is defined to consist of all recursively enumerable filters, where Q is some free Boolean algebra without any atoms. These lattices are closely tied to the study of recursively enumerable Pi-0-1 classes.