# Defeating Russell's paradox

I am not very big in mathematics yet(will be hopefully), naive set theory has a problem with Russell's paradox, how do they defeat this sort of problem in mathematics? Is there a greater form of set theory than naive set theory that beats this problem? (Maybe something like superposition if is both or neither)?

• The best way to defeat something is to not face it. – Adhvaitha Nov 23 '14 at 1:33
• so it is ignored? There is nothing that can be done? – beginner Nov 23 '14 at 1:33
• The way it is done is by avoiding unrestricted comprehension as part of axioms of set theory. I am sure @AsafKaragila or someone more qualified in set theory can give a detailed explanation. – Adhvaitha Nov 23 '14 at 1:40
• @beginner they don't ignore it, they avoid making the mistake that brings us into contact with it. – rschwieb Nov 23 '14 at 15:22
• @beginner, fyi: I remember at least Goldblatt in Topoi and Awodey in Category Theory mention Russell paradox in relation to categories, so it is not just a problem in set theory. – alancalvitti Nov 23 '14 at 17:48

The Zermelo-Fraenkel Axioms for set theory were developed in response.

The key axiom which obviates Russell's Paradox is the Axiom of Specification, which, roughly, allows new sets to be built based on a predicate (condition), but only quantified over some set.

That is, for some predicate $p(x)$ and a set $A$ the set

$\{x \in A : p(x)\}$

exists by the axiom, but constructions of the form:

$\{x : p(x) \}$

(not quantified over any set) are not allowed.

Thus the contradictory set $\{x : x \not\in x\}$ is not allowed. If you consider $S = \{x \in A: x \not\in x\}$, there's no contradiction. The same logic as in Russell's paradox gives us that $S \not\in S$, but then the conclusion is simply that $S \not\in A$, instead of any contradiction.

There are other problems with Russell's program which led to Gödel's work, which is also something you should check out, but ZF is where Russell's Paradox was fixed.

• As a side note, because of what aes said there are some parts of modern mathematics (prominently category theory) where the need arises to talk about things that cannot be ZF sets. They are called proper classes, are not formalized in ZF, and examples are the class of sets, the class of groups, etc. – Fra Nov 23 '14 at 3:17
• I am trying to understand this answer, so with the Zermelo-Fraenkel axioms, we do $\{x\in A: p(x)\}$, which in words means we are creating a set of elements in $A$ such that $p(x)$ is holds. Whereas in the other one we do a set of elements of $x$ in general, such that $p(x)$ holds. So the old form is $x\in \text{universal}$ such that $p(x)$ holds? – beginner Nov 23 '14 at 3:34
• @beginner Exactly. When you take the set of elements such that p(x), you need to specify which set you're looking in. – aes Nov 23 '14 at 3:45
• And, just to make this explicit, there's no universal set in ZF. As Fra alluded to above, if you really want to talk about all of something, there's a different term for that (a class), and you can't treat it as a set. (A class is basically just a term for talking about such things.) – aes Nov 23 '14 at 4:04
• I believe this answer is missing the important point that sets (and their existence) is built up from construction around an atom, usually the empty set. Otherwise it just changes the question to "does Russell's set exist in the Universal set". – DanielV Nov 23 '14 at 5:34

I'm aware of two principal approaches to solving Russell's paradox:

One is to reject $x \not\in x$ as a formula. This is what Russell himself did with his theory of types: inhabitants on the universe are indexed with natural numbers (types), and $x \in y$ is only a valid formula if the type of $y$ is one greater than the type of $x$. Basically, this slices the universe into "elements", "sets of elements", "sets of sets of elements", etc, and then there is no slice that admits a concept of membership of itself.

One drawback of this approach is that we then have, e.g. many empty sets of different types. Sometimes this is addressed by introducing type-shifting automorphisms, so that you can somehow recognise that the empty sets are all really the same. Another approach is to say that comprehension formulae are permitted only if you could give types to the variables, but you don't actually have to do so – this is the basis of Quine's New Foundations set theory. NF even has a universal set, but still manages to avoid Russell messing things up. This actually leads to a slightly odd situation where in NF the universal set $V$ actually does satisfy $V \in V$, and does not satisfy $V \not\in V$, so we don't forbid this kind of consideration entirely, it's just not permitted when building sets by comprehension.

The other main approach is to permit $x \not\in x$, but reject the formation of the set $\{x : x\not\in x\}$. Some argued that this set is problematic because it is in some sense far too large, a substantial slice of the whole universe – if we only stuck to sensible things like $\mathbb N$ and $\mathbb R$ and $\aleph_\omega$ then everything would be fine. Zermelo–Fraenkel set theory (ZF) proposed to build sets by more concrete means: start with things you know are sets, like the empty set, and operations that you know make sets, like union and power set, and just keep applying those operations, and take all the sets you can prove to exist in this way. ZF only allows selection of subsets of existing sets by arbitrary properties, that is $\{x \in A : p(x) \}$ instead of the more general comprehension $\{x : p(x)\}$ that ruined everything.

As a sidenote, ZF actually includes the Axiom of Foundation, which implies that $x\not\in x$ is true for all $x$. But there are also theories like ZF but without Foundation in which some $x$ do contain themselves.

• ZF needs also the Replacement Axiom, which allows selections from “classes” that are not necessarily sets. This is more technical, though, and doesn't invalidate your nice answer. – egreg Nov 23 '14 at 14:39

It lead to the development of a number of solutions in logic and set theory, as well as other insights. You can find a nice introduction to the topic in the Stanford Encyclopedia of Philosophy section on Russell's Paradox in Contemporary Logic.

• i am reading this now thank you – beginner Nov 24 '14 at 0:12

To the best of my knowledge, the Theory of Types http://en.wikipedia.org/wiki/Type_theory , was designed specifically to address this.

Basically you restrict the objects you can refer to , by the choice of types.

• My understanding is that type theory was a bit of a dead-end in mathematics, though the ideas are now very useful in computer science. – David Richerby Nov 24 '14 at 10:36
• Russell's Theory of Types has hardly any connection with computer science type theory. The names make them sound related, but they are not. – MJD Dec 7 '14 at 6:05

Another way of escaping from Russell's paradox, not yet mentioned in the answers here, is Morse-Kelley set theory. In MK set theory, there are good collections (sets) and bad collections (classes) and only the good collections (sets) are allowed to be members; unless $$x$$ is a set, $$x\notin y$$ holds for all $$y$$.

Suppose $$\Phi$$ is some property. In naïve set theory, you can construct $$\{x\mid \Phi(x)\}$$ the set of all $$x$$ with property $$\Phi$$; this is the principle that causes the trouble of Russell's paradox. In ZF set theory, this unrestricted comprehension is forbidden; all you can have is $$\{x\in S\mid \Phi(x)\}$$ which is the subset of $$S$$ for which $$\Phi$$ holds. MK goes a different way. $$\{x\mid \Phi(x)\}$$ is allowed, but it only represents the class of all sets $$x$$ with property $$\Phi$$. That is, it is the collection of all $$x$$ such that $$x$$ has property $$\Phi$$ and $$x$$ is a set.

Now take $$\Phi(x) = “x\notin x”$$ and let $$S = \{x\mid x\notin x\}$$. In naïve set theory we have $$S\in S$$ if and only if $$S\notin S$$, which is absurd. But in MK set theory we have $$S\in S$$ if and only if $$S\notin S$$ and $$S$$ is a set. There's no contradiction here; we've merely proved that $$S$$ is not a set. Since $$S$$ is not a set, it is not allowed to be a member of any collection, so $$S\notin T$$ is true for all $$T$$, and in particular $$S\notin S$$. Everything is fine.

In MK set theory one can also construct a universal class $$V$$ which contains all sets—but $$V$$ is not itself a set and is not a member of itself.

