Russell’s Paradox

For the next element of the paradox set, we move to set theory, and to the British philosopher and mathematician Bertrand Russell. Russell died in 1970 at the age of 97, in the general area where the eccentric and sometimes disturbing television series The Prisoner was filmed — perhaps a fitting place for a philosopher to be. But about 70 years earlier, he had identified a mathematical situation that we call Russell’s Paradox.

There’s a popular framing of Russell’s Paradox in more easily understandable terms involving a town barber, so I’ll present it that way first:

There’s a town that has one barber, a man who lives in the town. In this town, it is the case that the barber shaves all those men, and only those men, who live in the town and do not shave themselves.

Who, then, shaves the barber?

Now, this doesn’t quite capture what Russell devised, but it’s close enough to understand what’s going on. We have a self-referential situation that appears to make sense, but it leads to a contradiction:

• If the barber shaves himself, then he is being shaved by the barber. But the barber shaves only those men who do not shave themselves.
• But if he does not shave himself, then he must be shaved by the barber. So he must shave himself.

Often, the barber puzzle comes with trick wording that gives the puzzler an out. Perhaps the barber is a woman, or a child, or someone who lives outside of town. But I’ve worded this version to eliminate that hedging, so how can we resolve this?

The answer is that we can’t, that this is an example of the third category of paradox:

It has exposed an inconsistency in the logic system, and adjustments are necessary.

That is, we’ve created a system — the town, with the specified set of rules — that is not consistent. Such a system can’t really exist without an exception to make it consistent. This, for example, will work:

There’s a town that has one barber, a man who lives in the town. In this town, it is the case that the barber shaves himself and all other men, and only those men, who live in the town and do not shave themselves.

On to a bit about sets, and the real formulation of Russell’s Paradox. Things get very geeky at this point. Give it a try, if you like, or come back tomorrow for something lighter.

Here’s a set, which we’ll call S:
  S := { A, B }
It has two elements, called A and B.
We say that A is an element of S, and we write it thus: A ∈ S.
A set that contains some of the same elements as S is a subset of S. { A } is a subset of S, and we write it this way: { A } ⊂ S.
It’s also the case that { B } ⊂ S, that S ⊂ S, and that {} &sub S (this is the empty set, which we also denote as Φ).

Now, we can make a set of anything, even a set of sets. So the set of all subsets of S is
  { {}, { A }, { B }, { A, B } }
We call this the power set of S, and denote it as P(S).

We’ll also note that if we have a well defined formula f that operates on a set S, we can construct a new set, T, of the results of applying the formula to all the set’s elements:
  T := { f(x) : x ∈ S }

Having the concept of a set of sets, and a way of defining sets, we can observe that it’s possible for a set to be an element of itself, or not (note that we’re talking about element here, not subset; every set is a subset of itself, but “most” sets are not elements of themselves). For example, suppose we define Q to be the set of all sets that are sets of sets. In other words, W ∈ Q if and only if W is a set of sets. Looking at the set S from above, we see that it is not an element of Q, but its power set is (P(S) ∈ Q).

What about Q itself? Well, Q is a set of sets, so it’s true that Q ∈ Q. That is, Q is an element of itself. That’s not true of the other sets we’ve seen: S ∉ S, for example.

So, then, let’s create a new set R, of all sets that are not elements of themselves.
  R := { A | A ∉ A }
Russell’s Paradox looks at whether or not R ∈ R, and arrives at the same contradiction as we did with the barber:

• If R ∈ R, then by the definition of R, R ∉ R.
• If R ∉ R, then by the definition of R, R ∈ R.

Bertrand Russell thus showed an inconsistency in naïve set theory — an inconsistency that was corrected by some of the axiomatic set theories that followed several years later. Zermelo-Fraenkel is the standard form of axiomatic set theory used today.