Computability Learning Seminar

Jonny Stephenson, Pure Mathematics, University of Waterloo

"Embedding Lattices into the Computably Enumerable Degrees"

The question of which finite lattices can be embedded into the c.e.
degrees first arose with the construction of a minimal pair by Yates,
and independently by Lachlan, showing the 4 element Boolean algebra
can be embedded. This result was rapidly generalised to show any
finite distributive lattice can also be embedded. For non-distributive
lattices, the situation is more complicated.

There are two minimal nondistributive lattices M_5 and N_5 with the
property that a lattice is nondistributive if and only if it contains
one as a sublattice. Both of these lattices are embeddable (but not
all nondistributive lattices are). In this talk we will discuss the
use of the pinball machine method to give an embedding of M_5.