Prove $\exists x (P(x) \lor Q(x)) ≡ \exists x P(x) \lor \exists x Q(x)$.

Question

$$ \exists x (P(x) \lor Q(x)) ≡ \exists x P(x) \lor \exists x Q(x) $$

I have to prove this. I'm extremely new and yet to grasp the whole tautology logics. I believe, that $$ \exists x P(x) \lor \exists x Q(x) $$ requirement is that all integers are even OR all integers are odd (I'm using integers as a universe of discourse), but for $$ \exists x (P(x) \lor Q(x)) $$ For all $x$ where $x$ is an integers, $x$ is even OR $x$ is odd. I don't know how to further prove the whole statement, what could be the further proof of equivalency?

Answer 1

1. Prove that $∃x(P(x) ∨ Q(x)) \implies ∃xP(x) \lor ∃xQ(x)$

• Let $x=x_0$ be a value that satisfies $∃x(P(x) ∨ Q(x)) \implies P(x_0) \lor Q(x_0)$$\implies ∃xP(x) \lor ∃xQ(x)$ (namely, for $x=x_0$)

2. Prove that $∃xP(x) \lor ∃xQ(x) \implies ∃x(P(x) ∨ Q(x))$

• $∃xP(x) \lor ∃xQ(x)$ implies

  (a) $∃x=x_1$ s.t. $P(x_1) \implies P(x_1) \lor Q(x_1) \implies ∃x(P(x) \lor Q(x))$ (namely, for $x=x_1$)

  OR

  (b) $∃x=x_2$ s.t. $Q(x_2) \implies P(x_2) \lor Q(x_2) \implies ∃x(P(x) \lor Q(x))$ (namely, for $x=x_2$).

Answer 2

Let LHS be True.

Then there is $x_0$ in the universe s.t. $P(x_0) \lor Q(x_0)$ holds true.

WLOG, let $P(x_0)$ holds true.

Then the proposition $\exists x P(x)$ holds true for $x_0$.

And hence the proposition $\exists x P(x) \lor \exists x Q(x)$ holds true.

Similarly you can prove the other direction.