Many students encounter the proof that the cardinality of the power set of a set $S$ is strictly greater than the cardinality of $S$. The proof of this may at first appear somewhat contrived and lends itself to being forgotten easily. I will try to introduce the subject in a way that makes it seem more intuitive and also easier to remember.
First we consider the set $S$ of all binary sequences (strings of zeroes and ones), and we ask if $S$ is countable. It turns out that it isn't, and the most intuitive way to prove this is by contradiction. Thus, we shall suppose that $S$ is countable, pick an enumeration, and then show that there exists a binary sequence that is not in the enumeration.
Let $s_1, s_2, \ldots$ be an enumeration of $S$, and let $s_{ij}$ denote the $j$th term of the $i$th sequence.
Let $(t_k)$ be the sequence given by $t_k=0$ if $s_{kk}$=1 and $t_k=1$ if $s_{kk}=0$. By construction this is a binary sequence, and so must be in $S$, but it can't be in the above enumeration because it differs from $s_i$ in the $s_{ii}$ term.
This is our desired contradiction, and so it follows that $S$ is uncountable.
From this follows pretty easily the uncountability of the real numbers (by producing the appropriate injections and applying the Cantor-Bernstein Theorem).
In general, we have the following theorem:
Theorem. $|P(S)|>|S|$
Proof. It is fairly easy to see that $|P(S)| \geq |S|$. Suppose for contradiction that $|S| = |P(S)|$. Thus there exists a bijective function $f:S \rightarrow P(S)$. Similarly to the above argument, we will construct a set that cannot be in the range of this function. Let $A_0$ be the set consisting of all elements $n$ that satisfy $n \notin f(n)$. This is rather similar to what we did with the binary sequences - if an element is not contained in its image under $f$, we put it in the set, and otherwise we leave it out. This way our set differs from $f(n)$ for each $n$.
We thus suspect that $A_0$ cannot be in the range of $f$. Suppose it is. Then $A_0 = f(N)$ for some $N$. But then we can ask if $N\in A_0$, and we get the contradictions $N \in A_0 \rightarrow N \notin A_0$ (and vice versa).
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment