1.4 Nested Quantifiers

DEFINITIONS:

It is existed where by one quantifier is within the scope of another.

Example: ∀x∃y(x+y=0) can be translated as

              ∀x Q(x) where Q(x) is ∃y P(x,y) and P(x,y) is x+y=0

Solving Stated Involving Nested Quantifers

Assume that the domain x,y є R, then

①     ∀x∀y(x+y=y+x) shows that x+y=y+x for all real number of x and y (commutative law)

②     ∀x∀y(x+y=0) shows that for all real number of x, there is a real number y such that x+y=0 (additive inverse)

③     ∀x∀y∀z(x+(y+z)=(x+y)+z) shows associative law for addition of real numbers.

To prove that ∀x∀y P(x,y) is true, we loop through the values for x, and for each x, we loop through the values through y; if it’s true if all values of x,y is true.

Order of Nested Quantifiers

The orders of nested quantifiers are important unless all the quantifiers are of universal quantifiers or all are existential quantifiers.

Statement	True Condition	False Condition
∀x∀y P(x,y) ∀y∀x P(x,y)	P(x,y) is true for every pair x,y.	There is one pair x,y for which P(x,y) is false.
∀x∃y P(x,y)	For every x, there is a y solution for which P(x,y) is true.	There is a x such that P(x,y) is false for every y.
∃x∀y P(x,y)	There is a x for which P(x,y) is true for every y	For every x, there is a y for which P(x,y) is false
∃x∃yP(x,y) ∃y∃xP(x,y)	There is a pair x, y for which P(x,y) is true.	P(x,y) is false for every pair x, y.

Tips: ∀x∃y P(x,y) can also meant there is at least 1 solution for every value of x.

     ∃y∀x P(x,y) can also meant every solution y must be valid for some x.

Negating Nested Quantifiers

The negation of nested quantifiers is shown in the following table by applying De Morgan’s Law:

Statement	Negation
∀x∀y P(x,y)	∃x∃y ¬P(x,y)
∀x∃y P(x,y)	∃x∀y ¬P(x,y)
∃x∀y P(x,y)	∀x∃y ¬P(x,y)
∃x∃yP(x,y)	∀x∀y ¬P(x,y)