Does van der Waerden's Theorem hold for $\omega_1$?

Question

One way to phrase van der Waerden's Theorem is:

For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is monochromatic.

My question is whether the same thing is true for the first uncountable ordinal $\omega_1$. Specifically, is it true that:

$(*)$ For every finite coloring of $\omega_1$ and every finite $F \subseteq \omega_1$, there exist $\alpha,\beta \in \omega_1$ such that $\alpha + \beta \cdot F$ is monochromatic.

The operations $+$ and $\cdot$ are the usual operations of ordinal arithmetic.

---

Remark 1: There is more than one way to generalize the statement of van der Waerden's Theorem to $\omega_1$, but this one seems the most interesting from the point of view of combinatorics. If you restrict $F$ to being a finite interval, then $(*)$ is simply true by the usual van der Waerden Theorem (and we can always take $\alpha, \beta \in \omega$). If we let $F$ range over all countable subsets of $\omega_1$, then $(*)$ cannot be proved from ZFC. This doesn't make it uninteresting, and in fact I've asked another question about that version here. I also don't know what happens when we use countable colorings instead of finite colorings.

Remark 2: This question arose while I was wondering whether the ultrafilters proof of van der Waerden's Theorem generalizes nicely to other settings. That same kind of proof doesn't seem to give us anything about $(*)$, but I also can't think of any obvious counterexamples.

Answer 1

The answer is no; this generalization is inconsistent, even with just two colors, and with $F=\{\omega,\omega^2\}$ of size two.

Theorem. There is a coloring of ordinals with two colors, such that for any ordinals $\alpha$ and $\beta$, the ordinals $\alpha+\beta\cdot\omega$ and $\alpha+\beta\cdot\omega^2$ get different colors.

Proof. Given an ordinal $\eta$, look at its Cantor normal form $$\eta=\omega^{\eta_n}+\cdots+\omega^{\eta_0}\qquad\text{ with }\eta_n\geq\cdots\geq \eta_0.$$ Let us color $\eta$ with the even/odd parity of the last exponent $\eta_0$.

Suppose that $\alpha$ and $\beta$ are ordinals. I claim that $\alpha+\beta\cdot\omega$ and $\alpha+\beta\cdot\omega^2$ get different colors.

To see this, let $\beta=\omega^{\beta_n}+\cdots+\omega^{\beta_0}$ be the Cantor normal form of $\beta$, with $\beta_n\geq\cdots\geq\beta_0$. Note that $\beta\cdot\omega=\omega^{\beta_n+1}$, because $\omega$ copies of $\beta$ is at least this big, and conversely also $$\beta\cdot\omega\leq(\omega^{\beta_n}\cdot (n+1))\cdot\omega=\omega^{\beta_n}\cdot((n+1)\cdot\omega)=\omega^{\beta_n}\cdot\omega=\omega^{\beta_n+1};$$ so they are equal. It follows that $\beta\cdot\omega^2=\omega^{\beta_n+2}$.

Thus, $\alpha+\beta\cdot\omega=\alpha+\omega^{\beta_n+1}$, and furthermore, $\omega^{\beta_n+1}$ will be the final term in the Cantor normal form of this ordinal, because the smaller terms of $\alpha$, if any, will simply be absorbed into it.

Similarly, $\alpha+\beta\cdot\omega^2=\alpha+\omega^{\beta_n+2}$, and $\omega^{\beta_n+2}$ will be the final term in the Cantor normal form of this ordinal also.

So the proof is completed by noting that $\beta_n+1$ and $\beta_n+2$ have opposite parities, and so $\alpha+\beta\cdot\omega$ and $\alpha+\beta\cdot\omega^2$ get different colors under the coloring I defined. QED

Update. Here is another coloring that works with $F=\{\omega,\omega+\omega\}$.

Theorem. There is a coloring of ordinals with two colors such that for any ordinals $\alpha$ and $\beta$, the ordinals $\alpha+\beta\cdot\omega$ and $\alpha+\beta\cdot(\omega+\omega)$ get different colors.

