Hindman's theorem on coloring a set with $n$ colours

407 Views Asked by At

Hindman's theorem states that if we colour $\mathbb{N}$ (positive integers) with a finite number of colours $c_1,\ldots,c_n$, then there exists a color $c_i$ and an infinite subset $A \subset \mathbb{N}$ such that every finite sum of elements in $A$ has the same colour.

But wouldn't this imply that each element of $A$ has the same colour? If $a,b \in A$ and the colour of $a$ and $b$ are different, then ... that's a contradiction, right?

Clearly I'm misunderstanding something. If someone could shed some light on this that would be great.

1

There are 1 best solutions below

4
On BEST ANSWER

A sum of one term is still a sum. So yes, your reasoning is correct--the set $A$ must be all the same color.

That the set itself also has the same color is also made clear by Wikipedia, emphasis mine:

We can reformulate a special case of Hindman's Theorem in more familiar terms: Suppose the natural numbers are "colored" with $n$ different colors; each natural number gets one and only one of the $n$ colors. Then there exists a color $c$ and an infinite set $D$ of natural numbers, all colored with $\boldsymbol{c}$, such that every finite sum over $D$ also has color $c$.

I previously erroneously claimed that it is equivalent that there exists an infinite subset of $\mathbb{N}$, all of the same color, and closed under addition--the set of all finite sums of elements of $A$. This is incorrect. The difference is that "finite sum" refers here only to sums of a finite number of distinct elements. I apologize for the error.