Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo
We have seen with Sam two proofs of Ramsey’s Theorem. This time we give a third proof of that uses Konig’s Lemma but can be carried out in RCA0.M3-4206
Russell Miller, Queens College - City University of New York
Michael Deveau, Department of Pure Mathematics, University of Waterloo
Russell Miller, Queens College - City University of New York
David Belanger, Cornell University
Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo
We present the notion of Turing Ordinal of a class of structures. The Turing Ordinal was introduced by Jockusch and Soare as a computability theoretic method for comparing complexities of classes of structures. We explain an example by Montalban of a class of structures that doesn’t have a Turing Ordinal.M3 4206
Mohammad Mahmoud, Pure Mathematics, University of Waterloo
We continue to show that the class Kw has no Turing Ordinal. We construct a set D which is not enumeration reducible to R_\A for any structure \A in Kw. This will imply directly that if the Turing ordinal exists then it must be strictly greater than 0. On the other hand Joe Miller showed that, for our class, if the Turing Ordinal exists it must be 0. Both statements tell us that the Turing Ordinal can't exist.
Jonny Stephenson, Pure Mathematics, University of Waterloo
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.
Michael Deveau, Department of Pure Mathematics, University of Waterloo
We continue with the proof that the non-distributive lattice M5 can be embedded into the c.e. degrees. We will begin with a somewhat brief reminder of the details of the construction presented last week by Jonny, and then begin work on the verification of the construction to show that it gives the desired result.MC 5403
Michael Deveau, Department of Pure Mathematics, University of Waterloo
We finish the proof that the non-distributive lattice M5 can be embedded into the c.e. degrees, picking up with where we left off last week: the verification that the minimal pair condition holds pairwise for A1, A2andA3.