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

  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.
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: