Talk on Reverse Mathematics and Ramsey Theory

This is a copy of my notes from a two-hour talk I gave at our local combinatorics seminar about Reverse Mathematics and Ramsey Theory. The audience consisted of our combinatorialists, who are not logicians, and so the talk is intended to introduce some ideas and viewpoints from my how we look at combinatorics in Reverse Mathematics, without getting into technical details.

First, we have some notation from Ramsey Theory. We let $\omega$ be a synonym for $\mathbb{N}$, the set of natural numbers. For $m \in \omega$, $[\omega]^m$ is the set of $m$-element subsets of $\omega$, and $[\omega]^\omega$ is the set of infinite subsets of $\omega$.

A tour of some Ramsey Theory results

The results we are interested in from the perspective of Reverse Mathematics are partitional Ramsey-type results. Ramsey’s eponymous theorem was predated by a theorem of Schur 20 years earlier.

Theorem (Schur 1916)
If $\omega = C_1 \cup \cdots \cup C_r$, there is an $i \leq r$ and $x,y,z \in C_i$ with $x + y = z$.

Theorem (Ramsey 1939)
If $[\omega]^k = C_1 \cup \cdots \cup C_r$ there is an $X \in [\omega]^\omega$ such that $[X]^k \subseteq C_i$ for some $i \leq r$.

Theorem (Folkman c. 1965)
If $\omega = C_1 \cup \cdots \cup C_r$ then for all $m \in \omega$ there is an $i\leq r$ and an
$X \in [\omega]^m$ such that for all finite nonempty $F \subseteq C$, we have $\sum F \in C_i$.

Theorem (Hindman 1974)
If $\omega = C_1 \cup \cdots \cup C_r$ then there is an $i\leq r$ and an
$X \in [\omega]^\omega$ such that for all finite nonempty $F \subseteq X$, we have $\sum F \in C_i$.

The last two theorems I will state relate to arithmetical progressions, which are finite sequences of natural numbers with evenly spaced gaps.

Theorem (van der Waerden 1927)
If $\omega = C_1 \cup \cdots \cup C_r$ then there is an $i \leq r$ such that
$C_i$ contains arbitrarily long (finite) arithmetical progressions.

Theorem (Szemerédi 1975)
If $C \subseteq \omega$ has positive upper density (that is, $0 < \limsup \dfrac{|C \cap n|}{n}$) then $C$ contains arbitrarily long (finite) arithmetical progressions.

The Green-Tao Theorem (2004) is a variant of Szemerédi’s theorem where $C$ is taken to be the set of primes, which has upper density 0.

Note that there are two kinds of results here:

  1. Results that assert the existence of a special infinite set with some property, e.g. Ramsey’s theorem and Hindman’s theorem. These results are classified as $\Pi^1_2$ under a general classification in Reverse Mathematics.
  2. Those that simply assert that one of the color sets $C_i$ has a property, e.g. van der Waerden’s theorem and Folkman’s theorem. These are classified as $\Pi^1_1$ under the general classification.

In Reverse Mathematics, we see that $\Pi^1_2$ statements can often be classified in terms of their “set existence strength”: how hard is it to construct the special infinite set? However, $\Pi^1_1$ theorems can be classified in terms of their “induction strength”: how hard is it to verify that one of the colors has the desired property? We are most often interested in $\Pi^1_2$ theorems, because we are most often interested in the set existence aspect of theorems, although both aspects are important.

There are, roughly speaking, three main proof methods for results like the ones stated above:

  1. “Combinatorial proofs”: these use complicated induction arguments to establish a theorem.
  2. Ultrafilter-based proofs: these use ultrafilters on $\omega$ to establish combinatorial theorems. The space of all these ultrafilters, $\beta \mathbb{N}$, is the Stone-Cech compactification of $\omega$, and has many topological properties that these proofs can utilize.
  3. Dynamical proofs: these use methods of topological dynamics or Ergodic theory. In particular, results in combinatorics often correspond to “recurrence theorems” in dynamics.

In some cases, such as Hindman’s theorem, proofs of all three kinds are known. In other cases, only some kinds of proofs have been discovered. For example, there is no dynamical proof of Ramsey’s theorem.