The way around Russell's paradox which Georg Cantor chose (and if you read Russell's letter describing the paradox to Frege, who fell into it, so to speak--this is found on pp 124-5 of van Heijenoort's book "From Frege to Goedel: A Source Book in Mathematical Logic, 1879-1931"--you find that Russell held that his paradox showed "that under certain circumstances a definable collection [Menge--(the German word for set, my comment)] does not form a totality", and therefore falls into Cantor's means of avoiding the set-theoretical paradoxes (there are others, namely Cantor's, Burali-Forti's, and Curry's paradoxes)) is this: you can divide the notion of 'collection' into those collections that form a consistent, completed totality (these are the sets), and those which do not (these are called proper classes). You might consider reading Penelope Maddy's paper "Proper Classes" (Journal of Symbolic Logic, Volume 48, Number 1, March 1983, pp. 113-139, although I found a pdf file of it on the Web, look for it using author and title) as an introduction.

You might also want to look at my mathstackexchange question (867626) "A Question Regarding Consistent Fragments of Naive (Ideal) Set Theory". In the comments section you will find a link to a paper titled "Maximal consistent sets of naive comprehension" by Luca Incurvati and Julien Murzi. You asked "how do they defeat this sort of problem in mathematics?". Incurvati's and Murzi's paper show that even though one has maximal consistent fragments of naive Comprehension (call it COMP, the axiom that gets one in trouble with Russell's paradox) there will be incompatible maximal consistent sets of naive Comprehension, that is, there exists in COMP (in a first-order language (V,$\in$) the axiom COMP, i.e. ($\exists$y)(x)(x$\in$y iff $\phi$(x)) is an axiom schema, that is, a collection of first-order sentences with distinct first-order formulae $\phi$) two maximally consistent subcollections of COMP, $COMP_1$ and $COMP_2$ such that there exists a first-order formula $\psi$(x) such that $\psi$(x)$\in$$COMP_1 and \lnot$$\psi$(x)$\in$$COMP_2$ so even if you rid yourself of the problem caused by Russell's paradox, you still have for Naive Set Theory another sort of inconsistency--that caused by the independence results.

Finally, you might want to look at Cantor's letter to Dedekind (in van Heijenoort, pp. 113-117). There he discusses the distinction between "consistent multiplicities [sets]" and "inconsistent multiplicities [now called proper classes]" and also discusses Cantor's Paradox, and discovers the Burali-Forti paradox (in fact, in that letter, Cantor shows (pg. 115 of van Heijenoort) that the collection $\Omega$ of all ordinals "is an inconsistent, absolutely infinite multiplicity" and therefore not a set).

Suppose there exists a set $r$ such that, for any object $x$, $x\in r$ if and only if $x\notin x$. This leads to the obvious contradiction that $r\in r$ if and only if $r\notin r$. Therefore, no such set can exist. This is only a problem if, as in naive set theory, such a set must exist simply because you can define it. So, a consistent set theory cannot allow such a set to exist. The widely used Zermelo-Fraenkel axioms of set theory have been particularly successful in this regard. After over a century of intensive scrutiny, no such contradictions have been shown to arise from these axioms.

They build set thoery on axioms, as ZF or ZFC, and then prove (if possible) that there would be no contradiction inside the builded theory (read on Godel 193?, and Cohen 1963).

• The work you are referring to dealt with AC and (G)CH, and not consistency of ZF. – André Nicolas Nov 23 '14 at 1:50

Russell's paradox is based on the naive assumption that the set of all sets does exist. They defeat it with the opposite assumption, that the set of all sets does not exist. Sets are instead "built" starting from the empty set, and step by step, being careful not to build too big sets in a single step. Certain axioms are introduced, e.g. pairs, power set, replacement, comprehension, which allow one to form a new set, based on old sets, and restrict the formation of sets defined just by "a property". Thus, the property of a set being a member (or not being a member) of itself is not allowed to be the defining property for a new set. But, for any given set $A$ one may form the set $B=\{a\in A: a$ is not a member of itself$\}$. Then $B$ is a set, but $B$ need not be an element of $A$ so even if $B$ is not a member if itself,the definition of $B$ would not imply that $B$ is a member of itself, which formally resolves the paradox.

• No, Russell's paradox is based on the naive assumption that every property defines a set. In particular this assumption means that there is a set of all sets, since "$x$ is a set" is an example of such property. – Asaf Karagila Nov 23 '14 at 11:05
• Because the Russell paradox is not based on the assumption that the set of all sets exists. If so, why doesn't it appear in Quine's New Foundations where there is a set of all sets? – Asaf Karagila Nov 23 '14 at 15:29
• Your answer hints that this is the basis for the paradox. It is not. It has nothing to do with the paradox, as shown by the fact that there are axiomatic set theories in which there is a universal set. If you meant something else, please write you meant. – Asaf Karagila Nov 23 '14 at 15:49
• @Asaf you may read and see "hints" in my answer as you wish. Show me an axiomatic set theory in which there is no universal set, yet there is Russell's paradox. – Mirko Nov 23 '14 at 15:58
• You are reading my comments backwards. Your answer begins with the sentence "Russell's paradox is based on the naive assumption that the set of all sets does exist.", and this means that if a set theory has a universal set, then it will be susceptible to Russell's paradox. I am just saying that this is not true, and that this first sentence is very misleading. There are set theories which have universal sets, but Russell's paradox fail there. I'm not quite sure what else to say about that, since you seem to ignore my comment and read them otherwise, so I'll stop now. Have a nice day! – Asaf Karagila Nov 23 '14 at 16:06

Most set theories solve this problem by giving up on unlimited comprehension. Unlimited comprehension posits the existence of "a set of all sets such that..." where you can state any clear criterion that talks about sets and their membership. Unlimited comprehension gives you the set of all sets, and also a set of all sets that aren't a member of themselves. Giving up on unlimited comprehension is a smart thing to do, because the combination of unlimited comprehension and classical two valued logic (true versus not true) gives you Russell's Paradox.

Several such approaches are well covered in excellent sister answers.

There is however also another way out - or there at least might be. Keep unlimited comprehension. Throw away the classical logic instead. Suppose we adopt a multi-valued logic where a truth value can be true ($1$), false ($0$), or anything in between, such as one half. Suppose that the negation of a statement whose truth value is $1\over 2$ is also $1\over 2$. (This isn't the only way to define negation over partial truths, but we need to pick one.) Instead of classical sets we now have fuzzy sets where membership is a matter of degree. Can we have a set of all sets that do not contain themselves? Yes, we can. The big question: Does this set contain itself? Answer: $1\over 2$.

As you can see, this isn't exactly a superposition of the big question being answered by both $0$ and $1$, but it comes close.