Nested Quantifiers

Nested quantifiers

By nested, we mean that a quantifier is in the scope of another quantifier. If we focus only on two quantifiers, there are four nesting possibilities. Assume an arbitrary domain $D$, with $n$ elements, and a predicate $P$, with two variables.

We know that,

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

Any such statement asserts that for every pair $(x,y)$ picked from $D, P(x,y)$ is true.

We also know that,

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

Every such statement asserts that we can pick at least one pair $(x,y)$ from $D$, such that $P(x,y)$ is true.

Now, let’s look at the remaining two cases. Let’s discuss them one by one.

For all $x$ there is a $y$

Let’s discuss the case when existential quantifier comes in the scope of universal quantifier, that is,

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

In such a case, the quantified statement asserts that for every element $x$ of the domain, there is at least one element $y$ (in the domain), such that $P(x,y)$ is true. Let’s look at a few example scenarios with such statements.

Examples

---

Let’s take the domain as the set of all people alive and the following predicate.

• $L(x,y)$: $x$ loves $y$.

---

Now, let’s quantify this predicate as follows:

• $\forall x \exists y L(x,y)$: Every person loves at least one person.

We can write it briefly as follows:

• $\forall x \exists y L(x,y)$: Everybody loves someone.

---

Again, take the domain as the set of all people alive and consider the following predicate:

• $M(y,x)$: $y$ is mother of $x$.

---

After quantification, we have,

• $\forall x \exists y M(y,x)$: Everybody has a mother.

---

Consider the set of integers as the domain and define the following predicate:

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

Now let’s quantify it as follows:

• $\forall x \exists y I(x,y)$: Every integer has an additive inverse.

---

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

• $S(x,y)$: $y=x^2.$

---

Now, let’s quantify it as follows:

• $\forall x \exists y S(x,y)$: Every integer has a square.

There is an $x$, such that, for all $y$

Now, let’s discuss the case when a universal quantifier comes in the scope of an existential quantifier, that is,

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

In such a case, the quantified statement asserts that there is at least one member $x$ of the domain, such that for every member $y$ of the domain, $P(x,y)$ is affirmative. Let’s look at some examples of such quantification.

Examples

Consider the set of integers as the domain and define the following predicate:

• $M(x,y)$: $x\times y=y.$

Let’s quantify $M$ as follows:

• $\exists x \forall y M(x,y)$: There is an integer $x$ if multiplied with any integer $y$, the result is $y$.

We can write it briefly as follows:

• $\exists x \forall y M(x,y)$: Integers have a multiplicative identity.

We are familiar that the multiplicative identity is one.

---

Let’s take the domain as the set of all people alive and define the following predicate:

• $L(x,y)$: $x$ loves $y$.

---

Now, let’s quantify this predicate as follows:

• $\exists x \forall y L(x,y)$: There is at least one person who loves everyone.

We can write it succinctly as follows:

• $\exists x \forall y L(x,y)$: Someone loves everybody.

---

Again, take the domain as the set of all people alive and define the following predicate:

• $F(x,y)$: $x$ is wealthier than $y$:

---

Now, quantify this predicate as follows:

• $\exists x \forall y F(x,y)$: Someone is wealthier than everyone.

Quiz

Multiple domains

Until now, we’ve seen only the scenarios where we took more than one variable from a single domain. There are many scenarios where each variable in the predicate has a different domain. Let’s look at a few examples to elaborate on this point further.

Examples

Here are a few examples.

---

Let’s consider the set of people and the set of tourist places.

Let’s define a predicate as follows:

• $P(x,y)$: $x$ is planning to visit $y$ this summer.

---

Notice that $x$ is from people and $y$ is from tourist places.

Let’s quantify this predicate as follows.

• $\forall x \exists y P(x,y)$: Everybody is planning to visit some tourist place this summer.

Now, let’s quantify the same predicate differently.

• $\exists y \forall x P(x,y)$: There is some tourist place that everybody is planning to visit this summer.

• $\forall x \forall y P(x,y)$: Everybody is planning to visit every tourist place this summer.

• $\exists x \exists y P(x,y)$: Someone is planning to visit some tourist place this summer.

Quantifiers as loops

Let’s assume a predicate $P$ and domain $D$. We can think of a universal quantifier as looping through $D$ and verifying that $P$ is true for every member. Similarly, we can think about existential quantifiers as looping through $D$ and confirming that $P$ is true for at least one member of it.

Let’s define two sets as follows.

• $A = \{$ Ahmad, John, Smith, Beth, Sara$\}$

• $B = \{$Apple, Mango, Grapes, Melon, Banana$\}$

Now, assume that $x\in A$ and $y\in B$. Let’s define a predicate.

• $P(x,y)$: $x$ likes to eat y.

Run the following code to see when each of $\forall x\forall y P(x,y), \exists x\exists y P(x,y), \forall x \exists y P(x,y),$ and $\exists x \forall y P(x,y)$ is true. We can change the variables A and B by adding or subtracting a few elements to play with this code.

Explanation

• Lines 1–2: We specify the domain for the variables x, and y.

• Lines 3–9: We loop through $A$ and $B$ and generate the proposition that needs to be true to prove $\forall x\forall y P(x,y)$ is true.

• Lines 10–16: We loop through $A$ and $B$ and generate the proposition that needs to be true to prove $\exists x\exists y P(x,y)$ is true.

• Lines 17–24: We loop through $A$ and $B$ and generate the proposition that needs to be true to prove $\forall x \exists y P(x,y)$ is true.

• Lines 25–32: We loop through $A$ and $B$ and generate the proposition that needs to be true to prove $\exists x \forall y P(x,y)$ is true.