数量詞ランク

数理論理学において、式の量化子の階数とは、その量化子の入れ子の深さのことである。これはモデル理論において重要な役割を果たしている。

量指定子のランクは、式自体（つまり言語における表現）の特性です。したがって、論理的に等価な2つの式であっても、同じことを異なる方法で表現している場合、量指定子のランクは異なる場合があります。

定義

を一階述語論理式とする。の量指定子の階数（と表記）は次のように定義される $\varphi$ $\varphi$ $\operatorname {qr} (\varphi)$

$\operatorname {qr} (\varphi )=0$ 、がアトミックの場合。 $\varphi$
$\operatorname {qr} (\varphi _{1}\land \varphi _{2})=\operatorname {qr} (\varphi _{1}\lor \varphi _{2})=\max(\operatorname {qr} (\varphi _{1}),\operatorname {qr} (\varphi _{2}))$ 。
$\operatorname {qr} (\lnot \varphi )=\operatorname {qr} (\varphi )$ 。
$\operatorname {qr} (\exists _{x}\varphi)=\operatorname {qr} (\varphi)+1$ 。
$\operatorname {qr} (\forall _{x}\varphi)=\operatorname {qr} (\varphi)+1$ 。

備考

を満たすすべての一階論理式の集合をと書きます $\operatorname {FO} [n]$ $\varphi$ $\operatorname {qr} (\varphi )\leq n$
リレーショナル(関数記号なし) は常に有限のサイズです。つまり、有限の数の式が含まれます。 $\operatorname {FO} [n]$
冠頭正規形では、の量指定子の階数はに現れる量指定子の数とまったく同じです。 $\varphi$ $\varphi$

固定小数点論理では、最小の固定小数点演算子は次のようになります $\operatorname {LFP}$ $\operatorname {qr} ([\operatorname {LFP} _{\phi }]y)=1+\operatorname {qr} (\phi )$

\forall x\exists yR(x,y)

\forall xR(y,x)\wedge \exists xR(x,y)

R(x,y)\wedge x\neq y

\forall x\exists y\exists z((x\neq y\wedge xRy)\wedge (x\neq z\wedge zRx))

\forall x(\exists y(x\neq y\wedge xRy))\wedge \exists z(x\neq z\wedge zRx))

エビングハウス、ハインツ＝ディーター；フルム、イェルク（1995）『有限モデル理論』、シュプリンガー、ISBN 978-3-540-60149-4。
グレーデル、エーリッヒ；コライティス、フォキオン・G.；リブキン、レオニード；マールテン、マルクス；スペンサー、ジョエル；ヴァルディ、モシェ・Y.；ヴェネマ、イデ；ワインスタイン、スコット（2007年）『有限モデル理論とその応用』『理論計算機科学テキスト。EATCSシリーズ』ベルリン：シュプリンガー・フェアラーク、133ページ、ISBN 978-3-540-00428-8、Zbl 1133.03001。