Negation of Nested Quantifiers

How to negate nested quantifiers

For a domain $D$, and predicate $P$, we know that,

$$\neg \forall x P(x)\equiv \exists x \neg P(x),$$

and

$$\neg \exists x P(x)\equiv \forall x \neg P(x).$$

This is due to the DeMorgan’s laws. If we have nested quantifiers, we can use the same knowledge to deal with them.

Negation of $\forall x \forall y P(x,y)$

Assume an arbitrary domain and predicate on two variables, both quantified universally.

We can apply DeMorgan’s law twice as follows.

$$\neg \forall x [\forall y P(x,y)] \equiv \exists x \neg[\forall y P(x,y)].$$

In the second step, we have,

$$\exists x \neg[\forall y P(x,y)]\equiv \exists x \exists y \neg P(x,y).$$

Therefore,

$$\neg \forall x \forall y P(x,y) \equiv \exists x \exists y \neg P(x,y).$$

Let’s look at some examples to see the effect of negation.

Examples

---

Assume the domain of integers and define the following predicate.

• $P(x,y)$: $x\times y>x + y.$

---

Let’s make a statement $s$ by quantifying $P$ as follows:

• $s=\forall x \forall y P(x,y)$: The product of any two integers is greater than their sum.

The truth value of $s$ is false. We can construct a counterexample by taking $x$ to be three and $y$ to be a negative one. Because $(3)\times(-1) \ngtr (3)+(-1)$, $s$ is false.

Let’s look at $\neg s$:

• $\neg s= \neg \forall x \forall y P(x,y).$

• $\neg s\equiv \exists x \exists y \neg P(x,y).$

• $\neg s$: There exists a pair of integers, such that, $x\times y \ngtr x+y.$

The truth value of $\neg s$ is true, as we have already observed that such a pair $(x=3,y=-1)$ exists.

---

Again, assume the domain of integers and define the following predicate:

• $P(x,y)$: $x>y \Rightarrow x^2>y^2.$

---

Let’s quantify $P$ to make a statement $t$ as follows:

• $t=\forall x \forall y P(x,y)$: For every pair of integers, the greater number has a greater square.

We can represent the negation of $t$ as follows:

• $\neg t\equiv \exists x \exists y \neg P(x,y)$: There exists a pair of integers such that the square of the greater number is not greater.

If we take $x=2$ and $y=-3$, we observe a counterexample for $t$.

$$\left(\left(2>-3\right) \land \left(4\le9\right)\right).$$

Therefore, $t$ is false and $\neg t$ is true.

Negation of $\exists x \exists y P(x,y)$

Apply DeMorgan’s law twice as follows:

$$\neg \exists x [\exists y P(x,y)] \equiv \forall x \neg[\exists y P(x,y)].$$

In the second step, we have,

$$\forall x \neg[\exists y P(x,y)]\equiv \forall x \forall y \neg P(x,y).$$

Therefore,

$$\neg \exists x \exists y P(x,y) \equiv \forall x \forall y \neg P(x,y).$$

Examples

Let’s go through some examples.

---

Take the domain of integers and define the following predicate:

• $P(x,y)$: $x^y > y^x.$

---

Let’s quantify the variables in $P$ to make a statement $r$ as follows:

• $r=\exists x \exists y P(x,y)$: There exists a pair of integers, $(a,b)$, such that, $a^b>b^a.$

If we look at $\neg r$, it will follow.

• $\neg r \equiv \forall x \forall y \neg P(x,y)$: For every pair $(a,b)$ of integers, $a^b \le b^a.$

If we take $x=3$ and $y=2$, we observe that, $3^2>2^3$.

So, $r$ is true and $\neg r$ is false.

---

Again, consider the domain of integers and define the following predicate:

• $P(x,y)$: $5x+2y=0.$

---

Let’s make a statement $g$ by quantifying $P$ as follows.

• $g=\exists x \exists y P(x,y)$: There exists a pair $(a,b)$ of integers, such that, $5a+2b=0.$

The negation of statement $g$ is as follows:

• $\neg g \equiv \forall x\forall y \neg P(x,y)$: For every pair $(a,b)$ of integers, $5a+2b \ne 0.$

