Provide the Proof for $\forall x\,\bigl ( P(x) \land Q(x)\bigr ) \leftrightarrow \forall x \,P(x) \land \forall x\, Q(x)$

Question

Provide the Proof for $$\forall x\,\bigl ( P(x) \land Q(x)\bigr ) \leftrightarrow \forall x \,P(x) \land \forall x\, Q(x)$$

This is all I got so far:

Assume $\forall x \,\bigl( P(x) \land Q(x) \bigr)$ is true in some Universe $U$. Then $x\, E \,P(x)$, $x\, E\, Q(x)$

I dont kno where to go from here :(.

Please help!

Answer 1

We prove it with Natural Deduction

i) For the "$\rightarrow$" part :

(1) $\forall x ( P(x) \land Q(x) )$ --- assumed

(2) $P(a) \land Q(a)$ --- from (1) by $\forall$-elim

(3) $P(a)$ --- from (2) by $\land$-elim

(4) $\forall x P(x)$ --- from (3) by $\forall$-intro

(5) $Q(a)$ --- from (2) by $\land$-elim

(6) $\forall x Q(x)$ --- from (5) by $\forall$-intro

(7) $\forall x P(x) \land \forall x Q(x)$ --- from (4) and (6) by $\land$-intro

(8) $∀x ( P(x) \land Q(x) ) \rightarrow (\forall x P(x) \land \forall x Q(x))$ --- from (1) and (7) by $\rightarrow$-intro .

ii) In the same way, we can prove the "$\leftarrow"$ part :

$(\forall x P(x) \land \forall x Q(x)) \rightarrow ∀x ( P(x) \land Q(x) )$.

---

Comment

For a "semantic" argument, we can prove it in this way.

Consider an interpretation $\mathcal I$ with domain (or universe) $U$.

From the assumption $\forall x ( P(x) \land Q(x) )$ we have that, for each object $a \in U$, the "predicate" $P(x) \land Q(x)$ holds for it; i.e. :

$P(a) \land Q(a)$ is true in the interpretation.

Thus, both $P(a)$ and $Q(a)$ are true.

But $a$ is an objcet whatever in the domain; thus also $\forall xP(x)$ and $\forall xQ(x)$ are true in the interpretation, and finally :

$\forall xP(x) \land \forall xQ(x)$

is true in $\mathcal I$.

But $\mathcal I$ is an interpretation whatever; thus, the above argument shows that :

$\forall x ( P(x) \land Q(x) ) \vDash \forall xP(x) \land \forall xQ(x)$

i.e. the RHS formula is true in every interpretation in which the LHS formula is.

This is the definition of logical consequence.

By properties of logical consequence, it follows that :

$\vDash \forall x ( P(x) \land Q(x) ) \rightarrow (\forall xP(x) \land \forall xQ(x))$.