Top Qs
Timeline
Chat
Perspective

Quantifier rank

Depth of nesting of quantifiers in a formula From Wikipedia, the free encyclopedia

Remove ads

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

Summarize
Perspective

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 : .

Remove ads

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:
Remove ads

See also

References

Loading content...
Loading content...
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads