The quantifier rank of a first-order formula is the maximum nesting depth of quantifiers. Atomic formulas have rank zero; negation preserves rank, binary Boolean connectives take the maximum, and either quantifier increases rank by one. It is not the total number of quantifiers.
Two first-order structures are rank-n equivalent if they agree on all sentences of quantifier rank at most . The tuple version compares formulas at fixed tuples. For finite relational vocabulary this is equivalent to a Duplicator winning strategy in the -round Ehrenfeucht-Fraïssé game.
Articles by others on the same topic
Quantifier rank is a concept from model theory, a branch of mathematical logic. It relates to the complexity of formulas in logic, particularly those formulated in first-order logic. In first-order logic, quantifiers are symbols used to express statements about the existence (∃) or universality (∀) of elements in a domain.