Computability Learning Seminar

Jonny Stephenson, Pure Mathematics, University of Waterloo

"Embedding Lattices in the Computably Enumerable Degrees (continued)"

This talk is a continuation of one given August 6th.

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).

We will continue with our construction of an embedding of the nondistributive lattice M_5 into the computably enumerable Turing degrees.