202311292211

Tags : Logic

Quantifier rank

---

Quantifier rank is just the number of layers deep quantifiers go in a formula.

• If $\phi$ is atomic then $\text{qr}(\phi )=0$
• $\text{qr}({\phi }_1\vee {\phi }_2)=\text{qr}({\phi }_1\wedge {\phi }_2)$ which is $\max (\text{qr}({\phi }_1),\text{qr}({\phi }_2))$
• $\text{qr}(\phi )=\text{qr}(\neg \phi )$
• $\text{qr}(\exists x\phi )=\text{qr}(\phi )+1$

We use the notion $\text{FO[k]}$ to denote the set of first order formulas of rank up to $k$

---

References

• Ehrenfeucht-Fraïssé Game
• Rank-k Types (FO)