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

Richard Heck heck at fas.harvard.edu
Mon Aug 26 15:32:23 EDT 2002

```>
>
>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

```