Drinker paradox

The drinker paradox (also known as the drinker's theorem, the drinker's principle, or the drinking principle) is a theorem of classical predicate logic and not an actual paradox. Its apparently paradoxical nature comes from the way it is usually stated in natural language: There is someone in the pub such that, if he is drinking, then everyone in the pub is drinking. It seems counterintuitive that 1) there is a person who is causing the others to drink, or 2) there is a person such that all through the night that one person is always the last to drink. The first objection comes from confusing formal IF ... THEN statements with causation (see Correlation does not imply causation). The formal statement of the theorem is timeless, eliminating the second objection because the person the statement holds true for at one instant is not necessarily the same person it holds true for at any other instant. The actual theorem is

\exists x\in P.\ [D(x)\rightarrow \forall y\in P.\ D(y)].\,

where D is an arbitrary predicate and P is an arbitrary set. It was popularised by the mathematical logician Raymond Smullyan, who called it the "drinking principle" in his 1978 book What Is the Name of this Book?^[1]

Proofs

The proof begins by recognizing it is true that either everyone in the pub is drinking, or at least one person in the pub is not drinking. Consequently, there are two cases to consider:^[1]^[2]

Suppose everyone is drinking. For any particular person, it cannot be wrong to say that if that particular person is drinking, then everyone in the pub is drinking — because everyone is drinking. Because everyone is drinking, then that one person must drink because when that person drinks everybody drinks, everybody includes that person.^[1]^[2]
Otherwise at least one person is not drinking. For any nondrinking person, the statement if that particular person is drinking, then everyone in the pub is drinking is formally true: its antecedent ("that particular person is drinking") is false, therefore the statement is true due to the nature of material implication in formal logic, which states that "If P, then Q" is always true if P is false.^[1]^[2] (These kinds of statements are said to be vacuously true.)

A slightly more formal way of expressing the above is to say that, if everybody drinks, then anyone can be the witness for the validity of the theorem. And if someone does not drink, then that particular non-drinking individual can be the witness to the theorem's validity.^[3]

The proof above is essentially model-theoretic (can be formalized as such). A purely syntactic proof is possible and can even be mechanized (in Otter for example), but only for an equisatisfiable rather than an equivalent negation of the theorem.^[4] Namely, the negation of the theorem is

\neg [\exists x.\ [D(x)\rightarrow \forall y.\ D(y)]]\,

which is equivalent with the prenex normal form

\forall x\exists y.\ [D(x)\wedge \neg D(y)]\,

By Skolemization the above is equisatisfiable with

\forall x.\ [D(x)\wedge \neg D(f(x))]\,

The resolution of the two clauses $D(x)$ and $\neg D(f(x))$ results in an empty set of clauses (i.e. a contradiction), thus proving the negation of the theorem is unsatisfiable. The resolution is slightly non-straightforward because it involves a search based on Herbrand's theorem for ground instances that are propositionally unsatisfiable. The bound variable x is first instantiated with a constant d (making use of the assumption that the domain is non-empty), resulting in the Herbrand universe:^[5]

\{d,f(d),f(f(d)),f(f(f(d))),\ldots \}

One can sketch the following natural deduction:^[4]

${\cfrac {{\cfrac {{\cfrac {\forall x.\ [D(x)\wedge \neg D(f(x))]\,}{D(d)\wedge \neg D(f(d))}}\forall _{E}}{\neg D(f(d))}}\wedge _{E}\qquad {\cfrac {{\cfrac {\forall x.\ [D(x)\wedge \neg D(f(x))]\,}{D(f(d))\wedge \neg D(f(f(d)))}}\forall _{E}}{D(f(d))}}\wedge _{E}}{\bot }}\ \Rightarrow _{E}$

Or spelled out:

Instantiating x with d yields $[D(d)\wedge \neg D(f(d))]$ which implies $\neg D(f(d))$
x is then instantiated with f(d) yielding $[D(f(d))\wedge \neg D(f(f(d)))]$ which implies $D(f(d))$ .

Observe that $\neg D(f(d))$ and $D(f(d))$ unify syntactically in their predicate arguments. An (automated) search thus finishes in two steps:^[5]

