Nested Qualifiers

Tom Kelliher, MA 190

Feb. 6, 2008

Modeling Nested Qualifiers as Nested Loops

1. $\forall x \forall y \: P(x, y)$

   Example: For every pair of real numbers, their sum is a real number.

   proved := true;
   for x := each element in its domain
      confirmed := true;
      for y := each element in its domain
         if P(x, y) == false
            confirmed := false;
            break;
   
      if confirmed == false
         proved := false;
         break;
   
   return proved;
   

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

   Example: For every integer, $i$, there is an integer, $j$, such that $i + j = 0$.

   proved := true;
   for x := each element in its domain
      confirmed := false;
      for y := each element in its domain
         if P(x, y) == true;
            confirmed := true
            break;
   
      if confirmed == false
         proved := false;
         break;
   
   return proved;
   

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

   Example: There is a real number that when multiplied by any real number, $x$, results in a product of $x$.

   proved := false;
   for x := each element in its domain
      confirmed := true;
      for y := each element in its domain
         if P(x, y) == false
            confirmed := false;
            break;
   
      if confirmed == true
         proved := true;
         break;
   
   return proved;
   

4. $\exists x \exists y \: P(x, y)$

   Example: There are two integers whose product is 12.

   proved := false;
   for x := each element in its domain
      confirmed := false;
      for y := each element in its domain
         if P(x, y) == true
            confirmed := true;
            break;
   
      if confirmed == true
         proved := true;
         break;
   
   return proved;
   

Exercises

1. (1 a, b, c) Translate these statements into English. The domain is all real numbers.
   1. $\forall x \exists y \: (x < y)$

   2. $\forall x \forall y \: (((x \geq 0) \wedge (y \geq 0)) \rightarrow (xy \geq 0))$

   3. $\forall x \forall y \exists z \: (xy = z)$

2. (5 e) Translate this statement into English. $W(x, y)$ means that student $x$ has visited web site $y$. The domain for $x$ is all Goucher students and the domain for $y$ is all web sites.
   
   $$\exists y \forall z \: (y \neq ({\rm David~Belcher}) \wedge (W({\rm David~Belcher}, z) \rightarrow W(y, z)))$$
   
   

3. (9 b, c, d, h) Let $L(x, y)$ be the statement ``$x$ loves $y$,'' where the domain for both $x$ and $y$ consists of all people. Use quantifiers to express these statements.
   1. Everybody loves somebody.

   2. There is somebody whom everybody loves.

   3. Nobody loves everybody.

   4. There are exactly two people whom Lynn loves.

4. (37 b, c) Express each of these statements using quantifiers. Then, form the negation of the statement so that no negation is to the left of a quantifier. Next, express the negation in simple English.
   1. Someone has visited every country in the world except Libya.

   2. Every movie actor has either been in a movie with Kevin Bacon or has been in a movie with someone who has been in a movie with Kevin Bacon.

Tom Kelliher