The Russell Paradox

$\text{[math]}$

Set theory is formulated on the postulate that there is a fundamental relation $\displaystyle \in$ , which is a function of two variables, that will return either TRUE or FALSE. It is important to realise that there is no definition of what $\displaystyle \in$ is, or for that matter what ‘elements’ and ‘sets’ are. Instead we have 9 axioms that speak of $\displaystyle \in$ , ‘elements’ and ‘sets’, and this produces the set theory on which all of modern mathematics is built.

‘Elements’ and ‘Sets’

We intuitively think of elements as things which are in sets. It is natural to think that a set has some property, $\displaystyle P$ , which is either true or false for a given element. If $\displaystyle P( x)$ is true for element $\displaystyle x$ , then the element is a member of that set.

When you see $\displaystyle x\in y$ in your A-level maths textbook, you informally read it as $\displaystyle x$ is an element of $\displaystyle y$ , $\displaystyle x$ belongs to the set $\displaystyle y$ , etc. It simply means $\displaystyle x$ has the property $\displaystyle P$ which determines if it is a member of $\displaystyle y$ .

We use curly brackets, $\displaystyle \{$ … $\displaystyle \}$ , around a list of objects to signify the set of all those objects. For example $\displaystyle \{2,5,8,9\}$ is the set with elements $\displaystyle 2,\ 5,\ 8$ and $\displaystyle 9$ .

Instead of listing the elements inside curly brackets, we can specify a set by the property which determines if an element is in the set. For example, let’s say we want to have a set $\displaystyle Y$ which contains all the integers from $\displaystyle 1$ to $\displaystyle 9$ . The property is “true if an integer from 1 and 9”. We could write it in the following ways,

$\displaystyle Y=\{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9\}$

$\displaystyle Y=\{x\in \mathbb{Z} \ :\ 1\leq x\leq 9\}$

$\displaystyle Y=\{x\ :\ x\ \mathrm{is\ an\ integer\ betweeen\ 1\ and\ 9\ inclusive}\}$

which all mean the same thing.

In general we write,

$\displaystyle \{x\ :\ x\ \mathrm{has\ property\ P}\}$

for the set of all $\displaystyle x$ such that $\displaystyle x$ has property $\displaystyle P$ (some property which may or may not be true for a given $\displaystyle x$ ).

The colon ‘:’ is equivalent to ‘such that’.

You might also see $\displaystyle x\notin y$ , and you can read that as $\displaystyle x$ is not an element of $\displaystyle y$ .

Just from the fundamental postulate we can define,

$\begin{equation*} x\notin y\ :\Leftrightarrow \ \neg ( x\in y) \end{equation*}$

using the negation symbol $\displaystyle \neg$ .

We can also define a subset,

$\begin{equation*} x\subseteq y\ :\Leftrightarrow \ \forall a:\ ( a\in x\Rightarrow a\in y) \end{equation*}$

That is, $\displaystyle x$ is a subset of $\displaystyle y$ if and only if all elements of $\displaystyle x$ are also elements of $\displaystyle y$ .

Equality of sets can also be defined,

$\begin{equation*} x=y\ :\Leftrightarrow \ ( x\subseteq y) \ \land \ ( y\subseteq x) \end{equation*}$

Is it really straightforward?

We might naively think this is all there is to ‘sets’ and ‘elements’. So far everything seems to be logically sound. But let’s take a closer look at $\displaystyle \{x\ :\ x\ \mathrm{has\ property\ P}\}$

Let’s construct the following set,

$\begin{equation*} R=\{x\ :\ x\notin x\} \end{equation*}$

That is, $\displaystyle x$ is in the set $\displaystyle R$ if it is not an element of itself. It seems logically fine, until we ask ourselves if $\displaystyle R$ belongs to itself. This leads to something very worrying.

Let’s take the case that $\displaystyle R$ is an element of itself. In order for that to be true, it must have the property that $\displaystyle R$ is not an element of itself! A contradiction!

$\begin{equation*} R\in R\ \Rightarrow \ R\notin R \end{equation*}$

Now take the case that $\displaystyle R$ is not an element of itself. That means that it does indeed have the property that puts it in the set. So, this means $\displaystyle R$ is an element of R. Another contradiction!

$\begin{equation*} R\notin R\ \Rightarrow \ R\in R \end{equation*}$

This contradiction is known as Russell’s paradox. British mathematician Bertrand Russell wrote a letter to Frege, just as Frege was about to publish his major work on set theory. The consequence of this paradox was highly alarming for Frege, who had nightmares of his life work being burned by every library in the country.

It is interesting to note, Russell’s paradox relies for the most part on our ability to make statements which refer to themselves. Such statements can be paradoxical in the sense that judging them as either true or false results in a contradiction. There exists a multitude of such paradoxical statements in everyday language, but even a logical mathematical construct like set theory can lead to paradoxes if we are not rigorous with our axioms. A consequence of Gödel’s incompleteness theorem means we still cannot prove that axiomatic set theory is free from contradictions.

Can you come up with another paradox in mathematics?