Barber paradox

From Wikipedia, the free encyclopedia

This article or section does not adequately cite its references or sources.
Please help improve this article by adding citations to reliable sources. (help, get involved!)
Any material not supported by sources may be challenged and removed at any time. This article has been tagged since November 2006.

This article is about a paradox of self-reference attributed to Bertrand Russell. For an unrelated paradox in the theory of logical conditionals with a similar name, introduced by Lewis Carroll, see the Barbershop paradox.

The Barber paradox is a puzzle attributed to Bertrand Russell. It shows that an apparently plausible scenario is logically impossible.

1 The paradox
2 History
3 In prolog
4 In first-order logic
5 In literature
6 References
7 External link

[edit] The paradox

Suppose there is a town with just one male barber; and that every man in the town keeps himself clean-shaven: some by shaving themselves, some by attending the barber. It seems reasonable to imagine that the barber obeys the following rule: He shaves all and only those men who do not shave themselves.

Under this scenario, we can ask the following question: Does the barber shave himself?

Asking this, however, we discover that the situation presented is in fact impossible:

If the barber does not shave himself, he must abide by the rule and shave himself.
If he does shave himself, according to the rule he will not shave himself.

[edit] History

This paradox is often attributed to Bertrand Russell. It is analogous to Russell's Paradox, which he devised to show that set theory as it was used by Georg Cantor and Gottlob Frege contained contradictions.

[edit] In prolog

In Prolog, one aspect of the Barber paradox can be expressed by a self-referencing clause:

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

where negation as failure is assumed. If we apply the stratification test known from Datalog, the predicate shaves is exposed as unstratifiable since it is defined recursively over its negation.

[edit] In first-order logic

$(\exists x ) (barber(x) \wedge (\forall y) (\neg shaves(y, y) \Leftrightarrow shaves(x, y)))$

This sentence is unsatisfiable (a contradiction) because of the universal quantifier. The universal quantifier y will include every single element in the domain, including our infamous barber x. So when the value x is assigned to y, the sentence can be rewritten to $\neg shaves(x,x) \Leftrightarrow shaves(x,x)$ , which simplifies to $shaves(x, x) \wedge \neg shaves(x,x)$ , a contradiction.

[edit] In literature

In his book Alice in Puzzleland, the logician Raymond Smullyan had the character Humpty Dumpty explain the apparent paradox to Alice. Smullyan argues that the paradox is akin to the statement "I know a man who is both five feet tall and six feet tall," in effect claiming that the "paradox" is merely a contradiction, not a true paradox at all, as the two axioms above are mutually exclusive.

A paradox is supposed to arise from plausible and apparently consistent statements; Smullyan suggests that the "rule" the barber is supposed to be following is too absurd to seem plausible.