FOM: Cantor's argument

[friedman@math.ohio-state.edu]

As far as I can tell, not a single issue has been raised about Cantor's 
Diagonal Argument in all of the many many postings about it on the FOM e-mail 
list. The general issue of the evolution of standard set theoretic notions has 
been addressed earlier by me (June 26, 2002) and more recently by Tait, and I 
suggest that the contributors to this list on this topic take these into 
account.

As I wrote earlier on the FOM, a particularly clean formulation is:

"every listing of sets of natural numbers omits a set of natural numbers".

If this is to be done competely formally, in a formal set theory, then one 
would naturally use all of the ZFC axioms except choice, replacement, powerset. 
One can just use intuitionistic logic. 

If one wants to be particularly minimalistic, then with some care, one could 
even omit the axiom of infinity and extensionality. The idea is that if the 
listing is infinite then we get the axiom of infinity, and if the listing is 
finite then we do not need the axiom of infinity to diagonalize. The natural 
way to make this work is to require that in every listing of anything, the 
domain of the listing (an initial segment of the natural numbers, possibly all 
of them) exists. 

The proof (by Cantor) is as follows. Let x0,x1,x2,... be a listing of sets of 
natural numbers. Then the set of natural numbers, {n: n notin xn}, is not on 
the list. 

"Arthur, Richard" <arthur at middlebury.edu> said:

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

The more abstract formulation that you are talking about says

"there is no one-one correspondence between the set M of all real numbers in 
[0,1] and the set N of all natural numbers".

There is no listing of M whatsoever in this formulation. In the proof (not the 
statement) one postulates such a listing in order to derive a contradiction and 
thereby complete the proof that there is none. 

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

This is wrong. The argument proves that there are more reals than naturals, 
period. (Here we are using "more" in the sense that has become standard in set 
theory). 
> 
> 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.

M is the set of all reals in [0,1], and there is no contradiction. A 
contradiction is generated under the needed assumption that M is in one-one 
correspondence with the set N.

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

No, M is the set of all reals in [0,1], and therefore not countable. Why? By 
Cantor. 

>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?

We get a contradiction from M being countable, and also M' and M'' do not exist 
(or if you set it up differently, they are simply M). This has nothing to do 
with N. In fact, N consists of all of the natural numbers.
 
> Whether the alternative formulations of the diagonal argument that have been
> offered on this list escape these antinomies is beyond my capacity to
> determine. 

What antinomies? One is not even close to any paradox in this discussion and 
any of the earlier discussions.