If you find any mistakes, please make a comment! Thank you.

## If A and B have the same cardinality, then Sym(A) and Sym(B) are isomorphic

Let $\theta : \Delta \rightarrow \Omega$ be a bijection. Define $\varphi : S_\delta \rightarrow S_\Omega$ by $\varphi(\sigma) = \theta \circ \sigma \circ \theta^{-1}$ for all $\sigma \in S_\Delta$ and prove the following.

(1) $\varphi$ is well defined; that is, if $\sigma$ is a permutation of $\Delta$ then $\theta \circ \sigma \circ \theta^{-1}$ is a permutation of $\Omega$.
(2) $\varphi$ is a bijection. (Find a two-sided inverse.)
(3) $\varphi$ is a homomorphism; that is, $\varphi(\sigma \circ \tau) = \varphi(\sigma) \circ \varphi(\tau)$.

Solution:

(1) Let $\sigma \in S_\Delta$. Note that $\theta \circ \sigma \circ \theta^{-1} : \Omega \rightarrow \Omega$, and that the composition of bijections is a bijection, so that $\theta \circ \sigma \circ \theta^{-1}$ is in fact a permutation of $\Omega$.

(2) Define $\psi : S_\Omega \rightarrow S_\Delta$ by $\psi(\tau) = \theta^{-1} \circ \tau \circ \theta$. Then $$(\psi \circ \varphi)(\sigma) = \theta^{-1} \circ \theta \circ \sigma \circ \theta^{-1} \circ \theta = \sigma,$$ and similarly $(\varphi \circ \psi)(\tau) = \tau$. So $\psi$ is a two-sided inverse for $\varphi$, and thus $\varphi$ is a bijection.

(3) We have $$\varphi(\sigma \circ \tau) = \theta \circ \sigma \circ \tau \circ \theta^{-1} = \theta \circ \sigma \circ \theta^{-1} \circ \theta \circ \tau \circ \theta^{-1} = \varphi(\sigma) \circ \varphi(\tau),$$ hence $\varphi$ is a homomorphism.