ags@pucc-i (Seaman) (03/06/84)
First, a clarification. Someone posted an induction proof that n < 2**n
for all n. The proof was correct, but it led to some rather vague
statements about numbers with infinitely many digits being greater
than 2**n for any n. As I pointed out, "greater than" has no meaning
in this context.
What follows is a different proof that n < 2**n, which has the advantage of
extending to arbitrary sets (finite and infinite) as well as the natural
numbers (which are finite sets of a particular form). This leads to a
different proof that the real numbers are uncountable.
Quick review: If A and B are sets, then A**B is the set of all mappings
f: B --> A.
In particular, what does 2**A mean? Since 2 is the set {0,1}, 2**A must
be the set of all mappings
f: A --> {0,1}.
There is a natural correspondence between 2**A and the set of all subsets
of A: With the mapping f we may associate the subset
{x in A | f(x) = 1}.
Another way of saying this is that each subset is associated with its
CHARACTERISTIC MAPPING: 1 in the set and 0 outside. Because of this
natural correspondence, the set of all subsets of A is often written
as 2**A, called the POWER SET OF A.
PROPOSITION. For any set A, the power set 2**A is larger than A.
PROOF. We must show that for every map f: A --> 2**A, there is an
element of 2**A which is not in the image of f. Such an element is
B = {x in A | not (x in f(x))}.
B is clearly a member of 2**A (i.e. a subset of A). Suppose B = f(y) for
some y in A. It follows by the definition of B that y is in B if and only
if y is not in B. Therefore no such y can be found, and the mapping f is
not onto, Q.E.D.
-------------------
Exercise: The above argument is called DIAGONALIZATION. Why? How does
it relate to the familiar diagonalization proof that the reals
are uncountable?
Notice that we have not assumed anywhere that A is a finite set. This is
the basis for a new proof that the real numbers are uncountable, to follow
in next (and probably last) article.
--
Dave Seaman
..!pur-ee!pucc-i:ags
"Against people who give vent to their loquacity
by extraneous bombastic circumlocution."