by Alexander Zenkin

alexzen@com2com.ru .

An extended version of the paper "Mistake of Georg Cantor",
- Voprosy Filosofii (Philosophy Problems), 2000, No. 2, 163-168.

    The theory of sets is one of the basic disciplines of modern mathematics. On the other hand, the problem of the foundations of that sets theory is one of the most important problems of the philosophy of mathematics. Some historical, logical and philosophical aspects of this important and topical scientific problem are examined in this work.

    Modern (axiomatic) theory of sets is the only mathematical discipline, which "knows how" to differentiate infinite sets one from another according to their powers, i.e., basing on the number of elements making up that set. The one and only basis for such differentiation of infinities is the famous George Cantor's theorem about the uncountablity of the set of all real numbers. As is well known, G. Cantor proved his theorem in 1878, i.e., half a century before the emergence of meta-mathematics. Consequently, this G. Cantor's theorem is not a meta-mathematical one. Moreover, it is difficult to call it a mathematical theorem because it is only three elementary mathematical notions, -namely: the concepts of the natural number, the real number and the set (sequence) of such numbers, that are used in its proof. In summary, one can say that the famous G. Cantor's theorem is a purely logical statement, which is proved with classical elementary logic, since a mathematical logic as well was not existing at that time.

    The Cantor's proof still has one more unique peculiarity. The point is that today it is quite difficult to surprise anybody with a complexity and a volume of mathematical proofs. For instance, the famous solution of the four-color problem occupies about 100 pages of a mathematical text (plus about 1000 hours of computer calculations). The famous solution of the Great Fermate's Theorem takes about 1000 pages of a mathematical text. Finally, the solution of the simple finite groups' classification problem takes about 15000 journal pages.
    Against this background, the proof of Cantor's theorem looks simply fantastic: it takes in all 10 lines and is characterized by the "parameter" of the deep psychological and philosophical meaning: one line of that proof fits into 10 years of its existence.

    I don't have any doubt that logical analysis of that 10 lines of a non-mathematical text is completely comprehensible for any non-professional in the modern meta-mathematics.

    I shall cite the full text of that famous Cantor's theorem and its proof.

    Let's denote X the set of all real numbers, or just the same, of all points of the unit segment [0,1]. We introduce the following agreements:
    1) for simplicity, we will be using the binary number system for the real numbers presentation;
    2) instead of the long expression "real number x is an element of the set X", we shall write x X, and in place of the negation of a statement, say, A, we shall write A;
    3) Exclusively for the ease of subsequent references, we shall use various records, enclosed in curly braces "{}".

    Thus, let's consider the traditional proof of Cantor's theorem (see for instance, S.K.Kleene, "Introduction to metamathematics", M.: IL, 1957, p.13).

    CANTOR'S THEOREM: {Thesis A:} The set X is uncountable.
    CANTOR'S PROOF. According to the proof by contradiction, we assume that { A:} the set X is countable. This means, by the countable sets definition, that all elements of X can be enumerated with ordinary finite natural numbers.

    Let a sequence

    x1, x2, x3, xn ,                  (1)

be some enumeration of all x X, i.e. ,

{B:} for any z, if z X, then z (1).

    Further, applying his famous diagonal method to the enumeration (1), G. Cantor builds a new real number, say, y1 , - we shall call it Cantor's Diagonal Number (CDN), - such that by definition y1 X, but by design y1 differs from each element of the enumeration (1), i.e. CDN y1 does not belong to the enumeration (1). Consequently,

{ B:} y1 X, but y1 is not included in the enumeration (1).

    Thus, we have obtained the contradiction between B and B. From that contradiction, taking into account the arbitrariness of the enumeration (1), Cantor comes to his famous conclusion: the assumption A about the countablity of the set X is false. Consequently,

{A:} the set X is uncountable. QED.

    However, it is appropriate to mention here the following. While proving Cantor's theorem, the so-called diagonal of the enumeration (1):

    0, x11 x22 x33 xnn ,                 (*)

is used, i.e. the infinite sequence, where the digit x11 is the first binary digit of the first element x1 of the enumeration (1), the digit x22 is the second binary digit of the second element x2 of the enumeration (1), the digit x33 is the third binary digit of the third element x3 of the enumeration (1), etc. As was shown above, G.Cantor, using the diagonal (*), builds a new infinite binary sequence:

    y1 = 0, y11 y12 y13 y1n ,         (**)

