FOM: Cantor's Diagonal Argument

[Arthur, Richard]

Diagonalization

What I am about to say will no doubt bring the Wrath of Fom down on my head,
but I hope to learn from the responses. It is on the issues raised by Dean
Buckner in this forum. My remarks are made from the point of view of Leibniz
(I am currently exploring whether there is a viable Leibnizian alternative
to standard Cantorian set theory.)

John Goodrick writes:
Roughly speaking, if one assumes that there are infinite sets and that for
every set, the collection of all its subsets is also a set, plus maybe a few
other basic things, then one must conclude that there are infinite sets
whose elements cannot all be listed by the set of natural numbers.

This first assumption, that there are infinite sets, whilst obviously
natural for a set theorist, is perhaps not as innocent as it might seem.
What if, like Leibniz, one does not accept the existence of infinite sets?
On this view it is granted that one can attribute things universally to
numbers or other objects, provided the "all" in (x)Px is interpreted
distributively and not collectively. But it is denied that an infinity of
things can be treated as a whole or totality without contradiction.

Leibniz proposed this position as the best way of avoiding the contradiction
in Galileo's Paradox: if there are just as many squares as [natural]
numbers,  and there is such a thing as the set of all numbers (and the set
of all squares), then the part (proper subset, the set of all squares) is
equal to the whole (set of all naturals). As is well known, Cantor followed
Bolzano in rejecting the applicability of the part-whole axiom (i.e. that
every set is greater than its proper subset) to infinite sets (which can be
defined in terms of their _not_ obeying it.)

Now Dean Buckner has raised questions about the adequacy of one-one
correspondence as a criterion for equality, in connection with De Morgan's
argument. From a Leibnizian perspective they can be expressed as follows.
1-1 correspondence is not sufficient for defining equality. We also need the
axiom that N includes all the natural numbers, and that S includes all the
squares. Otherwise one could claim that although every number has a
corresponding square, and every square a corresponding number (where the
"every" is distributive), this establishes nothing about the set or totality
of all numbers and its relation to the set or totality of all squares.

Similar implicit assumptions about totalities are made by Cantor in his
diagonal argument. It is necessary to assume not only that _all the reals_
in [0,1] are listed in some set M, but that in indexing these by natural
numbers, we set up a 1-1 correspondence between the elements of this set and
the elements of the set of _all the natural numbers_ N. Again, if this were
not so, it might be that there were other reals between 0 and 1 that were
not included in M, and when the antidiagonal element is formed, no
contradiction would be forthcoming. Again, if M did not list all the reals
and N all the naturals, then 1-1 correspondence with N, although it would
establish countability, would not establish that there were just as many in
M as in N. (Recall the discussion of Galileo's Paradox.) But once this
assumption is made explicit, and we diagonalize and derive a contradiction,
what can we now infer? The argument does not prove that there are more reals
than naturals unless the set M lists all the reals and N lists all the
naturals. But the assumption that M lists all the reals in [0,1] is
precisely what the diagonal argument disproves.

To recap: we assumed that M contains all the reals in [0,1]. If it doesn't,
nothing can be inferred about its totality or cardinal number. But if it
does, we get a contradiction; so it doesn't contain all the reals. So
nothing can be inferred about its cardinality, or how many elements it has.

This is enough. But I'll risk more. If we form another set M' from the
elements of M together with its antidiagonal, then we can easily put this
set in 1-1 correspondence with the naturals (Hilbert's Hotel). So this set,
like our original set M, is countable. But, also like M, it is susceptible
to another diagonal argument. Why should we not then conclude that M, M',
M'' etc. are all countable, but that none of them contains all the reals in
[0,1]? That being so, are we not compelled to infer that N, though
countable, does not contain all the natural numbers either?

Whether the alternative formulations of the diagonal argument that have been
offered on this list escape these antinomies is beyond my capacity to
determine. But if there is some very obvious error to my arguments given
above, I would be glad to hear it; and I will apologize in advance if I have
wasted anyone's time.

Richard Arthur