Using predicate logic, prove $(\forall x) [P(x) \land Q(x)]\to (\forall x)P(x) \land (\forall x)Q(x)$.

Question

$$(\forall x) [P(x) \land Q(x)]\to (\forall x)P(x) \land (\forall x)Q(x)$$

I am having trouble understanding predicate calculus proofs. I am a beginner. Any help is welcomed!

Answer 1

You could use the method of analytic tableaux, like so

The tree was generated by this site: https://www.umsu.de/trees/.

Answer 2

You need to think of proofs in natural language. $P$ and $Q$ are properties about elements in your universe of discourse. The statement says that "If both $P$ and $Q$ are valid for every $x$, then $P$ is valid for every $x$, and $Q$ is valid for every $x$".

So to prove it, in natural language and in a very pedantic manner, would be something like

1. Suppose that both $P$ and $Q$ are valid for every $x$. We need to prove that, given an arbitrary $x$, $P$ is valid for $x$, and also that given any arbitrary $y$, $Q$ is valid at $x$.

2. We first will prove that, given arbitrary $x$, $P$ is valid at $x$. So let $x$ be arbitrary. By hypothesis, $P$ and $Q$ are valid for $x$.

3. In particular, $P$ is valid for $x$.

4. Since $x$ was arbitrary, $P$ is valid for all $x$.

5. (and 6.) And similarly, $Q$ is also valid for all $x$.

6. Therefore, $P$ is valid for all $x$, and $Q$ is valid for all $x$.

The formal proof is simply writing down the argument above in the language of first-order logic. Notice that the very first paragraph is a realization of the Deduction Theorem. That is, let us prove that $$\forall x(P(x)\land Q(x))\vdash(\forall xP(x))\land(\forall xQ(x))$$

The proof follows:

1. $$\forall x(P(x)\land Q(x))\tag{hypothesis}$$
2. $$P(x)\land Q(x)\tag{Universal instantiation of 1.}$$
3. $$P(x)\tag{simplification of 2.}$$
4. $$\forall xP(x)\tag{universal generalization of 3.}$$
5. $$Q(x)\tag{simplification of 3.}$$
6. $$\forall xQ(x)\tag{universal generalization of 5.}$$
7. $$(\forall xP(x))\land(\forall xQ(x))\tag{conjunction of 4. and 6.}$$

This proves $\forall x(P(x)\land Q(x))\vdash (\forall x P(x))\land(\forall xQ(x))$. By the Deduction Theorem, $$\hspace{0pt}\vdash\forall x(P(x)\land Q(x))\to\left[(\forall xP(x))\land(\forall xQ(x))\right]$$

Answer 3

Here is a formal proof using Fitch natural deduction:

The proof idea is similar to the one provided by Luiz Codeiro, but if we assume a rule system with a full set of elimination and introduction rules for all of the connectives, we don't need to make use of the deduction theorem: Instead we can show the derivability of the implication directly in one natural deduction proof by applying the $\to$-introduction rule as a last step after the subderivation of the consequent $\forall Px \land \forall Qx$ from the assumption $\forall x(P(x) \land Q(x))$.
In addition, we have different choice for the order of $\land$-eliminiation and $\forall$-introduction: We could do the $\forall$-introduction on $P(a)$ directly after extracting it from the conjunction and treat $Q(a)$ afterwards, or first eliminate both conjuncts and then apply $\forall$ on them, like I did; that is, we could swap the order of the lines 4 and 5.