# Why is this true? $(\exists x)(P(x) \rightarrow (\forall y) P(y))$

Why is this true?

$$\exists x\,\big(P(x) \rightarrow \forall y\:P(y)\big)$$

• Smullyan calls this the "drinker's paradox": there exists a person $p$ such that if $p$ drinks, then everyone drinks.
– MJD
Jun 5, 2013 at 21:14
• See my math blog posting, "The Drinker's Paradox" (dated June 3, 2014) at dcproof.wordpress.com Jun 3, 2014 at 20:56
• Equivalently there is a woman such that if she is pregnant then all women are pregnant. People who don't understand how "stupid" the mathematical implication is, really think that you are mocking them. Jun 19, 2023 at 7:02

Since this may be homework, I do not want to provide the full formal proof, but I will share the informal justification. Classical first-order logic typically makes the assumption of existential import (i.e., that the domain of discourse is non-empty). In classical logic, the principle of excluded middle holds, i.e., that for any $\phi$, either $\phi$ or $\lnot\phi$ holds. Since I first encountered this kind of sentence where $P(x)$ was interpreted as "$x$ is a bird," I will use that in the following argument. Finally, recall that a material conditional $\phi \to \psi$ is true if and only if either $\phi$ is false or $\psi$ is true.

By excluded middle, it is either true that everything is a bird, or that not everything is a bird. Let us consider these cases:

• If everything is a bird, then pick an arbitrary individual $x$, and note that the conditional “if $x$ is a bird, then everything is a bird,” is true, since the consequent is true. Therefore, if everything is a bird, then there is something such that if it is a bird, then everything is a bird.
• If it is not the case that everything is a bird, then there must be some $x$ which is not a bird. Then consider the conditional “if $x$ is a bird, then everything is a bird.” It is true because its antecedent, “$x$ is a bird,” is false. Therefore, if it is not the case that everything is a bird, then there is something (a non-bird, in fact) such that if it is a bird, then everything is a bird.

Since it holds in each of the exhaustive cases that there is something such that if it is a bird, then everything is a bird, we conclude that there is, in fact, something such that if it is a bird, then everything is a bird.

## Alternatives

Since questions about the domain came up in the comments, it seems worthwhile to consider the three preconditions to this argument: existential import (the domain is non-empty); excluded middle ($\phi \lor \lnot\phi$); and the material conditional ($(\phi \to \psi) \equiv (\lnot\phi \lor \psi)$). Each of these can be changed in a way that can affect the argument. This might not be the place to examine how each of these affects the argument, but we can at least give pointers to resources about the alternatives.

