I have a question for my exam and I find it hard to understand.

I have to prove that the following formula is logically valid:


The professor told me to "push" all the symbols inside the brackets, and use the deduction theorem.

But I don't know how to do it, because I can't find the identities to push the "exist" symbol inside the brackets.

Your help is appriciated, thank you.


  • 4
    $\begingroup$ See the drinker's paradox. $\endgroup$ – Git Gud Feb 11 '15 at 21:20
  • $\begingroup$ That's very interesting! Thanks, I'll have a look. $\endgroup$ – Alan Feb 11 '15 at 21:28
  • 1
    $\begingroup$ See also this, this comment and this thread. $\endgroup$ – Git Gud Feb 11 '15 at 21:30

Assume $\forall yp(y)$. Then $p(x)\to\forall yp(y)$ is true for any $x$. If on th eother hand $\neg \forall yp(y)$, then $\exists y\neg p(y)$. Let $x$ be such an $y$ then again $p(x)\to\forall yp(y)$ is true, this time because the antecedent is false.

  • $\begingroup$ Thanks, sounds good, I'll try that now. $\endgroup$ – Alan Feb 11 '15 at 21:28

Perhaps he meant something like this:

\begin{align} \exists x\ \big(p(x) &\to \forall y\ p(y)\big) \\ \exists x\ \big(\neg p(x) &\lor \forall y\ p(y)\big) \\ \big(\exists x\ \neg p(x)\big) &\lor \big(\forall y\ p(y)\big) \\ \neg\big(\forall x\ p(x)\big) &\lor \big(\forall y\ p(y)\big) \\ \big(\forall x\ p(x)\big) &\to \big(\forall y\ p(y)\big) \\ \end{align}

Please note that the step from line 2 to 3 is not an equivalence, if the universe is empty, then line 3 is true, but line 2 is false.

I hope this helps $\ddot\smile$


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.