1
$\begingroup$

$\#2^{\Omega} = 2^{\#\Omega}$

So far I know that when the size of $\Omega$ is 0, we have the $\emptyset$ and the size of the power set for $\Omega$ will be 1, or $2^{0} = 1 $

How do I start by proving this for any size $n$ of $(\Omega)$.

Also does $\Omega$ have to be finite for this to be true?

I know induction has to be used but am having trouble figuring out how to begin.

Thanks for any help.

  • 0
    The statement is true for infinite $\Omega$ as well, given the right definition of exponentiation. for the finite case, split the subsets of $\Omega$ into those containing $x_0$ and those not containing it (after selecting an $x_0\in \Omega$)2012-09-10

2 Answers 2

1

HINT: Suppose that you know that $\{1,\dots,n\}$ has $k$ subsets. Start with one of these $k$ sets. To get a subset of $\{1,\dots,n,n+1\}$ you can either stick with the set that you have, or you can add $n+1$ to it. In this way each subset of $\{1,\dots,n\}$ gives rise to two subsets of $\{1,\dots,n+1\}$. Can you see that every subset of $\{1,\dots,n+1\}$ can be obtained in this way? So $\{1,\dots,n+1\}$ must have $2k$ subsets. Use this observation to carry out the induction step of your proof by induction.

(There are also proofs that don’t use induction, as William points out in his answer.)

0

Suppose $\Omega$ is a finite set of $n$ elements. So we may as well call $\Omega = \{1, 2, ..., n\}$. Every subset $X \subset \Omega$ corresponds to a binary string $\sigma_X$ of length $n$ where the $k^\text{th}$ bit of $\sigma_X$ is $0$ if $k \notin X$ and $1$ if $k \in X$. Now by a counting argument, there are $2^n$ many distinct binary strings of length $n$.

  • 0
    @Lok Yes, that is the idea.2012-09-10