# Quantifier rank

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.

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

• $qr(\varphi )=0$ , if φ is atomic.
• $qr(\varphi _{1}\land \varphi _{2})=qr(\varphi _{1}\lor \varphi _{2})=max(qr(\varphi _{1}),qr(\varphi _{2}))$ .
• $qr(\lnot \varphi )=qr(\varphi )$ .
• $qr(\exists _{x}\varphi )=qr(\varphi )+1$ .

Remarks

• We write FO[n] for the set of all first-order formulas φ with $qr(\varphi )\leq n$ .
• 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: $qr([LFP_{\phi }]y)=1+qr(\phi )$ ## Examples

• A sentence of quantifier rank 2:
$\forall x\exists yR(x,y)$ • A formula of quantifier rank 1:
$\forall xR(y,x)\wedge \exists xR(x,y)$ • A formula of quantifier rank 0:
$R(x,y)\wedge x\neq y$ $\forall x\exists y\exists z((x\neq y\wedge xRy)\wedge (x\neq z\wedge zRx))$ • A sentence, equivalent to the previous, although of quantifier rank 2:
$\forall x(\exists y(x\neq y\wedge xRy))\wedge \exists z(x\neq z\wedge zRx))$ 