Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to read the Hales-Jewett regularity theorem given as Theorem 1 here. I have a doubt in the proof which I am hoping someone here can clarify.

Here are some background definitions and a lemma:

Suppose $X$ is a set, $\mathcal{S}$ a collection of sets (usually subsets of X), and $N$ a cardinal number. We call $\mathcal{S}$ $N$-regular in $X$ if, for any partition of $X$ into $N$ parts, some part has as a subset a member of $\mathcal{S}$. If $\mathcal{S}$ is $n$-regular in $X$ for each integer $n$, we say $\mathcal{S}$ is regular in $X$.

Lemma 3: Let $X$ be a semigroup, $\mathcal{S}\subset 2^X$. Suppose for each positive integer $k$, $\mathcal{S}$ is $k$-regular in a finite subset of $X$. Then for each $n$, $\mathcal{S}_n=\{A_1A_2\cdots A_n:A_i\in \mathcal{S}\}$ is regular in $X$.

Let $W$ be a fixed set and $t\notin W$. Let $X$ be the free semigroup on the set $W$. A functional $f$ is a mapping of $W$ into $X$ which can be described as follows. For some positive integer $n$ there is an $n$-tuple $\alpha = (\alpha_1,\alpha_2,\cdots,\alpha_n)$ of elements of $W\cup\{t\}$ in which $t$ appears at least once, such that, for $w\in W$, $f(w)$ is the result of replacing the $t$ by a $w$ and multiplying (in $X$) the $n$ components of the new $n$-tuple.

Finally let $I_{m,j}$ be the statement: If $B$ is an $m$-order subset of $W$ there exists an integer $p$ such that $\{f(B): f\text{ is a functional}\}$ is $j$-regular in $B^p$. ($B^p$ is the set of $p$-sequences made from elements in $B$.)

My doubt is in the third paragraph of the proof of theorem 1:

By $I_{n-1,j}$, the fact that $B^s$ is finite for each $s$, and Lemma 3, we see that $\{f_0(B)f_1(B)\cdots f_r(B): f_i\text{ is a functional}\}$ is $(k + 1)$-regular in the subsemigroup of $X$ generated by $B$, namely, $\cup_{i=1}^\infty B^i$.

I have been racking my brains trying to understand this. Can someone please explain this statement to me.


share|cite|improve this question
up vote 2 down vote accepted

You have $A\in W^{(n)}$, $a\in A$, and $B=A\setminus\{a\}$, and an integer $r$ such that $$\{f(A):f\text{ is a functional}\}$$ is $k$-regular in $A^r$.

$B\in W^{(n-1)}$, so for each $j$, $(I_{n-1,j})$ applies to $B$: for each $j$ there is an integer $p_j$ such that $\{f(B):f\text{ is a functional}\}$ is $j$-regular in $B\,^{p_j}$. (Note: $B\,^{p_j}$ is not the Cartesian product: it’s the set of semigroup products of $p_j$ elements of $B$.) Let $$\widehat B=\bigcup_{s\ge 1}B^s\;,$$ the subsemigroup of $X$ generated by $B$. For each $j$ the set $B\,^{p_j}$ is a finite subset of $\widehat B$. Thus, for each positive integer $j$ the set $\{f(B):f\text{ is a functional}\}$ is $j$ regular in a finite subset of $\widehat B$, and hence by Lemma 3 $$\{f_1(B)f_2(B)\dots f_m(B):f_1,\dots,f_m\text{ are functionals}\}$$ is regular in $\widehat B$ for each $m$. In particular, taking $m=r+1$, $$\mathscr{S}=\{f_0(B)f_1(B)\dots f_r(B):f_0,\dots,f_r\text{ are functionals}\}$$ is regular in $\widehat B$ and hence $(k+1)$-regular in $\widehat B$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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