FOM: Proper Names and the Diagonal Proof
William Tait
wwtx at uchicago.edu
Wed Jun 26 21:46:16 EDT 2002
At 1:33 PM -0400 6/26/02, Richard Heck wrote:
>>...[T]he modern version of Cantor's argument...is formalized in
>>Zermelo-Fraenkel set theory.... 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.
>The argument can actually be formalized using very limited
>resources, and there is a reasonable sense in which the argument is
>"constructive":
Cantor's Theorem is proved, using only a minor modification of
Cantor's original argument, in Bishop's _Foundations of Constructive
Analysis_, p. 25. (Curiously, Bishop writes that it is essentially
Cantor's ``diagonal proof''---which it isn't---it is C's original
proof.)
Bill Tait
More information about the FOM
mailing list