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

[Richard Heck]

>
>
>1.  Let f be a function, f: N -> S, from objects to sets of objects.
>Suppose f is "onto"
>2.  Suppose that there is a set M, of all objects satisfying "x is not in f(x)".
>3.  For some m, M = f(m) (since f is onto)
>4.  Forall x, x in f(x) iff x not in f(m)  (from 2)
>5.  Thus if m is in M, it is not in M, and if it is not in M, it is in M (instantiating m)
>
>Since (5) is a contradiction, it's standard to reject assumption (1): that there is such a mapping from things to sets of things.
>
>But why can't we reject assumption (2), that there really is a set of all numbers satisfying the predicate "x is not in f(x)"?
>
First of all, the argument here needs to be cleaned up a bit, in a way 
that matters. For the set-theoretic presentation of the argument, N 
needs to be a set and its range needs to be contained in P(N) = the set 
of subsets of N. [P(N) does not actually have to exist: We just need to 
know that, if x is in N, f(x) is a subset of N.]

Obviously, one could, in principle, reject (2). But the question is what 
else you would have to reject to reject it. In the standard 
presentation, (2) would be justified by an application of separation, 
which, roughly speaking, says that, if X is a set, and A(z) is some 
formula, then there is a subset of X consisting of just those objects 
satisfying A(z). In this case, we have our set N, and we have the 
formula "z is not in f(z)": M = {x: x is in N & x is not in f(x)}; 
separation then guarantees the existence of M. Separation is not 
typically taken to be a controversial axiom. It is especially 
uncontroversial when the formula involved is quantifier-free, as in this 
case.

The significance of this last remark is clearer if we formalize the 
argument a different way, namely in pure second-order logic. Let F be a 
"concept" (second-order whatzit). We will show that there is no 
"function" from the objects that satisfy F onto the "subconcepts" of F. 
By a subconcept of F, of course, we mean a concept G such that: (x)(Gx 
--> Fx).

To carry out this argument, we treat two-place relations as in 
combinatory logic, thinking of them as functions from objects to 
concepts: So if we have a relation ...R__ and fix the first argument as, 
say, a, then we are left with aR__, which we may think of as a concept, 
with '__' indicating the argument-place: aR__ is the "value" of the 
"function" R for argument a.

For there to be a function of the sort mentioned, then, would be for 
there to be a relation R such that, for each subconcept G of F, there is 
some x such that Fx where aR__ just is G. Formally:
    (ER)(G)[(x)(Gx --> Fx) --> (Ey)(Fy & (z)(Gz <--> yRz))].
What we show is that that cannot be so.

(One can carry the argument out with functions, instead of concepts, but 
I find it less clear, myself. In any event, we lose nothing by this 
presentation. The relation R may be defined from a function of the sort 
one would have in the set-theoretic presentation as follows: xRy <--> y 
is in f(x).)

We assume:
(1)    (ER)(G)[(x)(Gx --> Fx) --> (Ey)(Fy & (z)(Gz <--> yRz))]
By EI,
(2)    (G)[(x)(Gx --> Fx) --> (Ey)(Fy & (z)(Gz <--> yRz))]
By predicative comprehension,
(3)    (EH)(x)[Hx <--> -xRx & Fx]
EI gives us:
(4)    (x)[Hx <--> -xRx & Fx]
By UI on (2),
(5)    (x)(Hx --> Fx) --> (Ey)(Fy & (z)(Hz <--> yRz))
Clearly, the antecedent will be satisfied, in virtue of how we 
characterized H, so ignore it. Apply EI to the consequent:
(6)    Fa & (z)(Hz <--> aRz)
Detach the second conjunct, and apply UI:
(7)    Ha <--> aRa
But now (6) and (7) obviously contradict (4), once we apply UI to it:
(8)    Ha <--> -aRa & Fa
For we have Fa, from (6), so (8) simplifies to
(9)    Ha <--> -aRa,
directly contradicting (7). Discharging the EI steps, we can therefore 
conclude:
(9)    -(ER)(G)[(x)(Gx --> Fx) --> (Ey)(Fy & (z)(Gz <--> yRz))]
And that holds for any F.

The point of all the tedium is to make it plain that nothing remotely 
controversial is needed for this argument. The step here that 
corresponds to Dean's (2) is (3): But the instance of comprehension used 
here is /predicative/. And predicative comprehension is (as is familiar) 
very weak (the result of adding predicative comprehension to most (?) 
reasonable theories will be a conservative extension of the original 
theory); it can even be interpreted in substitutional terms.

There is no simpler set theory than predicative second-order logic. To 
reject even that much would be to reject all talk of sets. That makes 
Dean's way out pricey.

Richard Heck