FOM: Proper Names and the Diagonal Proof

[William Tait]

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