3
$\begingroup$

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.

In this question I ask about one possible extension of this theorem to $\omega_1$, which I call $(*)$. In this question I'm asking about another possible extension:

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

It's fairly easy to show that $(**)$ is equivalent to:

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

Question: Is $(**)$ consistent with ZFC?

Remark 1: Usually the elements of $\omega_1$ are also used to represent the initial segments of $\omega_1$ (i.e., every ordinal is the set of its predecessors). That seems confusing here, which is why I'm using $I$.

Remark 2: The negation of $(**)$ is consistent with ZFC. To see this, force with finite partial functions $\omega_1 \rightarrow 2$ (i.e., add $\aleph_1$ Cohen reals). Interpret the generic object as a $2$-coloring of $\omega_1$. A simple argument using dense sets shows that for every infinite initial segment $I$ and every $\alpha, \beta$, $\alpha + \beta \cdot I$ cannot be monochromatic. In fact, since this argument mentions only $\aleph_1$ dense sets and the forcing is ccc, the same argument shows that $(**)$ is incompatible with MA.

Remark 3: If some coloring gives a counterexample to $(**)$ in one model of set theory, it continues to give a counterexample in any larger model, provided that $\omega_1$ is the same in both models.

$\endgroup$
  • $\begingroup$ Your argument at the end about downward absoluteness seems to work provided that $\omega_1$ is also absolute to the ground model. But it is possible that $\omega_1^L$ is much smaller than $\omega_1$ in $V$. So I'm not sure your claims about $V=L$ at the end are quite right. $\endgroup$ – Joel David Hamkins May 18 '15 at 16:29
  • $\begingroup$ Yes, you're right -- my bad. I'll edit accordingly. $\endgroup$ – Will Brian May 18 '15 at 16:33
5
$\begingroup$

I had pointed out earlier that the question as asked has a negative answer, in light of the counterexample provided by my answer to your previous question.

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, using the usual ordinal arithmetic.


Update. But meanwhile, it was suggested on your other question to use natural (commutative) arithmetic on the ordinals, and in that case, the counterexample described above no longer works.

So let me provide a different counterexample here in the infinite case, using natural arithmetic. The principle (**) remains inconsistent with ZFC, even if one should use natural arithmetic.

Theorem. For any infinite set $A\subset\mathbb{N}$, there is coloring of the ordinals with two colors, such that there is no $\alpha$ and $\beta$ such that $\alpha+\beta\cdot A$ is monochromatic, using natural ordinal arithmetic.

Proof. First, we observe that the infinite case of van der Waerden's theorem fails in the case of natural numbers:

Lemma. For any infinite $A\subset\mathbb{N}$, there is a coloring of $\mathbb{N}$ with two colors, such that there are no natural numbers $a$ and $b$ for which $a+b\cdot A$ is monochromatic.

To prove the lemma, fix the set $A$, and now build up the coloring by finite approximations. Since there are only countably many pairs $(a,b)$, we may consider each of them in turn, and then since $A$ is infinite, we may make sure to ensure that $a+b\cdot A$ has a point of each color. So the lemma is proved.

Next, we lift this counterexample to the case of all ordinals as follows. For any ordinal $\eta$, we may consider its unique representation in Cantor normal form, $$\eta=\omega^{\eta_n}+\cdots+\omega^{\eta_0}\quad\text{ where }\eta_n\geq\cdots\geq\eta_0.$$ Let $T(\eta)$ be the number of terms that appear in the Cantor normal form of $\eta$, which might be called the trace of the ordinal. Note that $T(n)=n$ for any finite number $n$, since $n=\omega^0+\cdots+\omega^0$.

Claim. $T:\text{Ord}\to\mathbb{N}$ is a homomorphism with respect to natural addition and multiplication. That is, $$T(\alpha+\beta)=T(\alpha)+T(\beta)$$ $$T(\alpha\cdot\beta)=T(\alpha)\cdot T(\beta),$$ where on the left-hand side, we use natural arithmetic on the ordinals, and on the right hand side is the usual arithmetic on $\mathbb{N}$.

The claim can be proved by considering the definition of natural sum and product. Basically, the natural sum $\alpha+\beta$ is defined from the Cantor normal form by rearranging the terms from the form of $\alpha$ and the form of $\beta$ so as to be in the right order, and therefore it preserves the total number of terms. Similarly, the natural product performs all possible products of terms in the Cantor normal form (using distributivity) and rearranges them into the right order, so that every cross term is present, contributing one term to the Cantor normal form of the result. (It would help for this to verify that $\omega^\alpha\cdot\omega^\beta=\omega^{\alpha+\beta}$ using natural sum and product, an issue I recall coming up on MathOverflow previously.)

Now, fix the coloring $n\mapsto c(n)$ that is provided by the lemma for the given infinite set $A\subset\mathbb{N}$. Extend this coloring to all ordinals by defining $c(\eta)=c(T(\eta))$. That is, we color an ordinal $\eta$ according to the color that the trace $T(\eta)$ would get via $c$.

I claim finally that for any ordinals $\alpha$ and $\beta$, the collection of ordinals given by $\alpha+\beta\cdot A$ is not monochromatic, using natural arithmetic. To see this, observe that the color of $\alpha+\beta\cdot n$ is the same as the color of its trace in the natural numbers $T(\alpha+\beta\cdot n))=T(\alpha)+T(\beta)\cdot n$, using the homomorphism properties of $T$, and so if $\alpha+\beta\cdot A$ were monochromatic, then so would be $a+b\cdot A$, where $a=T(\alpha)$ and $b=T(\beta)$. But by the choice of the coloring on the natural numbers, this is impossible. QED

$\endgroup$
  • $\begingroup$ Does anyone know if the function $T$ that I am using here has an established name? $\endgroup$ – Joel David Hamkins May 20 '15 at 0:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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