2005/06/01 志村先生 [前回] # 直前でなく、その少し前の話から... LK の完全性定理 →A が LK で証明可能 <=> A が恒真 これの証明 ( <= ) の中で... | A から始まるタブローを用いた これの代わりに \Ganmma | \Delta から始まるタブローを用いると.. \Ganmma → \Delta が LK で証明可能 <=> \Ganmma → \Delta が恒真 を示すことができる。 # ここで、用語を少し整理する.. def 論理式 A は v(A)=1 となる付値 v が存在するとき 論理式 A は「充足可能」であるという。 # 恒真の双対概念 A が充足可能 <=> \not A が恒真でない # これは、対偶を取れば、直に解る def 論理式の集合 \Ganmma ( 無限集合でも良い ) が「充足可能」とは ある付値 v が存在し、任意の A \in \Ganmma に対して v(A)=1 def \Ganmma → \Delta が「充足可能」とは、 ある付値 v が存在し、 任意の A \in \Ganmma に対して v(A)=1 または、 任意の B \in \Delta に対して v(B)=0 Col. \Ganmma → \Delta が充足可能でない <=> \Ganmma → \Delta が恒真 def. \Ganmma, \Delta が論理式の集合 ( 無限かもしれない ) の時 \Ganmma → \Delta が「LK で証明可能」 <=> \Ganmma の有限部分集合 \Ganmma_0 \Delta の有限部分集合 \Delta_0 があって、 \Ganmma_0 → \Delta_0 が LK で証明可能 と定義する。 # LK では、もともと、両辺に、有限のものしか考えていなかった # => 無限の場合も考えなければならない # 有限個の場合は、元の定義と一致している ( ので、自然な発展にっている ) ## 前回やったのは、有限個の場合だけだった。 今回は、\Ganmma, \Delta が無限の場合も同値であることを証明する。 => 「LK の強完全性」 # 証明の方法は色々あるが... == [今回の話] LK の強完全性 任意の論理式の集合 \Ganmma, \Delta に対して \Ganmma → \Delta が LK で証明可能 <=> \Ganmma → \Delta が恒真 # 一般的な形で証明してもできるが、今回は話を簡単にするために、\Ganmma, \Delta が加算集合の場合を示す ## 「どうゆう場合に加算でないか ?」を考えるのも大変なのだが.. ここでは、\Delta, \Ganmma が加算集合の時の証明を行う # [考え方] \Delta, \Ganmma が加算集合なので、番号付けを行う \Ganmma = { A_0, A_1, A_2, ..., } \Delta = { B_0, B_1, B_2, ..., } # 普通、証明するときに、対偶の形で行う prof) \Ganmma → \Delta が証明可能でないとする ## 最初に、上記が「普通にはなりたたないこと」を示す。 特に、 A_0 → B_0 は LK で証明可能でない すると、(LK のもとの..) 完全性定理より v_0(A_0)=1, v_0(B_0)=0 となる付値 v_0 が存在する 同様に、 A_0,A_1 → B_0,B_1 は LK で証明可能でない ので、 v_1(A_0)=v_1(A_1)=1, v_1(B_0)=v_1(B_1)=0 となる付値 v_1 が存在する。 一般に、任意個数 n + 1 のものに関して v_n(A_0)=..=v_n(A_n)=1, v_n(B_0)=..=v_n(B_1)=0 となる、付値 v_n が存在する # 任意有限個に関して成立する 一方、我々が欲しいのは.. 「 v_n(A_0)=..=v_n(A_n)=..=1 v_n(B_0)=..=v_n(B_1)=..=0 を満す v が存在する」 こと。 現時点で、有限個に関しては、v が存在するが、それを用いて、無限個の場合を示したい。 # (しかし..一般的には.. ) 任意有限個に関して成立するからといって、無限個に成立するという保証はない ## 一種の方程式を解いている ( 根は、付値 ) # ここでは、論理式の話をしているが、すこし、それを離れて、「数」の話をする ## 「任意有限個に関して成立するからといって、無限個に成立するという保証はない」こと(例)を示すため.. [例] x_1, x_2, .., x_n を未知数とし x_1 = x_2 + 1 x_2 = x_3 + 1 .. x_n = x_{n+1} + 1 .. という方程式を考える 連立方程式有限個なら、解は存在する 無限個だとすると、そのような自然数の解は存在しない # x_0 = n とすると、x_{n+1} がマイナスの数になるので.. # 「任意有限個数で成立している場合に、無限個でも成立する」ことは不思議な状況 ## 普通は成立しない ( 当りまえには成立しない.. ) [K\"Onig (ケーリッヒ)の補題] 枝分れが有限であるような無限木は、無限の長さの道を持つ # 「木」をまず、ちゃんと定義しないといけない ( 有限木は、最初の講議でやった ) def ( T, \le ) が「木」である o \le は T の上の半順序 # 木の枝の親子関係が \le と対応する o \le に関する最小元がある # 木の根 (root) に相当する o { y \in T | y \le x } は有限全順序集合 # この集合は、x から root に到る道上のノードの集合を意味する ## 道の上にあるので、互いに比較可能 => 全順序 # cf. dag ( 後で合流する ) 場合は、この集合が全順序にならない # => 経路が二つに分れるので、途中で互いに比較できいない要素が存在する。 ## 「木」は、「合流」がない def (T, \le) が木の全順序部分集合を T の「道」と呼ぶ # 定義としては、root をふくめたり、極大性を入れることもある ## しかし、今回の証明では、どの定義でも、結果は同じ #{ y \in T | y \le x } は道だが、一般の道は無限集合に成りうる # def (T, \le) が無限 <=> T が無限 [例] 有限でない木の例 根の所で、 長さ 1 の枝 長さ 2 の枝 長さ 3 の枝 .... と無限に分岐している 無限木だが、道の長さはどれも有限 # n 番目の枝の長さは n なので.. 根の所の枝わかれだけが無限 ( 他の枝は分岐しない.. ) この木の性質 幾らでも長い道はあるが、無限の道はない => こんな変なことが起きるのは、無限に分岐する点があるから !! [K\"Onig (ケーニッヒ)の補題]の証明 ( T, \le ) : 無限木、どの点でも枝わかれは有限個 r を T の根とする この時、無限列 x_0 \le x_1 \le .. を次のように作る x_0 = r とする x_i の子 (x_i の直後の点) は、 有限個なので、 # def x に対して x \le y かつ、\forall z [ x \le z => y \le z ] とき、y を x の直後の点と呼ぶ それを t_0, t_1, .., t_m とする ( 有限個であることに注意. ) そして、それに対して、 T_k = { y | t_k \le y } とすれば、 T_k \cap T_j = \phai ( k \ne j ) # 木の性質から T = {x_0} \cup T_0 \cup T_1 \cup .. \cup T_m となる。 ここで、T は無限集合なので、 T_k の中に、少くても一つは無限集合になる # 引き出し論法 ので、そのような t_k を x_{i+1} とする。 このようにして、 x_0 \le x_1 \le 無限の道が作成できる。 # この {x_i} は、無限の道になるので、補題が証明できたことになる。 # ここで話を戻して、「LK の強完全性」の証明にたちかえる [「LK の強完全性」の証明] \Ganmma_i → \Delta_i を A_0, A_1, .., A_i → B_0, B_1, .., B_i とする。 すると ( 論理式が有限個数なので、) \Ganmma_i → \Delta_i に 現れる命題変数全体 (V_i) から、{1,0} への写像 ( 付値の可能性 ) は有限個 今、 T' = { | \exists i ( f : V_i → {0,1}, V_i 上で f と一致する v により \Ganmma_i → \Delta_i は充足される } # \Ganmma_i → \Delta_i を充足可能な付値 v の集合が T このような集合上で、次のように半順序を定義する def. \le <=> i \le j ( つまり V_i \sub V_j ) g は f の拡張 ( g を V_i に制限すると f と同じ ) # これでは、最小元が存在しないので、テクニカルに r' (根) を追加する T = T' r' (根) を追加したもの # このような T について、次のような性質が成立する o (i を固定すれば..) { | \in T } は有限集合 # もともと、f は V_i から{0,1} への写像なので、最大でも、2^|V_i| 個からないから.. ## これは「枝わかれが有限である」ことを意味する o T は木 # \le の定義より、枝の合流はありえない o T は無限木 # これは、充足不能性を利用している 任意の i に対して \in T となるような f が存在する ∵ \Ganmma_i → \Delta_i は、LK で証明可能でないので、 \Ganmma_i → \Delta_i を充足する付値 v_i を (V_i に) 制限すれば ( それが、求める なので、それを選べば.. ) 良い 上記の性質と、[K\"Onig (ケーニッヒ)の補題]を使うと、 T に無限の道 \le \le .. が存在する。 つまり、 f_0 \sub f_1 \sub .. となる系列が存在する。 この { f_i } に関係して f = \Cup f_n とすると、 1) f は \Cup V_i から {0,1} への写像 # これは、良く出るので、証明は略 !! 2) f と \Cup V_i 上で一致する付値は \Ganmma → \Delta を充足する ∵) \Ganmma = \Cup \Ganmma_n ( \Ganmma_0 \sub \Ganmma_1 \sub .. ) とし、 A \in \Ganmma とすると、(仮定より、) A \in \Ganmma_i となる i が存在し、 f_i と V_i 上で、一致する付値 v に対して v(A)=1 となる。 ここで、 f は f_i と V_i 上で一致し V_i \sub \Cup V_i が成立するので、 f と \Cup V_i 上で一致する 付値 v に対して v(A)=1 == [まとめ] LK の完全性が、有限個の場合に成立したことを利用して、無限の場合も成立することを示した 任意有限個で成立することが、無限でも成立するよう拡張することは一般にはできない # この証明は色々あるが.. # => 値が {0,1} という有限であることが利いている