CSCE 222 Chapter 1.4

« previous | Sunday, February 20, 2011 | next »

Nested Quantifiers

Think of nested quantifiers as loops:

$\forall x\forall yP(x,y)$

for x in Domain do
  for y in Domain do
    p(x,y)
  end
end

Order Matters

$\forall x\exists y(x+y=0)\not \equiv \exists y\forall x(x+y=0)$

Left side: For all real numbers $x$, there is a real number $y$ such that $x+y=0$. (Namely, $y=-x$)

Right side: There is a real number $y$ such that for all real numbers $x$, $x+y=0$. (can never be true)

Negating Nested Quantifiers

Follow rules of negating quantifiers and De Morgan's Laws, just cascade down the line.

${\begin{aligned}\forall w\neg \forall a\exists f(P(w,f)\wedge Q(f,a))&\equiv \forall w\exists a\neg \exists f(P(w,f)\wedge Q(f,a))\\&\equiv \forall w\exists a\forall f\neg (P(w,f)\wedge Q(f,a))\\&\equiv \forall w\exists a\forall f(\neg P(w,f)\vee \neg Q(f,a))\end{aligned}}$