305 – Friedman’s theorem

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 has property iff there are no integers such that the sequence is a subsequence of .

Here, we are using the notion of subsequence where terms must appear in order but are not required to be consecutive: A sequence is a subsequence of iff there are indices such that

Theorem (H. Friedman, 2001). For any positive integer there is a longest finite sequence in letters with property .

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

502 – König’s lemma (2)

We continue with the example of domino systems.

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

 

Of course, for specific systems 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

(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

 

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 -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 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- compactification, De Gruyter, (1998).
• Stevo High-dimensional Ramsey theory and Banach space geometry, in Ramsey methods in Analysis, Spiros Argyros, Stevo 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

Homework problem 5. (). Show that if then in fact .

Question. If is Dedekind-finite but is Dedekind-infinite, does it follow that there is an infinite Dedekind-finite set such that ?

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