数理論理学：ノート4 - クッキーの日記

読んでいる本（出典）：数理論理学 | 戸次大介 |本 | 通販 | Amazon

前回：ノート3 ／次回：まだ
目次：数理論理学

以下、第5章後半の自分の理解。
最後の節（標準形）がまだ読めていないので、後でこの記事に加筆するか、新しい記事にまとめる。

前回までのあらすじ（一階述語論理の統語論）

命題論理では扱えない「すべての $x$ について～」「ある $x$ が存在して～」のような知見を表現すべく、論理式を名前と述語に分けます。
$\forall$ や $\exists$ といった量化子を導入します。
論理式がすごい増えてしまいそうですが、自然数で番号付けできます（ゲーデル数）。
- 但し、論理式のパーツになる記号の集合 $\mathcal{A}$ は高々可算集合とする。

一階述語論理の意味論

命題論理のときと同様、「論理式の集合真偽の領域」であるような解釈を考える。
命題論理のときは、は「原子命題の真偽の組合せの全パターン」ということで原子命題の数個あった。
一方、一階述語論理では原子命題がさらに項と述語に分かれるので、「各項が指し示しているもの」「各述語について、項が指し示しているものに対応する、論理式の真偽」として考えるのがよい（構造）。
あと変項もあるので、変項に何を割り当てたかも論理式の真偽にかかわる（割り当て ）。
つまり、ある1つの解釈を与えるには、以下を完全に決めればよい。
- そもそもどんなものたちについて命題を述べるのか（存在物）の集合： $D_M$
- 名前記号が指す存在物は何か： $F_M : \{ a_1, a_2, \cdots \} \to D_M$
- $n$ 個の存在物に $n$ 項演算子を適用したときに指す存在物は何か： $F_M : \{ o_{n,1}, o_{n,2}, \cdots \} \to {D_M}^{{D_M}^n}$
- $n$ 個の存在物に $n$ 項述語を適用したときの真偽はどうか： $F_M : \{ \theta_{n,1}, \theta_{n,2}, \cdots \} \to {D_t}^{{D_M}^n}$
- 変項に何を割り当てたか： $g : \{\xi_1 , \xi_2, \cdots \} \to D_M$

Ex．あるゲームのキャラクターたちについて命題を述べるとする（以下、ネタバレな上にしようもない例）。

　　 $M_1$ をダンガンロンパのキャラクターの構造とすると、 $D_{M_1}=\{$ 苗木誠, 舞園さやか, 桑田怜恩, $\cdots \}$ 。
　　名前記号から存在物への対応付けは例えば、 $F_{M_1}(a_1)=$ 苗木誠 , $F_{M_1}(a_2)=$ 舞園さやか , $\cdots$ 。
　　例えば $o_{1,1}(\tau_1)$ が「 $\tau_1$ を殺した犯人」のような1項演算子なら、 $F_{M_1}(o_{1,1})($ 舞園さやか $) =$ 桑田怜恩。
　　例えば $\theta_{2,1}(\tau_1, \tau_2)$ が「 $\tau_1$ は $\tau_2$ を殺した」のような2項述語なら、 $F_{M_1}(\theta_{2,1})($ 苗木誠, 舞園さやか $) = 0$ 。
　　このように、各名前記号が指す存在物、各 $n$ 項演算子が指す存在物（項が指す存在物による）、各 $n$ 項述語の
　　真偽（項が指す存在物による）を完全に決めれば、この論理体系のすべての基本述語の真偽は完全に決まる。

　　※ ここで、「桑田怜恩が舞園さやかを殺したから $F_{M_1}(o_{1,1})($ 舞園さやか $) =$ 桑田怜恩」ということではなく、
　　　あくまで $o_{1,1}(\tau_1)$ という1項演算子をこの写像で定義したということに注意。
　　※ ただ、 $o_{1,1}(\tau_1)$ が本当に「 $\tau_1$ を殺した犯人」になるように定義されていて、 $\theta_{2,1}(\tau_1, \tau_2)$ が本当に「 $\tau_1$ が
　　　 $\tau_2$ を殺した」かどうかを表すように定義されているなら、 $\theta_{2,1}(o_{1,1}(\tau_1), \tau_1)$ はどの解釈でも真になりそう。
　　　殺されていないキャラクターを代入したときの取り扱いは適切にする必要があるけど。

　　他方、別の解釈の下では、論理体系にはスーパーダンガンロンパ2のキャラクターの構造 $M_2$ が当てはめられて
　　いるかもしれない。 $D_{M_2}=\{$ 日向創, 七海千秋, $\cdots \}$ 。
　　この場合の名前記号の対応付けは例えば、 $F_{M_2}(a_1)=$ 日向創 , $F_{M_2}(a_2)=$ 七海千秋 , $\cdots$ かもしれない。

