Show $\forall x P(x) \land Q(x)$ has the same truth value as $\forall x P(x) \land \forall x Q(x)$

Question

Show $\forall x P(x) \land Q(x)$ has the same truth value as $\forall x P(x) \land \forall x Q(x)$.

I am able to show this when the universe of discourse is countable by

$\forall x P(x) \land Q(x)\equiv (P(x_1)\land Q(x_1))\land(P(x_2)\land Q(x_2))\land\dots(P(x_n)\land Q(x_n))\equiv P(x_1)\land P(x_2) \land \dots P(x_n) \land Q(x_1)\land Q(x_2) \land Q(x_n)\equiv \forall x P(x) \land \forall x Q(x)$

How would I show this when the universe of discourse is uncountable as I would not be able to expand as above?

Thanks!

Answer 1

You do this using a formal semantics, i.e. using the rules that govern when a statement is true or false.

In general, a universal statement $\forall x \phi(x)$ is true under some interpretation if and only if all objects of the domain of that interpretation satisfy the formula $\phi(x)$, or 'make the formula true'.

More formally, we can write $I \vDash \phi$ to write that interpretation $I$ makes statement $\phi$ true, and the formal semantics of the $\forall$ is such that:

$I \vDash \forall x \phi(x)$ if and only if for all objects $d \in D_I : I \vDash \phi[d]$

Here, $D_I$ is the domain of interpretation $I$

and $I \vDash \phi[d]$ is our way of writing that $d$ 'satisfies' formula $\phi(x)$. Note that $d$ is an object of the domain of the interpretation, and not a symbol of our language, and so we can not write $I \vDash \phi(d)$. But, we can work out $I \vDash \phi[d]$ as follows:

$I \vDash \phi[d]$ if and only if $I[d/c] \vDash \phi(c)$, where $c$ is a new constant that is being added to our language, and where $I[d/c]$ is the interpretation that 'extends' interpratation $I$: it has the same doamain as $I$, and interprets everything the same as $I$, but now that we have a new constant symbol, it in addition interprets $c$ as object $d$.

So note that this way, we can deal with uncountable domains, even as the language itself is countable.

OK, and now we can formally prove that $\forall x (P(x) \land Q(x)) \Leftrightarrow \forall x \ P(x) \land \forall x \ Q(x)$, i.e. that these statements are equivalent, i.e. that they always have the same truth-value.

In general, two statements $\phi$ and $\psi$ are equivalent if and only if for all possible interpretations $I$, we have that $I \vDash \phi$ if and only if $I \vDash \psi$

Well, consider any interpretation $I$ with domain $D_I$. We now have:

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

for all objects $d \in D_I$: $I \vDash (P(x) \land Q(x))[d]$ iff (as explained above)

for all objects $d \in D_I$: $I[d/c] \vDash P(c) \land Q(c)$ iff (by formal semantics of $\land$)

for all objects $d \in D_I$: $I[d/c] \vDash P(c)$ and $I[d/c] \vDash Q(c)$ iff (as explained above)

for all objects $d \in D_I$: $I \vDash P(x)[d]$ and $I[d/c] \vDash Q(x)[d]$ iff (pure logic)

for all objects $d \in D_I$: $I \vDash P(x)[d]$ and for all objects $d \in D_I$: $I[d/c] \vDash Q(x)[d]$ iff (by formal semantics of $\forall$)

$I \vDash \forall x \ P(x)$ and $I \vDash \forall x \ Q(x)$ (by formal semantics of $\land$)

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

which completes the formal semantical proof.

Slightly less technical would be to do:

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

for all objects $d \in D_I$: $I \vDash P[d] \land Q[d]$ iff (by formal semantics of $\land$)

for all objects $d \in D_I$: $I \vDash P[d]$ and $I \vDash Q[d]$ iff (pure logic)

for all objects $d \in D_I$: $I \vDash P[d]$ and for all objects $d \in D_I$: $I \vDash Q[d]$ iff (by formal semantics of $\forall$)

$I \vDash \forall x \ P(x)$ and $I \vDash \forall x \ Q(x)$ (by formal semantics of $\land$)

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

Finally, I would like to draw your attention to the 'pure logic' step. Note that here we are simply relying on our 'pure' logical and mathematical understanding of 'all ' and 'and' to justify what is effectively the same as what you are trying to show: that the universal distributes over the conjunction. So, if anyone is doubting that very equivalence, then you're up the creek. However, once you grant that equivalence, then we can also formally prove the formal equivalence of the formally represented expressions.

Answer 2

You just need to assume the following two axioms (for any infinity, not only countable infinity).

I.$ \hspace{0.3cm}\forall x P(x)\implies P(y)$

II.$ \hspace{0.3cm}\forall x(P(x)\implies Q(x))\implies (\forall xP(x)\implies \forall xQ(x))$

The proof is as follows. Since for any $x$ $$ P(x)\land Q(x)\implies P(x) \quad\text{and}\quad P(x)\land Q(x)\implies Q(x) $$ By axiom II, there is $$ \forall x(P(x)\land Q(x))\implies \forall xP(x)\quad\text{and}\quad \forall x(P(x)\land Q(x))\implies \forall xQ(x) $$ Thus $$ \forall x(P(x)\land Q(x))\implies \forall xP(x)\land \forall xQ(x) $$ This proves "$\implies$".

On the other hand, by axiom I $$ \forall xP(x)\implies P(y)\quad\text{and}\quad \forall xQ(x)\implies Q(y) $$ So for any $y$, there is $$ \forall xP(x)\land \forall xQ(x)\implies P(y)\land Q(y) $$ By axiom II, this means $$ \forall y(\forall xP(x)\land \forall xQ(x))\implies \forall y(P(y)\land Q(y)) $$ Since $y$ is not bounded by the left of above formula, there is $$ \forall x(P(x)\land \forall xQ(x))\implies \forall y(P(y)\land Q(y)) $$ This proves "$\impliedby$".