mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

, the quantifier rank of a

formula In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...

is the depth of nesting of its quantifiers. It plays an essential role in

model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mat ...

. The quantifier rank is a property of the formula itself (i.e. the expression in a language). Thus two

logically equivalent In logic and mathematics, statements p and q are said to be logically equivalent if they have the same truth value in every model. The logical equivalence of p and q is sometimes expressed as p \equiv q, p :: q, \textsfpq, or p \iff q, depending on ...

formulae can have different quantifier ranks, when they express the same thing in different ways.

Definition

In first-order logic

Let

\varphi

be a first-order formula. The quantifier rank of

\varphi

, written

\operatorname(\varphi)

, is defined as: *

\operatorname(\varphi) = 0

, if

\varphi

is atomic. *

\operatorname(\varphi_1 \land \varphi_2) = \operatorname(\varphi_1 \lor \varphi_2) = \max(\operatorname(\varphi_1), \operatorname(\varphi_2))

. *

\operatorname(\lnot \varphi) = \operatorname(\varphi)

. *

\operatorname(\exists_x \varphi) = \operatorname(\varphi) + 1

. *

\operatorname(\forall_x \varphi) = \operatorname(\varphi) + 1

. Remarks * We write

\operatorname /math> for the set of all first-order formulas \varphi with \operatorname(\varphi) \le n .
* Relational \operatorname /math> (without function symbols) is always of finite size, i.e. contains a finite number of formulas.
* In

prenex normal form A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in propos ...

, the quantifier rank of

\varphi

is exactly the number of quantifiers appearing in

\varphi

In higher-order logic

For fixed-point logic, with a least fixed-point operator

\operatorname

) = 1 + \operatorname( \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

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 ))

References

* . * .

External links

Quantifier Rank Spectrum of L-infinity-omega
BA Thesis, 2000 {{Mathematical logic Finite model theory Model theory Predicate logic Quantifier (logic)