## Ramsey theory of very small countable ordinals

November 6, 2014

I was an undergraduate student at Los Andes, from 1992 to 1996. This year, their mathematics program is turning 50. There was a conference in September to celebrate the event, and I had the honor to give one of the talks (see here for the English version of the slides).

The Faculty of Science publishes a magazine, Hipótesis, and a special edition will be devoted to the conference. I have submitted an expository paper, based on my talk.

The topic is the partition calculus of very small countable ordinals (mainly ordinals below $\omega^2$, actually). The paper reviews Ramsey’s theorem and a few finite examples, before discussing the two main results.

1.

One is an old theorem by Haddad and Sabbagh, unfortunately not well known. In 1969, they computed the Ramsey numbers $r(\omega+n,m)$ for $n,m$ finite.

Given nonzero ordinals $\alpha,\beta$, recall that $r(\alpha,\beta)$ is the least $\gamma$ such that any red-blue coloring of the edges of $K_\gamma$ either admits a red copy of $K_{\alpha}$ or a blue copy of $K_\beta$. Clearly $r(\alpha,1)=1$, $r(\alpha,\beta)\ge r(\alpha,2)=\alpha$ if $\beta\ge2$, and $r(\alpha,\beta)=r(\beta,\alpha)$, so we may as well assume that $\alpha\ge\beta>2$, and we adopt this convention in what follows.

Ramsey proved two theorems about this function in a famous 1928 paper that introduced the topic. In the notation we have just set up, his first result asserts that $r(n,m)$ is finite whenever $n,m$ are finite, and his second result states that $r(\omega,\omega)=\omega$. The computation of the numbers $r(n,m)$ is an extremely difficult, most likely unfeasible, problem, though $r$ is obviously a recursive function. We are concerned here with the values of the function when at least one of the arguments is infinite.

It turns out that $r(\omega+1,\omega)$ is already $\omega_1$. Hence, if we are interested in studying the countable values of the function $r(\alpha,\beta)$, then we must assume that either $\omega=\alpha$, in which case $r(\alpha,\beta)=\omega$ and there is nothing more to say, or else (that is, if $\alpha$ is countable and strictly larger than $\omega$) we must assume that $\beta$ is finite.

The function has been intensively studied when $\alpha$ is a limit ordinal, particularly a power of $\omega$. Here we look at the much humbler setting where $\omega<\alpha<\omega2$. Recalling that each ordinal equals the set of its predecessors, and using interval notation to describe sets of ordinals, the Haddad-Sabbagh result is as follows:

Lemma. For all positive integers $n, m$ there exists a positive integer $k\ge n, m$ such that for any red-blue coloring of the edges of $K_{[0,k)}$, and such that $K_{[0,m)}$ is blue, there is a subset $H$ of ${}[0, k)$ with $K_H$ monochromatic, and either $K_H$ is blue and $|H| = m + 1$, or else $K_H$ is red, $|H|=n+1$, and $H\cap[0,m)\ne\emptyset$.

Denote by $r_{HS}(n+1,m+1)$ the smallest number $k$ witnessing the lemma.

Theorem. If $n,m$ are positive integers, then $r(\omega +n,m)=\omega(m-1)+t$, where $r_{HS}(n+1,m)=(m-1)+t$.

The theorem was announced in 1969, but the proof never appeared. I have written a survey on the topic, including what should be the first proof in print of this result.

## 580 -Partition calculus (7)

May 6, 2009

Let me begin with a couple of updates.

In the last Corollary of the Appendix to lecture I.5, I indicate that in ${{\sf ZF},}$ we have that

$\displaystyle \aleph(X)<\aleph({\mathcal P}^2(X))$

whenever ${\aleph(X)}$ is not ${\aleph_\alpha}$ for some infinite limit ordinal ${\alpha<\aleph_\alpha.}$ In fact,

$\displaystyle {\mathcal P}(\aleph(X))\preceq{\mathcal P}^2(X)$

holds.

This result is best possible in terms of positive results. In Theorem 11 of the paper by John Hickman listed at the end, it is shown that for any such ${\alpha}$ it is consistent with ${{\sf ZF}}$ that there is an ${X}$ with ${\aleph(X)=\aleph_\alpha}$ for which ${\aleph(X)=\aleph({\mathcal P}^2(X)).}$

I also want to give an update on the topics discussed in lecture III.3.

${\mbox{Erd\H os}}$ and Hajnal asked whether it is possible to have infinite cardinals ${\tau,\lambda,\kappa}$ such that

