The barbershop paradox was proposed by

Lewis Carroll Charles Lutwidge Dodgson (; 27 January 1832 – 14 January 1898), better known by his pen name Lewis Carroll, was an English author, poet and mathematician. His most notable works are '' Alice's Adventures in Wonderland'' (1865) and its sequ ...

in a three-page essay titled "A Logical Paradox", which appeared in the July 1894 issue of '' Mind''. The name comes from the "ornamental" short story that Carroll uses in the article to illustrate the paradox. It existed previously in several alternative forms in his writing and correspondence, not always involving a barbershop. Carroll described it as illustrating "a very real difficulty in the Theory of Hypotheticals". From the viewpoint of modern logic it is seen not so much as a

paradox A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-contradictory or a logically u ...

than as a simple

logical error A fallacy is the use of invalid or otherwise faulty reasoning, or "wrong moves," in the construction of an argument which may appear stronger than it really is if the fallacy is not spotted. The term in the Western intellectual tradition was intr ...

. It is of interest now mainly as an episode in the development of algebraic logical methods when these were not so widely understood (even among logicians), although the problem continues to be discussed in relation to theories of implication and modal logic.

The paradox

In the story, Uncle Joe and Uncle Jim are walking to the barber shop. They explain that there are three barbers who live and work in the shop—Allen, Brown, and Carr—and some or all of them may be in. We are given two pieces of information from which to draw conclusions. Firstly, the shop is definitely open, so at least one of the barbers must be in. Secondly, Allen is said to be very nervous, so that he never leaves the shop unless Brown goes with him. Now, according to Uncle Jim, Carr is a very good barber, and he wants to know whether Carr will be there to shave him. Uncle Joe insists that Carr is ''certain'' to be in, and claims that he can prove it logically. Uncle Jim demands this proof. Uncle Joe gives his argument as follows: Suppose that Carr is out. We will show that this assumption produces a contradiction. If Carr is out, then we know this: "If Allen is out, then Brown is in", because there has to be someone in "to mind the shop". But, we also know that whenever Allen goes out he takes Brown with him, so as a general rule, "If Allen is out, then Brown is out". The two statements we have arrived at are incompatible, because if Allen is out then Brown cannot be both In (according to one) and Out (according to the other). There is a contradiction. So we must abandon our hypothesis that Carr is Out, and conclude that Carr must be in. Uncle Jim's response is that this conclusion is not warranted. The correct conclusion to draw from the incompatibility of the two "hypotheticals" is that what is hypothesized in them (that Allen is out) must be false under our assumption that Carr is out. Then our logic simply allows us to arrive at the conclusion "If Carr is out, then Allen must necessarily be in".

Origin

The paradox arose out of a disagreement between Carroll and his Oxford colleague, Wykeham Professor of Logic

John Cook Wilson John is a common English name and surname: * John (given name) * John (surname) John may also refer to: New Testament Works * Gospel of John, a title often shortened to John * First Epistle of John, often shortened to 1 John * Second ...

, the two of whom had a long-running antagonism. The problem was also discussed by others with whom Carroll corresponded, and was addressed in later articles published by

John Venn John Venn, Fellow of the Royal Society, FRS, Fellow of the Society of Antiquaries of London, FSA (4 August 1834 – 4 April 1923) was an English mathematician, logician and philosopher noted for introducing Venn diagrams, which are used in l ...

, Alfred Sidgwick and

Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ...

among others. Cook Wilson's view is represented in the story by the character of Uncle Joe, who attempts to prove that Carr must always remain in the shop. Others had taken the same view when Carroll circulated his privately printed versions of the problem. As Carroll noted, "I am in correspondence with about a dozen logicians on this curious point; & so far, opinions appear equally divided as to C's freedom".

Simplification

Notation

When reading the original it may help to keep the following in mind: *What Carroll called "hypotheticals" modern logicians call "

logical conditional Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...

s". *Uncle Joe concludes his proof ''

reductio ad absurdum In logic, (Latin for "reduction to absurdity"), also known as (Latin for "argument to absurdity") or ''apagogical arguments'', is the form of argument that attempts to establish a claim by showing that the opposite scenario would lead to absu ...

'', meaning in English "

