Dealing with Quantifiers and Logic Connectives

Question

I was wanting to formally prove how ∀x(P(x)∧Q(x)))≡∀xP(x)∧∀xQ(x). Any help would be much appreciated.

Answer 1

We can use formal semantics to prove this. So, let's first define what it means for two statements $\phi$ and $\psi$ to be equivalent: it means that for every interpretation (or structure) $I$: $I$ sets $\phi$ to true (we write this as $I \vDash \phi$) if and only if $I$ sets $\psi$ to true ($I \vDash \psi$).

In this case we are dealing with some universals, and the formal semantics for the universal is as follows:

$I \vDash \forall x \phi(x)$ iff for any object $d$ in the domain of $I$: $I[c/d] \vDash \phi(c)$ where $c$ is a new constant that $I[c/d]$ interprets as $d$. (that is: $c$ does not occur in the original language, and so is not interpreted by $I$, but $I[c/d]$ extends $I$ by interpreting $c$ as object $d$). This is really just a very technical way of saying: $I$ sets $\forall x \phi(x)$ to True iff $\phi$ holds for every objects in the domain. E.g.: $\forall x P(x)$ iff all objects in the domain have the property that $I$ interprets the predicate symbol $P$ as.

OK, so now let's look at your specific case. We have for any interpretation $I$:

$I \vDash \forall x (P(x) \land Q(x))$ iff (semantics $\forall$)

$I[c/d] \vDash P(c) \land Q(c)$ for every $d \in I$ iff (semantics $\land$)

$I[c/d] \vDash P(c)$ and $I[c/d] \vDash Q(c)$ for every $d \in I$ iff (semantics $\forall$)

$I \vDash \forall x P(x)$ and $I \vDash \forall x Q(x)$ iff (semantics $\land$)

$I \vDash \forall x P(x) \land \forall x Q(x)$

So, since we have shown that for any interpretation $I$:

$I \vDash \forall (P(x) \land Q(x))$ iff $I \vDash \forall x P(x) \land \forall x Q(x)$

we have that

$\forall x (P(x) \land Q(x)) \equiv \forall x \ P(x) \land \forall x \ Q(x)$

Alternatively, we can try to show the equivalence using a (sound) proof system. There are many proof systems though, so if you need to use a particular one, you may want to let us know your rules, or try to transform the following formal proof into one that your system is happy with: