After learning logical laws for quantified statements, we now study one of the most important transformations in predicate logic: negation. Negation of quantified statements changes the quantifier and negates the predicate. This is the formal version of the ordinary idea that “not all” means “at least one not,” and “none” means “all not.” In this lesson, negation of quantified statements will be simplified using quantifier rules, De Morgan’s laws, and the negation of implication. :::theorem[Negation of a Universal Statement] For any predicate $p(x)$, $$\begin{equation*} \neg[\forall x\,p(x)]\leftrightarrow\exists x\,\neg p(x). \end{equation*}$$ This means that “not all elements satisfy $p$” is equivalent to “there exists at least one element that does not satisfy $p$.” ::: :::proof Given that $p(x)$ is a predicate over a universe $U$. To prove that $\neg[\forall x\,p(x)]\leftrightarrow\exists x\,\neg p(x)$. The statement $\forall x\,p(x)$ means that every element of $U$ satisfies $p(x)$. Therefore $\neg[\forall x\,p(x)]$ means that it is not true that every element satisfies $p(x)$. Thus, at least one element of $U$ does not satisfy $p(x). Therefore$\exists x\,\neg p(x)$is true. The same reasoning in reverse shows that if$\exists x\,\neg p(x)$is true, then$\forall x\,p(x)$is false. Hence$\neg[\forall x\,p(x)]\leftrightarrow\exists x\,\neg p(x)$.$\square$::: :::theorem[Negation of an Existential Statement] For any predicate$p(x)$$, \begin{equation*} \neg[\exists x\,p(x)]\leftrightarrow\forall x\,\neg p(x). \end{equation*} This means that “there does not exist an element satisfying$$p$” is equivalent to “every element fails to satisfy$p$.” ::: :::definition[Negations of Negated Quantified Statements] For any predicate$p(x)$$, \begin{align*} \neg[\forall x\,\neg p(x)]&\leftrightarrow\exists x\,p(x),\\ \neg[\exists x\,\neg p(x)]&\leftrightarrow\forall x\,p(x). \end{align*} These follow by applying the basic quantifier-negation laws and double negation. ::: :::solved-problem Let the universe be the set of all integers. Let$$p(x):x$is odd and$q(x):x^2-1$is even. Negate$\forall x[p(x)\to q(x)]$. ::: :::solution Given that the statement is$\forall x[p(x)\to q(x)]$. To negate it, use$\neg[\forall xA(x)]\leftrightarrow\exists x\neg A(x)$$. Therefore, \begin{equation*} \neg[\forall x[p(x)\to q(x)]]\leftrightarrow\exists x\neg[p(x)\to q(x)]. \end{equation*} Since the negation of$$p(x)\to q(x)$is$p(x)\land\neg q(x)$$, the negation is \begin{equation*} \exists x[p(x)\land\neg q(x)]. \end{equation*} Thus, the negation is: there exists an odd integer$$x$such that$x^2-1$is not even. ::: :::solved-problem Let the universe be the set of all integers. Let$r(x):2x+1=5$and$s(x):x^2=9$. Negate$\exists x[r(x)\land s(x)]$. ::: :::solution Given that the statement is$\exists x[r(x)\land s(x)]$. To negate it, use$\neg[\exists xA(x)]\leftrightarrow\forall x\neg A(x)$$. Therefore, \begin{equation*} \neg[\exists x[r(x)\land s(x)]]\leftrightarrow\forall x\neg[r(x)\land s(x)]. \end{equation*} By De Morgan’s law, \begin{equation*} \neg[r(x)\land s(x)]\leftrightarrow\neg r(x)\lor\neg s(x). \end{equation*} Hence the simplified negation is \begin{equation*} \forall x[\neg r(x)\lor\neg s(x)]. \end{equation*} ::: :::solved-problem Determine whether the proposed negation is correct. Statement: for all real numbers$$x,y$, if$x^2>y^2$, then$x>y$. Proposed negation: there exist real numbers$x,y$such that$x^2>y^2$but$x\leq y$$. ::: :::solution Given that the original statement is \begin{equation*} \forall x\forall y[(x^2>y^2)\to(x>y)]. \end{equation*} To negate it, apply the negation rules: \begin{equation*} \neg[\forall x\forall yA(x,y)]\leftrightarrow\exists x\exists y\neg A(x,y). \end{equation*} Therefore the negation is \begin{equation*} \exists x\exists y\neg[(x^2>y^2)\to(x>y)]. \end{equation*} Since the negation of$$p\to q$is$p\land\neg q$$, this becomes \begin{equation*} \exists x\exists y[(x^2>y^2)\land(x\leq y)]. \end{equation*} Therefore the proposed negation is correct. For example,$$x=-2$and$y=1$satisfy$x^2=4>1=y^2$but$-2\leq 1$. ::: :::exercise Negate each statement and simplify:$\exists x[p(x)\lor q(x)]$;$\forall x[p(x)\land\neg q(x)]$;$\forall x[p(x)\to q(x)]$;$\exists x[(p(x)\lor q(x))\to r(x)]$. ::: :::answer The simplified negations are$\forall x[\neg p(x)\land\neg q(x)]$,$\exists x[\neg p(x)\lor q(x)]$,$\exists x[p(x)\land\neg q(x)]$, and$\forall x[(p(x)\lor q(x))\land\neg r(x)]$. ::: :::faq[Frequently Asked Questions] Q: What happens to$\forall$under negation? A: It becomes$\exists$, and the predicate is negated. Q: What happens to$\exists$under negation? A: It becomes$\forall$, and the predicate is negated. Q: How do we negate an implication inside a quantifier? A: Use$\neg(p\to q)\leftrightarrow p\land\neg q$. ::: :::call-to-action[Practise Quantifier Negation] subtitle: Simplify negated quantified statements before moving to multiple and nested quantifiers. button: Next Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/multiple-and-nested-quantifiers button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/predicates-and-quantifiers/logical-laws-for-quantified-statements :::