47.5 The Hales-Jewett Theorem

Proof. (1): By (U) of the Stone-Čech compactification.

(2): Suppose for contradiction that $p$ is a minimal idempotent in $\beta T$, then $L = (\beta T)p$ is a minimal left ideal in $\beta T$. Since $(\beta T)*p \subset \beta V \cap (\beta T)p$, $(\beta T)p \cap \beta V = (\beta T)p$ by minimality, and $(\beta T)p \subset \beta V$. As such, $(\beta S)p \subset \beta S \cap (\beta T)p \cap \beta V = \emptyset$, which is impossible.

(3): By Theorem 47.4.11, $S \setminus \beta S$ admits a minimal idempotent $p$, which is idempotent in $\beta T$. By the idempotent refinement lemma, there exists a minimial idempotent $q \in \beta T$ such that $pq = qp = q$.

Suppose again for contradiction that $q \in \beta S$, then $pq = q \in (\beta S)p$, which is minimal in $\beta S$. As such, $(\beta S)q \subset (\beta S)p$, and $(\beta S)q = (\beta S)p \subset \beta S$, so $q$ is a minimal idempotent in $\beta S$. By (2), $q$ is not minimal in $\beta T$, which is impossible.$\square$

Proof. (IF): Let $T = (A \sqcup \bracsn{*})^{+}$ be the free semigroup of all non-empty words in $A \sqcup \bracsn{*}$.

For each $a \in A$, let $\pi_{a}: T \to S$ be the corresponding substitution map, and $\beta \pi_{a}: \beta T \to \beta S$ be its continuous extension. Let $p \in \beta S \setminus S$ be a minimal idempotent. By Lemma 47.5.3, there exists a minimal idempotent $q \in \beta T$ be a minimal idempotent with $pq = qp = q$ and $q \in \beta T \setminus \beta S = \beta V$.

As $\pi_{a}|_{S} = \text{Id}_{S}$, $\beta \pi_{a}|_{\beta S}= \text{Id}_{\beta S}$, so $\beta \pi_{a}(p) = p$. Since $q$ is idempotent and $\beta \pi_{a}$ is a semigroup homomorphism, $\beta \pi_{a}(q) \in \beta S$ is also idempotent. Further,

and

so $\beta \pi_{a}(q)p = p\beta \pi_{a}(q) = \beta \pi_{a}(q)$. In particular, $\beta \pi_{a}(q) = \beta \pi_{a}(q)p \in (\beta S)p$, where $(\beta S)p$ is a minimal left ideal in $\beta S$. By minimality, $(\beta S)\beta \pi_{a}(q) = (\beta S)p$, and there exists $u \in \beta S$ with $p = u\beta \pi_{a}(q)$. As such,

Let $S = \bigsqcup_{j = 1}^{r} C_{r}$ be a finite colouring of $S$, then there exists a unique $1 \le i \le r$ such that $C_{i} \in p$. Since $\beta \pi_{a}(q) = p$ for all $a \in A$, $\bigcap_{a \in A}\pi_{a}^{-1}(C_{i}) \in q$. As $q \in \beta T \setminus \beta S = \beta V$, $V \in q$, and $V \cap \bigcap_{a \in A}\pi_{a}^{-1}(C_{i}) \ne \emptyset$. Therefore any element of $V \cap \bigcap_{a \in A}\pi_{a}^{-1}(C_{i})$ generates a combinatorial line, contained in $C_{i}$.

(F): Let $r \ge 1$ and suppose for contradiction that for every $N \in \natp$, there exists an $r$-colouring $c_{N}: A^{N} \to \bracsn{1, \cdots, r}$ such that $c_{N}$ contains no monochromatic combinatorial line. Define

then $c$ is a $r$-colouring of $S$ containing no monochromatic combinatorial lines, which contradicts (IF).$\square$

Proof. Let $A = \bracsn{1, \cdots, k}$ and

By the Hales-Jewett Theorem, there exists $N = N(r)$ such that $\tilde c$ contains a monochromatic combinatorial line. In other words, there exists a variable word $v \in (A \sqcup \bracsn{*})^{N} \setminus A^{N}$ such that the set

is monochromatic. Let $J = \bracsn{1 \le j \le N|v_j = *}$, then as $v \not\in A^{N}$, $J$ is non-empty. Take $n = |J|$ and $a = \sum_{j \not\in J}v_{j}$, then for each $1 \le i \le k$,

In particular, for each $1 \le i, i' \le k$,

Therefore the arithmetic progression $\bracsn{a + in|1 \le i \le k}$ is monochromatic.$\square$