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, attributed to Bertrand Russell, see the Barber paradox."

The Barbershop Paradox was proposed by Lewis Carroll in a three-page essay entitled " [http://fair-use.org/mind/1894/07/notes/a-logical-paradox A Logical Paradox] ," which appeared in the July 1894 issue of "Mind". 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).

The paradox

Briefly, the story runs as follows: Uncle Joe, Uncle Jim and their nephew are walking to the barber shop. There are three barbers who 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 house 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, Carr must logically be in.

implification

Carroll wrote this story to illustrate a controversy in the field of logic that was ragingat the time. His vocabulary and writing style can easily add to the confusion of the coreissue for modern readers.

Notation

When reading the original it may help to keep the following in mind:
*What Carroll called "hypotheticals" modern logicians call "conditionals."
*Whereas Uncle Joe concludes his proof reductio ad absurdum, 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 inherentin this story:

Substituting this into

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 in the case where Allen is in (perhaps Brown met Allen at Allen's house, they walked together to the shop but at some point Brown left the shop, leaving Allen 'stranded').

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

howing Conditionals Compatible

It should be noted that 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 DeMorgan'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 and apodosis of the implication "If Carr is in..." are "incorrectly divided". However, application of the Law of Implication removes the "If..." entirely (reducing todisjunctions), so no protasis and apodosis exist and no counter-argument is needed.

Further reading

* Lewis Carroll (1894), [http://fair-use.org/mind/1894/07/notes/a-logical-paradox A Logical Paradox] . "Mind", New Series, Vol. 3, No. 11 (Jul., 1894), 436-438.
* Bertrand Russell (1903), [http://fair-use.org/bertrand-russell/the-principles-of-mathematics/s.19#s19n1 The Principles of Mathematics § 19 "n." 1] . Russell suggests a truth-functional notion of logical conditionals, which (among other things) entails that a false proposition will imply "all" propositions. In a note he mentions that his theory of implication would dissolve Carroll's paradox, since it not only allows, but in fact requires that "both" "p implies q" and "p implies not-q" be true, so long as p is not true.

ee also

* Lewis Carroll
* Russell's Paradox