ags@pucc-i (Seaman) (03/16/84)
Last time I showed that for any set A, the power set 2**A is larger
than A. The proof was by Cantor Diagonalization.
The set of natural numbers is called "omega," which is the FIRST TRANSFINITE
ORDINAL NUMBER. The cardinality of omega is called ALEPH-NULL. A set
which is larger than ALEPH-NULL (i.e. a set which is too large to be
placed in one-to-one correspondence with omega) is called UNCOUNTABLE.
I will close this series of articles by showing that the cardinality of the
reals must be at least as great as 2**(ALEPH-NULL). The opposite inequality
is left as an exercise. The method is to construct a set A of cardinality
ALEPH-NULL and a one-to-one mapping f : 2**A --> [0,1] from the power set
into (not onto) the unit interval. This is all that is needed. (Why? It's
not COMPLETELY trivial).
Here is my set A: {2/3, 2/9, 2/27, ...} = All rationals of the form
2/(3**k), k=1,2,3,....
Clearly A has cardinality ALEPH-NULL. We need a map f : 2**A --> [0,1].
Since an element of 2**A may be viewed as a subset of A, we may define
f as the mapping which takes a collection of rational numbers in A
into the sum of that set of rationals. In particular, A itself is a
member of 2**A and
inf.
-----
\
\
f(A) = / 2 / (3**k) = 1.
/
-----
k = 1
Any other sum is well-defined, since it extends over a subset of the sum
above.
Exercise: Show that f is one-to-one. Compare the function g, which adds
terms of the form 2**(-k) for k=1,2,3,.... Show that g is NOT
one-to-one.
Exercise: Describe the image of f. This set is called the CANTOR SET.
One of its many interesting properties is that, although it is
uncountable, it has measure zero. Measure is a generalization
of area. One way of saying this is that if you pick a point at
random in [0,1], the probability that the point belongs to the
Cantor Set is zero, despite the fact that the Cantor Set and
its complement in [0,1] both have the SAME NUMBER of points,
namely 2**(ALEPH-NULL).
--
Dave Seaman
..!pur-ee!pucc-i:ags
"Against people who give vent to their loquacity
by extraneous bombastic circumlocution."