according to his famous diagonal rule:

    for any i: [if xii = 0, then y1i = 1] and [if xii = 1, then y1i = 0].         (***)

    By definition, any infinite (in this case - binary) sequence of the type (**) is a real number of the segment [0,1], i.e., this CDN  y1 X. It is obvious that if the enumeration (1) is finite, then its diagonal (*), and the corresponding "anti-diagonal" sequence (**) will also be finite, i.e.,  in such the case it does not define any real number. In other words, the inapplicability of Cantor's diagonal method to finite enumerations is so obvious that nobody ever examined that issue. However, that "obviousness" is only an ingrained psychological stereotype of meta-mathematical thinking.

    Really, let's take an arbitrary infinite binary sequence as initial "half-finished product" for building the Cantor's Diagonal Number, for instance, the simplest such sequence which is the identical zero:

    z1 = 0, 01 02 03 0n ,     (**)

and apply the Cantor's diagonal rule to the enumeration (1) in the following form:

    for any i: [if xii = 0, then 0i = 1] and [if xii = 1, then 0i = 0].     (***)

    It is easy to see that, literally repeating Cantor's reasoning, we will obtain, as a result, a real number z1, which is different from all elements of the enumeration (1), and identically coincides with Cantor's real number y1.
    And what will happen in the case where the enumeration (1) is finite? It is obvious that while applying Canter's diagonal method in the forms of (**) and (***) to any finite enumeration, say,

    x1 , x2 , x3, xn ,         (1a)

we shall get a rational (even with the zero "tail") number:

    z1 = 0, z11 z12 z13 z1n 0 0 0 ,

