User:FrankP/Drafts/Barbershop

Sources

Main references

Carroll described it as illustrating "a very real difficulty in the Theory of Hypotheticals".

Its interest is mostly as a episode in the development of algebraic logical methods at a time when many logicians did not fully understand the newer perspective.

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.

Copi and Burks published on this in 1950 (and Bartley says "since widely discussed")

Moktefi, A. (2007). "Lewis Carroll and the British nineteenth-century logicians on the barber shop problem." Proceedings of The Canadian Society for the History and Philosophy of Mathematics’ Annual Meeting (Concordia University, Montréal, July 27-29, 2007), 20. Ed. A. Cupillari. pp189−199.

McKinsey, J.C.C. (1950) Review of Burks and Copi, Journal of Symbolic Logic, 15:3, pp. 222-223

https://doi.org/10.2307/2266828

Quotations from Bartley

• "The history of logic is conventionally divided into three main periods [Aristotelian, Boolean (algebraic), mathematical (Frege/Russell)] .."
• "For the remainder of the nineteenth century [from 1847 (Boole/deMorgan)] algebraic logic dominated logical work, teaching, and research, except in Oxford, where it got comparatively little attention."
• "Lewis Carroll's academic career coincides almost exactly with the breakdown of Aristotelian logic and the flowering of Boolean algebraic logic."

The paradox stated

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—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 the 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 Joe notes that this seems paradoxical; the two "hypotheticals" seem "incompatible" with each other. So, by contradiction, Carr must logically be in.

However, the correct conclusion to draw from the incompatibility of the two "hypothetical" 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".

FRP draft explanation

• In vs Out: Before coming to the knottier logical stuff, let's just clear up one small confusion. Some commenters have assumed that Allen or Brown go out to the shop to work, or one has to pick the other up at his house, or whatever. As noted by some replies, this is not what the problem states. The barbers live and work at the shop. If you have access to the original paper you'll see there is no doubt about this. In the narrative the states of being "in", "at home" and on shaving duty are all used interchangeably.

• Paradox?: My next point is about whether or not this is an actual paradox. In the lede of that article you will see that, "Informally, the term paradox is often used to describe a counter-intuitive result." It is probably in that sense that we should take it. In fact, Carroll presented this problem in a succession of versions (see next item), and did not always describe it as a paradox, but also under other titles such as A logical puzzle and A disputed point in logic. He never used the exact phrase The Barbershop Paradox, but that is how it has come to be known.

• Historical context: Commenters have rightly asked for the puzzle to be given some context, especially as to why it might be important, ultimately asking whether it merits an article at all. I am strongly of the opinion that it does, and hope to show you why. I rely on the following source which I will add to the article when I edit it: Carroll, Lewis (1977). Bartley, William Warren (ed.). Symbolic Logic, Parts I and II. Harvester Press. ISBN 0855279842.

Bartley tracked down, in various collections, never-published galley proofs of the unfinished second volume of Carroll's Symbolic Logic, which had long been thought to be lost. He has also collected together correspondence and privately printed papers by Carroll which together tell the story of the debates around this problem and other developments within the study of logic in this period. Carroll would habitually print and circulate challenging logical puzzles to various acquaintances, and in particular he had a long-running antagonism with his Oxford colleague, the Wykeham Professor of Logic John Cook Wilson. Wilson is here represented by the character of Uncle Joe, who attempts to prove that Carr must always be in the shop.

• The central issue: The earliest form of the problem arose from correspondence between Carroll and Cook Wilson, and was presented by Carroll in different forms before settling on the Barbershop narrative that was published in Mind in 1894. The heart of the issue was Wilson's inability to correctly negate a conditional. With hindsight it's easy for us to say how thoroughly wrong he was (hope that's NPOV enough?!). But (i) at the time, especially in Oxford, modern logical methods were poorly understood and (ii) Carroll did everything he could to obfuscate the issue, perhaps to trap the eminent Professor (there is support for this view in Carroll's journals) or perhaps to make a point about the difficulties of capturing natural language in logic (WP:OR).

Suppose we wish to negate a simple conditional statement, like "If A then B". Anyone who has studied logic will know that to say "If A then not B" is the wrong answer. "If you are French, you are a great painter" is untrue. But we don't express its opposite by claiming, "If you are French, you are not a great painter". Cook Wilson's reply to Carroll's problem relied on this exact fallacy.

Here's how Cook Wilson's argument actually went:

• We are told that (X) "If Allen is out, Brown is also out" (to keep him company)
• We also know (Y) "If Carr is out, then if Allen is out, Brown must be in" (so that there is someone to mind the shop)
• But (Y) is equivalent to "If Carr is out, then not (X)" (reasoning fallaciously as to the negation of a conditional)
• And we know (X) is true, so by reductio ad absurdum Carr is definitely in.