• Existential import asserts that the universe of discourse is non-empty. Free logics relax this constraint. If the universe of discourse were empty, it would seem that $\exists x.(P(x) \to \forall y.P(y))$ should be vacuously false.
• Intuitionistic logics do not presume the excluded middle, in general. The argument above started with a claim of the form “either $\phi$ or $\lnot\phi$.”
• There are plenty of philosophical difficulties with the material conditional, especially as used to represent “if … then …” sentences in natural language. If we took the conditional to be a counterfactual, for instance, and so were considering the sentence “there is something such that if it were a bird (even if it is not actually a bird), then everything would be a bird,” it seems like it should no longer be provable.
• What if your domain is empty? That is, if $\exists x: Q$ is false for all statements $Q$? Jun 5, 2013 at 21:09
• @ThomasAndrews I just meant that the semantics of classical first order logic are typically defined in terms of a semantic interpretation function $\cal I$ and a variable mapping $\nu$ (which maps each variable to an element of the domain) that says that a sentence $\forall x. \phi(x)$ is true if and only if the interpretation function and every variable mapping $\nu'$ (which is the same as $\nu$ for each variable excepting that it may differ on $x$) make $\phi(x)$ true. Jun 5, 2013 at 21:27
• @ThomasAndrews Regarding $\exists x.(P(x) \lor \lnot P(x))$: this sentence is a theorem of classical first-order logic. It is easy to prove by contradiction. Suppose $\lnot\exists x.(P(x) \lor \lnot P(x))$. Then $\forall x.\lnot(P(x) \lor \lnot P(x)$, and this is equivalent to $\forall x.(\lnot P(x) \land \lnot\lnot P(x))$, which is equivalent to $\forall x.(\lnot P(x) \land P(x))$, which is false if the universe of discourse is non-empty, which existential import ensures. Therefore, $\exists x.(P(x) \lor \lnot P(x))$. Jun 5, 2013 at 21:37
• Well, non-empty discourse is what I'm talking about, so yes, if you assume some axiom that implies non-empty discourse, you are correct. Jun 5, 2013 at 22:24
• @ThomasAndrews Right, if you don't have existential import, then the sentence isn't necessarily true. Classical first-order logic doesn't require the assumption of “some axiom that implies non-empty discourse,” though; it's built into the inference rules. E.g., $\forall x.x=x$ should be true whether the universe is empty or not. But by universal elimination we may infer $a=a$, and from that, by existential introduction, $\exists x.x=x$, which implies that the domain is not empty. Free logic is a fascinating topic, and attempts to address these types of issues. Jun 5, 2013 at 23:56

Hint: The only way for $A\implies B$ to be false is for $A$ to be true and $B$ to be false.

I don't think this is actually true unless you know your domain isn't empty. If your domain is empty, then $\forall y: P(y)$ is true "vacuously," but $\exists x: Q$ is not true for any $Q$.

• I'm probably looking at this the wrong way. But suppose P(x) means x is a person. Doesn't it say "There exists something that is a person, so everything is a person."?
– Mats
Jun 5, 2013 at 20:54
• Instead of $A \Rightarrow B$, think of $\lnot A \lor B$. Jun 5, 2013 at 20:56
• That's the problem with implication in logic. $A\implies B$ is not a statement about "for all," it is a statement about specific instances. That can be a little confusing. If it is not true that all things are people, say, Z is my dog. Then since $P(Z)$ is false, we know that $P(Z)\implies Q$ for any statement $Q$. So $\exists x: P(x)\implies Q$. Jun 5, 2013 at 20:57
• So in my case, there exists something that isn't a person, hence the whole statement is true?
– Mats
Jun 5, 2013 at 21:00
• @Matts Not quite. $\forall x.(P(x) \to \forall y.P(y))$ says that "there is an $x$ such that if $x$ is a person, then …". It does not make the assertion that "there is an $x$ such that $x$ is a person." Jun 5, 2013 at 21:03

The examples with birds or drinkers were designed to make this simple logical truth sound paradoxical. Perhaps an example from ordinary mathematics will dispel the air of paradox. Consider a nonempty set $X$ and a function $f:X\rightarrow\{0,1\}$. Does the following proposition seem strange and unintuitive?

Theorem. There is an element $m\in X$ such that, if $f(m)=1$, then $f(x)=1$ for all $x\in X$.

Proof. The function $f$ has an absolute minimum. (The domain is nonempty and the range is a finite set of numbers.) Let $m$ be a point in $X$ where $f$ attains its minimum value. Clearly, if $f(m)=1$, then $f(x)=1$ for all $x$.

Really, all that logical formula is saying is that the truth value ($1$ for true, $0$ for false) of the "propositional function" $P(x)$ attains its minimum.

• The resolution of this paradox bothered me until I read this. It seemed irrelevant to declare $x$ to be "either anything, or a counterexample if there is one", since neither one is really a uniform description of a deciding element. But phrasing it like this makes it feel more acceptable since regardless of whether $f \cong 1$, the description of a deciding element is the same. Jun 5, 2013 at 23:39
• In mathematics, there's no such thing as an uniform description. Jun 17, 2013 at 14:35

Here's a different approach: this can be fairly-straightforwardly proved from simple boolean algebra, starting from a tautology.$$\quad$$ $$((\forall y)P(y)) \lor (\lnot (\forall x) P(x)) \\ ((\forall y)P(y)) \lor ((\exists x)\lnot P(x))\\ (\text{anything} \Rightarrow (\forall y)P(y)) \lor ((\exists x)(P(x) \Rightarrow \text{anything})) \\ ((\forall x)P(x) \Rightarrow (\forall y)P(y)) \lor ((\exists x)(P(x) \Rightarrow (\forall y)P(y))) \\ ((\exists x)(P(x) \Rightarrow (\forall y)P(y))) \lor ((\exists x)(P(x) \Rightarrow (\forall y)P(y))) \\ (\exists x)(P(x) \Rightarrow (\forall y)P(y))$$

In classical logic the following equivalence is logically valid: $$\exists x (\varphi\Rightarrow\psi)\Longleftrightarrow(\forall x\varphi\Rightarrow\psi)$$ providing that $x$ is a variable not free in $\psi$. So the formula in question is logically equivalent to $\forall xP(x)\Rightarrow\forall yP(y)$.

Looking at the poblem from a slightly different perspective. Either (i) all objects in the domain of discourse have property $P$, i.e. $\forall y P(y)$ is true or (ii) there is $a$ in the domain for which $P$ fails, i.e. $\neg P(a)$ is true. In (i) $P(x)\Rightarrow\forall y P(y)$ must be true, so $\exists x(P(x)\Rightarrow\forall y P(y))$ is true. In (ii) $P(a)\Rightarrow\forall y P(y)$ must be true, therefore the sentence in question must be true as well.

In mathematics, if not in philosophy, the domain of quantification is usually made explicit in statements. If we let the domain be some set $U$, your statement becomes

$$\exists x\in U (P(x) \Rightarrow \forall y\in U (P(y))$$

or equivalently

$$\exists x(x\in U \wedge (P(x) \Rightarrow \forall y(y\in U\Rightarrow P(y))))$$ Then you can formally prove this statement is true iff $U$ is non-empty as sketched here:

For non-empty $U$, consider two cases:

$$\forall y\in U (P(y))\lor \neg\forall y\in U (P(y))$$

In each case, obtain

$$\exists x\in U (P(x) \Rightarrow \forall y\in U (P(y))$$ For empty U, assume to the contrary that

$$\exists x\in U (P(x) \Rightarrow \forall y\in U (P(y))$$

Full text of formal proof at http://dcproof.com/Mats.htm

• @j4nbur53 You can use either sets or predicates to restrict the domains of quantification. For some reason, I find $x\in U$ easier to visualize that $U(x)$. In mathematical proofs, you would usually use a set. Oct 9, 2018 at 18:52
• @j4nbur53 Not a problem in this case. No axioms of set theory are used, so $\in U$ is just another predicate. Oct 10, 2018 at 3:38

The location of the parentheses is crucial here. Note that $(\exists x)(P(x) \Rightarrow (\forall y) P(y))$ is very different from $(\exists x)(P(x)) \Rightarrow (\forall y) P(y))$. To see why the former statement is true, consider its negation which is

$$\forall x (P(x) \wedge \neg \forall P(x)) \equiv \forall x(P(x) \wedge \exists x \neg P(x))$$

which is clearly false if your domain is nonempty. In classical logic, we restrict to nonempty domains, so your original statement will always be true.

Translate it to english:

In any universe of things, there can always be found an instance which, if it has some property, then all other things have that property.

For any given property, you can find an instance in a set of things to make it true. (As long as that set is not the empty set, by the way; existential assertions are false for empty sets.)

• If none of the things have the property, then you can choose any one of them. Call that chosen instance $a$. $P(a) \Rightarrow (\forall y) P(y)$ is vacuously true, because $P \Rightarrow Q$ is true whenever $P$ is false.

• If all of the things have the property, then you can also choose any of them to be the instance $a$. $P(a) \Rightarrow (\forall y) P(y)$ is then true because $P(a)$ is true, and $(\forall y) P(y)$ is true.

• If some things have the property but not others, then you just choose one which does not have the property to be the instance $a$. Then $P(a) \Rightarrow (\forall y) P(y)$ is, again, vacuously true on account of $P(a)$ being false.

But let's look at it by taking the contradiction and seeing where it leads: $\neg(\exists x)(P(x) \Rightarrow (\forall y) P(y))$

In any universe of things, there cannot be found an instance such that if it has some property, then all other things have that property.

we can move the negative inside: $(\forall x)\neg(P(x) \Rightarrow (\forall y) P(y))$

In any universe of things, for every one of its elements, it is false that if a given property holds true of the element, then it holds for all other elements.

Then we can integrate the $\neg$ into the formula by way of $\neg (Q \rightarrow P) = Q \land\neg P$ to arrive at: $(\forall x)(P(x) \land\neg (\forall y) P(y))$

But this asserts $P(x)$ for all $x$; i.e. that if we think of any property $P$, all things have that property! This is clearly absurd for any nonempty set; we can come up with all kinds of properties $P$ which holds only for some things in a set, or none at all.

To add a proof in Fitch style, natural deduction:

2  | |__________ ~Ex(Px -> VyPy)   New Subproof for ~ Introduction
3  | | |________ Pa                New Subproof for -> Introduction
4  | | | |_____b                   variable for Universal Introduction
5  | | | | |____ ~Pb               New Subproof for ~ Introduction
6  | | | | | |__ Pb                New Subproof for -> Introduction
7  | | | | | |   _|_               5,6 _|_ Introduction
8  | | | | | |   VyPy              7 _|_ Elimination
.  | | | | | <-------------------- end subpproof
9  | | | | |     Pb -> VyPy        6-8 -> Introduction
10 | | | | |     Ex(Px -> VyPy)    9 Existentional Introduction
11 | | | | |     _|_               2,10 _|_ Introduction
.. | | | | <---------------------- end subpproof
12 | | | |       ~~Pb              5-11 ~ Introduction
13 | | | |       Pb                12 ~~ Elimination
.. | | | <------------------------ end subpproof
14 | | |         VyPy              4-13 Universal Introduction
.. | | <-------------------------- end subpproof
15 | |           Pa -> VyPy        3-14 -> Introduction
16 | |           Ex(Px -> VyPy)    15 Existentional Introduction
17 | |          _|_                2,16 _|_ Introduction
.. | <---------------------------- end subpproof
18 |            ~~Ex(Px -> VyPy)   2-17 ~ Introduction
19 |            Ex(Px -> VyPy)     18 ~~ Elimination


This is the shortest I managed, I don't think a shorter proof using the standard introduction and elimination rules exist

For explanation I compare this "paradox" with:

If the last person has left the room, all people have left the room.

Therefore

There is a person if he has left the room, all people have left the room.

The first statement is a truism , so how can the last statement not be one?

• Note: This proof presumes that there is something in the domain of discourse which you may label as $a$. So it is only valid in non-empty domains. Apr 12 at 1:46

$\tag 1 \exists x \; [P(x) \Rightarrow \forall y \, P(y)]$

Claim: (1) is a tautology, since it leads to an equivalence chain that ends in a well-known tautology:

$\tag 2 \exists x \; [ \neg P(x) \, \text{ or } \, \forall y \, P(y)]$

$\tag 3 \exists x \; [ \neg P(x)] \, \text{ or } \, \forall y \, P(y)$

$\tag 4 \neg \, \forall x \, P(x) \, \text{ or } \, \forall y \, P(y)$

$\tag 5 \neg \, [\forall z \, P(z)] \, \text{ or } \, [\forall z \, P(z)]$

The equivalence chain ends with a tautology, so (1) must also be one.

We can go from (2) to (3) since the existential qualifier distributes over disjunction and $( \exists x) (\forall y) \, P(y) \equiv \forall y \, P(y)$.

In (5) the $[\;]$ brackets were put around identical expressions. It was not necessary to change both $x$ and $y$ to $z$ - they both were 'quantified away' and can be viewed as just logical placeholders.

Finally, this paradox can be viewed as a contortion of counterexample logic. The only useful tautology is (3); you can replace the $\text{or-disjunction}$ with $\text{XOR}$ (exclusive or).

Here is a sequent calculus style proof:

       ------------ (Id)
P(y) |- P(y)
--------------------- (Weak Right)
P(y) |- P(y), ∀yP(y)
--------------------- (⇒ Right)
|- P(y), P(y)⇒∀yP(y)
------------------------- (∃ Right)
|- P(y), ∃x(P(x)⇒∀yP(y))
--------------------------- (∀ Right)
|- ∀yP(y), ∃x(P(x)⇒∀yP(y))
------------------------------- (Weak Left)
P(z) |- ∀yP(y), ∃x(P(x)⇒∀yP(y))
-------------------------------- (⇒ Right)
|- P(z)⇒∀yP(y), ∃x(P(x)⇒∀yP(y))
------------------------------------- (∃ Right)
|- ∃x(P(x)⇒∀yP(y)), ∃x(P(x)⇒∀yP(y))
------------------------------------- (Contr Right)
|- ∃x(P(x)⇒∀yP(y))


It uses a multi-consequent sequent calculus, so possibly cannot be reduced to intuitionistic logic. Also the contraction structural rule shows that a substructural logic would possibly not do. These speculations could possibly substantiated by some non-classical logic model theoretic considerations.

This drinker's theorem can be simply derived and explained as the implication rule during prenex normal form conversion in classic logic as referenced here:

The rules for removing quantifiers from the antecedent are (note the change of quantifiers):

($$\forall$$x $$\phi$$) $$\rightarrow$$ $$\psi$$ is equivalent to $$\exists$$x($$\phi$$ $$\rightarrow$$ $$\psi$$)

The above rule is essentially an easy result of material conditional replacement plus null quantification rule since there's no free occurrences of $$x$$ in $$\psi$$. Now we simply replace formula $$\phi$$ and $$\psi$$ as follow:

$$\phi$$=P(x), $$\psi$$ =$$\forall$$y P(y)

Then we can have an equivalent proposition (from right hand side to left from above referenced first order equivalence) to prove that is:

($$\forall$$x P(x)) $$\rightarrow$$ $$\forall$$y P(y)

Now it's pretty obvious the last one is a tautological truth. By the way, the reference also contains another "unnatural" implication rule during normal form conversion:

($$\exists$$x $$\phi$$) $$\rightarrow$$ $$\psi$$ is equivalent to $$\forall$$x($$\phi$$ $$\rightarrow$$ $$\psi$$)

After some time it's not that hard to realize there's nothing unusual or mystic about above 2 seemingly unnatural equivalences.

Suppose otherwise. Then

$$\lnot\exists(Px\to \forall yPy).\tag{1}$$

Then for any $$a$$ in the domain, we have

$$\lnot(Pa\to \forall yPy).\tag{2}$$

The only way this can be the case is if

$$Pa\tag{3}$$

while

$$\lnot\forall yPy.\tag{4}$$

But $$(4)$$ means there exists a $$b$$ in the domain such that

$$\lnot Pb.\tag{5}$$

But $$(2)$$ holds for all elements of the domain; in particular,

$$\lnot(Pb\to \forall yPy),\tag{6}$$

which, as above, gives both $$Pb$$ and $$\lnot\forall yPy$$; in particular:

$$Pb.\tag{7}$$

But then $$(5)$$ contradicts $$(7)$$.

Taking contrapositive makes the formula easier to parse:

\begin{align}\exists x\big(\,P(x) \to\forall y P(y)\,\big) \tag1\\\iff\exists x\big(\,\exists y\lnot P(y)\to\lnot P(x)\,\big).\end{align}

So, the given sentence $$(1)$$ is equivalent to:

• “for some $$x,\quad$$ if some $$y$$ doesn't satisfy $$P,$$ then $$x$$ doesn't either”;

putting $$x:=y$$ here clearly shows that this sentence is true.

Alternatively, consider the predicate $$P(x),$$ which is either atomic or compound.

Assign $$s=1$$ if $$P(x)$$ is a logical validity, and $$s=0$$ otherwise. (In other words, pick the smallest truth value that $$P(x)$$ attains as the interpretation varies, and denote it by $$s.$$ )

Putting $$x:=s$$ into the given sentence $$(1)$$ shows that it is true.

Smullyan's Original Drinker Principle:

[T]here exists someone such that whenever he (or she) drinks, everybody drinks.

--R. Smullyan, "What is the name of this book?" p. 209

We begin by proving, for arbitrary predicate D and proposition Q:

$$\exists x: [D(x) \implies Q]$$

We make the very reasonable assumption that somewhere there exists even a single non-drinker. Then we would have:

$$\exists x: \neg D(x)$$

Applying existential specification, we can infer:

$$\neg D(a)$$

For any proposition $$Q$$ whatsoever, be it true or false, we also then have:

$$\neg D(a) \lor Q$$

Applying the definition of logical implication, we have:

$$D(a) \implies Q$$

Generalizing, we conclude:

$$\exists x: [D(x) \implies Q]$$

Note again that $$Q$$ need not even be true. It could be false or contradictory. Clearly, such constructs have very limited application in the "real world." Here, anything goes.

Example 1

As in Smullyan's original "Drinker Principle," we could set:

$$Q~\equiv ~ \forall y: D(y)$$

Here, $$Q$$ contradicts our original assumption!

As in Smullyan's original "Drinker Principle," we would have:

$$\exists x: [D(x) \implies \forall y: D(y)]$$

Example 2

Alternatively, as in in other popular versions of DP which explicitly mention a pub, we could set:

$$Q ~ \equiv ~ \forall y: [P(y) \implies D(y)]$$

Where "$$P(y)$$" mean y is in the pub.

Then we would have:

$$\exists x: [D(x) \implies \forall y: [P(y) \implies D(y)]]$$

Example 3

If, instead, we assume that not everyone is both a drinker and in the pub, we have:

$$\exists x: \neg [D(x) \land P(x)]$$

From which we can infer:

$$\exists x: [D(x) \land P(x) \implies Q]$$

For any predicates $$D$$ and $$P$$ and proposition $$Q$$.