$D(d)\wedge \neg D(f(d))$
$D(d)\wedge {\underline {\neg D(f(d))\wedge D(f(d))}}\wedge \neg D(f(f(d)))$

The proof by resolution given here uses the law of excluded middle, the axiom of choice, and non-emptiness of the domain as premises.^[4]

Explanation of paradoxicality

The paradox is ultimately based on the principle of formal logic that the statement $A\rightarrow B$ is true whenever A is false, i.e., any statement follows from a false statement^[1] (ex falso quodlibet).

What is important to the paradox is that the conditional in classical (and intuitionistic) logic is the material conditional. It has the property that $A\rightarrow B$ is true if B is true or if A is false (in classical logic, but not intuitionistic logic, this is also a necessary condition).

So as it was applied here, the statement "if he is drinking, everyone is drinking" was taken to be correct in one case, if everyone was drinking, and in the other case, if he was not drinking — even though his drinking may not have had anything to do with anyone else's drinking.

On the other hand, in natural language, typically "if ... then ..." is used as an indicative conditional.

History and variations

Smullyan in his 1978 book attributes the naming of "The Drinking Principle" to his graduate students.^[1] He also discusses variants (obtained by replacing D with other, more dramatic predicates):

"there is a woman on earth such that if she becomes sterile, the whole human race will die out." Smullyan writes that this formulation emerged from a conversation he had with philosopher John Bacon.^[1]
A "dual" version of the Principle: "there is at least one person such that if anybody drinks, then he does."^[1]

As "Smullyan's ‘Drinkers’ principle" or just "Drinkers' principle" it appears in H.P. Barendregt's "The quest for correctness" (1996), accompanied by some machine proofs.^[2] Since then it has made regular appearance as an example in publications about automated reasoning; it is sometimes used to contrast the expressiveness of proof assistants.^[4]^[5]^[6]

Non-empty domain

In the setting with empty domains allowed, the drinker paradox must be formulated as follows:^[7]

A set P satisfies

\exists x\in P.\ [D(x)\rightarrow \forall y\in P.\ D(y)]\,

if and only if it is non-empty.

Or in words:

If and only if there is someone in the pub, there is someone in the pub such that, if he is drinking, then everyone in the pub is drinking.

References

1 2 3 4 5 6 7 8 Raymond Smullyan (1978). What is the Name of this Book? The Riddle of Dracula and Other Logical Puzzles. Prentice Hall. chapter 14. How to Prove Anything. (topic) 250. The Drinking Principle. pp. 209–211. ISBN 0-13-955088-7.
1 2 3 4 H.P. Barendregt (1996). "The quest for correctness". Images of SMC Research 1996 (PDF). Stichting Mathematisch Centrum. pp. 54–55. ISBN 978-90-6196-462-9.
↑ Peter J. Cameron (1999). Sets, Logic and Categories. Springer. p. 91. ISBN 978-1-85233-056-9.
1 2 3 4 Marc Bezem, Dimitri Hendriks (2008). Clausification in Coq
1 2 3 J. Harrison (2008). "Automated and Interactive Theorem Proving". In Orna Grumberg; Tobias Nipkow; Christian Pfaller. Formal Logical Methods for System Security and Correctness. IOS Press. pp. 123–124. ISBN 978-1-58603-843-4.
↑ Freek Wiedijk. 2001. Mizar Light for HOL Light. In Proceedings of the 14th International Conference on Theorem Proving in Higher Order Logics (TPHOLs '01), Richard J. Boulton and Paul B. Jackson (Eds.). Springer-Verlag, London, UK, 378-394.
↑ Martín Escardó; Paulo Oliva. "Searchable Sets, Dubuc-Penon Compactness, Omniscience Principles, and the Drinker Paradox" (PDF). Computability in Europe 2010: 2.

Logical paradoxes

Self-reference	Barber Berry Bhartrhari's Court Crocodile Curry's Epimenides Grelling–Nelson Kleene–Rosser Liar Card Pinocchio Quine's Yablo's Richard's Russell's Socratic

Vagueness	Theseus' ship Sorites

Other paradoxes	Barbershop Catch-22 Drinker Entailment Lottery Raven Ross' Unexpected hanging

List of paradoxes

This article is issued from Wikipedia - version of the 10/24/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.