Barber paradox
Encyclopedia
The Barber paradox is a puzzle
derived from Russell's paradox
. It was used by Bertrand Russell
himself as an illustration of the paradox
, though he attributes it to an unnamed person who suggested it to him. It shows that an apparently plausible scenario is logically impossible.
Another way to state this is:
All this seems perfectly logical, until we pose the paradoxical question:
This question results in a paradox because, according to the statement above, he can either be shaven by:
However, none of these possibilities are valid! This is because:
(e.g., by Martin Gardner
in Aha!). It was suggested to him as an alternate form of Russell's paradox
, which he had devised to show that set theory
as it was used by Georg Cantor
and Gottlob Frege
contained contradictions. However, Russell denied that the Barber's paradox was an instance of his own:
This point is elaborated further under Applied versions of Russell's paradox.
, one aspect of the Barber paradox can be expressed by a self-referencing clause:
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.
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
, which simplifies to 
, a contradiction.
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.
The paradox is also mentioned several times in David Foster Wallace's first novel, The Broom of the System
.
Notice that the paradox still occurs if we claim that the barber is a man in our town with a beard. In this case, the barber does not shave himself (because he has a beard); but then according to his claim (that he shaves all men who do not shave themselves), he must shave himself.
In a similar way, the paradox still occurs if the barber is a man in our town who cannot grow a beard. Once again, he does not shave himself (because he has no hair on his face), but that implies that he does shave himself.
Puzzle
A puzzle is a problem or enigma that tests the ingenuity of the solver. In a basic puzzle, one is intended to put together pieces in a logical way in order to come up with the desired solution...
derived from Russell's paradox
Russell's paradox
In the foundations of mathematics, Russell's paradox , discovered by Bertrand Russell in 1901, showed that the naive set theory created by Georg Cantor leads to a contradiction...
. It was used by Bertrand Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
himself as an illustration of the paradox
Paradox
Similar to Circular reasoning, A paradox is a seemingly true statement or group of statements that lead to a contradiction or a situation which seems to defy logic or intuition...
, though he attributes it to an unnamed person who suggested it to him. It shows that an apparently plausible scenario is logically impossible.
The Paradox
Suppose there is a town with just one male barber. In this town, every man keeps himself clean-shaven by doing exactly one of two things:- Shaving himself, or
- going to the barber.
Another way to state this is:
- The barber shaves only those men in town who do not shave themselves.
All this seems perfectly logical, until we pose the paradoxical question:
- Who shaves the barber?
This question results in a paradox because, according to the statement above, he can either be shaven by:
- himself, or
- the barber (which happens to be himself).
However, none of these possibilities are valid! This is because:
- If the barber does shave himself, then the barber (himself) must not shave himself.
- If the barber does not shave himself, then the barber (himself) must shave himself.
History
This paradox is often attributed to Bertrand RussellBertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
(e.g., by Martin Gardner
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
in Aha!). It was suggested to him as an alternate form of Russell's paradox
Russell's paradox
In the foundations of mathematics, Russell's paradox , discovered by Bertrand Russell in 1901, showed that the naive set theory created by Georg Cantor leads to a contradiction...
, which he had devised to show that set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
as it was used by Georg Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
and Gottlob Frege
Gottlob Frege
Friedrich Ludwig Gottlob Frege was a German mathematician, logician and philosopher. He is considered to be one of the founders of modern logic, and made major contributions to the foundations of mathematics. He is generally considered to be the father of analytic philosophy, for his writings on...
contained contradictions. However, Russell denied that the Barber's paradox was an instance of his own:
This point is elaborated further under Applied versions of Russell's paradox.
In Prolog
In PrologProlog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
, 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
Stratification (mathematics)
-In mathematical logic:In mathematical logic, stratification is any consistent assignment of numbers to predicate symbols guaranteeing that a unique formal interpretation of a logical theory exists...
test known from Datalog
Datalog
Datalog is a query and rule language for deductive databases that syntactically is a subset of Prolog. Its origins date back to the beginning of logic programming, but it became prominent as a separate area around 1977 when Hervé Gallaire and Jack Minker organized a workshop on logic and databases...
, the predicate shaves is exposed as unstratifiable since it is defined recursively over its negation.
In first-order logic
This sentence is unsatisfiable (a contradiction) because of the universal quantifier
Universal quantification
In predicate logic, universal quantification formalizes the notion that something is true for everything, or every relevant thing....
. 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
, which simplifies to , a contradiction.In literature
In his book Alice in Puzzleland, the logician Raymond SmullyanRaymond Smullyan
Raymond Merrill Smullyan is an American mathematician, concert pianist, logician, Taoist philosopher, and magician.Born in Far Rockaway, New York, his first career was stage magic. He then earned a BSc from the University of Chicago in 1955 and his Ph.D. from Princeton University in 1959...
had the character Humpty Dumpty
Humpty Dumpty
Humpty Dumpty is a character in an English language nursery rhyme, probably originally a riddle and one of the best known in the English-speaking world. He is typically portrayed as an egg and has appeared or been referred to in a large number of works of literature and popular culture...
explain the apparent paradox to Alice
Alice (Alice's Adventures in Wonderland)
Alice is a fictional character in the literary classic, Alice's Adventures in Wonderland and its sequel, Through the Looking-Glass, And What Alice Found There. She is a young girl from Victorian-era Britain.-Development:...
. 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
Contradiction
In classical logic, a contradiction consists of a logical incompatibility between two or more propositions. It occurs when the propositions, taken together, yield two conclusions which form the logical, usually opposite inversions of each other...
, 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.
The paradox is also mentioned several times in David Foster Wallace's first novel, The Broom of the System
The Broom of the System
The Broom of the System is the first novel by the American writer David Foster Wallace, published in 1987.-Background:Wallace stated that the initial idea for the novel sprang from a remark made by an old girlfriend. According to Wallace, she said "she would rather be a character in a piece of...
.
Non-paradoxical variations
A modified version of the Barber paradox is frequently encountered in the form of a brainteaser puzzle or joke. The joke is phrased nearly identically to the standard paradox, but omitting a detail that allows an answer to escape the paradox entirely. For example, the puzzle can be stated as occurring in a small town whose barber claims: I shave all and only the men in our town who do not shave themselves. This version omits the gender of the barber, so a simple solution is that the barber is a woman. The barber's claim applies to only "men in our town," so there is no paradox if the barber is a woman (or a gorilla, or a child, or a man from some other town--or anything other than a "man in our town"). Such a variation is not considered to be a paradox at all: the true Barber paradox requires the contradiction arising from the situation where the barber's claim applies to himself.Notice that the paradox still occurs if we claim that the barber is a man in our town with a beard. In this case, the barber does not shave himself (because he has a beard); but then according to his claim (that he shaves all men who do not shave themselves), he must shave himself.
In a similar way, the paradox still occurs if the barber is a man in our town who cannot grow a beard. Once again, he does not shave himself (because he has no hair on his face), but that implies that he does shave himself.
In music
- Chip Hop (rap)Nerdcore hip hopNerdcore hip hop, is a sub-genre of hip hop music characterized by themes and subject matter considered to be of general interest to nerds, though it can appeal to others as well. Self-described nerdcore musician MC Frontalot has the earliest known recorded use of the term in the 2000 song...
artist MC Plus+ refers to the Barber paradox in his song "Man Vs Machine" from the album Chip Hop. He uses it to defeat his own fictional AIArtificial intelligenceArtificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
opponent, Max Flow, in a rap-battle.
External links
- Proposition of the Barber's Paradox
- Joyce, Helen. "Mathematical mysteries: The Barber's Paradox." Plus, May 2002.
- Edsger Dijkstra's take on the problem