Nested Quantifiers

Nested Quantifiers

Nested quantifiers are propositional functions where one or more quantifiers occurs within the scope of another quantifier.

Nested quantifiers commonly occur in mathematics and computer science.

Two quantifiers are nested if one is within the scope of the other, such as ∀x Ǝy (xy = 0)

This is same thing as ∀x Q(x), where Q(x) is Ǝy P(x, y) where P(x, y) is xy = 0

Example: Assume that the domain for the variables x and y consists of all real numbers. The statement ∀x ∀y (xy = yx) says that xy = yx for all real numbers x and y. This is the commutative law for addition of real numbers. Likewise, the statement

∀x Ǝy (xy = 0)

says that for every real number x there is a real number y such that xy = 0. This states that every real number has an multiplicative inverse. Similarly, the statement

∀x ∀y ∀z (x(yz)) = ((xy) z)

is the associtative law for multiplication of real numbers.

The order of quantifiers :

It is important to note that the order of the quantifiers is important, unless all the quantifiers are universal quantifiers or all are existential qauantifiers.

There are eight ways to apply the two quantifiers to the two variables, ∀x∀y, ∀y∀x, ∀xƎy, Ǝx∀y, Ǝy∀x, ∀yƎx, Ǝy Ǝx, Ǝx Ǝy

When more than one quantifiers, the order of evaluation is from left to right.

Let us consider the statement.

P(x, y) = x loves y. Then

∀x ∀y P(x,y) : Everyone loves everbody.

∀x Ǝy P(x,y): Everyone loves someone.

Ǝx ∀y P(x, y): Someone loves everyone.

Ǝx Ǝy P(x,y): Someone loves somebody.

∀y ∀x P(x,y): Everybody is loved by everyone.

∀y Ǝx P(x,y): Everyone is loved by someone.

Ǝy ∀x P(x,y): There is someone whom every one loves.

Ǝy Ǝx P(x,y) There is someone whom someone loves.

Translating Mathematical statements into statements involving Nested Quantifiers.

Example 1. Express the statement "Everyone has exactly one best friend" as a logical expression involving logical expression involving predicates, quantifiers with a domain consisting of all people and logical connectives.

Solution : Rewrite the given statement "For every person x, x has exactly one best friend." Attention "exactly one"!. Let B (x, y) :y is the best friend of x. So if a person z is not the person y, then z is not the best friend of x. Thus

∀x Ǝy (B(x, y) Ʌ (z≠y) → ┐B (x, z))

With the uniqueness quantifier Ǝ!

∀x Ǝ!y B(x, y)

Example 2. Translate the statement. "Every real number except zero has a multiplicative inverse." (A multiplicative inverse of a real number x is a real number y such that xy = 1.)

Solution: Rewrite the given statement "For every real number x except zero, x has a multiplicative inverse." We can rewrite this as "For every real number x, if x ≠ 0, then there exists a real number y such that xy= 1." This can be rewritten as

∀x ((x≠0) → Ǝy (xy = 1))

Translating from Nested Quantifiers into English

Example 1. Translate the statement

∀x (C(x) ^ Ǝy (C (y) ^ F(x,y)))

into English, where C (x) is "x has calculator" F (x, y) is "x and y are friends", and the domain for both x and y consists of all students in your school.

Solution: The statement says that for every student x in your school, x has a calculator or there is a student y such that y has calculator and x and y are friends. In other words, every student in your school has a calculator or has a friend who has a calculator.

Example 2. Translate the stement

Ǝx ∀y ∀z ((F(x, y) ^ F (x, z) ^ (y ≠ z)) → F (y, z)) into English, where F (x, y) means x and y are friends and the domain for x and y and z consists of all students in school.

Solution: There is a student none of whose friends are also friends with each other.

 Example 3. Translate these statements into English, where the domain for each variable consists of all real numbers.

(a) ∀ x ∀ y Ǝz (xy=z)

(b) ∀x Ǝy (x <y)

(c) ∀x ∀y (((x ≥ 0) ^ (y ≥ 0)) → (xy ≥ 0))

Solution: (a) For every real number x and real number y, there exists a real number z such that xy = z

(b) For every real number x there exists a real number such that x is less than y.

(c) For every real number x and real number y, if x and y are both non-negative, then their product is non-negative.

Negating Nested Quantifiers

Negating Nested Quantifiers: To negate a sequence of nested quantifiers, you flip each quantifier in the sequence and then negate the predicate. So the negation of ∀x Ǝy: P (x,y) is Ǝx ∀y: P(x,y) and So the negation of Ǝx ∀y: P(x, y) is ∀x Ǝy:

Additional Worked out Examples :

Example 1. Let L (x, y) be the statement "x loves y", where the domain for both x and y consists of all people in the world. Use quantifiers to express each of these statements.

(a) Everybody loves Ramu

(b) Everybody loves somebody

(c) There is somebody whom everybody loves.

(d) Nobody loves everybody.

(e) There is somebody whom Manju does not love.

(f) There is somebody whom no one loves.

(g) Everyone loves himself or herself.

(h) There is someone who loves no one besides himself or herself.

Solution : (a) ∀ x L [x, Ramu]

(b) ∀x Ǝy L [x, y]

(c) Ǝy ∀x L [x, y]

(d) ∀x Ǝy ┐L [x,y]

(e) Ǝx ┐L [Manju, x]

(f) Ǝx ∀y ┐L [y, x]

(g) ∀x L [x,x]

(h) Ǝx ∀y (L(x,y) ↔  x=y)

Example 2. Let S (x) be the predicate "x is a student," F(x) the predicate x is a faculty member," and F(x, y) the predicate "x has asked y a question," where the domain consists of all people associated with your school. Use quantifiers to express each of these statements.

(a) Ram has asked Professor Rajas a question.

(b) Every student has asked Professor Green a question.

 (c) Every faculty member has either asked Professor Kathiravan a question or been asked a question by Professor Kathiravan. (d) Some student has not asked any faculty member a question.

Solution :

(a) F (Ram, Rajas)

(b) ∀ x (S (x) → F (x, Green))

(c) ∀ x (g(x) → (F(x, Kathiravan)) v F (Kathiravan, x))

(d) Ǝx (S(x) Ʌ ∀ y(g (y) → ┐F(x, y))