After learning multiple and nested quantifiers, we now study how negation passes through several quantifier layers. Negation of nested quantified statements follows a simple rule: each $\forall$ changes to $\exists$, each $\exists$ changes to $\forall$, and the final predicate is negated. The difficulty lies in simplifying the final predicate correctly. In this lesson, negation of nested quantified statements will be applied to symbolic statements and standard mathematical definitions. :::definition[Principle of Negating Nested Quantifiers] When a quantified statement is negated, each quantifier changes as the negation passes through it: $$\begin{align*} \neg\forall x\,p(x)&\leftrightarrow\exists x\,\neg p(x),\\ \neg\exists x\,p(x)&\leftrightarrow\forall x\,\neg p(x). \end{align*}$$ Thus, $\forall$ changes to $\exists$, $\exists$ changes to $\forall$, and the final predicate is negated. ::: :::solved-problem Let $p(x,y)$, $q(x,y)$, and $r(x,y)$ be open statements. Negate and simplify $\forall x\exists y[((p(x,y)\land q(x,y))\to r(x,y))]$. ::: :::solution Given that the statement is $$\begin{equation*} \forall x\exists y[((p(x,y)\land q(x,y))\to r(x,y))]. \end{equation*}$$ To negate it, write $$\begin{equation*} \neg\{\forall x\exists y[((p(x,y)\land q(x,y))\to r(x,y))]\}. \end{equation*}$$ Move the negation through the first quantifier: $$\begin{equation*} \exists x\neg\{\exists y[((p(x,y)\land q(x,y))\to r(x,y))]\}. \end{equation*}$$ Move the negation through the second quantifier: $$\begin{equation*} \exists x\forall y\neg[((p(x,y)\land q(x,y))\to r(x,y))]. \end{equation*}$$ The negation of $A\to B$ is $A\land\neg B$. Here $A=p(x,y)\land q(x,y)$ and $B=r(x,y)$. Therefore the negation is $$\begin{equation*} \exists x\forall y[(p(x,y)\land q(x,y))\land\neg r(x,y)]. \end{equation*}$$ ::: :::definition[Negation of a Nested Quantified Implication] The negation $$\begin{equation*} \neg\{\forall x\exists y[((p(x,y)\land q(x,y))\to r(x,y))]\} \end{equation*}$$ is equivalent to $$\begin{equation*} \exists x\forall y[(p(x,y)\land q(x,y))\land\neg r(x,y)]. \end{equation*}$$ ::: :::solved-problem Negate the definition $\lim_{x\to a}f(x)=L$, where $$\begin{equation*} \forall \varepsilon>0\ \exists \delta>0\ \forall x[(0<|x-a|<\delta)\to(|f(x)-L|<\varepsilon)] \end{equation*}$$ defines the limit. ::: :::solution Given that $\lim_{x\to a}f(x)=L$ means $$\begin{equation*} \forall \varepsilon>0\ \exists \delta>0\ \forall x[(0<|x-a|<\delta)\to(|f(x)-L|<\varepsilon)]. \end{equation*}$$ To negate it, change each quantifier as the negation passes through: $$\begin{equation*} \exists \varepsilon>0\ \forall \delta>0\ \exists x\neg[(0<|x-a|<\delta)\to(|f(x)-L|<\varepsilon)]. \end{equation*}$$ The negation of the implication is $$\begin{equation*} (0<|x-a|<\delta)\land\neg(|f(x)-L|<\varepsilon). \end{equation*}$$ Since $\neg(|f(x)-L|<\varepsilon)$ is $|f(x)-L|\geq\varepsilon$, the negation becomes $$\begin{equation*} \exists \varepsilon>0\ \forall \delta>0\ \exists x[(0<|x-a|<\delta)\land(|f(x)-L|\geq\varepsilon)]. \end{equation*}$$ Hence $\lim_{x\to a}f(x)\neq L$ is represented by this statement. ::: :::solved-problem Let the universe for all variables be the set of all real numbers. Negate and simplify $\forall x\forall y[(x>y)\to(x-y>0)]$. ::: :::solution Given that the statement is $$\begin{equation*} \forall x\forall y[(x>y)\to(x-y>0)]. \end{equation*}$$ To negate it, $$\begin{equation*} \neg[\forall x\forall y[(x>y)\to(x-y>0)]] \end{equation*}$$ is equivalent to $$\begin{equation*} \exists x\exists y\neg[(x>y)\to(x-y>0)]. \end{equation*}$$ The negation of the implication is $$\begin{equation*} (x>y)\land\neg(x-y>0). \end{equation*}$$ Since $\neg(x-y>0)$ is $x-y\leq 0$, the simplified negation is $$\begin{equation*} \exists x\exists y[(x>y)\land(x-y\leq 0)]. \end{equation*}$$ ::: When negating a nested quantified statement, do not try to change the final predicate first. Move the negation inward one quantifier at a time. After all quantifiers have been changed, simplify the remaining propositional form using De Morgan’s laws and the rule $\neg(p\to q)\leftrightarrow p\land\neg q$. This order prevents mistakes in statements with three or more quantifiers. Nested negation works best when each quantifier is changed in order. Choose a template and read the transformation from the outside inward. The calculator separates the quantifier changes from the final propositional simplification, so the last step is not skipped. Use it to check that the final predicate is also negated, not only the quantifier symbols. :::calculator[Nested Negation Stepper] ::: :::exercise Negate and simplify: $\forall x\forall y[(x>y)\to(x-y>0)]$; $\forall x\forall y[((x>0)\land(y=\log_{10}x))\to(x=10^y)]$; $\forall x\forall y[(x<y)\to\exists z(x<z<y)]$; $\forall x\forall y[(|x|=|y|)\to(y=x\lor y=-x)]$. ::: :::answer The negations are $\exists x\exists y[(x>y)\land(x-y\leq 0)]$, $\exists x\exists y[(x>0)\land(y=\log_{10}x)\land(x\neq 10^y)]$, $\exists x\exists y[(x<y)\land\forall z\neg(x<z<y)]$, and $\exists x\exists y[(|x|=|y|)\land(y\neq x)\land(y\neq -x)]$. ::: :::faq[Frequently Asked Questions] Q: What changes when a negation passes through $\forall$? A: The quantifier becomes $\exists$ and the negation moves inward. Q: What changes when a negation passes through $\exists$? A: The quantifier becomes $\forall$ and the negation moves inward. Q: What is the most common error? A: Forgetting to negate the final implication or connective after changing the quantifiers. ::: :::call-to-action[Negate Nested Statements] subtitle: Practise moving negation through every quantifier before studying unique existence. button: Next Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/unique-existence button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/multiple-and-nested-quantifiers :::