Nested Quantifiers • Nested quantifiers are often necessary to express the meaning of sentences in English as well as important concepts in computer science and mathematics. • Example ○ “Every real number has an inverse” is ○ ∀x ∃y(x+y=0) ○ where the domains of x and y are the real numbers. • We can also think of nested propositional functions: ○ ∀x ∃y(x+y=0) can be viewed as ∀x Q(x) ○ where Q(x) is ∃y P(x, y) where P(x, y) is (x+y=0) Thinking of Nested Quantification • Nested Loops • To see if ∀x∀y P(x,y) is true, loop through the values of x: • At each step, loop through the values for y. • If for some pair of x and y, P(x,y) is false, then ∀x∀y P(x,y) is false and both the outer and inner loop terminate. • ∀x∀y P(x,y) is true if the outer loop ends after stepping through each x. • To see if ∀x∃y P(x,y) is true, loop through the values of x: • At each step, loop through the values for y. • The inner loop ends when a pair x and y is found such that P(x, y) is true. • If no y is found such that P(x, y) is true • the outer loop terminates as ∀x∃y P(x,y) has been shown to be false. • ∀x∃y P(x,y) is true if the outer loop ends after stepping through each x. • If the domains of the variables are infinite, • then this process cannot actually be carried out. Order of Quantifiers • Let P(x,y) be the statement “x+y=y+x.” • Assume that U is the real numbers. • Then ∀x∀y P(x,y) and ∀y∀x P(x,y) have the same truth value. • Let Q(x,y) be the statement “x+y=0.” • Assume that U is the real numbers. • Then ∀x∃y Q(x,y) is true, but ∃y∀x Q(x,y) is false. Questions on Order of Quantifiers • Example 1 ○ Let U be the real numbers, ○ Define P(x,y): x∙y=0 ○ ∀x∀yP(x,y)=F ○ ∀x∃yP(x,y)=T ○ ∃x∀yP(x,y)=T ○ ∃x∃yP(x,y)=T Example 2 ○ Let U be the positive real numbers, ○ Define P(x,y): x/y=1 ○ ∀x∀yP(x,y)=F ○ ∀x∃yP(x,y)=T ○ ∃x∀yP(x,y)=F ○ ∃x∃yP(x,y)=T Translating Nested Quantifiers into English • Example 1 ○ Translate the statement ∀x(C(x)∨∃y(C(y)∧F(x, y))) § where C(x) is “x has a computer,” § and 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 § Every student in your school has a computer or has a friend who has a computer. • Example 2 ○ Translate the statement § ∃x∀y∀z ((F(x, y)∧ F(x,z)∧(y ≠z))→¬F(y,z)) ○ Solution § There is a student none of whose friends are also friends with each other. • Example 3 ○ Translate the statement ∀x (B(x)∨∃y (B(y)∧S(y,x))) § Where B(x) is
