# Pulling universal quantifier out of parenthesis makes nonequivalent statement?

Assuming I have the statement ∀x(∀y¬Q(x,y)∨P(x)), can I pull the universal quantifier ∀y out of the parenthesis? Meaning, is this statement equivalent to ∀x∀y(¬Q(x,y)∨P(x)) ?

An approach I tried so far:

1. ∀x((∃y Q(x,y) ) => P(x)). (original eq.)
2. ∀x((∀y¬Q(x,y))∨P(x)) (De Morgan's application)
3. ∀x∀y(¬Q(x,y)∨P(x)). (Working off the assumption that taking out the ∀y is a valid operation).
4. ∀x∀y (Q(x,y) => P(x)) (Going backwards from the ¬P v Q definition of implication)

Statement 4 does not seem to be equivalent to statement 1, which suggests that pulling out the universal quantifier is not acceptable. I would greatly appreciate any confirmation of whether this is the case, and if so, what governs when quantifiers can be brought to the outside of the parenthesis.

• Btw, you can use MathJax to type equations: math.meta.stackexchange.com/questions/5020/…. Use dollar signs to enclose equations and backslashes for commands: \forall = $\forall$, \exists = $\exists$, etc. You can use detexify to find the name of a symbol. Aug 30 '20 at 19:03
• Your step from 1 to 2 is wrong: you replaced the expression inside the brackets by its negation. Aug 31 '20 at 7:58

For universal quantifier. In general, if $$x$$ apear in both $$A$$ and $$B$$ we have $$\exists xA(x)\to \forall xB(x)\Rightarrow\forall x(A(x)\to B(x))\tag{1}$$ $$\forall x(A(x)\to B(x))\not\Rightarrow \exists xA(x)\to \forall xB(x)\tag{2}$$ However, if $$x$$ not apear in $$B$$ we have $$\forall x(A(x)\to B)\Leftrightarrow\exists xA(x)\to \forall x B\tag{3}$$ The statement in question is similar to $$(3)$$, which is also valid. $$∀x∀y(Q(x,y)→P(x))\Leftrightarrow∀x(∃y Q(x,y)→P(x))\tag{4}$$ And we can formulate a direct proof for $$(4)$$ by nature deduction $$\def\fitch#1#2{\hspace{2ex}\begin{array}{|l}#1\\\hline#2\end{array}} \fitch{\forall x\forall y(Q(x,y)\to P(x))} {\fitch{\boxed{a}} {\forall y(Q(a,y)\to P(a))\\ \fitch{\exists y~Q(a,y)} {\fitch{\boxed{b}~Q(a,b)} {Q(a,b)\to P(a)\\ P(a)}\\ P(a)}\\ \exists y~Q(a,y)\to P(a)}\\ \forall x~(\exists y~Q(x,y)\to P(x))}\\$$ Hence $$\forall x\forall y(Q(x,y)\to P(x))\Rightarrow\forall x~(\exists y~Q(x,y)\to P(x))$$. For the another direction we have $$\fitch{\forall x(\exists y~Q(x,y)\to P(x))} {\fitch{\boxed{a}} {\exists y~Q(a,y)\to P(a)\\ \fitch{\boxed{b}~Q(a,b)} {\exists y~Q(a,y)\\ P(a)}\\ \forall y~(Q(a,y)\to P(a))}\\ \forall x\forall y~(Q(x,y)\to P(x))}$$ Therefore $$\forall x~(\exists y~Q(x,y)\to P(x))\Rightarrow \forall x\forall y(Q(x,y)\to P(x))$$. This proves $$(4)$$.

The original expression: $$\forall x~((\exists y~Q(x,y))\to P(x))$$ says "For any $$x$$ it holds that if some $$y$$ satisfies $$Q(x,y)$$, then $$P(x)$$ is satisfied."

Now either consequent is true for all $$x$$ or, whenever it is false, the antecedent is also false (ie for that $$x$$ no $$y$$ can satisfy $$Q(x,y)$$). Thus the expression equates to: $$\forall x~(\neg P(x)\to\forall y~\neg Q(x,y))$$

The final expression: $$\forall x~\forall y~(Q(x,y)\to P(x))$$ says: "For any $$x$$ and $$y$$, it holds that if $$Q(x,y)$$ then $$P(x)$$."

Now either consequent is true for all $$x$$ or, whenever it is false, the antecedent is also false; moreover false for all $$y$$ when $$P(x)$$ is false for some $$x$$. Thus the expression equates to: $$\forall x~\forall y~(\neg P(x)\to \neg Q(x,y))$$

Therefore the original and final expressions are equivalent.

They're equivalent.

Here is a proof:

This tree was generated here.