"INFINITUM ACTU NON DATUR" - ARISTOTLE
FATAL MISTAKE
OF GEORG CANTOR
by Alexander Zenkin
e-mail: alexzen@com2com.ru
.
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
x_{1}, x_{2}, x_{3}, … x_{n} , … (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, y_{1 }, - we shall call it Cantor's Diagonal Number (CDN), - such that by definition y_{1 }Î X, but by design y_{1} differs from each element of the enumeration (1), i.e. CDN y_{1 }does not belong to the enumeration (1). Consequently,
{Ø B:} y_{1 }Î X, but y_{1} 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, x_{11} x_{22 }x_{33 }… x_{nn }… , (*)
is used, i.e. the infinite sequence, where the digit x_{11} is the first binary digit of the first element x_{1} of the enumeration (1), the digit x_{22} is the second binary digit of the second element x_{2} of the enumeration (1), the digit x_{33} is the third binary digit of the third element x_{3} of the enumeration (1), etc. As was shown above, G.Cantor, using the diagonal (*), builds a new infinite binary sequence:
y_{1} = 0, y_{11 }y_{12 }y_{13 }… y_{1n }…, (**)
according to his famous diagonal rule:
for any i: [if x_{ii }= 0, then y_{1i }= 1] and [if x_{ii }= 1, then y_{1i }= 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 y_{1 }Î 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:
z_{1 }= 0, 0_{1 }0_{2 }0_{3 }… 0_{n }… , (**)
and apply the Cantor's diagonal rule to the enumeration (1) in the following form:
for any i: [if x_{ii }= 0, then 0_{i }= 1] and [if x_{ii }= 1, then 0_{i }= 0]. (***)
It is easy to see that, literally repeating Cantor's reasoning,
we will obtain, as a result, a real number z_{1}, which is different
from all elements of the enumeration (1), and identically coincides with Cantor's
real number y_{1}.
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,
x_{1 }, x_{2 }, x_{3}, … x_{n }, (1a)
we shall get a rational (even with the zero "tail") number:
z_{1} = 0, z_{11} z_{12 }z_{13 }… z_{1n }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 y_{1} 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 y_{1 }to the initial, countable-infinite enumeration (1), for instance, thus:
y_{1}, x_{1} , x_{2 }, x_{3 }, … x_{n }, … . (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 y_{2} such that
{Ø B: } the new y_{2 }ÎX, but this y_{2} is not included in (1.1).
But in that case a new countable-infinite enumeration, like this:
y_{2}, y_{1 }, x_{1} , x_{2 }, x_{3 }, … x_{n }, … . (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, y_{3} and shall prove that:
{Ø B: } this new CDN y_{3 }Î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:
y_{3} , y_{2 }, y_{1 }, x_{1 }, x_{2 }, x_{3 }, … x_{n }, … , (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:
y_{1 }, y_{2 }, y_{3 }, … y_{n }, … , (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:
x_{1}, y_{1 }, x_{2}, y_{2, }x_{3} , y_{3 }, … x_{n }, y_{n }, …, (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.Cantor’s 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.