From: kramsay@aol.commangled (Keith Ramsay)
Subject: Re: Russell's 'paradox' not a paradox
Date: 07 Jun 2001 01:24:50 GMT
Newsgroups: sci.math
Summary: Quine's New Foundations development of set theory

I wrote:
|So the real question is whether it makes sense to call these things
|sets. I guess I'm not sure that they correspond to anything I'd ever
|called a "set" before, but there's no reason we can't consider these
|additional "sets" as objects of study.

In article <3b1b8e75.1667837@nntp.sprynet.com>,
ullrich@math.okstate.edu (David C. Ullrich) writes:
|Otoh it seems to me (???) that this has nothing to do with the
|set of all sets problem - nothing in the proof that that leads
|to a contradiction uses foundation, so "there cannot be a set
|of all sets" is still a theorem of ZF-foundation+antifoundation.

At some point someone should mention a version of set theory which
does imply the existence of a set of all sets: Quine's New Foundations
system (with or without ur-elements, NFU or NF respectively).

Russell's paradox shows that the naive assumption that for every
predicate P there exists a set {x : P(x)} leads to a contradiction.
Then we observe that if there existed a universal set and the
separation axiom (that for every set S and predicate P, there exists
a set {x: x \in S and P(x)}) held, then they would together lead to
the same contradiction. In ZF-foundation, this gives an argument
against the existence of a universal set, because ZF-foundation has
the separation axiom. In NF or NFU, however, we don't have the full
separation axiom; we have an axiom which says that {x: P(x)} exists
when P is given by a "stratified" formula. A formula is stratified if
we can assign integer indices to the variables in such a way that
"x is a member of y" appears only for a variable x whose index is one
less than the index of the variable y, and u=v appears only for
variables with the same index. (There exists a universal set because
x=x is stratified.)

There are alternative analyses of why Russell's paradox goes wrong.
One explanation is that the Russell "set" is "too big". If one accepts
that explanation, then the separation axiom seems quite OK, because
the new set that we are considering is no bigger than the set which
we're selecting it out of. One is left with possible lingering doubts
about the power set axiom because it produces a set which is possibly
much bigger than the given set.

Another explanation is that the essential problem is with circularity.
Sets of non-set objects seem okay. Sets of those sets seem okay. Sets
of those sets seem okay. And so on. But maybe our problem is that we
really should have "build up" from the ground floor, and here we go
speculatively proceeding as though we already had a universe of sets,
out of which we're then going to make a new one (!) but act like it
must have already been there. This could lead one to favor the axiom
of foundation, which implies under the usual assumptions that sets
come in ranks, the rank of a set being the smallest ordinal which is
greater than the ranks of all the members of the set. Or it could lead
one to favor predicativity. A predicative definition isn't allowed to
refer to sets of which the set being defined might be a member. For
instance, defining a real number with reference to the properties of
the real line isn't a predicative definition.

Assuming the axiom of foundation is also enough by itself to imply the
nonexistence of a universal set, and to someone who finds the
"circularity" explanation for what's wrong with the Russell set, this
probably seems intuitive. My impression is that most writers about
this kind of thing tend to regard these intuitions as also supporting
the axiom of separation, however, and that therefore there aren't
likely to be many people who accept the axiom of foundation, but have
qualms about the separation axiom.

The intuitions behind Quine's NF or NFU are not as popular, and I
don't remember anybody giving a ringing endorsement of them. I guess
I haven't ever looked for Quine's own explanation for "stratification".
It seems to me to have some general resemblance to the idea that sets
have to be considered in "levels".

I once read a constructivist explanation of the paradox. It hinged on
considering the meaning of statement of the form "x is a member of y".
On this view the problem is that we've taken such statements to be
meaningful in too much generality, as if they could be assumed to be
meaningful without a context. In other words, whether x is a member
of x isn't always necessarily a meaningful question.

There are ways in which one is tempted to try to make it into a
universal question. For instance, one is tempted to fix the meaning by
saying that in all cases where the question isn't meaningful, we'll
regard the answer as "false". This is a lot like the strengthening of
the liar paradox where we say

    (1) Statement #1 is either false or meaningless or a paradox.

and it seems to fail in about the same way.

There was a further discussion of the difference between sets and
pre-sets. A pre-set is constructed by saying what it takes to
construct a member. A set is constructed by further saying what it
takes for two members to be equal. The author comments on the
tendancy to assume that there's a universe on which there's a global
equality relation, and expresses doubts about that. I wish I could
remember offhand more of the details. If I remember correctly, the
author considered a universal pre-set OK, but since there's no
global equality relation, it doesn't amount to a universal set.

All that may seem curiously cautious, but I think in fact it was a
somewhat bold attempt at hanging onto the original intuition about
"classes" or "sets", that we ought to be able to refer to extensions
of concepts as a kind of object. You can't just take the concepts
for granted, though.

Keith Ramsay