[FOM] The uncountability of continuum. 1.

[William Tait]

The following, from Hendrik Boom is in response to Alexander Zenkin's 
posting about Cantor's two proofs (the 1874 proof by nested intervals 
and the 1890 one by the diagonal argument). Zenkin referred to the 
former as a direct proof and the latter as indirect.

> So constructively, a direct proof of the uncountability of the 
> continuum
> is a reduction ad absurdum.
>
> Is there another way to define uncountability?  Perhaps by defining it 
> as
> "Every countable enumeration leaves something out."  If you do that,
> there is an obvious direct proof.

  Yes, there is a constructive proof in Bishop-Bridges of the theorem 
that no function from the integers to the reals is onto. But also 
Cantor's proof that no function f from a set M to the totality of 
subsets of M is onto actually constructs a witness, namely C = {x in M 
| x not in f(x)}, and so deserves to be called direct, if not 
constructive. The proof that there is no c in M such that C = fc seems 
constructive: c  in C -> c not in C; and so
c not in C. Hence c in C. So the assumption that C is in the range of f 
leads to contradiction, so C witnesses the fact that there is a subset 
of M not in the range of f.

It may seem that the argument in the 1874 paper is more direct in that 
the witness real number is constructed step-by-step so that, at the nth 
step, it is determined not to be any of the first n members in the 
given enumeration of reals, whereas the diagonal argument is a 
specialization of a general argument that has a bit the  look of 
logical slight-of-hand. But applied to the case of M = the set of 
natural numbers, it can also be viewed as a step-by-step construction 
of the witness C such that, at the nth stage, the fact that C is not 
one of the first n sets in the given enumeration is already determined 
(by having altering the kth diagonal element for k <n).

Bill Tait