Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: [HM] A question as to Cantor's Diagonal Method.
Replies: 13   Last Post: Oct 25, 2005 6:01 AM

 Messages: [ Previous | Next ]
 Alexander Zenkin Posts: 50 Registered: 12/3/04
Re: [HM] A question as to Cantor's Diagonal Method.
Posted: Aug 30, 2005 11:08 AM

-----Original Message-----
From: William Tait
Sent: Sunday, August 21, 2005 6:50 PM
To: historia-matematica@chasque.apc.org
Subject: Re: [HM] A question as to Cantor's Diagonal Method.

On Aug 18, 2005, at 3:54 AM, Alexander Zenkin wrote:

> Whether the following fact is known/described anywhere in mathematical
> literature?
>
> Here X=[0,1], N={1,2,3, ...},
> RAA = Reductio ad Absurdum,
> CDM = Cantor's Diagonal Method.
> |Z| - a cardinality of a set Z for any Z.
>
> THEOREM 5. If |X| = |N|, then there is NOT a rule/algorithm
> producing a 1-1-correspondence between elements of the sets, X and N.
> RAA-PROOF. Assume that |X| = |N|, BUT there is a rule/algorithm
> producing a 1-1-correspondence between elements of X and N. Then the
> rule/algorithm generates a list,
> x1, x2, x3, . . . , (1)
> containing ALL real numbers from X. Applying CDM to the list (1),
> Cantor
> generates a new real number, which doesn't belong to the list (1).
> So, the
> given list (1) contains NOT ALL real numbers from X. Contradiction.
> Q.E.D.
>

I believe that I noted this a while back in a communication to the
FOM list, in pointing out that the 'diagonal method' has a positive
content. (I expect that it has been pointed out many times before.)
Note, however, that what is quoted above from Alexander's posting
isn't quite Cantor's theorem (although it is surely an immediate
consequence of it): Rather it is: given a function from a set M to
2^M, we can construct an element of 2^M not in the range of the
function.

Regards to all,

Bill Tait

Dear Bill,

You are right - the Theorem 5 is not Cantor's theorem, since it
doesn't state the uncountability of X. The Theorem 5 doesn't state the
countability of X as well.
The Theorem 5 is a conditional statement: IF X is countable, THEN no
1-1-correspondence between elements of the sets, X and N, can be
established.
It is a quite unexpected statement, but if its RAA-PROOF (above) has
no fallacy as we, Cantor's diagonal method and me, hope :) , then the
statement is true.
And I would like to know whether this fact is described in
mathematical literature.

Best wishes,

AZ