Negation of Nested Quantified Statements

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.

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.

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

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.

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))]

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

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*}

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*}

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.

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)

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

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)]

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)

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.

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)]

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)]

The quantifier becomes

\exists

and the negation moves inward.

The quantifier becomes

\forall

and the negation moves inward.

Forgetting to negate the final implication or connective after changing the quantifiers.

BMLabs Mathematics

BMLabs Mathematics

Negation of Nested Quantified Statements

Negation of Nested Quantified Statements

NEGATING SEVERAL QUANTIFIERS

PRINCIPLE OF NEGATING NESTED QUANTIFIERS

NEGATION OF A NESTED QUANTIFIED IMPLICATION

A RELIABLE NEGATION PROCEDURE

NEGATING NESTED STATEMENTS STEP BY STEP

NESTED NEGATION STEPPER

FREQUENTLY ASKED QUESTIONS

NEGATE NESTED STATEMENTS

Introduction To Discrete Mathematics

Paths and Circuits