第4章 一階述語論理 — 構文

命題論理では言えないこと

命題論理は「$p$、$q$ が真か偽か」しか扱えません。でも数学の主張はもっと構造をもっています。 「すべての自然数 $n$ に対して $n<n+1$」「$x^2=2$ となる実数 $x$ が存在する」。 「すべて」「ある」、そして対象・関数・関係——これらは命題変数の真偽だけでは表現不可能です。

そこで論理を一段強くします。対象を指す変数と、それに掛ける量化子 $\forall$（すべて）・$\exists$（ある）、 対象の性質を表す述語、対象から対象への関数を導入する。これが一階述語論理です （“一階”とは、量化できるのが対象だけで、性質や集合には量化しないこと。それらまで量化するのが高階論理、第10章）。 この章では、この豊かになった言語の構文——記号の並べ方の規則——を、命題論理と同じ帰納的な精神で厳密に立てます。

一階述語論理 ＝ 命題論理 ＋ 対象変数・述語・関数・量化子 $\forall\exists$。まず「正しい式」を機械的に定める。

言語（シグネチャ）

まず、どんな記号を使うかを宣言します。論理そのものに属する記号（論理記号）と、扱う対象ごとに変わる 記号（非論理記号）を分けます。

例えば群の言語は $\mathcal L=\{\cdot,\ ^{-1},\ e\}$（2項関数・1項関数・定数）、順序体なら $\{+,\cdot,<,0,1\}$。 言語を変えれば、語れる数学の分野が変わる。論理の骨組みは共通で、非論理記号だけを差し替えるのがポイントです。

項と論理式

命題論理と同じく、帰納的定義で「正しい式」を作ります。まず対象を指す式＝項、次に真偽を主張する式＝論理式。

命題論理では原子式は命題変数でしたが、ここでは「項どうしの等式・述語の適用」が最小単位です。 そのぶん内部構造をもちます。そして量化子 $\forall x$ が加わったことで、新しい概念——変数が“縛られる”——が必要になります。

自由変数と束縛変数

$\forall x\,\varphi$ の中の $x$ は、もはや「特定の対象」ではなく「$\varphi$ の中で走る番号」のようなもの。 この違いを正確に区別しないと、代入で破綻します。

例：$\forall x\,(x<y)$ で、$x$ は束縛、$y$ は自由。この式の真偽は「$y$ に何を入れるか」に依存し、 $x$ には依存しません（$x$ は $\forall x$ に食われている）。文（自由変数なし）だけが、それ自体で真偽を問える主張になります （$\forall x\forall y(x<y\lor y<x\lor x=y)$ のような閉じた式）。自由変数を含む式は、値を代入して初めて真偽が決まります。

代入と代入可能性

「$\forall x\,\varphi$ が成り立つなら、$x$ に具体的な項 $t$ を入れた $\varphi[x:=t]$ も成り立つ」——量化子の推論の要は代入です。 ところが、素朴に代入すると**変数の取り違え（capture）**という罠があります。

この事故を防ぐ条件が代入可能性です。

代入可能でないときは、束縛変数を新しい変数に名前替え（$\alpha$-変換：$\exists y\,(x<y)$ を $\exists z\,(x<z)$ に）してから 代入すればよい。以後 $\varphi[x:=t]$ と書くときは、$t$ が $x$ に代入可能であると暗黙に仮定します。 この一手間が、次章の量化子規則の健全性（第6章）を支える縁の下の力持ちになります。

つまずきポイント

この章のまとめ

• 一階述語論理は命題論理に対象変数・関数・述語・量化子 $\forall\exists$ を加えたもの。**言語（シグネチャ）**を差し替えて各分野を語る。
• 項と論理式を帰納的に定義。量化子により変数に自由/束縛の区別が生まれ、**文（閉論理式）**だけが単独で真偽を問える。
• 代入 $\varphi[x:=t]$ は capture を避けねばならず、代入可能性（$t$ が $x$ に対して自由）を課す。必要なら $\alpha$-変換する。

次章は、この構文に意味を与えます。構造・付値・充足というタルスキの意味論で、「真である」を厳密に定義します。