2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 30 '20 at 19:03
  • $\begingroup$ Your step from 1 to 2 is wrong: you replaced the expression inside the brackets by its negation. $\endgroup$ Aug 31 '20 at 7:58
4
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

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.


$\endgroup$
2
$\begingroup$

They're equivalent.

Here is a proof:

enter image description here

This tree was generated here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.