305 – Friedman’s theorem

February 4, 2012

I am sketching here a proof of Harvey Friedman‘s result mentioned in lecture. The proof will not be needed for the rest of the course, but it is a nice argument that you may enjoy reading.

Recall that a sequence x_0 x_1 \dots x_n has property * iff there are no integers i<j\le n/2 such that the sequence x_i x_{i+1}\dots x_{2i} is a subsequence of x_j x_{j+1}\dots x_{2j}.

Here, we are using the notion of subsequence where terms must appear in order but are not required to be consecutive: A sequence a_1 a_2\dots a_k is a subsequence of b_1 b_2\dots b_l iff there are indices 1\le i_1<i_2<\dots<i_k\le l such that

b_{i_1}=a_1,b_{i_2}=a_2,\dots,b_{i_k}=a_k.

Theorem (H. Friedman, 2001). For any positive integer k there is a longest finite sequence x_1 x_2\dots x_n in k letters with property *.

(Of course, once we know that the theorem is true, we can proceed as in lecture and define n(k) as the length of this longest sequence.)

Read the rest of this entry »


502 – König’s lemma (2)

August 26, 2009

We continue with the example of domino systems.

Remark 1 There is no algorithm that determines whether a given {D} can tile the plane or not.

Of course, for specific systems {D,} we usually can tell by ad hoc methods which one is the case. What the remark above indicates is that there is no uniform way of doing this.

Read the rest of this entry »


502 – König’s lemma

August 24, 2009

(The material on mathematical logic is covered in the textbook starting with Chapter 5; however, for the first few lectures, I will be providing some required background topics and will not be following the book. There are several references that you may find useful. For example,

  • Kaye, Richard. The mathematics of logic, Cambridge University Press (2007).

I am also making use of a set of notes originally developed by Alexander Kechris for the course Math 6c at Caltech.)

Read the rest of this entry »


580 -III. Partition calculus

March 21, 2009

1. Introduction

Partition calculus is the area of set theory that deals with Ramsey theory; it is devoted to Ramsey’s theorem and its infinite and infinitary generalizations. This means both strengthenings of Ramsey’s theorem for sets of natural numbers (like the Carlson-Simpson or the Galvin-Prikry theorems characterizing the completely Ramsey sets in terms of the Baire property) and for larger cardinalities (like the {\mbox{Erd\H os}}-Rado theorem), as well as variations in which the homogeneous sets are required to possess additional structure (like the Baumgartner-Hajnal theorem).

Ramsey theory is a vast area and by necessity we won’t be able to cover (even summarily) all of it. There are many excellent references, depending on your particular interests. Here are but a few:

  • Paul {\mbox{Erd\H os},} András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: partition relations for cardinals, North-Holland, (1984).
  • Ronald Graham, Bruce Rothschild, Joel Spencer, Ramsey theory, John Wiley & Sons, second edn., (1990).
  • Neil Hindman, Dona Strauss, Algebra in the Stone-{\mbox{\bf \v Cech}} compactification, De Gruyter, (1998).
  • Stevo {\mbox{Todor\v cevi\'c},} High-dimensional Ramsey theory and Banach space geometry, in Ramsey methods in Analysis, Spiros Argyros, Stevo {\mbox{Todor\v cevi\'c},} Birkhäuser (2005), 121–257.
  • András Hajnal, Jean Larson, Partition relations, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., to appear.

I taught a course on Ramsey theory at Caltech a couple of years ago, and expect to post notes from it at some point. Here we will concentrate on infinitary combinatorics, but I will briefly mention a few finitary results.

Read the rest of this entry »


580 -II. Cardinal arithmetic

February 5, 2009

Homework problem 5. ({\sf ZF}). Show that if \omega\preceq{\mathcal P}(X) then in fact {\mathcal P}(\omega)\preceq{\mathcal P}(X).

Question. If X is Dedekind-finite but {\mathcal P}(X) is Dedekind-infinite, does it follow that there is an infinite Dedekind-finite set Y such that {\mathcal P}(Y)\preceq X?

From now on, until we cover determinacy, we assume the axiom of choice unless stated otherwise.

Read the rest of this entry »