Proof. Color any ordinal $\eta$ by the parity of the number of terms in the Cantor normal form $\eta=\omega^{\eta_n}+\cdots+\omega^{\eta_0}$, where $\eta_n\geq\cdots\geq\eta_0$. Suppose that $\alpha$ and $\beta$ are any two ordinals. As noted above, $\beta\cdot\omega$ has only one term in the Cantor normal form, and so $\beta\cdot(\omega+\omega)=\beta\cdot\omega+\beta\cdot\omega$ has precisely two (identical) terms. It follows that the Cantor normal forms of the ordinals $\alpha+\beta\cdot\omega$ and $\alpha+\beta\cdot(\omega+\omega)$ differ by exactly one term, and so they get different colors. (Note that the terms of $\alpha$ that are smaller than $\beta\cdot\omega$ cancel the same in both cases, and the larger terms don't cancel.) QED

Answer 2

Following a suggestion of Joel David Hamkins, I'm moving my previous edits to an answer -- hopefully this will make everything easier to follow. The point of this answer is to summarize a few things that have come out of this discussion.

First, although my question originally involved ordinal arithmetic, Joel suggested we look at natural arithmetic instead. Specifically, let's say that an ordinal $\delta$ satisfies van der Waerden's Theorem if:

For every finite coloring of $\delta$ and every finite $F \subseteq \delta$, there exist $\alpha,\beta \in \delta$ such that $\alpha + \beta \cdot F$ is a monochromatic subset of $\delta$.

Here $+$ and $\cdot$ denote natural addition and multiplication.

If you read Joel's answers to this question and the related linked question, he shows that (1) if we replace the natural operations with the standard operations of ordinal arithmetic, then only $\omega$ satisfies the above statement (2) if we only require that $F$ be countable (instead of finite), then no infinite ordinal can satisfy the above statement.

On the other hand, we have the following theorem:

Theorem: An ordinal $\delta$ satisfies van der Waerden's Theorem if and only if $\delta$ is indecomposable.

Proof: ("if") I have an ultrafilters-based proof of this below, but I found this morning a known result that this follows from fairly easily. The result is called the Gallai Theorem for commutative semigroups, and it can be found as Theorem 7.2 in these notes (but a proof is not given; for a proof, see below). This theorem states that if $(X,+)$ is any commutative semigroup, if we finitely color $X$, and if $F \subseteq X$ is finite, then there is some $a \in X$ and some $b \in \mathbb N$ such that $a+bF$ is monochromatic (where juxtaposition denotes repeated addition). That van der Waerden's Theorem holds for indecomposable ordinals now follows from the observation that indecomposable ordinals are closed under addition (so they are semigroups) and that $bF$ and $b \cdot F$ are the same.

("only if") Let $\delta$ be an ordinal that is not indecomposable. Fix $\gamma_0$ and $\gamma_1 < \delta$ such that $\gamma_0 + \gamma_1 > \delta$ (this just uses the definition of indecomposability). Color $\delta$ as follows: every $\alpha < \gamma_0$ is colored red, and every other element of $\delta$ is colored blue. Now let $F = \{0,\gamma_0,\gamma_1\}$ and fix $\alpha, \beta < \delta$ with $\beta > 0$. Since $\beta \cdot \gamma_0 \geq \gamma_0$, it is impossible to have $\alpha + \beta \cdot F$ all colored red. If $\alpha + \beta \cdot F$ is to be all colored blue, we must have $\alpha + \beta \cdot 0 = \alpha \geq \gamma_0$. But then $\alpha + \beta \cdot \gamma_1 > \gamma_0 + \gamma_1 > \delta$. QED

It might just be because I haven't looked hard enough, but I can't seem to find a readily-accessible proof of the Gallai Theorem for commutative semigroups. But you can prove this theorem using ultrafilters in a fairly straightforward way, so I'm putting a proof here for anyone who's interested.

Theorem: (Gallai) Let $(X,+)$ be a commutative semigroup and fix a finite coloring of $X$. If $F \subseteq X$ is finite, then there is some $a \in X$ and some $b \in \mathbb N$ such that $a+bF$ is monochromatic.

Proof: This is a modification of the standard proof of van der Waerden's Theorem using the semigroup structure of $\beta \mathbb N$. The version I'm modifying is from chapter 14 of Hindman and Strauss's book Algebra in the Stone-Cech compactification.

Let $\beta X$ be the right-topological extension of $(X,+)$ to the Stone-Cech compactification of $X$ (where $X$ is given the discrete topology). Fix some member $p$ of the minimal ideal of $\beta X$. We will show that every set in $p$ satisfies the conclusions of the theorem. This implies the result about colorings, because (as $p$ is an ultrafilter) there is a monochromatic set in $p$.

Let $F$ be a finite subset of $X$ and let $k$ be the cardinality of $F$. Then consider the semigroup $Y = \beta X \times \dots \times \beta X$ ($k$ factors). This is a semigroup compactification of $X^k$ (i.e., it is a right-topological compact semigroup containing $X^k$ as a dense subsemigroup). Let $F = \{f_1,\dots,f_k\}$ and consider $$E_0 = \{(a,\dots,a) + (n f_1, \dots, n f_k): a \in X, n \in \mathbb N \cup \{0\}\}$$ $$I_0 = \{(a,\dots,a) + (n f_1, \dots, n f_k): a \in X, n \in \mathbb N\}.$$ It is not hard to see that $E_0$ is a subsemigroup of $X^k$ and $I_0$ is an ideal of $E_0$. Let $E$ and $I$ denote the closures of $E_0$ and $I_0$ in $Y$, respectively. By Theorem 4.17 in the Hindman/Strauss book, $E$ is a subsemigroup of $Y$ and $I$ is an ideal of $E$.

Recall that $K(S)$ denotes the smallest ideal of a semigroup (if it exists -- and it always does for right-topological compact semigroups like $\beta X$ and $Y$). It is known that $K(Y) = K(\beta X) \times \dots \times K(\beta X)$ ($k$ factors) (Theorem 2.23 in Hindman/Strauss). If we can show that $E \cap K(Y) \neq \emptyset$, then it will follow that $K(E) = E \cap K(Y)$ (Theorem 1.65 in Hindman/Strauss) To show that $E \cap K(Y) \neq \emptyset$, we will show $(p,\dots,p) \in E$.

To see this, let $U = \overline{A_1} \times \dots \times \overline{A_k}$ be a basic open neighborhood of $(p,\dots,p)$. Since $p$ is an ultrafilter, $A = \bigcap_{i = 1}^kA_i \in p$. If $a \in A$, then $(a,\dots,a) \in E_0 \cap U$. Since $U$ was arbitrary, this shows $(p,\dots,p) \in \overline{E_0}^Y = E$, so we have proved $(p,\dots,p) \in E$.

As mentioned above, $(p,\dots,p) \in E$ implies that $K(E) = E \cap K(Y) = E \cap K(\beta X) \times \dots \times K(\beta X)$. But $I$ is an ideal in $E$, so $K(E)$ (being the smallest ideal) must be contained in $I$. If $A \in p$, then $\overline{A} \times \dots \times \overline{A}$ is a basic open neighborhood of $(p,\dots,p)$. Since $(p,\dots,p) \in E$, $$(p,\dots,p) \in E \cap K(\beta X) \times \dots \times K(\beta X) \subseteq I.$$ This implies $I_0 \cap \overline{A} \times \dots \times \overline{A} \neq \emptyset$. Therefore there is some $a \in X$ and $n \in \mathbb N$ such that $$(a,\dots,a) + (n f_1, \dots, n f_k) \in X^k \cap \overline{A} \times \dots \times \overline{A} = A \times \dots \times A.$$ In other words, $a + n F \subseteq A$. Since $A$ was an arbitrary element of $p$, every set in $p$ satisfies the conclusion of our theorem. QED