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

Dean Buckner Dean.Buckner at
Sat Aug 24 08:30:29 EDT 2002

The thing above is the most crucial ingredient in what is possibly Cantor's
most famous argument.  But what is it?

The argument is very clean.  It's a piece of logic: no diagonals, real
numbers, nothing.  Just:

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
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)"?

It is still perfectly consistent to hold that there are an infinite number
of objects satisfying the predicate.  Just not a set of all objects
satisfying it.  What's wrong with that?

Dean Buckner

Work 020 7676 1750
Home 020 8788 4273

More information about the FOM mailing list