The Barber Paradox is a nice little logical paradox with surprisingly far reaching consequence. It goes like this:

There is a male barber who lives on an island. The barber shaves all those men who live on the island who do not shave themselves, and only those men.

Does the barber shave himself?

If the barber shaves himself then he must be a man who lives on the island who the barber doesn’t shave, so he doesn’t shave himself.

However if he doesn’t shave himself then he’s a man on this island who doesn’t shave himself which means the barber shaves him (i.e he shaves himself).

So if he shaves himself he doesn’t and if he doesn’t he does. How can this be?

This is actually a neat example of the Russell’s Paradox of naïve set theory. This paradox was discovered by Bertrand Russell in the early 1900’s and says that:

The set of all sets that are not members of themselves is a member of itself only if it is not a member of itself, and is not a member only if it is.

Symbolically we might say

R = { x | ∉ x } then R ∈ R ⇔ R ∉ R

That is: R is the set of all sets that don’t contain themselves. Therefore R contains R only when R doesn’t contain R. This is clearly a paradox.

We can represent our troublesome barber as:

∃ x ∀ y ( shave(x, y) ↔ ¬ shave(y, y) )

Given that shave(x, y) is true if x shaves y, this can be read as follows. There exists an x such that, for all y: x shaves y if and only if y doesn’t shave himself.

So far so good, but is this a true proposition? We can show that it is not.

If we call our barber b and let b be the x in our proposition we can say that

∀ y ( shave(b, y) ↔ ¬ shave(y, y) )

Now this is true for all members of y, and b is a member y (the barber is a man on the island). Therefore

shave(b, b) ↔ ¬ shave(b, b)

This can’t be, so we can guess that either our proposition isn’t true or b isn’t a member of y. Since we state that the barber is a man who lives on the island b is a member of y so the proposition must be false.

We can go further and represent the problem in Prolog:

shaves(X, X) :-
   male(X),
   not(shaves(barber,X)).

shaves(barber, X) :-
   male(X),
   not(shaves(X,X)).

male(barber).

If we ask shaves(barber, barber). Prolog will recurse till it runs out of stack (at least in SWI-Prolog, other implementaitons such as DataLog may throw a stratification error).

This paradox is important and not because we’re concerned for the state of the barber’s facial hair. Set theory underpins most branches of mathematics. When this paradox was first discovered it was thought that this inconsistency in set theory may mean that any mathematical proof was not necessarily valid.

Fortunately we need not fear for mathematics just yet. There have been many solutions to Russell’s paradox and logicians and philosophers continue to propose new solutions.

Russell himself proposed a solution by introducing a theory of types as an alternative to naïve set theory. Russell’s type theory will be familiar to any modern day programmer. In it he creates a hierarchy of types and assigns each object to a type. Any given object is only built from objects of types higher up in the hierarchy. This prevents the kind of circular reference that creates the paradox.

The barber paradox is solved using Russell’s type theory because ‘a barber as a male who lives on the island who shaves himself’ and ‘a barber as a professional who shaves other people’ are of different types.