Simple proof involving quantifiers

Question

Task: Prove this theorem: $ \exists x (P(x) \Rightarrow \forall yP(y) )$.

I got this far: I figured out this is equivalent to $\exists x (\neg P(x) \lor \forall yP(y) )$.

I don't understand however how I can go about completing the proof without any other extra information. I can't really assume anything about the statement $P$ can I?

Answer 1

You can't assume anything about $P$, nor do you have to. Note that because $x$ is not free in $\forall y P(y)$, $$ \exists x(\neg P(x)\lor \forall y P(y)) \equiv (\exists x \neg P(x)\lor \forall y P(y)). \tag{1} $$ Now recall that $\exists\neg \equiv \neg\forall$, so the righthand side of (1) is equivalent to $$ \text{(1)}_{RHS} \equiv (\neg \forall x P(x)\lor \forall y P(y)).\tag{2} $$ By changing variables, $$ \text{(2)}_{RHS} \equiv (\neg \forall y P(y)\lor \forall y P(y)),\tag{3} $$ which is a tautology, hence provable and valid. These are all equivalent to the lefthand side of (1), which, as you noticed, is equivalent to the formula you wish to prove.

Answer 2

$A\implies B$ which is logically equivalent to $\neg A \vee B$. Therefore $$ \exists x(A\implies B) $$ is logically equivalent to $$ \exists x(\neg A \vee B) $$ no matter what the statements $A$ and $B$ are.

Answer 3

Using a tableau expansion:

1. Start with: $ \neg (∃x(P(x)⇒∀yP(y)))$
2. The leading connective is $\neg$ then $∃$: $∀x \neg (P(x)⇒∀yP(y))$
3. Instantiate: $ \neg (P(a)⇒∀yP(y))$
4. The leading connective is $\neg$ then $⇒$: $ (P(a)\wedge \neg ∀yP(y))$
5. We now have three formulas: $∀x \neg (P(x)⇒∀yP(y))$, $ P(a)$ and $\neg ∀yP(y)$
6. Or: $∀x \neg (P(x)⇒∀yP(y))$, $ P(a)$ and $∃y \neg P(y)$
7. Introduce a witness term: $\neg P(b)$
8. Instantiate:$ \neg (P(b)⇒∀yP(y))$
9. Or: $ (P(b)\wedge \neg ∀yP(y))$
10. P(b) and $\neg P(b)$
11. Close the branch, hence the tableau.

This theorem is by the way the drinker's theorem. See Drinker paradox -Wikipedia