【一階述語論理2】モデルと論理的帰結


▼ すべて展開/縮小

閉項の解釈・代入

定義(閉項の解釈)
\(L\)を言語とし, \(\mathcal{M} = \langle M ; F \rangle\)を\(L\)-構造とする. このとき,\(L(\mathcal{M})\)の閉項\(t\)の解釈を次で定める.
 1. \(t \equiv c \quad (c \in \mathcal{C})\)のとき, \(t^{\mathcal{M}} := c^{\mathcal{M}}\).
 2. \(t \equiv f(t_1, t_2, \cdots, t_n) \quad (f \in \mathcal{F}_n, n > 0)\)のとき, \(t^{\mathcal{M}} := f^{\mathcal{M}}(t_1^{\mathcal{M}}, t_2^{\mathcal{M}}, \cdots, t_n^{\mathcal{M}})\).
定義(閉項の代入)
\(L\)を言語とし, \(\mathcal{M} = \langle M ; F \rangle\)を\(L\)-構造とする. このとき, 自由変数\(x\)を持つ\(L(\mathcal{M})\)-論理式\(\varphi\)への\(L(\mathcal{M})\)-閉項\(t\)の代入とは, \(\varphi\)の自由出現する\(x\)をすべて\(t\)で置き換えた論理式のことであり, これを\(\varphi\lbrack x := t\rbrack\)と表す.

本来, 代入の際には意図しない変数の束縛が発生しないように注意しなければなならない. 閉項は自由変数を持たないため上記のように簡単に代入を定義できる.

論理式\(\varphi\)の真理値

定義(論理式の真理値)
\(L\)を言語とし, \(\mathcal{M} = \langle M ; F \rangle\)を\(L\)-構造とする. \(L(\mathcal{M})\)-閉論理式\(\varphi\)の真理値\(\mathcal{M}(\varphi) \in 2\)を次で帰納的に定義する. ただし, \(t_1, t_2, \cdots, t_n\)は項とし, \(R \in \mathcal{P}_n\), \(\psi, \theta\)は\(L(\mathcal{M})\)-論理式とする.

(原子論理式について)
 1. \(\mathcal{M}(\bot) = 0\),
 2. \(\mathcal{M}(t_1 = t_2) = 1 :\Longleftrightarrow t_1^\mathcal{M} = t_2^\mathcal{M}\),
 3. \(\mathcal{M}(R(t_1, t_2, \cdots, t_n)) = 1 :\Longleftrightarrow (t_1^\mathcal{M}, t_2^\mathcal{M}, \cdots, t_n^\mathcal{M}) \in R^\mathcal{M}\).

(論理式について)
 4. \(\mathcal{M}(\lnot \psi) := 1 – \mathcal{M}(\psi) \),
 5. \(\mathcal{M}(\psi \land \theta) := {\rm min}(\mathcal{M}(\psi), \mathcal{M}(\theta))\),
 6. \(\mathcal{M}(\psi \lor \theta) := {\rm max}(\mathcal{M}(\psi), \mathcal{M}(\theta))\),
 7. \(\mathcal{M}(\psi \rightarrow \theta) := {\rm max}(1 – \mathcal{M}(\psi), \mathcal{M}(\theta))\),
 8. \(\mathcal{M}(\forall x \psi) = 1 :\Longleftrightarrow\) 任意の \(m \in |\mathcal{M}|\) について\(\mathcal{M}(\psi \lbrack x := C_m\rbrack) = 1\)が成り立つ.
 9. \(\mathcal{M}(\exists x \psi) = 1 :\Longleftrightarrow\) ある \(m \in |\mathcal{M}|\) について\(\mathcal{M}(\psi \lbrack x := C_m\rbrack) = 1\)が成り立つ.

ただし, 真理値が1でないときには常に0である.

定義(\(L\)-閉論理式の真理値)
\(L\)を言語とし, \(\mathcal{M}\)を\(L\)-構造とする. \(L\)-閉論理式\(\varphi\)の真理値は\(\varphi\)を\(L(\mathcal{M})\)-閉論理式とみなした際の真理値\(\mathcal{M}(\varphi)\)とする. 集合として常に\(L \subset L(\mathcal{M})\)が成り立つので, この定義は可能である.

モデル

定義(\(\mathcal{M} \vDash \varphi\))
\(L\)-閉論理式\(\varphi\)と\(L\)-構造\(\mathcal{M}\)について, \(\mathcal{M}(\varphi) = 1\)が成り立つことを\(\mathcal{M} \vDash \varphi\)と表す.
定義(モデル)
\(L\)-閉論理式の集合を\(\Gamma\)とし\(\mathcal{M}\)を\(L\)-構造とする. 任意の\(\varphi \in \Gamma\)について\(\mathcal{M} \vDash \varphi\)が成り立つとき, \(\mathcal{M} \vDash \Gamma\)と表す. \(\mathcal{M} \vDash \Gamma\)を満たす\(L\)-構造\(\mathcal{M}\)のことを\(\Gamma\)のモデルという.

論理的帰結

定義(論理的帰結)
\(L\)-閉論理式の集合を\(\Gamma\), \(\mathcal{M}\)を\(L\)-構造, \(\varphi\)を\(L\)-閉論理式とする. 任意の\(\Gamma\)のモデル\(\mathcal{M}\)が\(\mathcal{M} \vDash \varphi\)を満たすとき\(\varphi\)は\(\Gamma\)の論理的帰結であるという.

参考文献

[1] 新井敏康,数学基礎論 増補版,東京大学出版会,2021.

[2] ケネス・キューネン, キューネン数学基礎論講義, 日本評論社,2016.

[3] 鹿島亮, 現代基礎数学15 数理論理学, 朝倉書店, 2009.

[4] Stephen Cole Kleene, Introduction To Meta-Mathematics, Ishi Press Internal, 1952.

[5] Joseph R. Shoenfield, Mathematical Logic, CRC Press, 1967.

[6] Richard E. Hodel, An Introduction to Mathematical Logic, Dover Publications Inc, 1995.

コメントを残す