| | |
Proof:
Suppose we denote the power set of $S$ by $P(S)$.
First note that it can't possibly happen that $P(S)$ has smaller cardinality than $S$, as for every element $x$ of S, $\{x\}$ is a member of $P(S)$.
It remains to show that the cardinality of $P(S)$ is not equal to that of $S$. We argue indirectly. Suppose they were equal. Then there would be a bijection $f(x)$ (i.e., a pairing) that takes elements of $S$ to elements of $P(S)$.
To think metaphorically, suppose the elements of $S$ are people. Then there is a one-to-one, and onto pairing between the people of $S$ and all possible subsets of people from $S$.
Perhaps one might imagine the subset related to any given person, say Fred for example, as those people (in $S$) that Fred believes should earn an award this year for their good work. It is possible that Fred believes he, himself, should earn an award this year. With this in mind, let us call Fred (and others like him) "cocky". Alternatively, if a person does not believe they should earn an award this year, let us call him or her "humble".
To put this mathematically, we have just defined sets $C$ (for "cocky") and $H$ (for "humble")
$$C=\{x \in S \; | \; x \in f(x)\} \textrm{ and } H=\{x \in S \; | \; x \not\in f(x)\}$$
Now, suppose we consider $H$, the set of all humble people in $S$. This is, of course, a subset of $S$, and given our assumption of a pairing (coming from the bijection) between the elements of $S$ and $P(S)$, there must be some person, say Abby, in $S$ that believes only the humble people in $H$ deserve an award this year.
In other words, given that $f(x)$ is a bijection, we can find some $a \in S$ such that $f(a)=H$.
Certainly, Abby must be either humble or cocky, but not both. However,
If Abby is humble, she must be in $H$. But then she believes she deserves an award this year, which makes her cocky.
If Abby is cocky, she can't be in $H$. But then she doesn't believe she deserves an award this year, which makes her humble.
More precisely, $a \in H$ implies $a \not\in f(a)$ which implies $a \not\in H$, while $a \not\in H$ implies $a \not\in f(a)$, which implies $a \in H$.
Either way, we get a contradiction. The only assumption we made was the existence of a bijection, so such a bijection must not exist. Hence, the cardinality of the power set of $S$ is necessarily larger than that of $S$, itself.