Mathematical mysteries: The Barber's Paradox

By 
Helen Joyce
May 2002

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

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.

Comments

This is the first time I've seen this paradox. It is confusing. But it just seems like a play on words. You can't seem to cross more than two levels unless you change the definition of the set. If A=odd #s and B=even #'s then A and B are not members of themselves. So if C=A+B then C could be considered the set of sets that are not members of themselves, or C could be the set of all real integers. But if A was the whole number digits of pi and B was all prime #'s then you can't really define A+B. I guess it is in the hierarchy. You can't really cross two levels by defining the second level as C when it is really undefined. You're just puting a label on something that doesn't fit. It is like saying A is all red motorcycles and B is all blue motorcycles and calling the set A+B the set of motorcycles. It's not true. You either would have to add them together and say the set of all blue and red motorcycles, or keep it as 2 separate sets that can not be combined because there is no definition to that set. So by saying you have a set of sets that are not members of themselves, you could be talking about a set of infinite possibilities with no real parameter defined. I guess in my opinion when you say a set of sets that are not a member of themselves, you could be talking about anything. Now if that "anything" happens to be a group of things that have a physical rule that each individual thing shares then it could be a set defined by that rule. But, if there is no physical common bond other than the "anything" is just a group of sets drawn together and labeled with a variable, then in my opinion they are not really a set. More of an irrational set. And in the Barber Paradox it seems to me that this is just an irrational statement. I shave everyone that doesn't shave themselves. Well, he misspoke. He shaves everyone who doesn't shave themselves, other than himself. The set was not defined properly. Basically, the barber is the definition of the set. The flaw to me is this. People who do not shave themselves are individuals with a rule. The barber is really a parameter, not an individual. You must first be an individual then follow the rule to be in the group. How can a set be a member of individual motorcycles that are red? It's not a motorcycle, it is a set. Anyway, that's my thoughts on the subject. I guess I would have to see how this applies in mathematics to fully understand.

Can God create a stone that he can not lift up?
This is based on the general assumption that everything is possible to god.So if he creates a stone which he cann't lift up,then it breaks the condition he can lift anything.At the same time if he cann't create a stone, then its against that he can create anything.

Well God can create a stone, that is already lifted up, since it is already lifted up, he cannot lift it up again.
condition proved.

if god can't lift up a stone that is already lifted, it states that god can't do anything, which he can, thus he can lift an already lifted stone.

An axiom: God is infinite. (True)

So let's study the action of creating that stone which God cannot lift up.
The stone would have to be of an infinite mass.
Therefore when God creates that stone, He would no longer exist.
Why? If God would still exist outside that stone, that would mean that the stone would be of a finite mass, which is false.
Therefore God would no longer exist while the stone which He cannot lift exists. So there would be no one left to lift that stone.

That proves that the paradox does not take place.

Hmm well your axiom
God is infinite..

violates your whole proof so nice try but it's a definite no go..

axiom : God is Infinite
predicate : God is Inifinite If and only if God has no mass

