0

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:

Example

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.

Alan

Alan
  • 2,721
  • 2
  • 22
  • 38
  • 4
    See the [drinker's paradox](http://en.wikipedia.org/wiki/Drinker_paradox). – Git Gud Feb 11 '15 at 21:20
  • That's very interesting! Thanks, I'll have a look. – Alan Feb 11 '15 at 21:28
  • 1
    See also [this](http://math.stackexchange.com/questions/815154/cant-see-the-intuition-behind-the-validity-of-this-formula-exists-x-exists), [this](http://math.stackexchange.com/questions/807092/proof-of-drinker-paradox#comment1668017_807096) comment and [this](http://math.stackexchange.com/questions/412387/why-is-this-true-exists-xpx-rightarrow-forall-y-py) thread. – Git Gud Feb 11 '15 at 21:30

2 Answers2

2

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.

Hagen von Eitzen
  • 1
  • 30
  • 346
  • 631
1

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$

dtldarek
  • 36,931
  • 9
  • 54
  • 123