which is different, by its first n digits, from each of n numbers of this finite enumeration (1a).

    Thus, Cantor's diagonal method proved to be applicable, without any changes, to both infinite and finite enumerations. Consequently, that method does not distinguish and does not take into account quantitative characteristics (properties) of those sets and enumerations which it is applied to. We come to the following, very significant for the mathematics philosophy conclusion: The only method, which hitherto allowed meta-mathematicians to differentiate sets according to the number of their elements, i.e. by their "power-cardinality", does not differentiate (distinguish) finite sets from infinite sets just by their power!

    Then, which properties of the enumeration (1) does Cantor's diagonal method take into account and explicitly (algorithmically) use? It's obvious that it is only the actuality of those enumerations to which the method is applied, i.e. the property (condition), according to which given enumeration contains ALL elements of some set. And only such the actuality condition permits Cantor to state that the CDN y1 is different from ALL elements of the given enumeration (1) and that the given enumeration (1) does not contain ALL elements of the set X. It is only this condition of the actuality that enabled Cantor to get the desired contradiction " B and B" of his proof.
    Thus, the famous Cantor's Diagonal Method uses only the actuality of the enumeration (1), and does not use its quantitative properties.

    But if we, nevertheless, remember that the enumeration (1) is not only actual (i.e., according to the Cantor's assumption, "contains all x X") but also it is infinite set, then Cantor's contradictions between B and B can be resolved or eliminated without any logical conflicts with the assumption A of the Cantor's proof of that Theorem.

    Indeed, according to Cantor's definition itself of the infinite set conception, the power of of an infinite set will not change if one new element (or even a countably infinite number of new elements - see Remark 1 below) is added to it. This is why we can add CDN y1 to the initial, countable-infinite enumeration (1), for instance, thus:

    y1, x1 , x2 , x3 , xn , .         (1.1)

Now we can state that, at this moment, the countable-infinite enumeration (1.1) contains all real numbers of the set X, i.e.

{B: } for any z, if z X, then z (1.1),

    Thus, we have eliminated Cantor's contradiction between B and B without any damage to the assumption A of Cantor's proof.

    However, it is obvious that appling Cantor's diagonal method again to the countable-infinite enumeration (1.1), we shall go to the construction of a new CDN, say y2 such that

{ B: }      the new y2 X, but this y2 is not included in (1.1).

    But in that case a new countable-infinite enumeration, like this:

    y2, y1 , x1 , x2 , x3 , xn , .         (1.2)

can be constructed and we shall get:

{B:}     for any z, if z X, then z (1.2).

    Applying diagonal method to that countable-infinite enumeration (1.2), we shall construct a new CDN, say, y3 and shall prove that:

{ B: }     this new CDN y3 X, but is not included in (1.2).

    Later, taking into consideration the infinity of (1.2), we shall build (construct) a new numerically infinite enumeration of the type:

    y3 , y2 , y1 , x1 , x2 , x3 , xn , ,         (1.3)

and prove that:

{B:}     for any z, if z X, then z (1.3).

and so on.

    It is obvious that Cantor's proof itself, turns, in that case, into the following unusual for classical logic "reasoning":

        A B B B B B . . .         (2)

    While doing this, it should be specially emphasized that in Nature there is neither logical, nor mathematical bases, reasons or other grounds to interrupt or to stop that uinfinite process (2). It is obvious as well that we shall not ever get any contradictions with the assumption A of Cantor's proof on the countablity of the initial enumeration (1), like with the countability of all subsequent enumerations. Taking into consideration the fact that, at each step of that potentially infinite process (2), a new real number, differing from all others already existing ones, is actually being built, we come to the following conclusions:

1. Cantor's "proof", in fact, contains a non-finite stage (2), i.e. this type of "reasoning" is not a mathematical proof in terms of D.Gilbert and, I add, in terms of classical mathematics.
2. Cantor's conclusion about uncountablity of the set X "jumps" through (over) the potentially infinite stage (2), i.e., Cantor's reasoning contains the fatal logical mistake "the unproved basis foundation" (Jump to a <desired conclusion").
3. Cantor's "proof", in reality, proves, and strictly mathematically, the potential, i.e. not being completed in principle, nature of the set X of "all" real numbers. In other words, Cantor's "proof" proves strictly mathematically the fundamental principle of classical logic and classical mathematics: "Infinitum Actu Non Datur" (Aristotle).

REMARK 1. It is obvious that in a common case the application of CDM to the given enumeration (1) can generate an infinite set, say, Y of new (anti-)diagonal reals not belonging to the list (1). Then two variants are possible.

a) The set Y is countable. Then, by definition, all it's elements can be numbered in a counting sequence, for instance like this:

    y1 , y2 , y3 , yn , ,         (3)

what means:

{ B:}     for any CDN y from Y: y X, but this CDN is not included in the enumeration (1).

    However, using the very popular "transfinite cavitation" method by G.Cantor [6], two countable sequences (1) and (3) can be written in the form of one countable sequence, for instance, like this:

    x1, y1 , x2, y2, x3 , y3 , xn , yn , ,         (3.1)

and consequently,

{ B:}     for any z, if z X, then z (3.1).

    Thus, we have again eliminated the contradiction between B and B without contradicting the assumption A about the countablity of the enumerations (1), (3.1), etc. And we have again gone to the potentially infinite process (2).

b) The set Y is uncountable. But that (i.e. the possibility itself of talking about an uncountability of sets) still needs to be proved, naturally with the same Cantor's Theorem only. But in that case, we shall simply be returning to the beginning of the Cantor's proof in which the set X ought to be changed with the set Y, i.e. again arriving to empty, infinite tautology of the (2) type.
    Thus, using any number system with a base 2, by virtue of well known properties of infinite sets, does not change anything, i.e. arriving to the same conclusions 1-3.

REMARK 2. Using the second popular version of Cantor's proof by assuming the existence of a 1-1-correspondence between infinite set, say U, and the set, P(U), of all its subsets (see for instance Hausdorff F., Theory of Sets. M.-L.: ONTI, 1937, p. 33-34) equally does not change anything, i.e. arriving to the same conclusions 1-3. As both proof versions, from the point of view of the model theory, are isomorphic (see P.S. Aleksandrov, Introduction to General Theory of Sets and Functions. - M. L.: Gostehizdat, 1948, p. 412)


* * *

    For the sake of a historical fairness, it is appropriate to add, that the famous Thesis by Aristotle "Infinitum Actu Non Datur", i.e. a statement on the impossibility of the existence (i.e. about the internal contradiction of the concept) of logical or mathematical (i.e. only conceivable and not naturally existing) actually infinite objects, was shared and supported, - in the course of the last 2300 years, - by such Aristotle's great like-minded person as Leibnis, Cauchy, Gauss, Kant, Kronecker, Poincare, Brouwer, Weyl, Luzin, and many other outstanding creators of classical logic and modern classical mathematics as a whole!
    Each of them was professionally studying (researching) the problem of mathematical infinity, and there can be no doubt about the fact that they understood the real Nature of the Infinity no less than G.Cantor. This is especially so if the basic importance of the fact that infinity as such does not depend on a progress and "technological" equipment of science, since it was never and will never become an object of instrumental researches - since even all conceivable computers together, can never complete the enumeration of all elements of the natural numbers series 1,2,3, It is exactly for this reason that all discussions about the impossibility of actual infinity in the course of two millenniums and up to Cantor was speculative in nature, did not depend on the obvious (in all other relations) progress of science. It is only proved contradiction of consequences, arising from the concept of actual infinity, could become the "last argument" against using that concept in science. But for that to happen, the discussion on the actual infinity needs to overstep the limits of speculative reasonings, based on pure subjective speculative preferences, and to come in the area of argumentation, which is accessible for a strict logical analysis.
    In that sense, the doubtless merit of Cantor is in the fact that, he first, from more or less substantiated reasonings about the possibility or impossibility of the actual infinity came over to its explicit, operational usage within the framework of classical logic and classical mathematics, and, by so doing, he, for the first time, made accessible the results of such the "mathematical" (see above) usage of the actual infinity conception for standardized methods of logical and mathematical analysis. It is exactly this type of analysis of logical aspects of Cantor's proof of the uncountablity theorem, - which is more than corner stone of the whole Cantor's "transfinite doctrine" and of all modern meta-mathematics, - carried out above, shows that the major assumption of Cantor's proof as to the actual infinity of the enumeration (1) leads to non-finite contradiction (2), which has no relation to Reduction ad Absurdum method, while Cantor's theorem itself about the uncountablity is simply wrong, from the point of view of Aristotle's classical logic.
    Why was such the analysis of Cantor's theorem not carried out in time, i.e. at the end of the XIX Century? - This, according to Zigmund Freud, is a very non-trivial topic for fundamental researched in the field of "psycho-pathology of an ordinary (scientific) consciousness".
    Full analysis of other logical mistakes of Cantor's proof of the theorem of the uncountable sets existence is contained in works [1-7].


1. A.A.Zenkin, New paradox of Cantor's Set Theory. International Conference "V.A.Smirnov's Readings" (Smirnovskije Chtenija), Moscow, 18-20 March, 1997. Section 1. Symbolic Logic. Abstracts, pp 17-18.
2. A.A.Zenkin, The Time-Sharing Principle and Analysis of One Class of Quasi-Finite Reliable Reasonings (with G.Cantor's Theorem on the Uncountability as an Example) - Doklady Mathematics, vol 56, No. 2, pp. 763-765 (1997). Translated from Doklady Akademii Nauk, Vol 356, No. 6, pp. 733 - 735.(1997).
3. A.A.Zenkin, Cognitive Visualization of some transfinite objects of the Classical Cantor Set Theory. - In the Collection "Infinity in Mathematics: Philosophical and Historical Aspects", Edr. Prof. A.G.Barabashev. - Moscow: "Janus-K", 1997, pp. 77-91, 92-96, 184-189, 221-224.
4. A.A.Zenkin, On Logic of Some Quasi-Finite Reasonings of Set Theory and Meta-Mathematics. New Paradox of Cantor's Set theory. - News of Artificial Intelligence, 1997, no.1, 64-98, 156-160.
5. A.A.Zenkin, Automated Classification of Logical and Mathematical Paradoxes. On one "Physical" Model of the "Liar" Paradox. - News of Artificial Intelligence, 1997, no. 3, pp. 69-79.
6. A.A.Zenkin, Whether the Lord exists in G.Cantors Transfinite Paradise? News of Artificial Intelligence, 1997, No. 1, . 156-160.
7. A.A.Zenkin, Transfinite Cavitation in the Ranks of G.Cantor's Ordinals. - News of Artificial Intelligence, 1997, no. 3, pp. 131-137.


= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

Prof. Alexander A. Zenkin,
Doctor of Physical and Mathematical Sciences,
Leading Research Scientist of the Computing Center
of the Russian Academy of Sciences,
Member of the AI-Association and the Philosophical Society of the Russia,
Full-Member of the International Union of Artists.
e-mail: alexzen@com2com.ru
WEB-Site http://www.com2com.ru/alexzen

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

"Infinitum Actu Non Datur" - Aristotle.

"Drawing is a very useful tool against the uncertainty of words" - Leibniz.