2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks, now it is very clear and very easy to prove. $\endgroup$ – David Cardozo Dec 9 '14 at 4:55
  • $\begingroup$ @David: You’re welcome. $\endgroup$ – Brian M. Scott Dec 9 '14 at 4:56

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.