In mathematical logic, the quantifier rank of a formula is the depth of nesting of its quantifiers. It plays an essential role in model theory.
The quantifier rank is a property of the formula itself (i.e. the expression in a language). Thus two logically equivalent formulae can have different quantifier ranks, when they express the same thing in different ways.
Definition
In first-order logic Let be a first-order formula. The quantifier rank of , written , is defined as:
, if is atomic. . . . .
Remarks We write for the set of all first-order formulas with . Relational (without function symbols) is always of finite size, i.e. contains a finite number of formulas. In prenex normal form, the quantifier rank of is exactly the number of quantifiers appearing in .
In higher-order logic For fixed-point logic, with a least fixed-point operator : .
Examples A sentence of quantifier rank 2:
A formula of quantifier rank 1:
A formula of quantifier rank 0:
A sentence in prenex normal form of quantifier rank 3:
A sentence, equivalent to the previous, although of quantifier rank 2:
See also Ehrenfeucht–Fraïssé game
References
. .
External links
Quantifier Rank Spectrum of L-infinity-omega BA Thesis, 2000