Show the semantic entailment ${(\forall x (\exists y (P(x) \lor Q(y))))} \vDash (\exists y (\forall x (P(x) \lor Q(y))))$ holds

Question

How do I prove the following entailment?

${(\forall x (\exists y (P(x) \lor Q(y))))} \vDash (\exists y (\forall x (P(x) \lor Q(y))))$

Answer 1

In general, we have $\phi \vDash \psi$ if and only if every model for $\phi$ (i.e. every interpretation $I$ that sets $\phi$ to True (which we write as $I \vDash \phi$)) is also a model for $\psi$, i.e iff for any $I$: If $I \vDash \phi$ then $I \vDash \psi$

OK, so let's take any interpretation $I$. We have:

If $I \vDash (\forall x (\exists y (P(x) \lor Q(y))))$

then by semantics of $\forall$:

For any $d \in D_I$ ($D_I$ is the domain of $I$): $I \vDash (\exists y (P([d]) \lor Q(y)))$ (you can't use $P(d)$, since $d$ is an object, rather than a symbol, so I use $P([d])$, where $[d]$ is a new individual constant that $I$ interprets as object $d$)

So by the semantics of $\exists$:

For any $d \in D_I$ there is some $d' \in D_I$ such that: $I \vDash P([d]) \lor Q([d'])$

Which by the semantics of $\lor$ means that:

For any $d \in D_I$ there is some $d' \in D_I$ such that: $I \vDash P([d])$ or $I \vDash Q([d'])$

Now, remember we want to show that $I \vDash (\exists y (\forall x (P(x) \lor Q(y))))$

Let's show this using a proof by contradiction, i.e. suppose that $I \not \vDash (\exists y (\forall x (P(x) \lor Q(y))))$

This means that there cannot be some $d_0 \in D_I$ such that $I \vDash Q([d_0])$, for if there would be, then we would have that for any $d \in D_I$: $I \vDash P([d])$ or $I \vDash Q([d_0])$, and thus by semantics of $\lor$ we would have that for any $d \in D_I$: $I \vDash P([d]) \lor Q([d_0])$, and thus by the semantics of $\forall$ we would have $I \vDash (\forall x (P(x) \lor Q([d_0])))$, and by the semantics of $\exists$ we would thus have $I \vDash (\exists y (\forall x (P(x) \lor Q(y))))$, which we assumed we didn't have.

So, how then can we still have that for any $d \in D_I$ there is some $d' \in D_I$ such that: $I \vDash P([d])$ or $I \vDash Q([d'])$? It must be because for any $d \in D_I$ we have $I \vDash P([d])$. As such we can pick just any $d_0 \in D_I$ and say that for any $d \in D_I$: $I \vDash P([d])$ or $I \vDash Q([d_0])$. So, by the semantics of $\forall$ we would have $I \vDash (\forall x (P(x) \lor Q([d_0])))$, and by the semantics of $\exists$ we would thus have $I \vDash (\exists y (\forall x (P(x) \lor Q(y))))$. However, this once again contradicts our assumption that $I \not \vDash (\exists y (\forall x (P(x) \lor Q(y))))$.

So, our assumption of $I \not \vDash (\exists y (\forall x (P(x) \lor Q(y))))$ leads to a contradiction, and thus we have $I \vDash (\exists y (\forall x (P(x) \lor Q(y))))$

OK, so we have shown that for any $I$: If $I \vDash (\forall x (\exists y (P(x) \lor Q(y))))$ then $I \vDash (\exists y (\forall x (P(x) \lor Q(y))))$

Therefore, $(\forall x (\exists y (P(x) \lor Q(y)))) \vDash (\exists y (\forall x (P(x) \lor Q(y))))$

(note: this tremendous pain-in-the-ass semantical proof is exactly why formal proofs are nicer: a formal proof would follow exactly this same line of reasoning, but would be a good bit more concise and readable!)

Answer 2

Hint: for a general bivariate relation $R(x,y)$, $\forall x(\exists y(R(x,y))$ is weaker than $\exists y(\forall x(R(x,y))$. This is because in the first case, every $x$ has a $y$ such that $R(x,y)$ is true, while in the second case, it has to be the same $y$. But in case the bivariate relation is factorizable, e.g. $R(x,y)=P(x)\lor Q(y)$, one can show that both statements equivalently factorize into

$$\forall x P(x)\lor \exists y Q(y).$$

One can then prove the proposition by showing

$$\forall x(\exists y(P(x)\lor Q(y))\;\leftrightarrow\;\forall x P(x)\lor \exists y Q(y)\;\leftrightarrow\exists y(\forall x(P(x)\lor Q(y)).$$