FOM: Proper Names and the Diagonal Proof

[Richard Heck]

>
>
>...[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": 
We are actually shown the set that is omitted from the list. For more on 
this latter issue, see George Boolos's last published paper, 
"Constructing Cantorian Counterexamples". Regarding the former, one can 
prove, in *predicative second order logic*, that:
-(ER)(F)(Ex)(y)[Rxy <--> Fy].
Think of relations as one does in combinatorial logic: A relation is a 
function from objects to concepts (properties or whatever). Then what 
the above says, in effect, is that there is no function (of any kind) 
from objects to concepts that has every concept in its range. A 
fortiori, there is no one-one map from the objects onto the concepts.

To prove this claim, assume the contrary, that is:
(ER)(F)(Ex)(y)[Rxy <--> Fy].
Instantiating, we have, for some R,
(1) (F)(Ex)(y)[Rxy <--> Fy].
Now, by *predicative* comprehension:
(EG)(x)(Gx <--> -Rxx).
Instantiating, we have, for some G,
(2) (x)(Gx <--> -Rxx).
But now we use UI on (1), instantiating 'F' with 'G':
(Ex)(y)[Rxy <--> Gy]
And the end is near. For some x, then:
(y)[Rxy <--> Gy]
and so:
Rxx <--> Gx.
But that will obviously contradict (2).

Richard Heck