Nested Quantifiers

• When we have one quantifier inside another, we need to be a little careful.
  • Consider these two propositions about arithmetic (over the integers):
    ∀x∃y(x+y=0)∃y∀x(x+y=0)
    

    
    
  • The first is true: if you pick any 
    x
    , I can find a 
    y
     that makes x+y=0
     true.
  • The second is false: there is no 
    y
     that will make x+y=0
     true for every x
    .
  • So the order of the quantifiers must matter, at least sometimes.
• But it turns out these are equivalent:
  ∀x∀yP(x,y)≡∀y∀xP(x,y)∃x∃yP(x,y)≡∃y∃xP(x,y)
  

  
  
  • i.e. you can swap the same kind of quantifier (
    ∀,∃
    ).
  • Informally: 
    ∀
     is essentially a bunch of ∧
    s, and ∃
     is essentially a bunch of ∨
    s. By the commutative law, we can re-order those as much as we want, as long as they're the same operator.