The Barber Paradox (Rosen, § 1.1, #44)

Last Update: 20 September 2010

Note: or material is highlighted

I understand that several of you had questions about HW #1, problem 44, about the barber who shaves all & only those who don't shave themselves.

The problem as stated in the book is not as clear as it could be. Here's another version:

Consider a (male) barber, who:

lives in the village,
shaves all those (males) who live in the village who don't shave themselves, and
shaves only those (males) who live in the village who don't shave themselves.

Who shaves the barber? (Or: Can such a barber exist?)

Suppose such a barber exists. Then:

either he shaves himself
or else ("⊕", i.e., XOR)
he does not shave himself.

(This is an exclusive disjunction: He can't both shave himself and not shave himself.)

Case I:

Suppose the barber shaves himself.
But he shaves only villagers who don't shave themselves.
That's a contradiction.
Therefore, our supposition is wrong.
Therefore, he does not shave himself.

Case II:

We have just concluded that the barber does not shave himself.
But he does shave all villagers who do not shave themselves!
Another contradiction.

Conclusion:

Such a barber cannot exist.

Another version of this considers a book that is a catalog of all book catalogs that do not list themselves.
By similar reasoning, no such catalog can exist.
By the way, there used to be, in SEL, a catalog of catalogs! It did list itself!

The most important version of this is the set of all sets that do not contain themselves as members.
No such set can exist.
This is called "Russell's paradox", because it was discovered by Bertrand Russell.

For more information, do a Google search on "barber paradox", or see:

"Barber paradox", Wikipedia.
"Barber Paradox", Wolfram MathWorld.