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

[Alexander Zenkin]

         There exists a widespread opinion that there are two proofs of
Cantor's
theorem on the uncountability of continuum (say X=[0,1]): the direct proof
(1874) and the Reductio ad Absurdum (RAA) proof (1890).
         The direct proof (e.g., in Kleene's formulation, 'Introduction to
metamathematics') is as follows.
         Cantor's THEOREM-1 (1874). There is not a 1-1-correspondence
between X and N={1,2,3, ...}.
         PROOF-1. Suppose that
         x1, x2,x3, ... ,   (1)
is a list or enumeration of some BUT NOT NECESSARY ALL of the real numbers
belonging to the set X. Applying Diagonal Method to the list (1), Cantor
produces a new real, say x* from X, not belonging to the list (1). So, no
list (1) contains all reals from X. QED.
         COROLLARY. From the THEOREM-1, Cantor's definition of the sets
inequivalency (if there is not a 1-1-correspondence between elements of
sets Z1 and Z2, then the sets, Z1 and Z2, are not equivalent), and the fact
that x* does not belong to (1), i.e., |N| < or = |X|, Cantor deduces that
|X| > |N|.

         I believe that the traditional PROOF-1 is slightly incorrect. A
correct
version of the PROOF-1 is as follows.

         PROOF-2 Suppose that
         x1, x2,x3, ... ,   (1)
is a list or enumeration of some BUT NOT NECESSARY ALL of the real numbers
belonging to the set X.
         There are two cases.
         CASE-1. Suppose that {A:} the given list (1) contains NOT ALL reals
from X.
Applying Diagonal Method to the list (1), Cantor produces a new real, say x*
from X, not belonging to the list (1). The existence of x* proves that {A:}
the list (1) contains NOT ALL reals from X. It means that in the CASE-1 we
have a deduction  A -- > A which (in classical logic) is called the error
'vicious circle', and any proof containing such an error proves nothing.
         CASE-2. Suppose that the list (1) contains ALL reals from X. - In
such a
case we have the traditional Cantor RAA-proof (1890).
         COROLLARY. There is not a direct proof of the statement |X| > |N|.
         REMARK. In my previous message ([FOM] RE: [HM] Cantor's diagonal
proof,
http://www.cs.nyu.edu/pipermail/fom/2004-March/008046.html) the following
statement was formulated:

         STATEMENT-1. The famous Cantor Diagonal Method (in its any
meta-mathematical realizations) is a special case of the Counter-Example
Method where a counter-example itself is not searched for in a set of all
possible realizations of a given common statement, but is algorithmically
deduced from the given common statement, which this counter-example must
disprove.

         Taking into account the CASE-1 (above), I must make accurate this
statement as follows:
         STATEMENT-1. The famous Cantor Diagonal Method (in its any
meta-mathematical realizations WITHIN THE FRAMEWORK OF REDUCTIO AD ABSURDUM
METHOD) is a special case of the Counter-Example Method where a
counter-example itself is not searched for in a set of all possible
realizations of a given common statement, but is algorithmically deduced
from the given common statement, which this counter-example must disprove.

         The basis of this more accurate definition: the counter example
method is applied only to disprove a COMMON statement (hypothesis),
but in the CASE-1 the statement A is not a common statement. So, in the
CASE-1 Cantor's Diagonal Method simply produces a concrete example of
a real not belonging to the list (1) which (the list), according to the
supposition,
'contains NOT ALL reals from X'.

         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).

         It would be interestingly to hear opinion of the FOM-list members.

         Alexander Zenkin