Quantifier rank (original) (raw)

From Wikipedia, the free encyclopedia

Depth of nesting of quantifiers in a formula

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.

In first-order logic

[edit]

Let φ {\displaystyle \varphi } {\displaystyle \varphi } be a first-order formula. The quantifier rank of φ {\displaystyle \varphi } {\displaystyle \varphi }, written qr ⁡ ( φ ) {\displaystyle \operatorname {qr} (\varphi )} {\displaystyle \operatorname {qr} (\varphi )}, is defined as:

Remarks

In higher-order logic

[edit]

For fixed-point logic, with a least fixed-point operator LFP {\displaystyle \operatorname {LFP} } {\displaystyle \operatorname {LFP} }: qr ⁡ ( [ LFP ϕ ] y ) = 1 + qr ⁡ ( ϕ ) {\displaystyle \operatorname {qr} ([\operatorname {LFP} _{\phi }]y)=1+\operatorname {qr} (\phi )} {\displaystyle \operatorname {qr} ([\operatorname {LFP} _{\phi }]y)=1+\operatorname {qr} (\phi )}.

∀ x ∃ y R ( x , y ) {\displaystyle \forall x\exists yR(x,y)} {\displaystyle \forall x\exists yR(x,y)}

∀ x R ( y , x ) ∧ ∃ x R ( x , y ) {\displaystyle \forall xR(y,x)\wedge \exists xR(x,y)} {\displaystyle \forall xR(y,x)\wedge \exists xR(x,y)}

R ( x , y ) ∧ x ≠ y {\displaystyle R(x,y)\wedge x\neq y} {\displaystyle R(x,y)\wedge x\neq y}

∀ x ∃ y ∃ z ( ( x ≠ y ∧ x R y ) ∧ ( x ≠ z ∧ z R x ) ) {\displaystyle \forall x\exists y\exists z((x\neq y\wedge xRy)\wedge (x\neq z\wedge zRx))} {\displaystyle \forall x\exists y\exists z((x\neq y\wedge xRy)\wedge (x\neq z\wedge zRx))}

∀ x ( ∃ y ( x ≠ y ∧ x R y ) ) ∧ ∃ z ( x ≠ z ∧ z R x ) ) {\displaystyle \forall x(\exists y(x\neq y\wedge xRy))\wedge \exists z(x\neq z\wedge zRx))} {\displaystyle \forall x(\exists y(x\neq y\wedge xRy))\wedge \exists z(x\neq z\wedge zRx))}