FOM: {n: n notin f(n)} ADDENDUM

Richard Heck heck at
Tue Aug 27 17:54:57 EDT 2002

Andrew Boucher pointed out what I believe to have been a mistake in my 
previous posting. I remarked there that, in the instance of separation 
one needs for Cantor's argument, the formula one needs is 
"quantifier-free". As Andrew notes, that does not appear to be true, at 
least in the most obvious way of formalizing the argument: The formula 
"n notin f(n)" hides a quantifier, because f is really an ordered pair. 
Maybe there is some trick that will reduce complexity here. I don't know.

On the other hand, the following is true: If have power set, then the 
quantifier in question can be bounded, and the formula in question will 
be delta-0. So rejecting Cantor's argument as Dean suggests means 
rejecting delta-0 instances of separation, which makes the set-theory 
quite weak, though not of course completely hopeless. One could still 
accept "open" instances.

So here's a very open-ended question: How much is known about such weak 
fragments of set-theory? Say, ZF, with separation limited to open, or 
delta-0, formulae? Any helpful references?


More information about the FOM mailing list