[FOM] RE: [HM] Cantor's diagonal proof

[Keith Brian Johnson]

Alexander Zenkin wrote:

>          In conclusion, I would like to repeat once again: there is
> not a
> direct
> proof of the uncountability of continuum, only RAA-proof is valid (in
> Cantor's sense).

I don't know whether either of the following would count as "direct" or
not.  They are my own versions of proofs I've previously seen.

I should state simply and clearly at the outset how the two proofs
prove that (0,1) is nondenumerable.  The first version shows that each
denumerable subset of (0,1) is a proper subset of (0,1), so that (0,1)
must be nondenumerable (if it were denumerable, then one of its
denumerable subsets--viz., itself--would be improper).  The second
version shows that each injection from N to (0,1) fails to be a
bijection.  In each case, one "extra" element suffices:  one "extra"
element shows that a denumerable subset of (0,1) is a proper subset of
(0,1), and one "extra" element shows that an injection is not a
bijection. 

First, one might consider the subset of the set of all decimal
representations of elements of (0,1) that do not end in all 9's.  Since
there is a one-to-one correspondence between these elements and a
proper subset of (0,1), proving this set nondenumerable will prove
(0,1) nondenumerable as well.  From this subset arbitrarily select any
denumerable subset and place the elements of that subset in an
arbitrary order.  Then show, by producing the "altered diagonal
element," that there is at least one decimal representation of an
element of (0,1) not ending in all 9's left over.  Since the order of
the elements was arbitrarily chosen, this will be true even if the
elements of the chosen subset have been ordered in such a way that
their listing has ordinal number w (omega) [this is important because
one could list denumerably many decimals as w decimals followed by
another w decimals, and the "altered diagonal element" formed from the
first w decimals could then simply be in the second w decimals and
hence be in the "list" after all].  Producing a decimal representation
corresponding to an element of (0,1) that is not in the arbitrarily
selected subset shows that the subset is a proper subset of the set of
all decimal representations of elements of (0,1) that do not end in all
9's.  (Notice that one such element suffices; we do not need to find
nondenumerably many such elements.)  But that denumerable subset was
arbitrarily selected; therefore, every denumerable subset of the set in
question must be a proper subset.  But that can only mean that the set
itself is nondenumerable.  So (0,1) must be nondenumerable.

Second--and, I think, better--is to consider an arbitrary injection
from the natural numbers into the set of decimal representations of
elements of (0,1) that do not end in all 9's.  Then display, via the
"altered diagonal element," a decimal representation of an element of
(0,1) not ending in all 9's that is not in the range of the injection. 
(Notice, again, that one such element suffices.)  Since the range is a
proper subset of the codomain, the injection is not a surjection and,
therefore, is not a bijection.  But the injection was arbitrarily
chosen (notice that speaking in terms of injections has the advantage
of automatically making both the selection of the range and its order
arbitrary).  Therefore, no such injection is a bijection.  Therefore,
the domain and the codomain are not bijectively equivalent.  But the
cardinality of the codomain is at least as great as that of the domain.
 Therefore, the codomain--the set of decimal representations of
elements of (0,1) not ending in all 9's--is nondenumerable.  Therefore,
(0,1) is nondenumerable.

It's important to notice the role of ordinality.  It's also important
to recognize that it's not enough simply to say, "Show me a denumerable
list of real numbers, and I'll produce a real number not in it"--one
could simply append it to the list.  Then, of course, another "altered
diagonal element" could be produced--and added to the list.  And so on.
 One would have to produce uncountably many "extra" elements!  One must
say more than simply, "Show me a denumerable list of real numbers, and
I'll produce a real number not in it"--one "extra" is enough for each
(denumerable) list, when listed with ordinal number w, but one actually
produces uncountably many "extra" elements--one for each denumerable
list.  The one "extra" for an arbitrary list is constructed, and it is
then inferred that there is such an "extra" for each list.  One must
deduce by universal generalization that every denumerable subset is
proper or that every injection fails to be a bijection.

As I said, I don't know whether either of those counts as constructive
or not, in Zenkin's usage.

Keith Brian Johnson


	
		
__________________________________
Do you Yahoo!?
New and Improved Yahoo! Mail - 100MB free storage!
http://promotions.yahoo.com/new_mail