Quantifier rank
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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
\operatorname{qr}(\varphi) = 0 , if \varphi is atomic. \operatorname{qr}(\varphi_1 \land \varphi_2) = \operatorname{qr}(\varphi_1 \lor \varphi_2) = \max(\operatorname{qr}(\varphi_1), \operatorname{qr}(\varphi_2)) . \operatorname{qr}(\lnot \varphi) = \operatorname{qr}(\varphi) . \operatorname{qr}(\exists_x \varphi) = \operatorname{qr}(\varphi) + 1 . \operatorname{qr}(\forall_x \varphi) = \operatorname{qr}(\varphi) + 1 . Remarks We write \operatorname{FO}[n] for the set of all first-order formulas \varphi with \operatorname{qr}(\varphi) \le n . Relational \operatorname{FO}[n] (without function symbols) is always of finite size, i.e. contains a finite number of formulas. In prenex normal form, the quantifier rank of \varphi is exactly the number of quantifiers appearing in \varphi . For fixed-point logic, with a least fixed-point operator \operatorname{LFP} : \operatorname{qr}([\operatorname{LFP}_\phi]y) = 1 + \operatorname{qr}( \phi ) .
Examples
A sentence of quantifier rank 2: \forall x\exists y R(x, y) A formula of quantifier rank 1: \forall x R(y, x) \wedge \exists x R(x, y) A formula of quantifier rank 0: R(x, y) \wedge x \neq y A sentence in prenex normal form of quantifier rank 3: \forall x \exists y \exists z ((x \neq y \wedge x R y) \wedge (x \neq z \wedge z R x)) A sentence, equivalent to the previous, although of quantifier rank 2: \forall x (\exists y (x \neq y \wedge x R y)) \wedge \exists z (x \neq z \wedge z R x ))
See also
Ehrenfeucht–Fraïssé game
References
. .
External links
Quantifier Rank Spectrum of L-infinity-omega BA Thesis, 2000
Text derived from https://en.wikipedia.org/w/index.php?oldid=1323636442 under CC BY-SA 4.0; modifications have been made.