Embedding Finite Lattices Into the Lattice of Ideals of Computably Enumerable Turing Degrees

William C. Calhoun

This talk will be a survey of results concerning lattice embeddings into the lattice of ideals of computably enumerable Turing degrees, I. The problem of embedding lattices into I is related to the well-known problem of embedding lattices into the computably enumerable Turing degrees, R.

I will discuss recent joint work with Lerman in which we show that the lattice L_{20} provides an example of a finite lattice that is not embeddable into I. The proof uses a reorganized and adapted version of Lempp and Lerman’s proof that the lattice L_{20} is not embeddable into R. We also obtain a Π_{2} necessary and sufficient condition for embedding lattices into I. The condition may be obtained by reduction to Lerman’s condition for embedding ranked finite partial lattices into R.

[1] W. C. Calhoun, The Lattice of Ideals of Recursively Enumerable Degrees, Ph.D. Thesis, University of California, Berkeley, CA (1990).

[2] S. Lempp and M. Lerman, A finite lattice that cannot be embedded into the enumerable Turing degrees, Annals of Pure and Applied Logic, Vol. 87 (1997), 167-185.

[3] M. Lerman, A necessary and sufficient condition for embedding ranked finite partial lattices into the computably enumerable degrees, Annals of Pure and Applied Logic 94 (1998) 143-180.

Address: Department of Mathematics and Computer Science, Bloomsburg University of Pennsylvania, Bloomsburg, PA 17815, USA

E-mail: wcalhoun@bloomu.edu