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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.