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 and explain why the order cannot be permuted.
Hint
Consider .
Show solutionHide solution
Solution
Example. .
Meaning. For every , there is such that, for every , there is with .
Permutation. If we tried , the single would have to work for all and simultaneously, which is much stronger.
Conclusion. Alternation depth controls expressiveness; the order of quantifiers cannot generally be changed.