Proof of $\exists x(P(x) \Rightarrow \forall y P(y))$

Question

Exercise 31 of chapter 3.5 in How To Prove It by Velleman is proving this statement: $\exists x(P(x) \Rightarrow \forall y P(y))$.

(Note: The proof shouldn't be formal, but in the "usual" theorem-proving style in mathematics)

Of course I've given it a try and came up with this:

Proof: Suppose $\neg \exists x(P(x) \Rightarrow \forall y P(y))$. This is equivalent to $\forall x(P(x) \wedge \neg \forall y P(y))$, and since the universal quantifier distributes over conjunctions, it follows that $\forall x P(x)$ and $\forall x \neg \forall y P(y)$. Thus, for any $x_0, \neg \forall y P(y)$. But this contradicts $\forall x P(x)$, therefore $\exists x(P(x) \Rightarrow \forall y P(y))$.

I'm not sure if the condradiction is legal, so I'd like to know if there are any flaws in my proof.

Thanks!

Answer 1

This is the drinker's paradox:

"In every (populated) bar there is a person such that, if that person is drinking, then everyone is drinking".

It takes advantage of the 2 cases of vacuous implication:

• (1) "False implies anything"
• (2) "Anything implies true"

So divide the theorem into 2 cases:

Case (1): Someone is not drinking. Then that person is an example of vacuous implication; specifically, if a person who is not drinking is drinking, then anything follows.

Case (2): Everyone is drinking. That is the other case of vacuous implication, if "anything" then everyone is drinking.

There error in your given proof is that you haven't explicitly stated the domain of $x$. In an empty universe, $\forall x ~~(p(x))$ is true no matter what $p$ is.

Answer 2

Your proof by contradiction is valid.

To confirm the result, observe:

$$\begin{align} \exists x\Big(P(x) &\to \big(\forall y \;P(y)\big)\Big) \\ &\Updownarrow &\text{implication equivalence}\\ \exists x \Big(\neg P(x) &\vee \big(\forall y \;P(y)\big)\Big) \\ & \Updownarrow & \text{quantifier movement}\\ \big(\exists x \;\neg P(x)\big) &\vee \big(\forall y\; P(y)\big) \\ & \Updownarrow & \text{quantifier negation}\\ \neg \big(\forall x\; P(x)\big) &\vee \big(\forall y\;P(y)\big) \\ &\Updownarrow & \text{change of variable}\\ \neg \big(\forall x\; P(x)\big) &\vee \big(\forall x\;P(x)\big) \\ &\Updownarrow & \text{tautology: } \neg A \vee A \\ & {\large\top} \end{align}$$

Remark:

The statement looks like it says "if there is one example then it's true for all".   However, that would be: $\big(\exists x\; P(x)\big)\to\big(\forall y\;P(y)\big)$, which is not the same thing at all.