Self-studying Russell's Paradox

Question

I'm self-studying and having trouble wrapping my head around Russell's paradox, even after looking here. I'd really appreciate a more intuitive explanation of the concept before I move on to Zermelo-Fraenkel set theory.

From my notes, this is a good formalization of the paradox:

Let $R = \{x\ |\ x \notin x \}$, then $R \in R \iff R \notin R$

I also know there's a more intuitive way of explaining this with the "barber paradox," but I'm not yet connecting the two well enough. Any help is very appreciated.

Answer 1

I read this description of Russell's Paradox in a book once and can't remember which book it was now.

You are working in a library. Every book in the library is either fiction or nonfiction. You are given the job to create 4 card catalogs:

• Card catalog A lists all fiction books
• Card catalog B lists all nonfiction books
• Card catalog C lists all books which mention themselves
• Card catalog D lists all books which do not mention themselves

You make card catalog A with no problem. You make card catalog B and remember to have it include all the card catalogs, since they are nonfiction. You create card catalog C, but ask "should card catalog C list itself"? Whether you add it or not, it is no problem.

But then you get to card catalog D (CCD). Suppose you list CCD in CCD. But then it references itself, so you realize it shouldn't be listed. So you remove the reference. Now CCD doesn't list itself. So you realize it should be added. Etc.

The point is that there is no way to make card catalog D, because it either must reference itself or it must not. That is the intuition behind Russell's Paradox, they had assumed such a construction was possible.

Answer 2

For this to make sense you need to first recall that in [classical] mathematical reasoning a statement is either true or false (and not both). So if $R$ is a set, either $R\in R$ or $R\notin R$. One of these has to be true.

Next you need to remember that the idea behind "set" is to allow collections of mathematical objects to be mathematical objects on their own accord.

Now, Russell's paradox comes to show that the idea that if $\varphi(x)$ is a property (of $x$), then the collection $\{x\mid\varphi(x)\text{ is true}\}$ is a set. This is known as "comprehension".

So if $R=\{x\mid x\notin x\}$ was a set, then either $R\in R$ or $R\notin R$. But $R\in R$ if and only if it satisfies the property defining $R$, namely $R\notin R$. This is a contradiction, so $R$ cannot be a set. And therefore not every property defines a set.

Answer 3

In the following, I am trying to formulate Russell's paradox and the barber's paradox as close as possible. Therefore, we have some redundant notation.

First of all, look at the Barber's paradox and notice that the following equivalence holds in the barber's village and defines a set of people:

x is shaven by the barber $\iff$ x is not shaven by x

Then let C be the set of the barber's customers (or the people who are shaven by the barber), i.e. $C = \{x\ |\ x\ \text{is shaven by the barber}\}$ (1). By our equivalence, we have $C = \{x\ |\ x\ \text{is not shaven by}\ x\}$ (2).

As we believe that the barber is a person of his village, we might ask what happens to him. So, let $b$ denote the barber, then $b\ \text{is shaven by}\ b \iff b \in C$ by (1). Also, $b\ \text{is shaven by}\ b \iff b \notin C$, by (2). Thus, we have $b \in C \iff b \notin C$. Contradiction.

Now look at Russell's paradox where we define a set of sets just like above with an equivalence:

$x$ is in $R$ $\iff$ $x$ is not in $x$

or:

$x \in R \iff x \notin x$

Now let C be the set of x in R, i.e. $C = \{ x\ |\ x \in R \}$ (1). By our equivalence, we have $C = \{x\ |\ x \notin x \}$ (2).

As we believe that $R$ is a set, we might ask what happens to $R$. We have $R \in R \iff R \in C$, by (1). Also, $R \in R \iff R \notin C$, by (2). Thus, we have $R \in C \iff R \notin C$. Contradiction.