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 in prenex normal form of quantifier rank 3:
- A sentence, equivalent to the previous, although of quantifier rank 2:
Remove ads
See also
References
External links
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads