Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.



1 Answer 1

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$.


This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .