Exercise 4.6.8 ($\text{If } S_\Omega \simeq S_\Delta \text{ then }|\Omega| = |\Delta|$)

Proof.

(a)

We prove $|D|=|\mathrm{\Omega }|$.

Let $𝒯$ be the set of transpositions :

$$𝒯=\{(ab)\mid a\in \mathrm{\Omega },b\in \mathrm{\Omega }\}.$$

We define ${𝒯}_0=\{1\},{𝒯}_1=𝒯$, and ${𝒯}_n$ the set of product of $n$ transpositions. Then

$$𝒯=\underset{n\ge 0}{\bigcup }{𝒯}_n.$$

We know that

$$D=⟨𝒯⟩.$$

The map

$$\{\begin{array}{ccc}\hfill 𝒯\hfill & \hfill \to \hfill & \mathrm{\Omega }\hfill \\ \hfill (ab)\hfill & \hfill \mapsto \hfill & a\hfill \end{array}$$

is surjective: If $a\in \mathrm{\Omega }$, take any $b\in \mathrm{\Omega }-\{a\}$. Then the image of $(ab)$ is $a$.

Therefore $|\mathrm{\Omega }|\le |𝒯|$. Moreover, $𝒯\subseteq D$, thus $|𝒯|\le |D|$, so

$$|\mathrm{\Omega }|\le |𝒯|\le |D|.$$

We prove by induction that $|{𝒯}_n|\le \mathrm{\Omega }$.

First $|{𝒯}_0|=1\le \mathrm{\Omega }$. Suppose that $|{𝒯}_n|\le \mathrm{\Omega }$. Consider the map

$$\phi \{\begin{array}{ccc}\hfill {\mathrm{\Omega }}^2\times {𝒯}_n\hfill & \hfill \to \hfill & {𝒯}_{n+1}\hfill \\ \hfill ((a,b),\sigma )\hfill & \hfill \mapsto \hfill & (ab)\sigma \hfill \end{array}$$

Then $\phi$ is surjective by definition of ${𝒯}_n$. Therefore the induction hypothesis shows that

$$|{𝒯}_{n+1}|\le |{\mathrm{\Omega }}^2\times {𝒯}_n|\le |\mathrm{\Omega }{|}^3=|\mathrm{\Omega }|.$$

The induction is done, which proves $|{𝒯}_n|\le \mathrm{\Omega }$ for all $n\ge 0$. Hence

$$|D|=\left|\underset{n\ge 0}{\bigcup }{𝒯}_n\right|\le |\mathrm{\Omega }|.$$

Using Cantor-Bernstein Theorem, this proves

$$|D|=|\mathrm{\Omega }|.$$

(b)

We prove $|A|=|D|$. If $\tau$ is any transposition, then $D=A\cup \mathit{𝜏𝐴}$. Moreover $|\mathit{𝜏𝐴}|=|A|$. Therefore $$|D|=|A|+|\mathit{𝜏𝐴}|=|A|.$$

(c)

Let $D_{\mathrm{\Omega }}$ be the subgroup of $S_{\mathrm{\Omega }}$ consisting of permutations which move only a finite number of elements of $\mathrm{\Omega }$. We define similarly $D_{\mathrm{\Delta }}$.

Suppose that $S_{\mathrm{\Omega }}\simeq S_{\mathrm{\Delta }}$, so that there is some isomorphism $\psi :S_{\mathrm{\Omega }}\to \mathrm{\Delta }$. Then $\psi (D_{\mathrm{\Omega }})=D_{\mathrm{\Delta }}$, therefore $|D_{\mathrm{\Omega }}|=|D_{\mathrm{\Delta }}|$.

By part (a), $|\mathrm{\Omega }|=|D_{\mathrm{\Omega }}|$ and $|\mathrm{\Delta }|=|D_{\mathrm{\Delta }}|$, thus

$$|\mathrm{\Omega }|=|\mathrm{\Delta }|.$$

In conclusion,

$$\text{if }{S}_{\mathrm{\Omega }}\simeq S_{\mathrm{\Delta }}\text{ then }|\mathrm{\Omega }|=|\mathrm{\Delta }|.$$