Notice that 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.
quantifier, rank, mathematical, logic, quantifier, rank, formula, depth, nesting, quantifiers, plays, essential, role, model, theory, notice, that, quantifier, rank, property, formula, itself, expression, language, thus, logically, equivalent, formulae, have, . 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 Notice that 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 Contents 1 Definition 2 Examples 3 See also 4 References 5 External linksDefinition editQuantifier Rank of a Formula in First order language FO Let f be a FO formula The quantifier rank of f written qr f is defined as q r f 0 displaystyle qr varphi 0 nbsp if f is atomic q r f 1 f 2 q r f 1 f 2 m a x q r f 1 q r f 2 displaystyle qr varphi 1 land varphi 2 qr varphi 1 lor varphi 2 max qr varphi 1 qr varphi 2 nbsp q r f q r f displaystyle qr lnot varphi qr varphi nbsp q r x f q r f 1 displaystyle qr exists x varphi qr varphi 1 nbsp q r x f q r f 1 displaystyle qr forall x varphi qr varphi 1 nbsp Remarks We write FO n for the set of all first order formulas f with q r f n displaystyle qr varphi leq n nbsp Relational FO n without function symbols is always of finite size i e contains a finite number of formulas Notice that in Prenex normal form the Quantifier Rank of f is exactly the number of quantifiers appearing in f Quantifier Rank of a higher order Formula For Fixpoint logic with a least fix point operator LFP q r L F P ϕ y 1 q r ϕ displaystyle qr LFP phi y 1 qr phi nbsp Examples editA sentence of quantifier rank 2 x y R x y displaystyle forall x exists yR x y nbsp A formula of quantifier rank 1 x R y x x R x y displaystyle forall xR y x wedge exists xR x y nbsp A formula of quantifier rank 0 R x y x y displaystyle R x y wedge x neq y nbsp A sentence in prenex normal form of quantifier rank 3 x y z x y x R y x z z R x displaystyle forall x exists y exists z x neq y wedge xRy wedge x neq z wedge zRx nbsp A sentence equivalent to the previous although of quantifier rank 2 x y x y x R y z x z z R x displaystyle forall x exists y x neq y wedge xRy wedge exists z x neq z wedge zRx nbsp See also editPrenex normal form Ehrenfeucht Fraisse game QuantifierReferences editEbbinghaus Heinz Dieter Flum Jorg 1995 Finite Model Theory Springer ISBN 978 3 540 60149 4 Gradel Erich Kolaitis Phokion G Libkin Leonid Maarten Marx Spencer Joel Vardi Moshe Y Venema Yde Weinstein Scott 2007 Finite model theory and its applications Texts in Theoretical Computer Science An EATCS Series Berlin Springer Verlag p 133 ISBN 978 3 540 00428 8 Zbl 1133 03001 External links editQuantifier Rank Spectrum of L infinity omega BA Thesis 2000 nbsp This mathematical logic related article is a stub You can help Wikipedia by expanding it vte Retrieved from https en wikipedia org w index php title Quantifier rank amp oldid 1211760990, wikipedia, wiki, book, books, library,