Quantifier order

In general, exchanging a universal and an existential quantifier changes a formula's meaning. A uniform witness satisfies a condition for every input, while a pointwise witness may vary with the input. For the equality relation on a two-element set,

\forall x \exists y (x = y)

holds but

\exists y \forall x (x = y)

fails.

Table of contents
- Pointwise witness Quantifier order
- Uniform witness Quantifier order

Pointwise witness ( $\forall x \exists y R (x, y)$ )

 0  0

A witness whose existence is asserted separately for each input. The witness need not be the same element for different inputs, so this condition is weaker than existence of a uniform witness.

Uniform witness ( $\exists y \forall x R (x, y)$ )

 0  0

One element that satisfies a relation simultaneously for every quantified input. A uniform witness also proves the corresponding pointwise statement, because it may be chosen for each particular input.