Problem in solving a logical Equivalence

Question

Prove or disprove the following equivalence: $$ ∀x Px \wedge ∀x Qx \Leftrightarrow ∀x ∃y ( Px \vee Qy ) $$

I've tried it, but I do not know how to solve logical equivalences involving quantifiers.

Answer 1

(1) Some Background

First let us recall some well-known equivalences:

(i) $\vDash ∀x(ϕ ∧ ψ) ↔ ∀xϕ ∧ ∀xψ$

(ii) $\vDash ∃x(ϕ ∨ ψ) ↔ ∃xϕ ∨ ∃xψ$

Since ∀ and ∃ are generalizations of ∧ and ∨ respectively, we observe that (i) and (ii) simply states that ∀ (∃) can be distributed over ∧ (∨). The same holds for their respective distribution over ∨ and ∧, but only if the condition below is met:

(iii) $\vDash ∀x(ϕ ∨ ψ) ↔ ∀xϕ ∨ ψ$, if $x \notin FV(ψ)$

(iv) $\vDash ∃x(ϕ ∧ ψ) ↔ ∃xϕ ∧ ψ$, if $x \notin FV(ψ)$

And finally:

(v) $\vDash \forall xϕ ↔ ϕ$, if $x \notin FV(ϕ)$

(vi) $\vDash ∃xϕ ↔ ϕ$, if $x \notin FV(ϕ)$

which simply means that a superfluous quantification can always be eliminated.

---

(2) The Answer

After considering those equivalences shown above, we can start by noticing that

\begin{align} ∀x Px \wedge ∀x Qx & \Leftrightarrow ∀x ∃y ( Px \vee Qy ) \tag{1}\\ & \Leftrightarrow ∀x (∃yPx \vee ∃yQy ) \tag{2}\\ &\Leftrightarrow ∀x (Px \vee ∃yQy ) \tag{3}\\ &\Leftrightarrow ∀x Px \vee ∃yQy \tag{4}\\ \end{align}

(that is, in (1) we apply (ii); in (2) we apply (vi); since $x \notin FV(∃yQy)$ we use (iii) in (3) and we obtain (4).)

Hence our original equivalence means that

$∀x Px \wedge ∀x Qx \Leftrightarrow ∀x Px \vee ∃yQy$

Now isn't easier to construct an interpretation where this does not hold?

• Let $M \vDash ∀x Px$: isn't possible that $M \vDash ∃yQy$ but not $M \vDash ∀x Qx$?

Can you work on the details?