[FOM] The uncountability of continuum. 1.
William Tait
wwtx at earthlink.net
Wed Mar 9 12:50:07 EST 2005
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
More information about the FOM
mailing list