2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ It's correct. This is the Drinker's Paradox. Edit: See alternative informal proofs here and here. $\endgroup$ – Git Gud Jan 9 '15 at 19:10
  • 1
    $\begingroup$ math.stackexchange.com/questions/412387/… $\endgroup$ – MJD Jan 9 '15 at 19:28
  • $\begingroup$ For slight variation of DP (more intuitive IHMO), see my blog posting "The Drinker's Paradox" (originally posting June 3, 2014) at dcproof.wordpress.com $\endgroup$ – Dan Christensen Jan 11 '15 at 18:01
  • $\begingroup$ I actually already read all those links (including the blog posting) before asking here, looking for clues about the correctness of my proof $\endgroup$ – user2103480 Jan 11 '15 at 18:41
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There was no specified domain given in the exercise...Does that mean I have to divide my proof into "Case 1: Universe is empty, then vacuously true" and "Case 2: Universe is not empty, ... (rest of my proof above)" for the proof to be valid? $\endgroup$ – user2103480 Jan 9 '15 at 19:31
  • $\begingroup$ Case 1, universe is empty means that the statement is false. Remember that you negated your claim and it resulted in a $\forall$. But yes, you are otherwise correct. $\endgroup$ – DanielV Jan 9 '15 at 20:23
  • $\begingroup$ Oh, so the the theorem is only correct if the universe isn't empty? $\endgroup$ – user2103480 Jan 9 '15 at 20:29
  • $\begingroup$ You are the one studying proofs, why do you ask my opinion? It is true if you can prove it and it is false if you can disprove it. I can say that the definition of $\forall x ~~(p(x))$ makes it false when the universe is empty, no matter what $p$ is. The rest you should be able to prove. $\endgroup$ – DanielV Jan 9 '15 at 20:33
  • $\begingroup$ I'd say that, if the universe is empty, since $\forall x \in \emptyset (P(x))$ is always true and the negation of the statement is of the form $\forall x (P(x))$, the negation is always true. Thanks for your time, I'll probably accept the answer later for others to have a shot (you already got my +1). $\endgroup$ – user2103480 Jan 9 '15 at 21:12
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I believe the quantifier movement step is a bit of misleading. I think the relevant "axioms" would be $\exists x ~ (P(x) \lor Q(x)) \vdash (\exists x ~ P(x)) \lor (\exists x ~ Q(x))$, and that $\exists x \forall y Q(y) \vdash \forall y Q(y)$ in the case of a non empty universe. $\endgroup$ – DanielV Jan 13 '15 at 4:45
  • 1
    $\begingroup$ In a similar manner $\forall x ~ (P(x) \land Q(x)) \vdash (\forall x ~ P(x)) \land (\forall x ~ Q(x))$ and $\forall x \neg \forall y P(y) \vdash \neg \forall y P(y)$ are the "hinges" of my proof I guess $\endgroup$ – user2103480 Jan 13 '15 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.