Barbershop paradox
Encyclopedia
- This article is about a paradox in the theory of logical conditionals introduced by Lewis CarrollLewis CarrollCharles Lutwidge Dodgson , better known by the pseudonym Lewis Carroll , was an English author, mathematician, logician, Anglican deacon and photographer. His most famous writings are Alice's Adventures in Wonderland and its sequel Through the Looking-Glass, as well as the poems "The Hunting of the...
in "A Logical Paradox." For an unrelated paradox of self-reference with a similar name, attributed to Bertrand RussellBertrand RussellBertrand 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...
, see the Barber paradoxBarber paradoxThe 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.- The Paradox...
.
The Barbershop Paradox was proposed by Lewis Carroll
Lewis Carroll
Charles Lutwidge Dodgson , better known by the pseudonym Lewis Carroll , was an English author, mathematician, logician, Anglican deacon and photographer. His most famous writings are Alice's Adventures in Wonderland and its sequel Through the Looking-Glass, as well as the poems "The Hunting of the...
in a three-page essay entitled "A Logical Paradox" which appeared in the July 1894 issue of Mind
Mind (journal)
Mind is a British journal, currently published by Oxford University Press on behalf of the Mind Association, which deals with philosophy in the analytic tradition...
. The name comes from the "ornamental" short story that Carroll uses to illustrate the paradox (although it had appeared several times in more abstract terms in his writing and correspondence before the story was published). Carroll claimed that it illustrated "a very real difficulty in the Theory of Hypotheticals" in use at the time.
The paradox
Briefly, the story runs as follows: Uncle Joe and Uncle Jim are walking to the barber shop. There are three barbers who live and work in the shop—Allen, Brown, and Carr—but not all of them are always in the shop. Carr is a good barber, and Uncle Jim is keen to be shaved by him. He knows that the shop is open, so at least one of them must be in. He also knows that Allen is a very nervous man, so that he never leaves the shop without Brown going with him.Uncle Joe insists that Carr is certain to be in, and then claims that he can prove it logically. Uncle Jim demands the proof. Uncle Joe reasons as follows.
Suppose that Carr is out. If Carr is out, then if Allen is also out Brown would have to be in—since someone must be in the shop for it to be open. However, we know that whenever Allen goes out he takes Brown with him, and thus we know as a general rule that if Allen is out, Brown is out. So if Carr is out then the statements "if Allen is out then Brown is in" and "if Allen is out then Brown is out" would both be true at the same time.
Uncle Joe notes that this seems paradoxical; the hypotheticals seem "incompatible" with each other. So, by 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...
, Carr must logically be in.
Criticism
Uncle Joe's reasoning based on paradoxic contradiction, relies on the premise that Allen is not in the store. Given there is no rational explanation to exclude the feasibility the aforementioned hypothetical; the following scenarios assure both the maintenance of the "paradox's" axioms, while discrediting Uncle Joe's argument:- Carr is out but Allen and Brown are BOTH in
- Carr and Brown are out and Allen is alone in the barbershop
Obviously, the latter would not stand true if the conditional implication X⇒Y was bilateral in nature (i.e X⇒Y AND Y⇒X)
In relation clarifying why this is not "really a paradox"; this could be because Uncle Joe's assumption that Allen is not in the store, is not based on any logical reasoning. Thus it is actually that exclusion of this possibility which results the paradoxic nature of the two simultaneously existing contradictory scenarios rather than the story itself.
Simplification
Carroll wrote this story to illustrate a controversy in the field of logic that was raging at the time. His vocabulary and writing style can easily add to the confusion of the core issue for modern readers.Notation
When reading the original it may help to keep the following in mind:- What Carroll called "hypotheticals" modern logicians call "logical conditionals."
- Whereas Uncle Joe concludes his proof reductio ad absurdumReductio ad absurdumIn logic, proof by contradiction is a form of proof that establishes the truth or validity of a proposition by showing that the proposition's being false would imply a contradiction...
, modern mathematicians would more commonly claim "proof by contradiction." - What Carroll calls the prostasis 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:
| Operator (Name) | Colloquial | Symbolic | ||
|---|---|---|---|---|
| Negation | NOT | not X | ¬ | ¬X |
| Conjunction Logical conjunction In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false.... |
AND | X and Y | ∧ | X ∧ Y |
| Disjunction | OR | X or Y | ∨ | X ∨ Y |
| Conditional | IF...THEN | if X then Y | ⇒ | X ⇒ Y |
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
Table of mathematical symbols
This is a listing of common symbols found within all branches of mathematics. Each symbol is listed in both HTML, which depends on appropriate fonts being installed, and in , as an image.-Symbols:-Variations:...
.
Restatement
To aid in restating Carroll's story more simply, we will take the following atomic statementsAtomic formula
In mathematical logic, an atomic formula is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subformulas. Atoms are thus the simplest well-formed formulas of the logic...
:
- 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
- Allen never goes anywhere without Brown
Uncle Joe presents a proof:
| Abbreviated English with logical markers | Mainly Symbolic |
|---|---|
| Suppose Carr is NOT in. | H0: ¬C |
| Given NOT C, IF Allen is NOT in THEN Brown must be in, to satisfy Axiom 1. | By H0 and A1, ¬A ⇒ B |
| But Axiom 2 gives that it is universally true that IF Allen is Not in THEN Brown is Not in (it's always true that if ¬A then ¬B) |
By A2, ¬A ⇒ ¬B |
| So far we have that NOT C yields both (Not A THEN B) AND (Not A THEN Not B). | Thus ¬C ⇒ ( (¬A ⇒ B) ∧ (¬A ⇒ ¬B) ) |
| Uncle Joe claims that these are contradictory. | ⊥ |
| Therefore Carr must be in. | ∴C |
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 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,
|
|
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, 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
Protasis (linguistics)
In linguistics, a protasis is the subordinate clause in a conditional sentence. For example, in "if X, then Y", the protasis is "if X"...
and apodosis
Apodosis
Apodosis may refer to:*In linguistics, the main clause in a conditional sentence*In logic, the apodosis corresponds to the consequent; ....
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.
See also
- Lewis CarrollLewis CarrollCharles Lutwidge Dodgson , better known by the pseudonym Lewis Carroll , was an English author, mathematician, logician, Anglican deacon and photographer. His most famous writings are Alice's Adventures in Wonderland and its sequel Through the Looking-Glass, as well as the poems "The Hunting of the...
- Russell's ParadoxRussell's paradoxIn 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...
- Conditional sentences in English
- Crocodile DilemmaCrocodile DilemmaThe Crocodile Dilemma is an unsolvable problem in logic. The premise states that a crocodile who has stolen a child promises the father that his son will be returned if and only if he can correctly predict whether or not the crocodile will return the child....
- List of paradoxes