# A special observetion about the set of all one-to-one mappings on S onto itself

Suppose $S$ has more than three elements, I want to prove that I can always find $\sigma, \tau \in A(S)$, where $A(S)$ is the set of all one-to-one mappings on S onto itself, such that $\sigma \circ \tau \neq \tau \circ \sigma$.

At the moment I have just proved that the composition of functions that belongs to $A(S)$ also is in $A(S)$, the associative law for mappings, the existence of the identity map on $A(S)$ and also the existence of inverses, i.e $\sigma^{-1} \in A(S)$ such that $\sigma \circ \sigma^{-1}$ is the identity map. But I cannot even seem to see a viable way to solve the problem. Any insight will be very appreciated.

Thanks!

Let $T$ be a three-element subset of $S$, and $X = S \setminus T$ the complement of $T$. Consider the set $\mathcal F$ of bijections (one-to-one, onto mappings) $f\colon S \to S$ that fix $X$: that is, such that $f(x) = x$ for each $x \in X$. Each such mapping is then determined uniquely by the restriction $f|_T\colon T \to T$.
If we rename the elements of $T$ as $1$, $2$, $3$, then restriction to $T$ followed by this identification $T \to \{1,2,3\}$ takes $\mathcal F$ to the symmetric group on three elements, $\Sigma_3$.
There are elements $\sigma,\tau$ of $\Sigma_3$ that have the property you demand, for example $\sigma = (1\ 2\ 3)$ and $\tau = (1\ 2)$. It follows the same holds for $\mathcal F$.
If $|S|\geq3$, there are three different elements $a,b,c\in S$. Consider a one-to-one mapping $f$ that does $$\begin{cases} a\mapsto b\\ b\mapsto c\\ c\mapsto a \end{cases}$$ and another one-to-one mapping $g$ that does $$\begin{cases} a\mapsto b\\ b\mapsto a\\ c\mapsto c \end{cases}$$ Then we see that $f\circ g$ does $$\begin{cases} a\mapsto c\\ b\mapsto b\\ c\mapsto a \end{cases}$$ while $g\circ f$ does $$\begin{cases} a\mapsto a\\ b\mapsto c\\ c\mapsto b \end{cases}$$ That is, $f\circ g\neq g\circ f$
HINT: Once you have an example for $|S|=4$, you can easily produce examples for sets of larger cardinality; how? For the case $S=\{1,2,3,4\}$, try a cyclic permutation and a single transposition. (You can actually do it for $|S|=3$ as well.)