Summer 2020 Ramsey Theory Reading Group

Last time we saw the proof of the Erdos-Rado theorem, that \(\left(2^{\aleph_0}\right)^+ \rightarrow (\aleph_1)_2^2\), modulo a few points where the proof requires some facts about cardinal arithmetic.

Addition, multiplication and exponentiation of cardinals is defined at the bottom of page 68. Everyone should look at this, and check that cardinal arithmetic is well-defined. Everyone should think about Exercise 2.29, as well, and Sean discuss it.

Exercise 2.30 (in full generality) is more difficult, but we only need two special cases:

• \(2^{\aleph_0} \cdot 2^{\aleph_0} = 2^{\aleph_0}\)
• \(2^{\aleph_0} + 2^{\aleph_0} = 2^{\aleph_0}\)

I challenge everyone to come up with direct proofs of both of these statements (remember that \(2^{\aleph_0}\) counts subsets of \({\mathbb N}\), and that there are easy injections from \(2^{\aleph_0}\) into both \(2^{\aleph_0} \cdot 2^{\aleph_0}\) and \(2^{\aleph_0} + 2^{\aleph_0}\), so by C-S-B it is enough to find injections from \(2^{\aleph_0} \cdot 2^{\aleph_0}\) and \(2^{\aleph_0} + 2^{\aleph_0}\) into \(2^{\aleph_0}\)). We can discuss both of these as a group.

The last tool that was needed in the proof of Erdos-Rado, but that we skipped over, was Lemma 2.34. Anthony can present this.

 

Last time we saw the proof of the Erdos-Rado theorem, that \(\left(2^{\aleph_0}\right)^+ \rightarrow (\aleph_1)_2^2\), modulo the technical “cloning” lemma. Ted will present the proof of that lemma (Lemma 2.39).

At a few points, the proof requires some facts about cardinal arithmetic. Addition, multiplication and exponentiation of cardinals is defined at the bottom of page 68. Everyone should look at this, and check that cardinal arithmetic is well-defined. Everyone should think about Exercise 2.29, as well, and someone can volunteer to discuss it.

Exercise 2.30 (in full generality) is more difficult, but we only need two special cases:

• \(2^{\aleph_0} \cdot 2^{\aleph_0} = 2^{\aleph_0}\)
• \(2^{\aleph_0} + 2^{\aleph_0} = 2^{\aleph_0}\)

I challenge everyone to come up with direct proofs of both of these statements (remember that \(2^{\aleph_0}\) counts subsets of \({\mathbb N}\), and that there are easy injections from \(2^{\aleph_0}\) into both \(2^{\aleph_0} \cdot 2^{\aleph_0}\) and \(2^{\aleph_0} + 2^{\aleph_0}\), so by C-S-B it is enough to find injections from \(2^{\aleph_0} \cdot 2^{\aleph_0}\) and \(2^{\aleph_0} + 2^{\aleph_0}\) into \(2^{\aleph_0}\)). We can discuss both of these as a group.

Finally, we will also need Lemma 2.34. Greyson can present this.

We will finish up with Section 2.6. Read the first page of that section; but since (in the interests of time) we’ll only prove results concerning just the cardinalities aleph-null, aleph-one, two to the power aleph-null, and the successor of this last, there is no need to pay much attention to Lemma 2.34, or to finite colourings of uncountable sets. Everyone can skip those sections, or skim them if you wish.

Return to careful reading at the bottom of page 72, and continue through to two-thirds of the way down page 79.  This encompasses the two results I would like to end with:
-> a two-colouring of the edges of the complete graph on aleph-null vertices does not necessarily contain a complete monochromatic subgraph on aleph-null vertices, and
-> the Erdos-Rado theorem, Theorem 2.38 (a positive result, salvaging the negative result just mentioned).

Presentations:

•  Henry can present the proof of Proposition 2.36
•  Nicholas can present the proof of the Erdos-Rado theorem, using Lemma 2.39 as a black box (and can tell us the statement of the lemma — note that missing from the statement in the book is that \(c\) is some fixed \(2\)-coloring of the pairs from a set whose cardinality is the successor of two to the power of aleph-null)
• Alex can present the proof of Lemma 2.39 (this will probably spill over to Friday).

 

We’ll begin with Bailee telling us about Cantor’s result, that for every set there is another set of larger cardinality (and so, iterating, there are “an infinity of infinities”).

We will then move on to Section 2.6. Read the first page of that section; but since (in the interests of time) we’ll only prove results concerning just the cardinalities aleph-null, aleph-one, two to the power aleph-null, and the successor of this last, there is no need to pay much attention to Lemma 2.34, or to finite colourings of uncountable sets. Everyone can skip those sections, or skim them if you wish.

Return to careful reading at the bottom of page 72, and continue through to two-thirds of the way down page 79.  This encompasses the two results I would like to end with:
-> a two-colouring of the edges of the complete graph on aleph-null vertices does not necessarily contain a complete monochromatic subgraph on aleph-null vertices, and
-> the Erdos-Rado theorem, Theorem 2.38 (a positive result, salvaging the negative result just mentioned).

