0
$\begingroup$

Here is a problem:

Show that if $\Omega$ is an infinite set, then $|\operatorname{Sym}(\Omega)|=2^{|\Omega|}$.

I have worked on a problem related to a group that is $S=\bigcup_{n=1}^{\infty } S_n$. Does it make sense we speak about the relation between $S$ and $\operatorname{Sym}(\Omega)$ when $\Omega$ is an infinite set. Moreover, I know that $|\operatorname{Sym}(\Omega)|=|\Omega|^{|\Omega|}$. How we can reach from $|\Omega|^{|\Omega|}$ to $2^{|\Omega|}$. Thanks.

$\endgroup$
  • $\begingroup$ If $\Omega$ is infinite, the two have the same cardinality. $\endgroup$ – André Nicolas Jul 11 '12 at 17:01
  • $\begingroup$ @AndréNicolas: Isn't Sym$(\Omega)\subset S$? $\endgroup$ – mrs Jul 11 '12 at 17:27
  • 1
    $\begingroup$ We can have two infinite sets $A$ and $B$, with $A$ a proper subset of $B$, but with $A$ and $B$ of the same cardinality. for example (Galileo) let $B$ be the integers, and $A$ the even integers. $\endgroup$ – André Nicolas Jul 11 '12 at 17:48
4
$\begingroup$

You have $|\Omega|^{|\Omega|} \geq 2^{|\Omega|}$, since $\Omega$ is infinite. Then, $|\Omega| < 2^{|\Omega|}$ (Cantor's theorem) so $|\Omega|^{|\Omega|} \leq (2^{|\Omega|})^{|\Omega|}=2^{|\Omega|.|\Omega|}=2^{|\Omega|}$, since $\Omega$ is infinite.

$\endgroup$
4
$\begingroup$

$\textbf{Lemma}$ : For cardinals, $2 \leq \kappa \leq \lambda$ where $\lambda$ is infinite, then $\kappa^\lambda = 2^\lambda$.

It is clear that $2^\lambda \leq \kappa^\lambda$. However $\kappa^\lambda \leq (2^\kappa)^\lambda = 2^{\kappa \cdot \lambda} = 2^{\lambda}$, where $\lambda \cdot \kappa = \text{max}\{\lambda, \kappa\}$, which can be proved.

Now taking $\kappa = \lambda = |\Omega|$ in the lemma, you have $2^{|\Omega|} = |\Omega|^{|\Omega|}$.

$\endgroup$

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.