proof by contradiction In logic and mathematics, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Proof by contradiction is also known ...

". *What Carroll calls the protasis of a conditional is now known as the antecedent, and similarly the apodosis is now called the consequent. Symbols can be used to greatly simplify logical statements such as those inherent in this story: Note: X ⇒ Y (also known as "Implication") can be read many ways in English, from "X is sufficient for Y" to "Y follows from X". (See also

Table of mathematical symbols A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object, an action on mathematical objects, a relation between mathematical objects, or for structuring the other symbols that occur in a formula ...

Restatement

To aid in restating Carroll's story more simply, we will take the following atomic statements: *A = Allen is ''in'' the shop *B = Brown is ''in'' *C = Carr is ''in'' So, for instance (¬A ∧ B) represents "Allen is out and Brown is in" Uncle Jim gives us our two axioms: #There is at least one barber in the shop now (A ∨ B ∨ C) #Allen never leaves the shop without Brown (¬A ⇒ ¬B) Uncle Joe presents a proof: Uncle Joe basically makes the argument that (¬A ⇒ B) and (¬A ⇒ ¬B) are contradictory, saying that the same antecedent cannot result in two different consequents. This purported contradiction is the crux of Joe's "proof". Carroll presents this intuition-defying result as a paradox, hoping that the contemporary ambiguity would be resolved.

Discussion

In modern logic theory this scenario is not a paradox. The law of implication reconciles what Uncle Joe claims are incompatible hypotheticals. This law states that "if X then Y" is logically identical to "X is false or Y is true" (¬X ∨ Y). For example, given the statement "if you press the button then the light comes on", it must be true at any given moment that either you have ''not'' pressed the button, or the light is on. In short, what obtains is not that ¬C yields a contradiction, only that it necessitates A, because ¬A is what actually yields the contradiction. In this scenario, that means Carr doesn't have to be in, but that if he isn't in, Allen has to be in.

Simplifying to Axiom 1

Applying the law of implication to the offending conditionals shows that rather than contradicting each other one simply reiterates the fact that since the shop is open one or more of Allen, Brown or Carr is in and the other puts very little restriction on who can or cannot be in the shop. To see this let's attack Jim's large "contradictory" result, mainly by applying the law of implication repeatedly. First let's break down one of the two offending conditionals: Substituting this into Which yields, with continued application of the law of implication, **note that : C ∨ ( (A ∨ B) ∧ (A ∨ ¬B) ) can be simplified to C ∨ A **since ( (A ∨ B) ∧ (A ∨ ¬B) ) is simply A And finally, (on the right we are distributing over the parentheses) So the two statements which become true at once are: "One or more of Allen, Brown or Carr is in", which is simply Axiom 1, and "Carr is in or Allen is in or Brown is out". Clearly one way that both of these statements can become true at once is in the case where Allen is in (because Allen's house is the barber shop, and at some point Brown left the shop). Another way to describe how (X ⇒ Y) ⇔ (¬X ∨ Y) resolves this into a valid set of statements is to rephrase Jim's statement that "If Allen is ''also'' out ..." into "If Carr is out and Allen is out then Brown is in" ( (¬C ∧ ¬A) ⇒ B).

Showing conditionals compatible

The two conditionals are not logical opposites: to prove by contradiction Jim needed to show ¬C ⇒ (Z ∧ ¬Z), where Z happens to be a conditional. The opposite of (A ⇒ B) is ¬(A ⇒ B), which, using

De Morgan's Law In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathem ...

, resolves to (A ∧ ¬B), which is not at all the same thing as (¬A ∨ ¬B), which is what A ⇒ ¬B reduces to. This confusion about the "compatibility" of these two conditionals was foreseen by Carroll, who includes a mention of it at the end of the story. He attempts to clarify the issue by arguing that the

protasis In drama, a protasis is the introductory part of a play, usually its first act. The term was coined by the fourth-century Roman grammarian Aelius Donatus. He defined a play as being made up of three separate parts, the other two being epitasis an ...

and apodosis of the implication "If Carr is in ..." are "incorrectly divided". However, application of the Law of Implication removes the "If ..." entirely (reducing to disjunctions), so no protasis and apodosis exist and no counter-argument is needed.