Proving that universal quantification distributes over conjunction

Question

Show that $$\vdash [\forall x(P(x))\wedge \forall x(Q(x))]\to \forall x[P(x)\wedge Q(x)]$$

My answer: by Q_{1}, it is the case that $\forall x \phi\to\phi_{t}^{x}$ so we have

$$\forall x P(x)\to P(t)$$

We also have

$$\forall x Q(x)\to Q(t)$$

Then $$ (\forall x)P(x)\wedge(\forall x)Q(x)\to P(t)\wedge Q(t)$$ and by QR $ P(x)\wedge Q(x)\to (\forall x)P(x)\wedge Q(x)$

so we get $$\vdash [(\forall x)(P(x))\wedge(\forall x)Q(x))]\to(\forall x)[P(x)\wedge Q(x)]$$

it is correct?

Answer 1

A formal proof, according to

• Christopher Leary, A Friendly Introduction to Mathematical Logic (2000)

is :

1) $\forall xP(x) \land \forall xQ(x)$ --- premise

2) $\forall xP(x)$ --- from 1) by (PC) : $p \land q \vDash p$

3) $\forall xQ(x)$ --- from 1) by (PC) : $p \land q \vDash q$

4) $P(x)$ --- from quantifier axiom (Q1) and 2) by modus ponens

5) $Q(x)$ --- from quantifier axiom (Q1) and 3) by modus ponens

6) $P(x) \land Q(x)$ --- from 4) and 5) by (PC) : $p,q \vDash p \land q$

7) $(\forall xP(x) \land \forall xQ(x)) \rightarrow (P(x) \land Q(x))$ --- from 1) and 7) by Deduction Theorem

8) $(\forall xP(x) \land \forall xQ(x)) \rightarrow \forall x(P(x) \land Q(x))$ --- from 7) by (QR) : $\psi \rightarrow \phi \vdash \psi \rightarrow \forall x \phi$, $x$ not free in $\psi$ [in our case, $\psi$ is : $\forall xP(x) \land \forall xQ(x)$].

Answer 2

The first step of your proof is not very clear, and in fact appears to be using what you are trying to prove to justify the step.

Lets try a simple proof by contradiction for some variety.

1. Assume $\neg ([\forall x(P(x))\wedge \forall x(Q(x))]\to \forall x[P(x)\wedge Q(x)])$

2. $[\forall x(P(x))\wedge \forall x(Q(x))] \wedge \neg \forall x[P(x)\wedge Q(x)]$ by the definition of $\to$ and DeMorgan the $\neg$ over the $\lor$.

3. $[\forall x(P(x))\wedge \forall x(Q(x))] \wedge \exists x \neg[P(x)\wedge Q(x)]$ by the definition of $\neg \forall$

4. $[\forall x(P(x))\wedge \forall x(Q(x))] \wedge \neg[P(t)\wedge Q(t)]$ by existential instantiation.

5. $[\forall x(P(x))\wedge \forall x(Q(x))]\wedge [\neg P(t) \lor \neg Q(t)]$ by DeMorgan

6. $ (\forall x(P(x))\wedge \forall x(Q(x)) \wedge \neg P(t)) \lor (\forall x(P(x))\wedge \forall x(Q(x)) \wedge \neg Q(t)))$ Distribute $\wedge$ over $\lor$

7. Since $t$ is some object in the domain of discourse, $\forall x(P(x)) \land \neg P(t)$ is a contradiction, and by the same argument $\forall x(Q(x)) \land \neg Q(t)$.