• Counter-intuitive: But this is not just about one logic professor's incompetence. Another way to look at the structure of the problem is to see that, supposing Carr is out, we have to simultaneously hold true that "if Allen is out, Brown is out" and also "if Allen is out, Brown is in", seemingly incompatible statements. We resolve the apparent contradiction when we realise that Carr being out only presents a problem if Allen tries to go out, whereas if he stays in, we avoid any difficulty. We conclude correctly, "if Carr is out then Allen is in". Again, this is easier to see with modern logical methods, but certainly presented problems for Carroll's contemporaries, especially those unfamiliar with the work of Boole, de Morgan and others.

• Material implication: One final point relates to the connection with material implication, which is a technical term referring to the mainstream interpretation (today) of how conditionals should work in mathematical logic. The conditional ${\text{A}}\Rightarrow {\text{B}}$ ("A implies B") is False only when A is True yet B is False. The conditional is True otherwise -- firstly in the intuitive case when A is True and B is consequently True, but also whenever A is False, no matter what value B has. This formulation works nicely in maths, but it leaves natural language behind, because sentences like "If I have three arms then the moon is made of green cheese" have to be accounted as true, whereas for most people they are patent nonsense.

There are other philosophical approaches to implication, such as causal implication, where a causal connection is required between antecedent and consequent before regarding the conditional statement as true. While the Barbershop Paradox is easily resolved by applying material implication, it should be noted that this is not where the problem lies. The arguments concerned will might just as well if the implications are considered causally -- Brown has to accompany Allen for a cause (Allen's nervousness), and the three barbers cannot leave at the same time because the shop may not be left unattended. The real issues are as described above, correctly negating conditionals and realising the compatibility of ${\text{A}}\Rightarrow {\text{B}}$ and ${\text{A}}\Rightarrow \neg {\text{B}}$ so long as A is False.

Reworking of explanations in the article

Explanatory notes on original

When reading the original it may help to keep the following in mind:

• What Carroll called "hypotheticals" modern logicians call "logical conditionals".
• Uncle Joe concludes his proof reductio ad absurdum, meaning in English "proof by contradiction".
• What Carroll calls the protasis of a conditional is now known as the antecedent, and similarly the apodosis is now called the consequent.

Basic statements

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

Notation

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	AND	X and Y	∧	X ∧ Y
Disjunction	OR	X or Y	∨	X ∨ Y
Conditional	IF ... THEN	if X then Y	⇒	X ⇒ Y

(See also Table of mathematical symbols.)

Implication

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

Restatement

In the notation above, for instance, (¬A ∧ B) represents "Allen is out and Brown is in"

Uncle Jim gives us our two axioms:

1. There is at least one barber in the shop now (A ∨ B ∨ C)
2. Allen never leaves the shop without Brown (¬A ⇒ ¬B)

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(A1).	By H0 and A1, ¬A ⇒ B
But Axiom 2(A2) gives that it is universally true that IF Allen is Not in THEN Brown is Not in (it is 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

Examining Joe's argument

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.

Are the conditionals incompatible?

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.

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:

"If Allen is out, then Brown is out" "Allen is in or Brown is out"

(¬A ⇒ ¬B) (A ∨ ¬B)

Substituting this into

"IF Carr is out, THEN If Allen is also out Then Brown is in AND If Allen is out Then Brown is out."

¬C ⇒ ( (¬A ⇒ B) ∧ (¬A ⇒ ¬B) )

Which yields, with continued application of the law of implication,

"IF Carr is out, THEN if Allen is also out, Brown is in AND either Allen is in OR Brown is out." "IF Carr is out, THEN both of these are true: Allen is in OR Brown is in AND Allen is in OR Brown is out." "Carr is in OR both of these are true: Allen is in OR Brown is in AND Allen is in OR Brown is out."

¬C ⇒ ( (¬A ⇒ B) ∧ (A ∨ ¬B) ) ¬C ⇒ ( (A ∨ B) ∧ (A ∨ ¬B) ) C ∨ ( (A ∨ B) ∧ (A ∨ ¬B) )

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

"Carr is in OR Either Allen is in OR Brown is in, AND Carr is in OR Either Allen is in OR Brown is out." "Inclusively, Carr is in OR Allen is in OR Brown is in, AND Inclusively, Carr is in OR Allen is in OR Brown is out."

C ∨ (A ∨ B) ∧ C ∨ (A ∨ ¬B) (C ∨ A ∨ B) ∧ (C ∨ A ∨ ¬B)

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