Let $S$ be a finite set. Show that $\text{Sym}(S)$ is a group.

Question

Wondering if someone could check I have answered this correctly, I’ve just started a course on Group theory and don’t feel confident in ability so far. The Question asks: “Let $S$ be a finite set. Show that $\operatorname{Sym}(S)$ is a group.”

Much appreciated, L

Answer:

Let $X,Y,W,Z\subseteq S$ be groups such that $$\mu\colon X\to Y,\quad\Phi\colon Y\to W,\quad p\colon W\to Z$$ Then we have

$G0)$ Closure: Let $x\in X$ be arbitrary. Then $$\Phi\circ\mu(x)=\Phi(\mu(x))=\Phi(y)\in\operatorname{Sym}(S)$$ for some $y\in Y$.

$G1)$ Associativity: $$\rho(\Phi\circ\mu(x))=\rho(\mu\circ\Phi(x))=\rho(\Phi(\mu(x)))\in\operatorname{Sym}(S)$$ and $$(\rho\circ\Phi)\circ\mu(x))=(\Phi\circ\mu)\circ\mu(x))=\rho(\Phi(\mu(x)))\in\operatorname{Sym}(S)$$ Thus, $\operatorname{Sym}(S)$ is closed under associativity.

$G2)$ Identity: Let $\sigma\colon S\to S,\,s\mapsto es$, then $\sigma$ is identity map $\operatorname{Id}\colon S\to S$ $$\sigma(s)=es=s$$ where $e$ is the identity element of $S$.

$G3)$ Inverse: Let $f\colon X\to Y$ and $g\colon Y\to X$ be maps where $X,Y\subseteq S$ and $f,g\in\operatorname{Sym}(S)$. Then, $$f\circ g (y)=f(g(y))=e\quad\text{and}\quad g\circ f(x)=g(f(x))=e$$ $\Rightarrow g(y)=f^{-1}(y)$

Thus, $\operatorname{Sym}(S)$ is a group under composition.

Answer 1

Besides a few mistakes you made (for example, you swapped the order of composition in your proof of $G1$ which is not possible in general) you seem to not have the right definition of $\operatorname{Sym}(S)$ at hand and do not completely understand what you have to show.

So let's start there. We define $\operatorname{Sym}(S)$ for a finite set (at some point you seem to assume that $S$ is a group, which is not the case) $S$ as the set of all its permutations which are nothing else than bijective maps $S\to S$. Indeed, permuting the elements of $S$ is nothing else than swapping them around one-to-one and onto. Hence, $$\operatorname{Sym}(S)=\{f\colon S\to S\,\mid\,f\ \text{bijective}\}$$ Now, we want to show that this set is a group under composition. For example, we have to show that there is an element $e\in\operatorname{Sym}(S)$ such that $f\circ e=f=e\circ f$ for all $f\in\operatorname{Sym}(S)$. So you have to explicitely construct a bijective map $S\to S$ which behaves as identity under composition. I will include the solution under a spoiler:

A good try would be the identity on $S$ (the name is chosen for a reason). This map is defined by $$\operatorname{id}\colon S\to S\,s\mapsto s$$ So, take some $f\in\operatorname{Sym}(S)$. We have to show that $f\circ\operatorname{id}=f=\operatorname{id}\circ f$, that is for $x$ arbitrary we have to show that $(\operatorname{id}\circ f)(x)=f(x)=(f\circ\operatorname{id})(x)$. By definition, $(\operatorname{id}\circ f)(x)=\operatorname{id}(f(x))=f(x)$ and similarily $(f\circ\operatorname{id})(x)=f(x)$ as desired.

The other group axioms follow using similar ideas.

There is a particular no need for introducing some subsets $X,Y,W,Z\subseteq S$ and maps between them. I think I understand what lead you to this discussion (namely, image considerations of maps $S\to S$) but it is unnecessary at best, highly confusing at worst.

Answer 2

In the following, the finiteness of $S$ doesn't enter at all, so the claim holds for infinite $S$, either.

If $f\in\operatorname{Sym}(S)$, then by definition of bijection: $\forall t\in S, \exists! s\in S\mid t=f(s)$. This latter, in turn, means that there is a map $g\colon S\to S$, $t\mapsto s=g(t)$, such that $t=f(s)=f(g(t))$. Note that $g$ is bijective too, namely $g\in\operatorname{Sym}(S)$: in fact, $g(t)=g(t')\Rightarrow f(g(t))=f(g(t'))\Rightarrow t=t'$ (injectivity); moreover, for every $s\in S$, $s=g(f(s))$ (surjectivity). Suppose now that $g'\colon S\to S$ is another map such that $t=f(g'(t))$; then, $\forall t\in S$, $f(g'(t))=f(g(t))$ and hence (by the injectivity of $f$) $g'(t)=g(t)$, and finally $g'=g$. To sum up, given $f\in\operatorname{Sym}(G)$, there is a unique $g\in\operatorname{Sym}(G)$ such that:

• $\forall s\in S$, $g(f(s))=s$
• $\forall t\in S$, $f(g(t))=t$

Since such a map $g\in\operatorname{Sym}(S)$ is unique and depends on $f$, the symbol "$f^{-1}$" is indeed suitable to denote it.

Now, you have to prove the closure of $\operatorname{Sym}(S)$ under map composition, namely that given $f,f'\in\operatorname{Sym}(S)$ and defined $\forall s\in S$:

$$(ff')(s):=f(f'(s))$$

it turns out that $ff'\in\operatorname{Sym}(S)$. In fact:

• injectivity of $ff'$: $(ff')(s)=(ff')(s')\Longrightarrow f(f'(s))=f(f'(s'))\stackrel{(f\space is\space inj.)}{\Longrightarrow}f'(s)=f'(s')\stackrel{(f'\space is\space inj.)}{\Longrightarrow}s=s'$;
• surjectivity of $ff'$: $\forall t\in S, \space\space t\stackrel{(f, f'\space have\space inverse)}{=}(ff')((f'^{-1}f^{-1})(t))$.

And now, the associative law: $\forall f,f',f''\in\operatorname{Sym}(S)$, $\forall s\in S$:

$$(f(f'f''))(s)=f((f'f'')(s))=f(f'(f''(s)))=(ff')(f''(s))=((ff')f'')(s)$$

whence $f(f'f'')=(ff')f''$.

Last but one point, the identity. Define $\iota(s):=s, \forall s\in S$; it is bijective, so $\iota\in\operatorname{Sym}(S)$, and indeed $f\iota=\iota f=f$ for every $f\in\operatorname{Sym}(S)$.

Finally, the inverse of $f\in\operatorname{Sym}(S)$: as defined in the opening, it precisely gives $ff^{-1}=f^{-1}f=\iota$.