Math 773 is canceled this semester due to lack of enrollment.
M975 Fall 2006 MWF 12:05-12:55
Topics in Mathematical Logic: Well quasi-order theory.
Instructor: A.Miller
Prerequisites: Naive set theory, ordinals, Borel sets.
Textbook: none
A highlight of the course will be Laver's Theorem
confirming Fraisse's conjecture: Given any sequence of
countable linear orders L0,L1,L2,... there exist i < j
such that Li is order embeddable into Lj. We will
present a proof of this result due to Simpson which
uses the Galvin-Prikry Theorem that Borel sets are
Ramsey (which I will also prove). A more elementary
result in this area is Kruskal's Theorem which says
that given any sequence of finite trees T0,T1,... there
is i < j such that Ti is embeddable into Tj.
Quasi-orderings (reflexive transitive relations) with
this property are called well quasi-orderings. It is
equivalent to saying there is no infinite descending
sequence or infinite antichain (pairwise incomparable
family).