量化論理式の真偽を解釈するには、への割り当てをすべての存在物に変異させる（というより、これがという論理式の定義そのものである）。
- $\langle M, g \rangle (\forall \xi \varphi)=1 \; \Longleftrightarrow \;$ すべての $a \in D_M$ について $\langle M, g \rangle [ \xi \mapsto a] (\varphi) = 1$ である．
- $\langle M, g \rangle (\exists \xi \varphi)=1 \; \Longleftrightarrow \; \langle M, g \rangle [ \xi \mapsto a] (\varphi) = 1$ となる $a \in D_M$ が存在する．
解釈について、以下が成り立つ。
- その変項が項／論理式の自由変項でないなら、その変項を変異させても項が指す存在物／論理式の真偽は変わらない。
- 項／論理式の変項にある項を代入した上で解釈しても、解釈の割り当ての変異によって変項をある項に変えても、どちらの場合も項が指す存在物／論理式の真偽は変わらない。
- 項 $\tau_1$ と $\tau_2$ が指す存在物が同じなら、項／論理式の変項を $\tau_1$ に変異させても $\tau_2$ に変異させても項が指す存在物／論理式の真偽は変わらない（外延性）。

一階述語論理における妥当な推論

意味論的含意の概念は一階命題論理のときと同じ。
量化論理式が推論の前提 or 帰結になる場合に色々な定理が成り立つ。

練習問題5.48
$n$ 項述語に渡せる項のセットのパターン数は、 $|D_M|^n$ パターンある。
それぞれのパターンが1か0を取りうるので $n$ 項述語は $2^{|D_M|^n}$ 種類ありうる。
例えば、 $D_M =\{A_1, A_2\}$ で、 $n=2$ だったら、 $2$ 項述語 $\theta_{2, i}$ は16種類ある。

$\tau_1$	$\tau_2$	$\theta_{2,1}$	$\theta_{2,2}$	$\theta_{2,3}$	$\theta_{2,4}$	$\theta_{2,5}$	$\theta_{2,6}$	$\theta_{2,7}$	$\theta_{2,8}$	$\theta_{2,9}$	$\theta_{2,10}$	$\theta_{2,11}$	$\theta_{2,12}$	$\theta_{2,13}$	$\theta_{2,14}$	$\theta_{2,15}$	$\theta_{2,16}$
$A_1$	$A_1$	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0
$A_1$	$A_2$	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0
$A_2$	$A_1$	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0
$A_2$	$A_2$	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0

練習問題5.55

「奇数の二乗は奇数である」は真だが、 $\forall x ($ 奇数 $(x) \; \land$ 奇数 $(x \times x) \, )$ は、 $x$ に例えば $2$ を割り当てたとき偽。
「二乗が奇数であるような奇数が存在する」は真で、 $\exists x ($ 奇数 $(x) \to$ 奇数 $(x \times x) \, )$ も真だが、前者は $2$ を割り当てると偽で、後者は $2$ を割り当てても真（というか後者はどんな数を割り当てても真）。

練習問題5.58　面倒なので略。

練習問題5.60　面倒なので略。

練習問題5.62　面倒なので略。

練習問題5.65　面倒なので略。

練習問題5.82　面倒なので略。

練習問題5.84　面倒なので略。

練習問題5.86　面倒なので略。

練習問題5.88　面倒なので略。

練習問題5.90　面倒なので略。

練習問題5.91
$\forall x (F(x)) \land G(a) = \! \! \! | | \! \! \! = \forall x (\lnot \lnot F(x)) \land G(a)$ を証明するには、二重否定律より $F(x) = \! \! \! | | \! \! \! = \lnot \lnot F(x)$ なので、これに量化論理式の置き換えを用いて $\forall x (F(x)) = \! \! \! | | \! \! \! = \forall x (\lnot \lnot F(x))$ 。これと $G(a) = \! \! \! | | \! \! \! = G(a)$ に対し複合論理式の置き換えを適用。

所感

「 $x$ は哺乳類である」「 $x$ は卵生である」の変項 $x$ に「友達の鈴木君」を割り当てる（98ページ）：確かに友達の鈴木君は哺乳類だし、卵生ではないけど、鈴木君的には友達からの扱いが「哺乳類の一個体」でいいのだろうか…。
集合における外延性は、「集合はそれが含む要素によって一意に定まる」。外延性の公理 - Wikipedia
一階述語論理の解釈の外延性（定理5.64）は、「論理式の真偽は項が指す存在物によって一意に定まる」。当たり前に感じられすぎてよくわからない。「定義されたこと以外は知らないふりをする《知らないふりゲーム》」（数学ガールゲーデルの不完全性定理の31ページ）は、こと「ある論理式が真か偽か」については経験がありすぎるので難しい。
ラムダ計算（114ページ）って何。
- ラムダ計算 - Wikipedia