Presentations:

•  Colin can present the proof of Proposition 2.36
•  Casey can present the proof of the Erdos-Rado theorem, using Lemma 2.39 as a black box (and can tell us the statement of the lemma — note that missing from the statement in the book is that \(c\) is some fixed \(2\)-coloring of the pairs from a set whose cardinality is the successor of two to the power of aleph-null)
• Ted can present the proof of Lemma 2.39 (this will probably spill over to Friday).

 

Here’s the goal for the time that is remaining: see how ordinals lead to cardinals (Section 2.5), and then see some of the result of Ramsey theory for cardinalities beyond countable, in particular the negative result Proposition 2.36, and the slight modification that turns the negative result positive (Theorem 2.38, the Erdos-Rado theorem). Given the time that we have, the treatment will necessarily be a little sketchy, but hopefully the key ideas will be clear.

Last time we saw the definition of a well-ordered set, and saw that being well-ordered is equivalent to having no infinite descending chains. We ended with the proof that every subset of the ordinals is well-ordered.

After I quickly recap that proof, Ted will present the argument that every set can be well-ordered (by a suitably chosen ordering), as long as we assume that axiom of choice, which Ted will also introduce. Everyone should think about exercise 2.18 (the axiom of choice is equivalent to the statement that every set can be well-ordered), and we’ll discuss that.  I’ll also make some comments about axiom of choice.

Then we’ll move on to cardinals (Section 2.5). Everyone should read through Section 2.5, and attempt as many of the exercises as time allows.

We’ll go quickly through exercise 2.19 (the exactly formula is really an unnecessary red herring here; what’s important is the picture that goes with the formula). Luca can present exercise 2.21 (\({\mathbb R}\) and \([0,1]\) have the same cardinality). We’ll talk about exercise 2.22 (cardinality is an equivalence relation) as a group.

Greyson can present exercise 2.23 (\(\omega^\omega\) and \(\omega\) have the same cardinality).

We’ll then introduce the definition of cardinality, and Bailee can present Cantor’s famous theorem that there is no largest cardinality.

 

Here’s the goal for the time that is remaining: see how ordinals lead to cardinals (Section 2.5), and then see some of the result of Ramsey theory for cardinalities beyond countable, in particular the negative result Proposition 2.36, and the slight modification that turns the negative result positive (Theorem 2.38, the Erdos-Rado theorem). Given the time that we have, the treatment will necessarily be a little sketchy, but hopefully the key ideas will be clear.

Last time we saw the definition of a well-ordered set, we saw that being well-ordered is equivalent to having no infinite descending chains, and we saw that every subset of the ordinals is well-ordered. We ended by seeing that every set can be well-ordered (by a suitably chosen ordering), as long as we assume the axiom of choice. Everyone should think about exercise 2.18 (the axiom of choice is equivalent to the statement that every set can be well-ordered), and we’ll discuss that.  I’ll also make some more comments about axiom of choice.

Then we’ll move on to cardinals (Section 2.5). Everyone should read through Section 2.5, and attempt as many of the exercises as time allows.

We’ll go quickly through exercise 2.19 (the exactly formula is really an unnecessary red herring here; what’s important is the picture that goes with the formula). Anthony can present exercise 2.21 (\({\mathbb R}\) and \([0,1]\) have the same cardinality). We’ll talk about exercise 2.22 (cardinality is an equivalence relation) as a group.

Sean can present exercise 2.23 (\(\omega^\omega\) and \(\omega\) have the same cardinality).

We’ll then introduce the definition of cardinality, and Joe can present Cantor’s famous theorem that there is no largest cardinality.

 

NOTE: this is probably too much for one meeting, so some of this may/will get put off until Thursday/Friday.

At the end of last time, I presented a simple example of compactness argument — deducing a finite statement from an infinite one. We’ll start on Tuesday with a more non-trivial example of compactness — deducing finite Ramsey’s theorem from the infinite Ramsey theorem. Colin and Henry can present this. Everyone should also read this (it is Section 2.2).

If you’ve seen some topology (or, even if you haven’t…), you can read Section 2.3, to learn why applications of Konig’s tree lemma are referred to as “compactness” arguments, but I don’t plan to spend any time talking about this. Instead, we will spend the next while looking at some infinite Ramsey theory, beyond just countable infinity.

Everyone should read Section 2.4, that introduces ordinals, ordinal arithmetic (addition, multiplication, exponentiation), transfinite induction, and the axiom of choice, and do all the exercises (including verifying the various assertions made throughout to illustrate the definitions). For presentations:

