20th Century Mathematics

sowa <sowa@turing.pacss.binghamton.edu>
Reply-To: cg@cs.umn.edu
Date: Sun, 2 May 93 11:01:59 EDT
From: sowa <sowa@turing.pacss.binghamton.edu>
Message-id: <9305021501.AA01600@turing.pacss.binghamton.edu>
To: cg@cs.umn.edu, interlingua@isi.edu, phayes@cs.uiuc.edu
Subject: 20th Century Mathematics
Cc: sowa@turing.pacss.binghamton.edu

I reread your note that had the 80+ character lines clipped, and
most of the topics seem to have been addressed in our other notes.
There is one issue that seems to keep coming up that I would like
to clarify:  You keep saying that I "reject all of 20th century
mathematics."  That is not true.  There is only one aspect about
which I am extremely skeptical, and that is Georg Cantor's so-called
"proof" of the existence of uncountable sets.  This so-called proof
hangs on one slender thread, namely Cantor's diagonal construction. 

A lot of other people have also been skeptical about that "proof",
including Alfred North Whitehead, who was by no means an intuitionist.
He made the point that when you have a proof by contradiction, the
most you can conclude is that somewhere among all your assumptions,
there does indeed exist a contradiction.  But the proof has no way of
telling you which of those assumptions happened to be wrong.  Whitehead
was willing to use a proof by contradiction, but only in cases where
the entire subject matter was well established, the consistency of the
axioms was either proved (or as in the case of much of mathematics
so well used and applied that its consistency was never in doubt),
and there was exactly one assumption whose truth was doubtful.

That is essentially my position.  I am not an intuitionist, and I am
willing to accept classical first-order logic, including proofs by
contradiction -- but with all the caveats that Whitehead noted.
I am also willing to accept all the techniques and results of 20th
century mathematics, except for one:  anything that critically depends
for its existence on Cantor's diagonal "proof".

To see why I don't accept that "proof", let me give a brief summary of
the underlying assumptions:

 1. If two infinite sets cannot be put in a one-to-one correspondence,
    one of them must be larger than the other.

 2. If a set could be placed in a one-to-one correspondence with the
    integers, then it should be possible to list all pairs in that
    correspondence in a long table.
 3. If such a table could be constructed for pairing the integers
    with the reals, then it should be possible to go along the 
    diagonal of the expansion of the real numbers in some representation,
    say as unending decimal fractions, to select the first digit from
    the first one, the second digit from the second one, etc.

 4. Then the sequence of digits so selected would correspond to the
    representation of some real number x, which may or may not be on
    the list.

 5. But it would be possible to generate another real number x' by
    changing each digit of x to some other digit.  That new number x'
    could not be on the list assumed by assumption #2, since for each
    integer n, x' would differ from the real number paired with n
    because its n-th digit would be different.

 6. Therefore, x' would be a real number not on the list assumed by #2.

I will certainly admit that this is a very clever construction, and I
will also admit that somewhere among these six assumptions there lies
a contradiction.  But which assumption or assumptions should be changed?
The first assumption sounds rather plausible, but there are so many
counterintuitive cases in the whole field, that nothing should really
be considered "intuitively obvious".  The fact that you can find a
one-to-one correspondence between the integers and the rationals is
very odd.  Even odder is the possibility of a one-to-one correspondence
between the points on a line and the points on a plane.  In measure
theory (a 20th century development that I am willing to accept),
a line on a plane has measure zero, yet Cantor claimed that they
both have the same number of points.  All these results are so
counterintuitive that even assumption #1, as "obvious" as it sounds,
is not above suspicion.

Then the assumptions #2, #3, #4, and #5 are the same basic constructions
that Turing used to show the existence of noncomputable functions.  I am
quite happy to believe Turing's result that there are many functions
that cannot be computed -- even though they are countable (i.e. subsets
of the pairs of integers).  But this result makes me even more suspicious
of Cantor's claim.  I would be willing to believe that the real number x'
in assumption #4 above or the list of pairs of integers & reals in assumption
#3 are examples of noncomputable things.  But there is a world of difference
between Turing's noncomputable (but countable) and Cantor's claim of

One further point that casts further doubt on Cantor's claim is
the Loewenheim-Skolem theorem, which says that for any finitely
axiomatizable theory, there must exist a countable model.  This says
that even for Cantor's axioms, from which he supposedly "proved"
the existence of uncountable sets, there must exist a countable model.
This is one further point that makes me extremely suspicious of any
claim that the diagonal proof shows the existence of uncountable sets.

If Cantor had simply said that the whole field of infinite sets is
rife with noncomputable functions and nonconstructive definitions, 
then I would certainly agree.  What I don't accept is the conclusion
that THEREFORE there must exist uncountable sets.

As far as the Knowledge Sharing Effort or the ANSI standards, I am
perfectly willing to let people use either KIF or CGs to state any
kind of nonsense they please, including axioms for "uncountable" sets.
But I don't want to let anything in the foundations of either KIF or
CGs depend on any assumptions of their existence.

So to allay your fears that I will prevent you from talking about
uncountables, I assure you that you can translate all your dubious
axioms into CGs or KIF and share them with anyone else who has your
taste for such nonsense.