A close shave for set theory

Suppose you walk past a barber's shop one day, and see a sign that says

"Do you shave yourself? If not, come in and I'll shave you! I shave anyone who does not shave himself, and noone else."

This seems fair enough, and fairly simple, until, a little later, the following question occurs to you - does the barber shave himself? If he does, then he mustn't, because he doesn't shave men who shave themselves, but then he doesn't, so he must, because he shaves every man who doesn't shave himself... and so on. Both possibilities lead to a contradiction.

This is the Barber's Paradox, discovered by mathematician, philosopher and conscientious objector Bertrand Russell, at the begining of the twentieth century. As stated, it seems simple, and you might think a little thought should show you the way around it. At worst, you can just say "Well, the barber's condition doesn't work! He's just going to have to decide who to shave in some different way." But in fact, restated in terms of so-called "naïve" set theory, the Barber's paradox exposed a huge problem, and changed the entire direction of twentieth century mathematics.

In naïve set theory, a set is just a collection of objects that satisfy some condition. Any clearly phrased condition is thought to define a set - namely, those things that satisfy the condition. Here are some sets:

• The set of all red motorcycles ;
• The set of all integers greater than zero;
• The set of all blue bananas - which is just the empty set!

This set is not a member of itself

Some sets are not members of themselves - for example, the set of all red motorcycles - and some sets are - for example, the set of all non-motorcycles. Now what about the set of all sets which are not members of themselves? Is it a member of itself or not? If it is, then it isn't, and if it isn't, then it is... Just like the barber who shaves himself, but mustn't, and therefore doesn't, and so must!

So now we realise that Russell's Barber's Paradox means that there is a contradiction at the heart of naïve set theory. That is, there is a statement S such that both itself and its negation (not S) are true. The particular statement here is "the set of all sets which are not members of themselves contains itself". But once you have a contradiction, you can prove anything you like, just using the rules of logical deduction! This is how it goes.

1. If S is true, and Q is any other statement, then "S or Q" is clearly true.
2. Since "not S" is also true, so is "S or Q and not S".
3. Therefore Q is true, no matter what it is.

The paradox raises the frightening prospect that the whole of mathematics is based on shaky foundations, and that no proof can be trusted. In essence, the problem was that in naïve set theory, it was assumed that any coherent condition could be used to determine a set. In the Barber's Paradox, the condition is "shaves himself", but the set of all men who shave themselves can't be constructed, even though the condition seems straightforward enough - because we can't decide whether the barber should be in or out of the set. Both lead to contradictions.

Attempts to find ways around the paradox have centred on restricting the sorts of sets that are allowed. Russell himself proposed a "Theory of Types" in which sentences were arranged hierarchically. At the lowest level are sentences about individuals. At the next level are sentences about sets of individuals; at the next level, sentences about sets of sets of individuals, and so on. This avoids the possibility of having to talk about the set of all sets that are not members of themselves, because the two parts of the sentence are of different types - that is, at different levels.

But to be a satisfactory philosophy, we have to be able to say why you are not allowed to mix levels. Although, for example, it is not true that the property of being red is itself red, this is surely a wrong statement, rather than actually meaningless. And there are properties that seem reasonably to apply to themselves - the Theory of Types disallows statements such as "It's nice to be nice" but really this seems like a reasonable and true statement!

For this and other reasons, the most favoured escape from Russell's Paradox is the so-called Zermelo-Fraenkel axiomatisation of set theory. This axiomatisation restricts the assumption of naïve set theory - that, given a condition, you can always make a set by collecting exactly the objects satisfying the condition. Instead, you start with individual entities, make sets out of them, and work upwards. This means you do not have to suppose that there is a set of all sets, which means you don't have to try to divide that set up into those sets that contain themselves and those which don't. You only have to be able to make this division for the elements of any given set, which you have built up from individual entities via some number of steps.

To end on a more flippant note, if Russell had been aware of the inbuilt sexism of the language of his day, the course of twentieth century mathematics might have been different. There is an easy solution to the Barber's Paradox, which doesn't require the opening of any nasty cans of set-theoretic worms. Just make the barber a woman...

About the author

Helen Joyce is editor of Plus.