otherwise God would take up all mass and there would be no stones.. :) (this was your argument not mine.. that a stone can't be infinite mass or god would be gone. , which is contrapositive to this this proposition)

nice try though..
So.
if god is infinite , he sure must be massless, energyless too for that matter..

There is no such thing as as an infinite stone. By the hotel room syndrome an hotel with infinite rooms can always make an empty room to check someone in. This proof does not appear to be valid.

In one of the first books of Journey to the West, Sun Wukong is tasked with leaving the palm of the hand of buddha. It turns out that there are universes within universes within universes and so on. Sun Wukong cannot leave buddha's hand since it is the universe. Sun Wukong actually peed on Buddha's hand and wrote insults on it. The pee and insults are like the infinite stone. This paradox is therefore destroyed!

Before talking Mathematics, I advise you to go and read some Philosophy of Mathematics...

A perfectly true sentence: "Identical objects are different."
To make this statement interesting i will give the answer two weeks after it's publication.

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

"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. "

A seemingly true paradox, but really just a naive question.

The parameters of the question are undefined. For instance; what defines a "shave"?
Is it considered a shave when you:
A. Remove all the hair from your face?
B. The initial cutting of hair that defines a shave?

Lets define this by way of common language:
I can start to shave and stop to answer the phone,
most likely my wife reminding me to shave,
so I answer, "I am not done shaving but I was shaving"

So by the aforementioned conversation, the "act of shaving" is the term by which we agree to acknowledge what consitutes a shave. There for by this "definition" the answer would have to be;
He would start to shave himself but never finish and from the point on only get some one else to shave him...

I used your Barber paradox in my blog today and included a link to the page I used. Great website, I hope I didn't anger you by using the example.

The Green Dude

Clearly, the "anti-sexist" way-out for the barber's paradox could have worked - had the original statement been that the barber is the person who shaves any MAN that does not shave himself. But it doesn't! It says that the barber shaves anyONE that doesn't shave himself - that is, women included.
To add to the "God paradox": can God create a barber? And must that barber then be of a non-human race?

To Helen Joyce,
Yes, this is all well but what actually is the answer? I would like to know!
Then also do you know any sites (other that this one) that give you long lost/forgotten mathematical mysteries that DON'T involve any algebra?
Please if you go post it on this site! Also I do think this is a bit sexist so I think it's best if you kind of think through what you're going to type and the viewpoints/opinions you're going to get about it. I thank you for your time reading this.
Yours Mysteriously,
Anonymous

If the barber were to wax his beard or hair off or have it removed by plucking or in any other way that does not include a razor, would that count as shaving? If not, then that would save him and everyone else the trouble of deciding whether or not he should shave himself.

What if the barber was bald and therefore he would not need someone to cut his hair.

The phrase 'one does not shave oneself' also includes the following cases along with the usual case in which one is shaved by another person:

1. one cannot (i.e. is not able to) grow hair (on head or beard or etc.)

2. one does not cut one's hair.

The barber could be a woman, a pre-beard child, an American Indian, skin can't grow hair due to fire accident on the face making it impossible, etc. Essencially, any situation where a barber growing a beard doesn't apply.

Let's assume the barber can grow a beard (some women included), and shaving includes all methods of removing hair (including things like fire to the face), then the solution is still obvious. One of premises in the original statement is false: "Do you shave yourself? If not, come in and I'll shave you! I shave [everyone] who does not shave himself, and noone else."

One of these premises are false:
1. Everyone in town has a clean shave, which includes the barbor. (so the barbor has a beard)
2. "I shave [everyone] who does not shave himself..." (so he doesn't shave everyone who does not shave himself)
3. "...and noone else." (so he shaves others too)

Bottom line: the orignal statement has to be false.

The real problem with the paradox is in the verb shave is used differently in two instances.

To demonstrate this, here is my solution to the paradox:

Those men that shave themselves do not go to the barber.

Those men that do not shave themselves are shaved by the barber. This should really be, those men that do not shave themselves are barbered by the barber.

And like that, the paradox is solved.

Does the barber shave himself? Yes, but he does not barber himself.

Alex

The principal of Russell College instructed her maintenance staff "If the front door is red, then paint it any other colour. But if it's any other colour, then paint it red."

That was some years ago and they're still painting.

There are in fact at least five barbers, each of whom shaves himself if and only if he doesn't.

The most famous one, call him Bertrand, shaves all and only those who don't shave themselves.
Alfred, on the other hand, is shaved by all and only those who don't shave themselves.
Gottlob shaves all and only those who don't shave him.
Georg is shaved by all and only those whom he doesn't shave.
Augustus (my favourite) shaves all and only those whom he doesn't shave.

Chris G

Easily solved, the barber is a woman, as it's states. 'I shave anyone who does not shave himself' "himself" not 'theirself' therefore she can shave all men, if she does grow a beard by chance, she can still shave herself, as she is a woman not a man, Hahaha easily solved :-)

They did say that on the last line.

Wow, it must have been a real slow day in your shop to come up with that. I am a female barber, I do not shave my face. How ever, I do straight razor shave men.

The paradox is clearly not about barbers or sets.

It can feature any verb or verb phrase - shave, adore, paint, include in a set, share a pizza with - that can take a subject, object, and crucially, a tense. Almost any verb you like in fact. What we're concerned with here however is the logical tense. This kind of tense isn't necessarily overtly marked by any grammatical suffix like "-ed" in English, or by a word like "then" or "now" or "tomorrow". But it is demonstrated just by the repetition of the verb in a compound proposition or sequence of such propositions. Each constituent clause or proposition featuring the same verb, even with the same grammatical tense, has a different logical tense and refers to a different time.

An artist paints all and only those who don't paint themselves. Each of the two occurrences of "paint" have a different logical tense since they occur at different place-times in this sequence of clauses. We can make this difference highly explicit: An artist will paint tomorrow all and only those who didn't paint themselves yesterday. So if the artist didn't paint herself, then she will. And if she did, then she won't. Simple. Logical. The set will include all and only those sets it didn't include before, so if it did include itself before then it won't next time, and vice versa. Any paradoxical contradiction is merely a result of failure to differentiate with respect to logical tense, of flattening out the entire argument into a kind of timeless present.

This shouldn't be an entirely unfamiliar idea. We use brackets to indicate arithmetical tense, that is the order in which operations are to be performed, to avoid contradiction.

Time heals all logical wounds.

Chris G

Actually this is only a paradox if we assume that it is impossible for the barber to lie. Just because the barber's sign STATES they "shave anyone who does not shave themselves and no one else" doesn't necessarily mean that IS the case. You might call that the Madison Avenue theory, or the P.T. Barnum... ;)

When the barber is saying:
"Do you shave yourself? If not, come in and I'll shave you! I shave anyone who does not shave himself, and noone else"
it means that he is a barber who obviously works in his shop during working hours, i.e. from 09:00 until 17:00. By the law, this must be clearly visible at the entrance door of his barbershop.
Before that time or after that time he is not working as a barber and he can easily shave himself; obviously he shaves himself.
The time element must be added to the equation.

I agree particularly with your last sentence, Robert, and would be interested in feedback from you about how I go about adding the time element in my comment "My solution" shortly before yours (in space that is, but a year in time).

The words you put in the barber's mouth "I shave anyone who does not shave himself, and noone else" also clarify the matter. He clearly isn't talking about what he does or doesn't do to his own bristles, that subject is irrelevant. Similarly with Russell's famous set. It may include any set that doesn't include itself and none other, but that has no implications to whether it includes itself.

In fact this point still stands even if the barber just says "I shave anyone." since he's still not talking about shaving himself. Even if he has no shop or special working hours, and even if he isn't a professional barber. It's really just a feature of how we use verbs (or verb phrases) that take an object. Consider the absurd syllogism "John shook hands with everyone in the room. John was in the room. Therefore John shook hands with himself". Same goes for "shave".