$\displaystyle \tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa}.$

Galvin and Prikry showed (see Corollaries 16 and 18 of lecture III.3) that any such ${\tau}$ must be larger than ${\lambda^\kappa}$ and that ${\kappa<\lambda.}$

Following a nice suggestion of Grigor Sargsyan, we use arguments as in Theorem 9 from lecture III.5 to show that this partition relation cannot hold.

The key is the following:

Lemma 1 If there are infinite cardinals ${\tau,\lambda,\kappa}$ such that ${\tau\rightarrow[\lambda]^\kappa_{\lambda^\kappa},}$ then for every sufficiently large ${\gamma}$ there is an elementary embedding ${j:M\rightarrow V_\gamma}$ such that ${|M|=\lambda^\kappa,}$ ${{\rm cp}(j)<\lambda,}$ ${j(\lambda)=\lambda,}$ and ${{}^\kappa M\subseteq M.}$

Here is a brief sketch:

Proof: By Corollary 20 from lecture III.3, the given relation is equivalent to ${\tau\rightarrow[\lambda]^\kappa_\lambda.}$ Consider a ${\kappa}$-Skolem function ${F:[V_\gamma]^\kappa\rightarrow V_\gamma}$ so that any ${Y\subset V_\gamma}$ closed under ${F}$ is both closed under ${\kappa}$-sequences and an elementary substructure of ${V_\gamma.}$

Use ${F}$ to define a coloring ${G:[\tau]^\kappa\rightarrow\lambda}$ by setting ${G(x)=F(x)}$ whenever ${F(x)\in\lambda,}$ and ${G(x)=0}$ otherwise. By assumption, there is ${H\in[\tau]^\lambda}$ with ${G''[H]^\kappa\ne\lambda.}$ Note that if ${Y}$ is the closure of ${H}$ under ${F,}$ then ${Y\cap\lambda=G''[H]^\kappa\cap\lambda\ne\lambda.}$ But we can assure that ${|H\cap\lambda|=\lambda,}$ and the result follows by taking as ${M}$ the transitive collapse of ${H.}$ $\Box$

One concludes the proof by noting that it is impossible to have such embeddings. For this, it suffices that ${{}^\omega M\subseteq M}$ and that ${M}$ admits a fixed point past its critical point. One then obtains a contradiction just as in Kunen’s proof that there are no embeddings ${j:V\rightarrow V,}$ see Corollary 9 in lecture III.3.

Similarly, Matthew Foreman has shown that there are no embeddings ${j:M\rightarrow V}$ with ${M}$ closed under ${\omega}$-sequences. The reason is that any such embedding must admit a fixed point past its critical point, as can be argued from the existence of scales. See the paper by Vickers and Welch listed at the end for a proof of this result.

On the other hand, it is still open whether one can have embeddings ${j:M\rightarrow V}$ such that ${M}$ computes cofinality ${\omega}$ correctly.

1. The Baumgartner-Hajnal theorem

In Theorem 2 of lecture III.5 we showed the ${\mbox{Erd\H os}}$-Rado result that

$\displaystyle \kappa\rightarrow_{top}(Stationary,\omega+1)^2$

whenever ${\kappa}$ is regular. It is natural to wonder whether stronger results are possible. We restrict ourselves here to the case ${\kappa=\omega_1.}$ Due to time constraints, we state quite a few results without proof.

## 580 -Partition calculus (6)

April 24, 2009

1. The ${\mbox{Erd\H os}}$-Rado theorem

Large homogeneous sets (of size ${\omega_1}$ or larger) can be ensured, at the cost of starting with a larger domain. The following famous result was originally shown by ${\mbox{Erd\H os}}$ and Rado using tree arguments (with ${\kappa+1}$ lowered to ${\kappa}$ in the conclusion). We give instead an elementary substructures argument due to Baumgartner, Hajnal and ${\mbox{Todor\v cevi\'c},}$ which proves the stronger version. For ${\kappa}$ a cardinal let ${2^{<\kappa}=\sup_{\lambda<\kappa}2^\lambda.}$

Theorem 1 (${\mbox{Erd\H os}}$-Rado) Let ${\kappa}$ be a regular cardinal and let ${\lambda=(2^{<\kappa})^+.}$ Then

$\displaystyle \lambda\rightarrow(\kappa+1)^2_\mu$

for all ${\mu<\kappa.}$