読者です 読者をやめる 読者になる 読者になる

数理論理学: ノート4

読んでいる本(出典): 数理論理学 | 戸次 大介 |本 | 通販 | Amazon

前回: ノート3 / 次回: まだ
目次: 数理論理学

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

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

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

一階述語論理の意味論

  • 命題論理のときと同様、「 I: 論理式の集合  \rightarrow 真偽の領域 D_t \equiv \{1, 0\}」であるような解釈  I を考える。
    命題論理のときは、 I は「原子命題の真偽の組合せの全パターン」ということで  2原子命題の数 個あった。
    一方、一階述語論理では原子命題がさらに項と述語に分かれるので、「各項が指し示しているもの」「各述語について、項が指し示しているものに対応する、論理式の真偽」として考えるのがよい(構造  M)。
    あと変項もあるので、変項に何を割り当てたかも論理式の真偽にかかわる(割り当て  g)。
    つまり、ある1つの解釈  I = \langle M, g \rangle を与えるには、以下を完全に決めればよい。
    • そもそもどんなものたちについて命題を述べるのか(存在物)の集合:  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 かもしれない。

  • 量化論理式 \forall \xi \varphi, \; \exists \xi \varphi の真偽を解釈するには、 \xi への割り当てをすべての存在物に変異させる(というより、これが \forall \xi \varphi, \; \exists \xi \varphi という論理式の定義そのものである)。
    •  \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 11111111 00000000
 A_1  A_2 11110000 11110000
 A_2  A_1 11001100 11001100
 A_2  A_2 10101010 10101010
練習問題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ページ)って何。