The Barber paradox is a puzzle attributed to Bertrand Russell. It shows that an apparently plausible scenario is logically impossible. An example of a simple puzzle. ... Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS (18 May 1872 – 2 February 1970), was a British philosopher, logician, and mathematician, working mostly in the 20th century. ...

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.

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. Robert Boyles self-flowing flask fills itself in this diagram, but perpetual motion machines cannot exist. ... Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS (18 May 1872 – 2 February 1970), was a British philosopher, logician, and mathematician, working mostly in the 20th century. ... Russells paradox (also known as Russells antinomy) is a paradox discovered by Bertrand Russell in 1901 which shows that the naive set theory of Frege is contradictory. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... Georg Cantor Georg Ferdinand Ludwig Philipp Cantor (March 3, 1845, St. ... Friedrich Ludwig Gottlob Frege (8 November 1848, Wismar – 26 July 1925, Bad Kleinen) was a German mathematician who evolved into a logician and philosopher. ...

In prolog

In Prolog, one aspect of the Barber paradox can be expressed by a self-referencing clause: Prolog is a logic programming language. ...

 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. A common default assumption is that what is not known to be true is believed to be false. ... Stratification 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. ... Datalog is a database query language that syntactically is a subset of Prolog. ...

In first order logic

First-order predicate calculus or first-order logic (FOL) is a theory in symbolic logic that permits the formulation of quantified statements such as there is at least one X such that. ...

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 barbor 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 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 logician is a philosopher, mathematician, or other whose topic of scholarly study is logic. ... Raymond Merrill Smullyan (born 1919) is a mathematician, logician, philosopher, and magician. ... Humpty Dumpty sits on a wall, not having yet fallen. ... Alice is a fictional character in the books Alices Adventures in Wonderland and its sequel Through the Looking-Glass, which were written by Charles Dodgson under the pen name Lewis Carroll. ... Broadly speaking, a contradiction is an incompatibility between two or more statements, ideas, or actions. ...

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.