• Casey and Alex can give us the definition of ordinals, explain successor and limit ordinals, define ordinal addition, and show that it is not commutative
• Greyson and Nicholas can define ordinal multiplication and exponentiation, and say what \(\varepsilon_0\) is
• Bailee and Joe can introduce well-ordering (Definition 2.14), and show that well ordering is equivalent to having no infinite descending chains (Proposition 2.15).
• Back to Greyson and Nicholas, who can show that the collection of ordinals is well-ordered (Proposition 2.26)
• Ted and Ryan can introduce the axiom of choice, and present the argument (beginning the middle of page 62) that, assuming axiom of choice,  every set can be well ordered.

Everyone should think about Exercise 2.8 (that the implication goes the other way — so the axiom of choice is equivalent to the statement that every set can be well ordered), and someone can volunteer a proof.

 

We’ll go back now to Chapter 2, on infinite Ramsey’s theorem, and its connection (via Konig’s tree lemma) to finite Ramsey’s theorem.

Everyone should read Chapter 2, through at least to the middle of page 48. There’s one substantial theorem in this span, namely Theorem 2.1 (although it’s not really too different from Theorem 1.31, finite Ramsey’s theorem, and is in fact a little easier, since one has much less “bookkeeping” to do to make the proof work. Section 2.2 through the middle of page 48 is mostly definitions (of partially ordered sets, tree orders, et cetera.).

Theorem 2.1 is proven by induction, with the base case being the obvious infinite pigeon-hole principle — if infinitely many pigeons arrange themselves among only finitely many pigeon holes, then at least one of the pigeon-holes will end up with infinitely many pigeons. I think it’s much more instructive to start with the base case \(p=2\). So: Greyson and Joe can present the proof of the following (the case [/latex]p=2[/latex] of Theorem 2.1): if the edges of an infinite complete graph are colored with finitely many colors, then the graph has an infinite complete subgraph all of whose edges have the same color. Then Luca and Sean can present the induction step that completes the proof of Theorem 2.1.

Then we’ll move onto to partial orders (to lay the groundwork for deducing finite results from infinite ones). As I said earlier, everyone should read through all the background on partial orders and tree-orders, and we can discuss and points that are confusing during the live meeting. Bailee and Anthony can first explain what it means for a partial order to be a tree (in the partial order sense), and then present Exercise 2.3 (connecting this concept to trees in the graph-theoretic sense); then Ted and Ryan can present Konig’s lemma (Theorem 2.6).

 

For Tuesday, everyone should read up through the end of Section 3.1, and do all the exercises. In general when reading mathematics it is a good idea to have paper to hand, to draw pictures and verify claims. This section is one of those situations where it is not a good idea — it is absolutely essential.

At the end of last time, we saw the “AP focussing” argument used to show that for each \(k\), \(W(k,2)\) exists, assuming that \(W(k-1,r)\) exists for every \(r\). Next, we will move onto to the argument that \(W(3,3)\) is finite. This requires a new ingredient, because now we need to focus three monochromatic APs of length 2 (all of different colors) on a single, final focal point. Casey can present this.

The argument that \(W(3,3)\) is finite generalizes to show that \(W(3,r)\) is finite, for every \(r\). Ted can present this.

The last special case we’ll consider is \(W(4,3)\) (requiring focussing three monochromatic APs of length 3, all of different colors, on a single, final focal point). Colin can present this.

We should now be in a position to understand what’s going on in the proof of the general statement, that for each particular choice of \(k\) and \(r\), \(W(k,r)\) is finite (under the inductive hypothesis that \(W(k-1,r’)\) is finite for every \(r’\)). Bailee can present this.

For Tuesday, everyone should read up through the end of Section 3.1, and do all the exercises. In general when reading mathematics it is a good idea to have paper to hand, to draw pictures and verify claims. This section is one of those situations where it is not a good idea — it is absolutely essential.

At the end of last time, we saw the “AP focussing” argument used to show that \(W(3,2)\) exists. To make sure that we fully understand that argument before moving on, we should start on Tuesday by using the same argument to show that for each \(k\), \(W(k,2)\) exists, assuming that \(W(k-1,r)\) exists for every \(r\). I’ll  present this (it is very quick — a valid upper bound is easy to justify using the same process that justified \(W(3,2)\leq 5\cdot 65\). The right picture fully explains the proof).

Next, we will move onto to the argument that \(W(3,3)\) is finite. This requires a new ingredient, because now we need to focus three monochromatic APs of length 2 (all of different colors) on a single, final focal point. Nick can present this.

The argument that \(W(3,3)\) is finite generalizes to show that \(W(3,r)\) is finite, for every \(r\). Sean can present this.

The last special case we’ll consider is \(W(4,3)\) (requiring focussing three monochromatic APs of length 3, all of different colors, on a single, final focal point).  Alex can present this.

We should now be in a position to understand what’s going on in the proof of the general statement, that for each particular choice of \(k\) and \(r\), \(W(k,r)\) is finite (under the inductive hypothesis that \(W(k-1,r’)\) is finite for every \(r’\)). Henry can present this.