Set-builder notation and Russell’s paradox

There is way of representing sets, both small and extremely large, using what is called ‘set-builder notation’. Set-builder notation specifies sets according to some specifiable rule, which decides whether something is in a given set or not. An example is: $$S=\{x \mid x\text{ is a sheep}\}$$ What is specified above is that the set $S$ consists of all $x$ provided $x$ is a sheep. In other words, $S$ is the set of all sheep. On the right side, after the symbol ‘$\mid$’, the rule for belonging, or not belonging, to the set is given. Namely, for any object $x$ whatsoever, check if $x$ is a sheep. If it is, it belongs to the set. If not, it does not belong to the set.

Here is another example: $$Even=\{x\mid \text{there is an }n \in \mathbb{N}\text{ such that }n \times 2=x\}$$ Here, the test is a bit more involved. It says that something belongs to the set $Even$ provided you can find a natural number, $n$, and multiplying by $2$ you get $x$. If you think about it, only the even numbers will pass this test. First, every even number $x$ is such that you can find another number, $n$, and $n\times 2=x$. For example, $6$ is an even number, and there is another number, $3$, such that $3 \times 2=6$. On the other hand, something like $13$ will not pass the test, since there is no natural number $n$ such that $n\times 2=13$. This is because $13/2=6.5$, and $6.5$ is not a natural number.

Interestingly, the set $Even$ is, of course, infinite, but what the set-builder notation allows us to do is specify it precisely, in a finite manner, without relying on murky notation like the dots ‘$…$’ above, which only implies that we can ‘go on’ indefinitely with listing our input-output pairs.

In fact, you can consider more extreme circumstances, like sheep. Take, for example, the famous cloned sheep Dolly. Is there a natural number $n$ such that $n \times 2=Dolly$? Clearly, there is no such number, so Dolly is also not in $Even$.

Russell’s paradox

At the inception of modern set theory, it was thought that every specifiable collection of things constitutes a set. That is, given any rule $R$, the following always gives you a set: $$S=\{x \mid x \text{ passes }R\}$$

However, it was quickly discovered that this will not do, since not just any specifiable collection of things is a set. How could this be? The reason for this is usually attributed to Bertrand Russell, a philosopher-logician-mathematician (yet another one!), and one of the most important intellectuals of the 20$^\text{th}$ century. Hence the name ‘Russell’s paradox’.

Let’s start from the beginning. As we said, some sets can be members of other sets. For example, regarding the set $S=\{\{1, 4, 2\}, 3, 6\}$, the set $\{1, 4, 2\}$ is in $S$. But if anything specifiable is a set, we may get some pretty weird stuff. Consider a set, $S$, and ask whether $S$ is in $S$. Can a set have itself as its own member? At first glance, there is no reason why not. We can specify: $$S=\{x\mid x = S\}$$ In this case, $S$ would have a single member, $S$ itself!

We can generalize on this idea, specifiying a set as follows: $$Q=\{x \mid x \in x\}$$ The set $Q$ is then the set of all sets that contain themselves. So the set $S=\{x \mid x =S\}$ would be in $Q$. But the set $\{1, 4, 2\}$ would not be, since $\{1, 4, 2\} \notin \{1, 4, 2\}$. Indeed, we seem to also be able to specify the set of all sets that do not contain themselves, by specifying: $$R=\{x \mid x \notin x\}$$ Regarding $R$, if $S=\{x \mid x =S\}$, $S \notin R$, since $S \in S$. On the other hand, since $\{1, 4, 2\} \notin \{1, 4, 2\}$, $\{1, 4, 2\} \in R$.

In general, $Q$ sounds like a set of rather weird sets that contain themselves, while $R$ seems like a set of perfectly normal sets that do not have as members themselves. But in fact, $R$ is quite problematic!

For note that $R$ is specified by being made up of all sets that do not contain themselves. And $R$ is itself a set! So presumably, we can apply the rule, specified for $R$, and see whether $R$ is in $R$, or $R$ is not in $R$. Now the rule specified for $R$ is that if $x \notin x$, for any $x$, then $x \in R$, otherwise, $x \notin R$. But now consider $R$ itself!

Well, if $R \in R$, then it must have passed the rule for $R$, so $R \notin R$. And if $R \notin R$, then it passes the rule, so $R \in R$. But surely, this is absurd! As a general rule, we want to say that a set is either in a set, or it is not in a set, but not both or neither. So we have two choices: either $R \in R$, or $R \notin R$. In the first case, we immediately get that $R \in R$ and $R \notin R$. In the second case, we immediately get that $R \notin R$ and $R \in R$. So in either case, we are in an impossible situation where $R$ is both in $R$, and not in $R$. A paradox.

There is an well-known illustration of Russell’s paradox, sometimes called the barber paradox. Suppose you are in a town that has a barber with a seemingly straightforward rule. The barber shaves those, and only those people who do not shave themselves. So if you shave yourself, the barber does not shave you! But if you do not shave yourself, the barber does shave you. But what about the barber himself? If he shaves himself, then given the fact that he is the barber that only shaves those who do not shave themselves, he does not shave himself. And if he does not shave himself, then given the fact that he only shaves those who do not shave themselves, he does shave himself! So either way, we have the same problem as before, that the barber both does and does not shave himself.

Because of issues like Russell’s paradox, modern set theory needed to look for firmer foundations than it was originally based on. In more modern formulations, like Zermelo–Fraenkel set theory (usually denoted ZF), sets cannot be members of themselves, hence Russell’s paradox is avoided. This also means that $U$ is not a set either. Since we won’t run into these types of issues later, we will not go into these matters further.