Predicate logic · Definition

Order of quantifiers

logicpredicates

Before you start you need to know

The order of quantifiers changes the meaning of a formula. Here we see why \(\forall x\,\exists y\,P(x,y)\) and \(\exists y\,\forall x\,P(x,y)\) are different.

Definition

For a predicate \(P(x,y)\), the order of the quantifiers can change the truth value of a formula.

\[\begin{gathered}\forall x\,\exists y\,P(x,y)\\\not\equiv\exists y\,\forall x\,P(x,y)\end{gathered}\]

When several quantifiers appear, their order can change the meaning of the formula. In general, \(\forall x\,\exists y\,P(x,y)\) is not equivalent to \(\exists y\,\forall x\,P(x,y)\).

The first formula allows the witness y to depend on the chosen x. The second requires a single y that works for all x.

Reading the order as a sequence of commitments helps avoid a frequent confusion: having an object for each case does not imply having a single object for all of them.

Think about it

What is the difference between a dependent witness and a global one?

The dependent one can change with x; the global one must work for all x at once.

Exercises 10

  1. In general, changing the order of ∀ and ∃...
  2. ∀x ∃y P(x,y) allows...
  3. ∃y ∀x P(x,y) states that...
  4. Which pair is not equivalent in general?
  5. The order of quantifiers matters especially when...
  6. In general, ∀x∃y R(x,y) and ∃y∀x R(x,y)...
  7. ∀x∃y R(x,y) allows...
  8. ∃y∀x R(x,y) states that...
  9. Select true statements about order.
  10. If every student has some book, it does not follow that...

References

  • Frederic P. Schuller, Lectures on the Geometrical Anatomy of Theoretical Physics · Lecture 1, Introduction / Logic of Propositions and Predicates, YouTube, 2015.