![Cardinality of the Power Set [Closed]](https://docuprint.cloud68.co/uploads/cardinality-of-the-power-set-closed_1200.jpg)
Show that the cardinality of the power set of a finite non-empty $N$ set is a multiple of $2$. Then, show that it is exactly expressed by $2^n$, where $n$ is the cardinality of $N$ and that this holds also when $N$ is empty.
5 Answers
Let $P(n)$ :: if $X$ is finite and Card($X$) $= n$, then the card of $2^X$ ($X$'s power set) is $2^n$
$P(1)$ is obvious
$P(2)$ is pretty obvious too :)
Now assume $P(n)$ is true and let $X$ be a finite set of card $n+1$.
Let's pick a particular element of $X$, say $x$. Now any subset of $X$ either includes $x$ or not (trivial). If it does include $x$, it is of the form $\{x\} \bigcup y$, where $y$ is a subset of $X$ that doesn't include $x$ and with cardinality $n$ (trivial).
If you write
- $Y$ the set of subsets of $X$ that don't contain $x$,
- $Z$ the set of subsets of $X$ that contain $x$, and
- $ \phi : Y \rightarrow Z$, $y \mapsto \{x\} \bigcup y$,
you have :
- $\mathcal{P}(X) = Y \bigcup Z$ and $Y \bigcap Z = \{\} $
- $\phi$ is a bijection (one-to-one function) from $Y$ to $Z$
- Card($Y$) = Card($Z$) = $2^n$ (because of $P(n)$)
and therefore:
- Card($2^X$) = Card($Y$)+Card($Z$) = $2^{n+1}$, i.e. $P(n+1)$
Standard proof using induction.
Assume $\vert 2^{N}\vert=2^{\vert N\vert}$ (where $2^N$ is the power set of $N$) for every set $N$ whose cardinality is $\le n$.
Now take a set $M$ with $\vert M\vert=n+1$. Split $M=N\cup\{x\}$ in two disjoint sets, taking away from $M$ a random element $x$. Now $\vert N\vert=n$ so you can apply induction, therefore $\vert 2^N\vert =2^n$.
Think of who is $2^M$: the set of all subsets of $M$. There are two kind of such subsets; those who contains $x$ and those who don't. In the first case, they belong to $2^N$, in the other case, they are just a subset of $N$ with the $x$ added. So $2^M$ is made up of two 'copies' of $2^N$, and then $\vert 2^M\vert=2\vert2^N\vert=2\cdot 2^n=2^{n+1}$, as wanted.
Let $x$ be an element of $N$. Consider the collection $A$ of all subsets of $N$ containing $x$, and the collection $B$ of all subsets of $N$ not containing $x$. Ther
$A \cup B = \text{power set of $N$}$, and
$A \cap B = \emptyset$.
(because every element of the power set either contains $x$ or it doesn't).
I claim that $A$ and $B$ are of equal cardinality, because there's a bijection from $A$ to $B$: take any set $P$ in $A$, and consider $P - \{x\} \in B$. For the inverse, take a set $Q \in B$ and consider $Q \cup \{x\}$.
For the second part, use induction: the power set of $N$ has cardinality twice that $B$, which is the power set of $N - \{x\}$, while the power set of $\emptyset$ has cardinality $1$.
As mentioned by @Vladimir Louis, the power set contains all possible combinations of elements in S. Therefore, $|P(S)|=\text{number of possibilities of combination}$.
Consider a string comprised of $1$'s and $0$'s, '1' at i-th position meaning i-th element in $S$ included(here we assume the set has a temporary order), '0' meaning i-th element excluded.
Hence, there are total number of $2^n$(either $1$ or $0$ in $n$ positions) possibilities of combinations.
Let $S$ be a set, with $|S|=n$, where $|S|$ denotes the cardinality of $S$. The power set, $\mathcal{P}(S)$, is the set of all subsets of $S$. Therefore, we can think of each element of $\mathcal{P}(S)$ as containing combinations not the permutations, since sets don't consider orders) of elements of $S$. This implies that the cardinality of $\mathcal{P}(S)$ is equal to the total number of possible combinations of the elements of S.
So we have, $$\left|\mathcal{P}(S)\right|={n\choose 0}+{n\choose 1}+{n\choose 2}+\ldots+{n\choose n}=\sum_{i=0}^{n}{n\choose i}=\sum_{i=0}^n{n\choose i}\cdot1^{i}\cdot1^{n-i}=(1+1)^n=2^n,$$ based on the Binomial Theorem, which indicates that the sum is the expansion of $(1+1)^2$.
The empty set has no element, but its power set must have the empty set as a member. So its cardinality is $1$, and the formula holds for $2^0=1$.