Let’s see if $g$ is true or its negation. If we take $x=2$ and $y=-5$, we observe that $5x+2y$ evaluates to zero. Therefore, $g$ is true.

Negation of $\forall x \exists y P(x,y)$

Again, we deal with nested quantifiers by applying DeMorgan’s law twice.

$$\neg \forall x [\exists y P(x,y)] \equiv \exists x \neg[\exists y P(x,y)].$$

In the second step, we have,

$$\exists x \neg[\exists y P(x,y)]\equiv \exists x \forall y \neg P(x,y).$$

So,

$$\neg \forall x \exists y P(x,y) \equiv \exists x \forall y \neg P(x,y).$$

Examples

---

Take integers as the domain and define the following predicate:

• $P(x,y)$: $x + y = 0.$

---

Let’s make a statement $h$ by quantifying $P$ as follows:

• $h = \forall x \exists y P(x,y)$: For every integer $a$, we have an integer $b$ such that their sum is zero.

The negation of $h$ is as follows:

• $\neg h \equiv \exists x \forall y P(x,y)$: There is an integer whose sum with any integer is not zero.

If we take any non-zero integer as $x$, then by taking $y=-x$, their sum is zero. For $x=0$, take $y=0$. Therefore, $h$ is true.

---

Consider the set, $S$, of students enrolled in a discrete mathematics class and a set of grades $G=\{A,B,C,D,F\}.$ Taking these two sets, we define the following predicate:

• $P(x,y)$: $x$ has $y$ grade in discrete mathematics.

---

Let’s quantify $P$ to make a statement $g$ as follows:

• $g = \forall_{ x \in S} \exists_{ y \in G} P(x,y)$: Every student in the discrete mathematics class got some grade.

The negation of $g$ is as follows:

• $\neg g = \exists_{x\in S} \forall_{y \in G} \neg P(x,y)$: There is a student in the discrete mathematics class who got no grade.

Negation of $\exists x \forall y P(x,y)$

We can apply DeMorgan’s law twice as follows:

$$\neg \exists x [\forall y P(x,y)] \equiv \forall x \neg[\forall y P(x,y)].$$

In the second step, we have,

$$\forall x \neg[\forall y P(x,y)]\equiv \forall x \exists y \neg P(x,y).$$

So,

$$\neg \exists x \forall y P(x,y) \equiv \forall x \exists y \neg P(x,y).$$

Examples

---

Consider a town named Happyhill. Let $S$ be the set of people, and $B$ be the set of buildings in the Happyhill. With this, we can construct the following predicate.

• $P(x,y)$: $x$ is a post office, and $y$ can post his mail through it.

---

We can quantify $P$ to make a statement $s$ as follows.

• $s=\exists_{x \in B} \forall_{y \in S} P(x,y)$: There is at least one post office building in Happyhill, and everyone in Happyhill can post their mail through it.

We can write it in simple words as follows:

• $s=\exists_{x \in B} \forall_{y \in S} P(x,y)$: Happyhill has one or more post offices for everyone to post their mail.

We can negate $s$ as follows:

• $\neg s = \forall_{x \in B} \exists_{y \in S} \neg P(x,y)$: For every building, there is someone who can not post their mail through that building in Happyhill.

---

Considering the set of integers, we can construct the following predicate:

• $P(x,y)$ : $x$ is an additive inverse of $y$.

---

We can quantify $P$ to make a statement $t$ as follows:

• $t=\exists x \forall y P(x,y)$: There exists an integer that is an additive inverse of all integers.

We know that $t$ is a false statement. Let’s look at its negation:

• $\neg t = \forall x \exists y \neg P(x,y)$: Every integer is not additive inverse of some integer.

The negation of $t$ is true. We can take any integer; it is not an additive inverse of it’s successor.

Summary

Let’s summarize the results regarding the negation of nested quantifiers covered in this lesson.

$$\neg \forall x \forall y P(x,y) \equiv \exists x \exists y \neg P(x,y).$$

$$\neg \exists x \exists y P(x,y) \equiv \forall x \forall y \neg P(x,y).$$

$$\neg \forall x \exists y P(x,y) \equiv \exists x \forall y \neg P(x,y).$$

$$\neg \exists x \forall y P(x,y) \equiv \forall x \exists y \neg P(x,y).$$