I'm sorry if this is a duplicate in any way. Throughout I use cycle notation and write maps $m:X\to Y$ on the right of their arguments (e.g. $xm=y$ for $m(x)=y$).

This is Exercise 1.7 of Howie's Fundamentals of Semigroup Theory.

The Details:

Definition 1: Let $S$ be a semigroup and $A$ be a subset of $S$. The subsemigroup of $S$ generated by $A$ is given by the intersection of all the subsemigroups of $S$ containing $A$, denoted $\langle A\rangle$.

Definition 2: The full transformation semigroup $\mathscr{T}_n$ on the set $N=\{1, \dots,n\}$ is given by all maps $\alpha:N\to N$, together with composition of transformations.

Definition 3: For $i\ne j$ in $N$, let $\lvert\lvert i\, j \rvert\rvert$ denote the map $\phi\in\mathscr{T}_n$ for which $$i\phi =j,\quad x\phi=x\quad (x\ne i).$$

Let $\pi=\lvert\lvert 1\, 2 \rvert\rvert$.

Lemma 1: The following hold: $$\begin{align} (1\, i)\circ\pi\circ (1\, i)&=\lvert\lvert i\, 2 \rvert\rvert\quad (i\ge 3), \\ (2\, j)\circ\pi\circ (2\, j)&=\lvert\lvert 1\, j \rvert\rvert\quad (i\ge 3), \\ (i\, j)\circ\lvert\lvert i\, j \rvert\rvert\circ (i\, j)&=\lvert\lvert j\, i \rvert\rvert\quad (i, j\ge 1, i\ne j). \end{align}$$

Proof: Just plug & chug.$\square$

Lemma 2: Let $\varphi\in\mathscr{T}_n$ with $\lvert\operatorname{im}\varphi\rvert=r\le n-1$. Let $i\ne j$ such that $i\varphi=j\varphi$ and let $z\in N\setminus\operatorname{im}\varphi.$ Then $$\varphi=\lvert\lvert i\, j \rvert\rvert\circ\hat{\varphi},$$ where $$i\hat{\varphi}=z,\quad k\hat{\varphi}=k\varphi\quad (k\ne i).$$

Proof: This is again just a matter of plug & chug: the maps agree on $N$.$\square$

The Question:

Let's get a possible typo out of the way first.

A subquestion: Does $$(1\, i)\circ(2\, j)\circ\lvert\lvert i\, j \rvert\rvert\circ (2\, j)\circ (1\, i)=\lvert\lvert i\, j \rvert\rvert$$ for $i,j\ge 3, i\ne j$?

Perhaps I'm being stupid but I can't get the LHS to agree with the RHS on $1$ (as $1\mapsto i\mapsto i \mapsto j\mapsto 2\mapsto 2$ but I need $1\lvert\lvert i\, j \rvert\rvert=1$). The correct version of this result is considered as part of Lemma 1.

Let $\tau=(1\, 2), \zeta=(1\, 2\, \dots \, n)$.

Deduce (from Lemma 1 and Lemma 2) that $\mathscr{T}_n=\langle\zeta, \tau, \pi\rangle$.

My Attempt:

I'm not sure where to start. I did the previous question of Howie's book (showing the symmetric group $\mathscr{S}_n=\langle\tau, \zeta\rangle$) without any trouble. That might be of some use here. I can see how Lemma 1 might be made to fit $\zeta, \tau$ and $\pi$, making elements of $\mathscr{T}_n$.

Please help :)


As for the subquestion: that is definitely a typo, the correct equality is:

$$(1\, i)\circ(2\, j)\circ\lvert\lvert 1\, 2 \rvert\rvert\circ (2\, j)\circ (1\, i)=\lvert\lvert i\, j \rvert\rvert$$

when $i,j\not = 1,2$, $i\not=j$.

As for the main question: Let $f_0\in T_n$ be arbitrary. Then either $f_0\in S_n$ or $f_0\in T_n\setminus S_n$. In the first case, $f_0\in \langle (1\,2), (1\,2\cdots n)\rangle$ and you're done. In the second case, $f_0\in T_n\setminus S_n$ and so, by Lemma 2, we can write $$f_0=||i_0\,j_0||\,f_1$$ for some $i_0, j_0$ and $f_1$ satisfying $\operatorname{rank}(f_1)=\operatorname{rank}(f_0)+1$. If $\operatorname{rank}(f_0)=n-k$ for some $k$, then repeatedly applying Lemma 2 you get $$\begin{align} f_0&=\lvert\lvert i_0\,j_0\rvert\rvert\,f_1 \\ &=\lvert\lvert i_0\,j_0\rvert\rvert\cdot\lvert\lvert i_{1}\,j_{1}\rvert\rvert\,f_2 \\ &=\dots \\ &= \lvert\lvert i_0\,j_0\rvert\rvert\cdot\lvert\lvert i_{1}\,j_{1}\rvert\rvert\cdot \dots \cdot \lvert\lvert i_{k-1}\,j_{k-1}\rvert\rvert\,f_k, \end{align}$$ where $f_k\in S_n$ (since $\operatorname{rank}(f_k)=n$). It follows that $f_0\in \langle \lvert\lvert 1\,2\rvert\rvert, (1\,2), (1\,2\cdots n)\rangle$.

  • $\begingroup$ Where are my manners? Thank you :) $\endgroup$ – Shaun Oct 5 '14 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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