A result of Rado

We will talk about another Ramsey-type result to illustrate the ultrafilter method. The Reverse Mathematics of this theorem has recently been studied by Cholak, Igusa, Patey, and Soskova (slides).

For this theorem, we view $[\omega]^2$ as the edge set of the complete graph with vertex set $\omega$. Suppose that $[\omega]^2= C_1 \cup C_r$. A monochromatic path is a sequence of vertices $p_1, p_2, \ldots$, which may be finite, infinite, or empty, which never repeats a vertex, such that for some $j$ we have $\{p_i, p_{i+1}\} \in C_j$ whenever $p_i$ and $p_{i+1}$ are in the sequence. Here we view $\{p_i, p_{i+1}\}$ as an edge in the path. Two paths are disjoint if they do not share any vertices.

Theorem (R. Rado 1978).
If $[\omega]^2 = C_1 \cup \cdots \cup C_r$, there is a sequence $(P_i)_{i \leq r}$ of disjoint monochromatic paths that cover all the nodes, such that for $j \leq r$ every edge in path $P_j$ has color $j$.

We will prove this theorem using ultrafilters. A nonprincipal ultrafilter on $\omega$ is a set $\mathcal{U} \subseteq P(\omega)$ such that:

  1. For alL $A \subseteq \omega$, $A \in \mathcal{U}$ or $A^c \in \mathcal{U}$.
  2. If $A,B \in \mathcal{U}$ then $A \cap B \in \mathcal{U}$.
  3. If $A \in \mathcal{U}$ and $A \subseteq B$ then $B \in \mathcal{U}$.
  4. No finite set is in $\mathcal{U}$.

Sets in $\mathcal{U}$ are considered “large” from the perspective of $\mathcal{U}$. Thus the axioms say that
each set is large, or else its complement is large; the intersection of large sets is large; a superset of a large set is large; and no finite set is large. It can be proved by Zorn’s lemma that a nonprincipal ultrafilter on $\omega$ exists.

Note that if $A \in \mathcal{U}$ is a disjoint union $A = B \sqcup C$ then exactly one of $B$ and $C$ is in $\mathcal{U}$. First, if $B$ and $C$ are both in $\mathcal{U}$ then so is $B \cap C = \emptyset$, which is impossible. Second, if neither $B$ nor $C$ is in $\mathcal{U}$ then $B^c \cap C^c = A^c$ is in $\mathcal{U}$, so $A \cap A^c$ is in $\mathcal{U}$, which is impossible.

Proof of Rado’s theorem. Let $\omega = C_1 \cup \cdots \cup C_r$. For each $m \in \omega$ and $i \leq r$ let
N(m,i) = \{ n : \{m,n\} \in C_i\}.
Let $\mathcal{U}$ be a nonprincipal ultrafilter on $\omega$.

Fix $m \in \omega$. Because $\omega \setminus \{m\} \in \mathcal{U}$, and $\omega \setminus \{m\} = N(m,1) \sqcup N(m,2) \sqcup \cdots \sqcup N(m,r)$, there is a unique $j$ such that $N(m,j) \in \mathcal{U}$, using the disjoint union argument noted above. Let
A_j = \{ m : A(m,j) \in \mathcal{U}\}.
Then $\omega = A_1 \sqcup A_2 \sqcup \cdots \sqcup A_r$. So we have induced an $r$-coloring of $\omega$. Moreover, if $m \not = n$ are in $A_j$ then $N(m,j)$ and $N(n,j)$ are in $\mathcal{U}$, then $N(m,j) \cap N(n,j) \mathcal{U}$.
So, in particular, $N(m,j) \cap N(n,j)$ will be infinite.

We now construct the path decomposition inductively. We begin by letting $P_j$ be empty for all $j \leq r$. At stage $n$, if vertex $n$ is already in a path, we move on to the next stage. Otherwise, there is a unique $j$ with $n \in A_j$. If $P_j$ is empty, we put $n$ in $P_j$ as the first node, and move to the next stage.

