# Showing the full transformation semigroup $\mathscr{T}_n=\langle\zeta, \tau, \pi\rangle$.

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

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