Use propositional logic to solve

Question

Argue that (∀x(P(x) ∨ ∃y P(y))) is equivalent to ∃x P(x)

Can anyone please explain how to do it?

Answer 1

$\forall x\, (P(x) \lor \exists y\,P(y)) \\ \forall x\, (P(x) \lor (\neg P(x) \land \exists y\, P(y)) \\ \forall x\, (\exists y\, P(y)) \\ \exists y\, P(y) \\ \therefore \exists x\, P(x) $

Basically $\forall x\, (P(x) \lor \exists y\,P(y))$ reads: for all values $x$ either the proposition holds, or there's some other value ($y$) for which it holds.   Which can be simplified to: there exists some value for which the proposition holds.

Answer 2

Don't be impressed by the formula.

When you just apply rules, you can observe

1. That x and y have nothing in common, so $\forall x:(P(x) \vee \exists y:P(y))$ rewrites to $(\forall x:P(x)) \vee (\exists y:P(y))$.
2. That x can be substituted for y in $\exists y:P(y)$
3. $\forall x:P(x) \vee \exists x:P(x) \equiv \exists x:P(x)$

(If my memory serves me well)