If $P_j$ is not empty, let $m$ be the last vertex in $P_j$. Let $v \in N(n,j) \cap N(m,j)$ be a vertex that is not yet in any path. Extend $P_j$ by $v$ and then $n$, so it ends with $m \rightarrow v \rightarrow n$. Then $P_j$ is still a monochromatic path with color $j$, so we may proceed to the next stage.

This construction, in the limit, produces a sequence of paths $(P_j)_{j \leq r}$ so that each vertex is in exactly one path and path $P_j$ is monochromatic with color $j$, QED.

The Reverse Mathematics of Rado’s theorem is not yet well understood. The ultrafilter proof does give a kind of upper bound on the strength, but finding a matching lower bound seems challenging at present.

Reverse Mathematics and principles weaker than Ramsey’s theorem

We will next discuss the following three theorems.

Ramsey’s theorem ($\text{RT}^k_r$)
If $[\omega]^k = C_1 \cup \cdots \cup C_r$ then there is an infinite $A \subseteq \omega$ and $i \leq r$ with $[A]^k \subseteq C_i$.

Chain-antichain principle (CAC)
Every countable poset has an infinite chain or an infinite antichain.

Ascending-descending sequence principle (ADS)
Every countable linear order has an infinite strictly increasing sequence or an infinite strictly decreasing sequence.

There are several key relations between these results:

  1. $\text{RT}^2_2$ implies CAC. We color $\{x,y\}$ red if $x$ and $y$ are comparable in the poset, and blue otherwise. An infinite homogeneous set for this coloring gives us an infinite chain or antichain in the poset.
  2. CAC implies ADS. Given a linear order $\leq_L$ on $\omega$, define $n \leq_P m$ if $n \leq m$ and $n \leq_L m$. Then $\leq_P$ is a partial order on $\mathbb{N}$. If $C$ is a chain under $\leq_P$ and we list it in increasing natural order, we obtain a strictly increasing sequence on $\leq_L$. If $C$ is an antichain on $\leq_P$ and we list it in increasing natural order, we obtain a strictly decreasing sequence on $\leq_L$.

In Reverse Mathematics, we study these kinds of results using computability. Informally, a function $f \colon \omega \to \omega$ is computable if there is an algorithm to compute it. This is a finite list of instructions so that a human with unlimited time and supplies can compute the function in a discrete stepwise manner, without any ingenuity, and without using any other devices (dice, etc.). There is a formal definition that makes the definition more precise, but the informal definition is accurate enough for most purposes. An important aspect of the definition is that there is no limit on the time, storage space (paper) or input size.

A set $A \subseteq \omega$ is computable if its characteristic function is computable. We can compute a set or function relative to another set or function, by using the latter as a black box as many times as we like when computing the former.

In Reverse Mathematics, we study relationship between mathematical principles such as $\text{RT}^2_2$, CAC, and ADS by treating the principles as axioms (set existence principles). We focus on $\omega$ and subsets of $\omega$, which allows us to use methods from computability theory.

Our base system, named $\text{RCA}_0$, essentially says that if I have a set $X$ and another set $Y$ is computable relative to $X$, then I can also form the set $Y$.

Other principles are based on theorems form mathematics.

  1. $\text{KL}_0$ is König’s lemma for subtrees of $\omega^{< \omega}$.
  2. $\text{WKL}_0$ is “weak König’s lemma”, which is the restriction to subtrees of $\{0,1\}^{<\omega}$.

We can show that particular principles do, or do not, imply other principles. In particular, the following diagram shows relationships between the principles mentioned above.

Diagram showing relationships between Reverse Mathematics subsystems

Implications in the diagram are transitive, and thus for example the diagram shows neither of $\text{RT}^2_2$ and $\text{WKL}_0$ implies the other. Double arrows represent strict implications (i.e. the converse implication does not hold). The diagram includes classical results as well as results of Hirschfeldt and Short 2007, Liu 2012, and Lerman, Solomon and Towsner 2013.

The diagram shows that $\text{KL}_0$ is equivalent to $\text{RT}^k_r$ for all $k \geq 3$ and $r \geq 2$. Separating these principles requires finer analysis than traditional Reverse Mathematics. Recently, these principles have been separated using Weihrauch reducibility.

This entry was posted in Talks, Uncategorized. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *