I’m having difficulties proving the following:

„Let $a, b, c, d$ and $d^{\prime}$ be cardinals with $d^{\prime}\le d$. Then $a\to(b)_c^d$ implies $a\to(b)_c^{d^\prime}$.“

Here’s what I know: We can assume $d<\infty$ and hence $d\in\mathbb{N}$ since $a\to(b)_c^d$ can’t hold otherwise. Now I’m familiar with the following approach. Take a coloring $f:[a]^{d^\prime}\to c$. Then we can construct a coloring $g:[a]^d\to c$ by setting $g(X)$ to $f(X^\prime)$ where $X^\prime$ is the subset of the $d^\prime$ least elements of the $d$-element set $X$. Now by assumption there’s a $g$-homogeneous subset $S$ of $A$ which is also supposed to be $f$-homogenious. However this last step isn’t clear to me. Let’s take $d=3$ and $d^\prime=2$. Then for $s_1<s_2<s_3<s_4$ in $S$ I get that {$s_1,s_2$} and {$s_2,s_3$} are colored the same due to

$$ f(\{s_1,s_2\})=g(\{s_1,s_2,x_4\})=g(\{s_2,s_3,x_4\})=f(\{s_2,s_3\}). $$

But why must {$s_3,s_4$} also have the same color? I think the source I read implicitly assumes $|S|\ge\infty$. But then what can we say for the case $|S|<\infty$, is there a counterexample? Or maybe I didn’t get the whole idea of this proof.

I hope someone can help me with this.^^

  • 1
    $\begingroup$ I found this topic already here. However in the only provided answer explicitly $|S|\ge\infty$ is required. $\endgroup$
    – ILUD0R
    May 27 at 13:40
  • 1
    $\begingroup$ The statement is not true in general, despite appearing as an exercise in a prominent textbook. $\endgroup$ May 30 at 10:45

1 Answer 1


This is not true in general. For example, trivially $d\to (d)^d_c$ for all finite $c$ and $d$, but when $d$ and $c$ are greater than $1$, $d\not\to (d)^1_c$.

  • $\begingroup$ Oh, I didn‘t think of that. Thanks a lot for the clarification! $\endgroup$
    – ILUD0R
    May 27 at 22:14

You must log in to answer this question.

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