Topological Ramsey numbers and countable ordinals

February 1, 2019

Paul Erdős and Eric Milner published in 1972 A theorem in the partition calculus, where they established that if \beta is a countable ordinal and n\in\omega, then there is a countable ordinal \alpha such that

\alpha\to(\beta,n)^2,

meaning that any graph whose set of vertices is \alpha either contains a clique (complete subgraph) whose set of vertices H has order type \beta or an independent set of size n.

The result is false if n is replaced by \omega, except for when \beta=\omega, in which case we can take \alpha=\omega as well, this is Ramsey’s theorem.

The least \alpha such that \alpha\to(\omega+1,\omega)^2 is \alpha=\omega_1, in which case a stronger result holds, namely \omega_1\to(\omega_1,\omega+1)^2. In fact, more is true: the homogeneous set H of order type \omega_1 can be taken to be a stationary subset of \omega_1, and the set of type \omega+1 can be required to be closed, meaning that its \omegath member is the supremum of the other members of the set. Since stationary sets contain closed subsets of any countable order type, we see that \omega_1\to_{cl}(\beta,\omega+1)^2 holds for any countable ordinal \beta, where the subindex cl indicates that the sets of vertices of type \beta or \omega+1 are required to be closed on their supremum.

It is thus natural to wonder whether a closed version of the Erdős-Milner theorem holds. Jacob Hilton and I establish precisely this result in our paper Topological Ramsey numbers and countable ordinals.

This was a problem I had been curious about for a while, but kept not finding time to investigate. Finally I found a student at Boise State interested in working on this question for their master’s thesis, which gave me the perfect excuse to think seriously about it. I wrote a series of detailed notes for my student, who ended up leaving the program early, so I decided to continue and turn the notes into a paper. I even gave a preliminary talk on the results I had, together with some other results on the partition calculus of small countable ordinals. Hilton was a graduate student at that point, and he contacted me when he found out I was studying the problem, since this was precisely the topic of his dissertation. We decided to combine what we had, and soon we managed to extend our results and solve the full problem.

Many questions remain, as we believe the general bounds we found can be significantly improved, and it seems interesting to compute the optimal value of \alpha such that \alpha\to_{cl}(\beta,n)^2 for specific values of \beta<\omega_1 and n<\omega. Omer Mermelstein has some striking results in this direction.

Our paper appeared in Foundations of Mathematics, the proceedings of the conference in honor of Hugh Woodin’s 60th birthday. It can also be found on the arXiv and on my papers page.

Advertisements

Set theory seminar -Stefan Geschke: Cofinalities of algebraic structures

January 6, 2009

This is a short overview of a talk given by Stefan Geschke on November 21, 2008. Stefan’s topic, Cofinalities of algebraic structures and coinitialities of topological spaces, very quickly connects set theory with other areas, and leads to well-known open problems. In what follows, compact always includes Hausdorff. Most of the arguments I show below are really only quick sketches rather than complete proofs. Any mistakes or inaccuracies are of course my doing rather than Stefan’s, and I would be grateful for comments, corrections, etc.

Definition. Let A be a (first order) structure in a countable language. Write {\rm cf}(A) for the smallest \delta such that A=\bigcup_{\alpha<\delta}A_\alpha for a strictly increasing union of proper substructures.

Since the structures A_\alpha need to be proper, {\rm cf}(A) is not defined if A is finite. It may also fail to exist if A is countable, but it is defined if A is uncountable. Moreover, if {\rm cf}(A) exists, then

  1. {\rm cf}(A)\le|A|, and
  2. {\rm cf}(A) is a regular cardinal.

Example 1. Groups can have arbitrarily large cofinality. This is not entirely trivial, as the sets A_\alpha may have size |A|.

Question 1. Is every regular cardinal realized this way?

Read the rest of this entry »