Ramsey theory of very small countable ordinals

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.

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.

A topological variant of the function $r$ is obtained by requiring that the homogeneous set be a faithful topological copy of the corresponding ordinal. The resulting function we denote $r_{cl}$ . Formally, $r_{cl}(\alpha,\beta)=\gamma$ iff $\gamma$ is least such that any for red-blue coloring of $K_\gamma$ there is an $H\subseteq\gamma$ such that $K_H$ is monochromatic and, if $K_H$ is red, then $H$ is order-homeomorphic to $\alpha$ , or if $K_H$ is blue, then $H$ is order-homeomorphic to $\beta$ .

The notion of order-homeomorphism is a natural one, the name itself is due to Baumgartner. We say that a set of ordinals $H$ is order-homeomorphic to an ordinal $\alpha$ iff, first of all, $H$ has order type $\alpha$ and, second, the unique order-isomorphism between $H$ and $\alpha$ is a homeomorphism. Here, ordinals are equipped with the order topology, and $H$ carries the subspace topology (it is easy to check that if $H\subseteq\beta\le\gamma$ , then the topology inherited by $H$ as a subspace of $\beta$ is the same as the topology inherited as a subspace of $\gamma$ . More concretely, the topological component of the definition simply assert that, for any limit ordinal $\beta<\alpha$ , the $\beta$ th element of $H$ is the supremum of its predecessors in $H$ . That is, $H$ is closed as a subset of its supremum.

To illustrate the difference between $r$ and $r_{cl}$ , let me mention that $r(\omega+1,3)=\omega2+1$ but $r_{cl}(\omega+1,3)=\omega^2+1$ , and $r(\omega+2,3)=\omega2+4$ but $r_{cl}(\omega+2,3)=\omega^22+\omega+2$ .

Theorem. The ordinal $r_{cl}(\omega n+m,k)$ is countable for all finite $n,m,k$ .

The proof provides concrete upper bounds. The argument proceeds by induction, the key technical tool being the function $r_{cl}(\alpha,\beta;1)$ that allows us to study the closed version of the pigeonhole principle:

One can prove that for all $\alpha,\beta$ there is a $\gamma$ such that whenever $\gamma=A\cup B$ , either $A$ contains a subset order-homeomorphic to $\alpha$ , or else $B$ contains a subset order-homeomorphic to $\beta$ . The smallest possible $\gamma$ with this property we denote $r_{cl}(\alpha,\beta;1)$ .

For example, $r_{cl}(\omega+1,\omega+1;1)=\omega^2+1$ , and $r_{cl}(\omega+2,\omega+2;1)=\omega^2+\omega+2$ . To verify that $r_{cl}(\omega+2,3)=\omega^22+\omega+2$ , what one actually proves is that $r_{cl}(\omega+2,3)=r_{cl}(\omega+1,3)+r_{cl}(\omega+2,\omega+2;1)$ .

This entry was posted on Thursday, November 6th, 2014 at 11:25 pm and is filed under math.LO, Papers. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

A kind of library