Barber paradox

Barber paradox

:"This article is about a paradox of self-reference. 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 derived from Russell's Paradox and often falsely attributed to Bertrand Russell."The Philosophy of Logical Atomism", reprinted in "The Collected Papers of Bertrand Russell, 1914-19", Vol 8., p. 228] It shows that an apparently plausible scenario is logically impossible.

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

History

This paradox is often attributed to Bertrand Russell (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. Of the Barber Paradox, Russell said the following:

This point is elaborated further under Applied versions of Russell's Paradox.

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.

In first-order logic

(exists x ) (barber(x) wedge (forall y) ( eg 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 eg shaves(x,x) Leftrightarrow shaves(x,x), which simplifies to shaves(x, x) wedge eg shaves(x,x), a contradiction.

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.

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. (Perhaps he lost all facial hair follicles in a painful accident). 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) artist MC Plus+ refers to the Barber's Paradox in his song "Man Vs Machine" from the album Chip Hop. He uses it to defeat his own fictional AI opponent, Max Flow, in a rap-battle.

References

External links

* [http://www.umsl.edu/~siegel/SetTheoryandTopology/TheBarber.html Proposition of the Barber's Paradox]
* Joyce, Helen. [http://plus.maths.org/issue20/xfile/index.html "Mathematical mysteries: The Barber's Paradox."] "Plus," May 2002.
* [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD923a.html Edsger Dijkstra's take on the problem]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • barber paradox — A village has a barber in it, who shaves all and only the people who do not shave themselves. Who shaves the barber? If he shaves himself, then he does not, but if he does not shave himself, then he does. The paradox is actually just a proof that …   Philosophy dictionary

  • barber — paradox …   Philosophy dictionary

  • Paradox — For other uses, see Paradox (disambiguation). Further information: List of paradoxes 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. Typically,… …   Wikipedia

  • Barber (disambiguation) — Professions*barber *barber surgeonPeopleNotable people whose last name is or was Barber include*Alden G. Barber Boy Scouts of America Scouting notable, awardee of the Bronze Wolf in 1975 *Andrea Barber (born 1976), U.S. actress *Anthony Barber,… …   Wikipedia

  • Russell's paradox — Part of the foundations of mathematics, Russell s paradox (also known as Russell s antinomy), discovered by Bertrand Russell in 1901, showed that the naive set theory of Frege leads to a contradiction.It might be assumed that, for any formal… …   Wikipedia

  • Barbershop paradox — This article is about a paradox in the theory of logical conditionals introduced by Lewis Carroll in [http://fair use.org/mind/1894/07/notes/a logical paradox A Logical Paradox] . For an unrelated paradox of self reference with a similar name,… …   Wikipedia

  • Grelling–Nelson paradox — The Grelling–Nelson paradox is a semantic self referential paradox formulated in 1908 by Kurt Grelling and Leonard Nelson and sometimes mistakenly attributed to the German philosopher and mathematician Hermann Weyl. It is thus occasionally called …   Wikipedia

  • Tritone paradox — The tritone paradox is an auditory illusion in which a sequentially played pair of Shepard tones [1] separated by an interval of a tritone, or half octave, is heard as ascending by some people and as descending by others …   Wikipedia

  • Russell's paradox — The most famous of the paradoxes in the foundations of set theory, discovered by Russell in 1901. Some classes have themselves as members: the class of all abstract objects, for example, is an abstract object. Others do not: the class of donkeys… …   Philosophy dictionary

  • number game — Introduction       any of various puzzles and games that involve aspects of mathematics.       Mathematical recreations comprise puzzles and games that vary from naive amusements to sophisticated problems, some of which have never been solved.… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”