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

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

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

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

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