Maths WorkshopMaths problems with full solutions
Exercise 1857Logic, sets and proofs › Quantifiers and negationL1Added 3 Nov 2026

Alternation depth of quantifiers

#quantifier alternation#depth#complexity

Statement

Give an example of a statement with quantifier alternation ∀∃∀∃\forall\exists\forall\exists and explain why the order cannot be permuted.

Hint

Consider ∀a∈N, ∃b∈N, ∀c∈N, ∃d∈N, ad−bc=1\forall a\in\mathbb{N},\ \exists b\in\mathbb{N},\ \forall c\in\mathbb{N},\ \exists d\in\mathbb{N},\ ad-bc=1.

Show solutionHide solution

Solution

Example. ∀a, ∃b, ∀c, ∃d, ad−bc=1\forall a,\ \exists b,\ \forall c,\ \exists d,\ ad-bc=1.

Meaning. For every aa, there is bb such that, for every cc, there is dd with ad−bc=1ad-bc=1.

Permutation. If we tried ∃d, ∀a, ∃b, ∀c, …\exists d,\ \forall a,\ \exists b,\ \forall c,\ \ldots, the single dd would have to work for all aa and cc simultaneously, which is much stronger.

Conclusion. Alternation depth controls expressiveness; the order of quantifiers cannot generally be changed.