Given a well-ordering of $\mathbb{R}$, there is a natural way to define an associated partition of pairs of real numbers into two pieces: one assigns the value $0$ to a pair $r<s$ if the well-ordering agrees with the standard ordering on the pair, and gives it the value $1$ if not.

This construction is due originally to Sierpiński, and it is an important example/counterexample in Ramsey Theory because this coloring cannot have an uncountable homogeneous set: the separability of $\mathbb{R}$ tells us there must be a rational number between any two consecutive elements of a well-ordered (or reverse well-ordered) subset of $\mathbb{R}$.

In the square-bracket notation (discussed in my last question), Sierpiński's result says $$2^{\aleph_0}\nrightarrow [\aleph_1]^2_2.$$

Now Galvin and Shelah state the following in their paper [1]

We remark that an easy generalization of Sierpiński's proof shows that $2^{\aleph_0}\nrightarrow [\aleph_1]^r_{r!(r-1)!}$ for every positive integer r.

Their conclusion says that one can color the increasing $r$-tuples of reals with $r!(r-1)!$ colors in such a way that for any uncountable $X\subseteq\mathbb{R}$ each of these colors is realized by some $r$-tuple drawn from $X$.

I was unsuccessful at verifying their claim, as the most straightforward (to my mind) generalization of Sierpiński's proof provides a weaker coloring of $r$-tuples using $r!$-colors: one takes a well-ordering $<^*$ of $\mathbb{R}$ and the coloring assigns to an $r$-tuple $a_0<\dots<a_{r-1}$ (in the usual ordering) the permutation of the index set $r$ that arises in the natural way once you rewrite your $r$-tuple in $<^*$-increasing order. Once again, the separability of finite powers of $\mathbb{R}$ is what allows you to conclude that every color appears on every uncountable set. So, this argument establishes only $$2^{\aleph_0}\nrightarrow [\aleph_1]^r_{r!}$$ and my question is how does one improve to obtain the stronger result mentioned by Galvin and Shelah?

It is not out of the question that there is a typo in their paper, but I am also aware that their definition of ''easy generalization'' is probably not the same as my own.

[1] Galvin, Fred; Shelah, Saharon, Some counterexamples in the partition calculus, J. Comb. Theory, Ser. A 15, 167-174 (1973). ZBL0267.04006.

  • $\begingroup$ Alternatively, instead of ordering the intervals $(a_i,a_{i+1})$ by length, you could order them in the order that the rational numbers (in some fixed enumeration) land in them, I think that would work too. $\endgroup$
    – bof
    Aug 23, 2022 at 6:51
  • $\begingroup$ @bof Yes, there's a general preference to use at least a top-level tag for every paper. The standard parent tag for set theory is lo.logic, but here gn.general-topology might be suitable too, or even co.combinatorics — the question would be: where in arXiv would a paper in this topic be most likely to be posted? This seems totally unrelated to analysis (and anyway real-analysis is not top-level). At this point I believe that lo.logic is suitable and covers such a question (but not necessarily every question about infinite sets!). $\endgroup$
    – YCor
    Aug 23, 2022 at 10:23
  • 2
    $\begingroup$ @bof Yes, this works! Thank you! I will try to write up a self-answer to get this documented. $\endgroup$ Aug 23, 2022 at 14:26

1 Answer 1


We may assume $r\ge3$. Let $\prec$ be a well-ordering of $\mathbb R$. For $n\in\mathbb N$ let $S_n$ denote the set of all permutations of the set $[n]=\{1,2,\dots,n\}$.

Consider a set $X=\{x_1,\dots,x_r\}\in\binom{\mathbb R}r$ with $x_1\lt x_2\lt\cdots\lt x_r$ and let $d_i=|x_i-x_{i+1}|$ for $1\le i\le r-1$. Put $X$ in the class $C_\sigma$ ($\sigma\in S_r$) if $x_{\sigma(1)}\prec x_{\sigma(2)}\prec\cdots\prec x_{\sigma(r)}$, and put $X$ in the class $D_\tau$ ($\tau\in S_{r-1}$) if $d_{\tau(1)}\gt d_{\tau(2)}\gt\cdots\gt d_{\tau(r-1)}$. We have defined $r!(r-1)!$ disjoint classes $C_\sigma\cap D_\tau$ ($\sigma\in S_r$, $\tau\in S_{r-1}$). I claim that every uncountable subset of $\mathbb R$ contains members of each of these classes.

Let $A$ be an uncountable subset of $\mathbb R$. We may assume that $A$ has order type $\omega_1$ in the well-ordering $\prec$, and that $U\cap A$ is uncountable whenever $U$ is open and $U\cap A\ne\varnothing$.

We recursively choose $r$ distinct points in $A$. The first two points are chosen arbitrarily. Now suppose $n$ points have been chosen, $2\le n\le r-1$. We designate one of the previously chosen points as a target, and the next point we choose is unequal to but very close to the target; say, at a distance less that $1/4$ of the minimum distance between any two previously chosen points. Let $X=\{x_1,\dots,x_r\}$ be the set of points chosen in this way, $x_1\lt x_2\lt\cdots\lt x_r$; the indices do not, of course, represent the order in which the points were chosen.

It is easy to see that, by picking our targets appropriately, the set $X$ constructed in this way can be made to belong to any given class $D_\tau$. E.g., if the first two points are $a\lt b$, the third point will be chosen close to $a$ if $\tau(2)\lt\tau(1)$, close to $b$ if $\tau(1)\lt\tau(2)$.

Next, for each $i\in[r]$ choose a very small neighborhood $U_i$ of $x_i$. Since $U_i\cap A$ is uncountable, we can successively choose $y_{\sigma(1)}\in U_{\sigma(1)}\cap A$, $y_{\sigma(2)}\in U_{\sigma(2)}\cap A$, etc., so that $y_{\sigma(1)}\prec y_{\sigma(2)}\prec\cdots\prec y_{\sigma(r)}$. Thus the set $Y=\{y_1,\dots,y_r\}\in\binom{\mathbb R}r$ belongs to $C_\sigma$; moreover, it still belongs to $D_\tau$ if the neighborhoods $U_i$ were chosen small enough.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .