Quantifier rank

Source: Wikipedia, the free encyclopedia.

In

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.

Definition

Quantifier Rank of a Formula in

First-order language
(FO)

Let φ be a FO formula. The quantifier rank of φ, written qr(φ), is defined as

  • , if φ is atomic.
  • .
  • .
  • .
  • .

Remarks

  • We write FO[n] for the set of all first-order formulas φ with .
  • 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 φ is exactly the number of quantifiers appearing in φ.

Quantifier Rank of a higher order Formula

  • For
    Fixpoint logic
    , with a least fix point operator LFP:

Examples

  • A sentence of quantifier rank 2:
  • A formula of quantifier rank 1:
  • A formula of quantifier rank 0:
  • A sentence, equivalent to the previous, although of quantifier rank 2:

See also

References

  • .
  • Grädel, Erich; Kolaitis, Phokion G.; .