FOM: ConstructiveProofofCantor'sTheorem?

[Robert Tragesser]

Neil Tennant stated that the proof
of Cantor's Theorem is constructive.
Here is a less muddled response to
Neil's statement. Maybe a case
can be made for there being a
constructive proof of the crucial
lemma to Cantor's Theorem, though
it is best to say that it is
"relatively constructive"(see
below). But I do not thinkm
that it is right to say that when
this lemma is brought to bear
on Cantor's Theorem, that the
result is really a constructive
proof of Cantor's Theorem:
My take on the matter is now this:
with respect to the theorem on the
nondenumerability of the reals
and Cantor's Theorem, we have two lemmas
which do seem to be
constructively proved, although there is
I think room for controversy on the second:
Lemma R: Given any list of decimal expansions of
real numbers between 0 and 1, there is a real
number not on that list.
Lemma S: Given any set of subsets of a set M
the members of which are put into 1-1 correspondence
with the members of M, there is a subset of M
not in S.
The subset D is defined in the following way:
  x element of D iff x element of M and for no
s element of S is x assigned to s in the 1-1
correspondence and also a member of s.

If the 1-1 correspondence exists, then D exists.

Now the proof of Cantor's theorem on the basis of
this last lemma S follows with two lines:
If S is the set of all subsets of M, then there
can be no 1-1 correspondence between S and M.
The set of all subsets S(M) of M is at the least
equinumerous with M because S(M) contains all of
the singleton subsets of M  (i.e., for any m element
of M, {m} is an element of M).
Therefore the cardinality of S(M) must be
greater than that of M.

I guess the the proof of Lemma S is one
could say _relatively
constructive_, -- constructive
relative to the constructibility
of M, S, and the 1-1 correspondence
between M and S.
But do we want to say that we have a
constructive proof of Cantor's Theorem
in the form:
Cantor's Theorem: The cardinality of
the set of all subsets of a set M is
greater than the cardinality of M.

I would think that a constructive proof
of this theorem would/should provide a rule
for determining the cardinality of S(M)
from that of M???

robert tragesser











_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com