第 10 章シンタクスの視点から論理学のゴールに迫る に無矛盾であることの証明と , ( 2 ) * が極大であることの証明の 2 つに分けて行う。 ( 1 ) IÄ* が無矛盾であること。 【証明】 271 ( 2 ) 【証明の前半】まず , 数学的帰納法を用いて , 系列 , IÄい・・・に現れるあらゆるが構文論的に無 矛盾であることを示す。 [Basis] は無矛盾である。なぜなら , は IÄにほかならず , IÄは仮定により無矛盾だから。 [lnduction stepl 集合の系列 ・・において , IÄk + 1 より前にあるすべての集合が無矛盾であ るとする ( 帰納法の仮定 ) 。 このとき , l'k + 1 も無矛盾であることを言おう。定義により , l*k + 1 は IAk U {Ak) が無矛盾であれ ば l*k U {Ak) であり , そうでなければである。前者の場合 , l*k + 1 は明らかに無矛盾。また , 後者の場合 , + l=IAk であるから , l*k + 1 は帰納法の仮定により無矛盾。 以上より , 系列 , い・・・のあらゆる要素が構文論的に無矛盾であることが分かった。■ 【証明の後半】次に示さなければならないのは , 系列 ro, I*I , ・・に現れるあらゆるが構文論的 に無矛盾であるならば , I** = CJI*i も構文論的に無矛盾だということである。これを示すには , 次の補助定理を使う。 【補助定理 44 ー 1 ー 1 】論理式の集合が構文論的に矛盾しているとき , のなんらかの有限部 分集合が構文論的に矛盾している (deduction の有限性 , つまり I' からの deduction で実際 に使われる I* の要素はいつも有限個であるということより , これはほとんど自明。だから 証明は省略 ) 。 IÄ* が構文論的に矛盾していると仮定する。そうすると , 補助定理 44 ー 1 ー 1 により I** のなんら かの有限部分集合にが構文論的に矛盾している。このに自体がそのまま系列 , , ・・・に出てく るという保証はないので , ちょっと工夫しなければならない。 には有限集合だから , それに含まれる式の中には最も番号の大きな式があるはずだ。それを Aj としよう。そうすると , にに含まれる式はみな + 1 のメンバーになっている。ところが , も しかりににが構文論的に矛盾しているのだとすると , r' に含まれる式はみな I'J + 1 のメンバーな のだから , l*j + 1 も構文論的に矛盾していることになってしまう。これは , 系列 1*0, I'I , ・・・のあら ゆる要素が無矛盾であるという仮定に反する。■ IÄ* が極大であること。 【証明】 IÄ* が無矛盾だが極大でないとしてみよう。そうすると , 少なくとも 1 つの論理式 Aj が あって , I**IJ{AJ} は無矛盾かっ Aj I' * となっているはずだ。 さて , 構文論的に矛盾した集合を部分集合として含むいかなる集合も構文論的に矛盾している から , この対偶をとれば , 構文論的に無矛盾な集合のどの部分集合も無矛盾である。ところで , rjU{Aj} は ' U { A 。 } の部分集合であるから , に U { A 。 } が無矛盾なら rjU{AJ} も無矛盾。しか し , だとすると , I** の構成の仕方によって , U {Aj } が I*J + 1 とされたはずだ。つまり , Aj e IÄ」 + 1 であり , したがって , Aj e I** だったはずなのである。これは仮定に反する。したがって , IÄ* U { Aj } が無矛盾であり , しかも Aj P* となるような式 Aj は存在しない。つまり , 1'* はつけ
270 第Ⅲ部論理をもう 1 つの目で見る 10.3.3 補助定理 44-1 の証明 補助定理 44 ー 1 は , 無矛盾な式の集合はいつでもそれを部分集合として含む極大無矛盾集合に 拡大することができるという内容だ。そこでこれを証明するには次の 2 段構えでいく。 ( 1 ) 任意の無矛盾な式集合が与えられたときにそれを * にまで拡大するための手順を与え ( 2 ) その手順に従って I* を拡大した IÄ * が本当に極大無矛盾集合になっていることを示す。 IÄを I** にまで拡大する手順 すべての論理式の集合は枚挙可能である , つまりすべての論理式を自然数の番号をつけて 1 列 に並べることができる ( 分からない人は付録 A の 4.4 を見よ ) 。そこで , すべての論理式を枚挙し た列が 1 つ与えられているとしよう。無矛盾なからはじめて , そこにこの列から論理式を順 にとってきて , もしそれを I' につけ加えても矛盾しないのならつけ加える , という操作を繰り 返し適用して , を膨らませていく。この操作によって極大無矛盾集合 IÄ * に到達できるのでは ないだろうか。具体的には次のようにして P* に達する。 【手順】次のようにして , 式の集合の系列 , IÄI , ・・・をつくる。 ( 1 ) I*O = I' とする。 ( 2 ) Ai が論理式の枚挙において i 番目に現れる論理式だとしよう。そのとき , ・ l*i U {Ai) が構文論的に無矛盾であるなら , それを IÄi + 1 とする。つまり , ・ IÄiCJ { Ai } が構文論的に矛盾するなら , + 1 = じとする。 {Ai) l*i + 1 この系列の 論理式は無限にたくさんあるので , この系列も終わりのない系列になる。だから , 最終項を極大無矛盾集合としましよう , と言うことはできない。そこで , I** が次の性質をもっことは作り方によって明らかである。 うにしてできた系列 , , ・・・に現れるすべての集合の合併集合を IÄ * とする。 【手順 ( 続き ) 】 P* = CJI*i なる集合 IÄ* を考え , これを極大無矛盾集合とする。つまりこのよ ( 1 ) 集合 I' * は定義によって , 系列 , , ・・・に現れる集合のどれかに属しているような式は 次に , こうしてつくった * が極大無矛盾であることを証明する。それは , ( 1 ) IÄ * が構文論的 I** が極大無矛盾であることの証明 ( 2 ) 集合 I' * はを部分集合として含んでいる。 みんな含んでおり , それ以外の式は含まない。
264 第Ⅲ部論理をもう 1 つの目で見る (a) {PvQ, P → Q , ¯IP} 構文論的無矛盾性 (b) {PvQ, •(PAQ), P—Q) (c) {P → Q, P, -•Q) うち ND 矛盾している論理式の集合はどれか , そしてそれが ND 矛盾していることを示せ。 式集合の構文論的無矛盾性と同じように公理系についても構文論的無矛盾性を定義することが できる。 【定義】公理系 K が構文論的に無矛盾である な論理式 A が存在しない。 K には , I—A かっ ト A となるよう K が矛盾した公理系だとどういうことになるのだろう。 A, ¯IA からは任意の式 B が deduci- ble だから , 結局 , 矛盾した公理系からは任意の式が provable だということになってしまう。 どんな式も出てくるような公理系なんて全くのナンセンスだろう。したがって構文論的無矛盾性 は公理系がまず第 1 に満たすべき最低限の要件だと言える。幸いなことに , 我々の公理系 APL については次の定理が成り立っている。 【定理 41 】 APL は無矛盾である。 証明はとても簡単。練習問題 76 で証明しておいた APL の健全性からすぐにえられる。 【証明】 APL は健全である。つまり , FA A はトートロジー , が成り立つ。したがって , トー トロジーでない論理式は APL で provable ではない。もし APL が矛盾していたら , APL ではあら ゆる論理式が provable のはずだから , provable でない式があるということは APL が無矛盾である まとめておこう。 マンティクスの両面から攻略しようとしていることがわかっただろうか。 10.2.3 完全性かなせ重要なのか ことを意味している。■ ' こでそれを表の形に トンネル工事が山の両側から掘り進むように , 論理学は 3 つの論理学的概念をシンタクスとセ
第Ⅲ部論理をもう 1 つの目で見る 加えても無矛盾性を保つような式はすべて含んでいる。■ 【補助定理 44 ー 2 ー 2 】 IA* を極大無矛盾集合とし , A と B を任意の論理式とする。 272 10.3.4 補助定理 44-2 の証明 になる。これは IÄ* が無矛盾だという仮定に反するので , A は IÄ* の要素でないとした仮定が誤り 方 , に c I* * , かっ I' c I' * なのだから , I' U に c IÄ* である。このことより , I** も矛盾していること ところが , IÄト A であったから , IÄ U にト A かっ I* U r'k- ーとなり , U r' は矛盾している。 ということが証明できるから , これにより , にト¯nA となる。 矛盾していることになる。 こで , 定理 40 と同様に , r'k-¯nA r'U{A) は構文論的に矛盾 , る。そうすると , 補助定理 44-1--1 により I** のなんらかの有限部分集合 r' が存在して , に CJ (A) が I** の要素でないとしてみよう。そうすると , * の極大性により I* * U {A} は構文論的に矛盾してい こで , かりに A は 【証明】ト A であり , I** をを部分集合として含む極大無矛盾集合とする。 て閉じている ) 。 とする。このとき , A は IÄ * の要素である ( つまり , 極大無矛盾集合は構文論的帰結関係に関し 【補助定理 44-2-1 】 IÄト A であり , なおかっ * をを部分集合として含む極大無矛盾集合 やれやれ。 補助定理 44 ー 2 を証明するためにはさらに次の 2 つの補助定理を導入しておかねばならない。 2 つの補助定理 を真にする首尾一貫した真理値の割り当て方が決まるということを示す。 最後に , 極大無矛盾集合 * が与えられると , それに含まれるすべての式を , そしてそれだけ だった。■ このとき , 次が成り立つ。 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) AGI** A △ B I' * A → BeIÄ* Ae → BGI'* —IAGP* (AEI** かっ BEIA*) または (AGIÄ* かっ BGIÄ*) AGIÄ* または BGIÄ* AGIA* または BGIÄ* AGI** かっ BGI'* この証明で補助定理 44 ー 2 ー 1 が活躍する。 —•AGI** と仮定する。そうすると , 極大無矛盾集合の定義によってに U { A } は矛盾す だと I* * は矛盾してしまい , I* * の無矛盾性に反するから。 【 ( 1 ) の証明】 AGI** と仮定する。そうすると , A * である。なぜなら , AGP* かっ¯nAer*
268 第Ⅲ部論理をもう 1 つの目で見る I*U{¯•A) は充足可能でない PU{¯•A) は構文論的に矛盾する と同じことである。さらに , ( 5 ) の対偶は IÄCJ{•A) は構文論的に無矛盾•PCJ{¯IA) は充足可能 である。 だから , 一般に ようするに , 自分に含まれていない式をそれ以上 1 つでもつけ加えたとたんに矛盾してしま ではないすべての論理式 A に対し△ U { A } は構文論的に矛盾している。 【定義】論理式の集合△が極大無矛盾である△は構文論的に無矛盾であり , △の要素 定義される。 しかもある意味でそれ以上大きな集まりはないようなぎりぎりの集合だ。正しくは , 次のように imally consistent set) と言われる。これはを部分集合としてすつほり含んでいて , 無矛盾で , ( 4 ) で「 r をすつばり含んだ証明上都合の良い集合に」と呼んだものは極大無矛盾集合 (max- 極大無矛盾集合 ( 5 ) * はを含んでいるから , ( 4 ) でつくった真理値割り当ては IÄのすべての式を真にす り当てを簡単に作り出すことができる ( そんな風につくったんだから ) ということを示す。 ( 4 ) I' * はその作り方からして , そこに含まれるすべての論理式を同時に真にする真理値割 ( 3 ) 或るやり方でを拡大して , をすつばり含んだ証明上都合のよい集合 IÄ * をつくる。 る。 から直接そうした真理値割り当てを構成することはできない。そこで次のように考え ( 2 ) ところが「構文論的に無矛盾ですよ」というだけではについての情報が乏しすぎて , なやり方はに応じてそのような真理値割り当てをつくる手順を与えることである。 て真にすることのできるような真理値割り当てがあることを示せばよい。一番ストレート ( 1 ) ヘンキンの定理を証明するには , 構文論的に無矛盾な集合 I* に含まれる論理式をすべ ヘンキンの定理を証明すれば強い完全性が証明されたことになる。この証明方針は次の通り。 ヘンキンの定理をどのように証明するか 定理の I* を I*U { A } とした特殊ケースだから , ヘンキンの定理からすぐに出てくる。 真にするような真理値の割り当てがある , ということを証明しておけばよい。 ( 6 ) はヘンキンの つまり , 構文論的に無矛盾な論理式の集合には必ずそれにふくまれるすべての論理式を一斉に 【定理 44 : ヘンキンの定理】論理式の集合が構文論的に無矛盾 I* は充足可能。
第 10 章シンタクスの視点から論理学のゴールに迫る 269 う , ぎりぎりまで大きくした無矛盾な式集合のことを言う。それ自体を相手にしていると , そ れに含まれる式をすべて真にする真理値割り当てを構成する方法が見あたらないのだが , 1* を極 大無矛盾集合 I* * にまで拡大すると , I* * に含まれる式をすべて真にする真理値割り当てはいっ でも同じ手順で簡単に手にはいることが示される。そして , c * ゆえ , この真理値割り当て はのすべての式を真にするから , は充足可能であることがわかる。これがヘンキンの定理 を証明する手順だ。 ・・あれ ? そのままだったら充足する真理値割り当てが見つからないから , うまい具合に拡 大して真理値割り当てをつくってやる , という手法はどこかで見たような・・ そうである。コ ンパクト性定理を証明したとき , タブローの方法が信頼できることを証明するために開放経路を ヒンティッカ集合へと拡大したとき , などにやったことと同じことをやろうとしているわけだ。 練習問題 82 極大無矛盾集合は次のように定義されることもある。 ることを示せ。 この定義は本書で採用した定義と同値であ 【定義】論理式の集合△が極大無矛盾である△は構文論的に無矛盾であり , 任意の論理 式 A について , 2 つの補助定理 以上のことから , 分かる。 A か A のいずれかが必ず△の要素になっている。 ヘンキンの定理を証明するには次の 2 つの補助定理を証明すればよいことが 【補助定理 44 ー 1 : リンデンバウムの補助定理 (Lindenbaum's lemma) 】 r が構文論的に無矛 このあとは , 2 つの補助定理を順に証明していく。それで完全性証明は完了。 極大無矛盾集合は充足可能である ( これは図の ( 2 ) に対応する ) 。 と , IÄ * に含まれるすべての式を真にする首尾一貫した真理値割り当てが決まる。つまり , 【補助定理 44 ー 2 : 極大無矛盾集合の充足可能性補助定理】極大無矛盾集合 * が与えられる 存在する ( これは図の ( 1 ) に対応している ) 。 盾な式の集合であるとき , を部分集合とするような極大無矛盾集合 1* * が少なくとも 1 っ 無矛盾 44 ー 2 極大無矛盾補助定理 ( 1 ) 補助定理 44 一 1 充足可能 ゆえ自明 充足可能
第 12 章古典論理にもまだ学ぶことがたくさん残ってる 323 が成り立っことを証明しなければならない。念のためにこの定理の意味をおさらいしておこう。 IÄFA は , 論理式の集合に属するいくつかの論理式を仮定して A を導く , 公理系 AFOL にお ける deduction があることを意味している。 I=A は , I* に属する論理式をすべて充足するモデ ルとアサインメントのもとで , つねに A も満たされる , ということを意味している。 完全性定理はどのように証明されるか ( 方針 ) 述語論理の完全性定理を最初に証明したのはかの有名なゲーデルだ ( 1930 年 ) 。しかし , 以下 にアウトラインを説明する証明法は , 1949 年にヘンキンが証明しなおしたときのヴァージョン である。その基本的方針は , 第 10 章で紹介した命題論理の完全性証明と全くかわらない。つま ( 1 ) まず , 証明すべきことを次の 2 つの方向にわける。 【定理 49 ー 1 】 I*FA ( 健全性 ) 【定理 49 ー 2 】 IÄk-A PI=A ( 完全性 ) ( 2 ) このうち健全性は簡単に証明できる。 AFOL の公理がすべて妥当式であることと , 変形規 則が意味論的帰結という性質を保存すること , つまり A, A → B ト B と A → B ト A → V EB を 示せばよい。 ( 3 ) 完全性の証明の方が難しい。ここでも命題論理の場合と同じように , 定理 49 ー 2 と同値な 結果 , 【定理 50 : ヘンキンの定理】論理式の集合 IÄが構文論的に無矛盾は充足可能。 を証明する。 ( 4 ) で , その証明をどのようにやるかというと , これまた命題論理の場合と基本的アイディア は同じ。 IA から直接に求めるモデルをつくることは難しいので , I* を含む都合の良い集合 ( 極大 無矛盾集合 ) IÄ * に I' を拡大したのちに , その I* * を充足するモデルをつくればよい。具体的には 次の 2 つの補助定理を証明する。 【補助定理 50-1 : リンデンバウムの補助定理】が FOL の論理式の無矛盾な集合であると き , を部分集合にする極大無矛盾な集合 I' * が少なくとも 1 っ存在する。 【補助定理 50 一 2 】極大無矛盾集合 I* * が与えられると , それに含まれるすべての論理式を充 足するモデル ( とアサインメント ) をつくることができる。つまり極大無矛盾集合は充足可 ような個体を用意しておけばよいのだろう。そのヒントはタブローの信頼性を証明した 7.3.5 こうしたモデルをつくる材料をどこから調達しようか ? つまり , 能である。 モデルの論議領域にはどの
この 2 つの定義はまったく別物だ。しかしそれでも , どちらも矛盾というばんやりした日常的 概念を論理学的に厳密化したものだと言ってよい。それは , これらの定義からそれぞれ次のよう によく似た結果が導かれるからだ。乱暴に言うと , 「矛盾からは何でも出てくる」ということ 第 10 章シンタクスの視点から論理学のゴールに迫る が構文論的に矛盾していないとき , I* は無矛盾であると言う。 •13 → A ・・ 263 【定理 39 】 ( 1 ) IÄが意味論的に矛盾している ( 2 ) I' が構文論的に矛盾している っ 任意の式 B について , 任意の式 B について , ト B ( 1 ) についてはとっくの昔に証明してあるので , 【証明】が構文論的に矛盾していると仮定する。 こでは APL について ( 2 ) を証明しておこう。 このとき定義により , I* I—A, l*k- •A となるよ うな論理式 A が存在する。したがって , 任意の式 B について A, •A ト B を示せば , I* から A の deduction, から¯nA の deduction, A と¯nA から任意の B への deduction が存在することにな るから , これら 3 つの deduction を並べて 1 つの deduction をつくれば , それはから任意の B へ の deduction になる。というわけで A , -- - ・ - IA ト B を示そう。 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ⑧ ⑨ A → ( B →ー IA ) ( ー・ IB →ーー - IA ) → ( ( ーー IB → A ) → B ) A → ()B → A) ()B → A) → B B ・・・仮定 ・・・仮定 ・・・ A 1 ・・・ ( 2X3 ) MP ・・・ A 3 ・・・ ( 4X5 ) MP ・・・ A 1 ・・・ ( 1X7 ) MP ・・・ ( 6X8 ) MP これにより , 構文論的に矛盾した式の集合からは任意の論理式の deduction が存在することが証 明された。ー ( 1 ) 次の定理を証明せよ。 練習問題 80 tion できない論理式がひとつでもあることを示せばよいことが分かる。 以上のことにより , が ( 構文論的に ) 無矛盾であることを証明したかったら , r から deduc- ( 2 ) IÄト NDA, I* トなる論理式 A があるとき , を ND 矛盾していると言うことにする。次の 【定理 40 】 IAU{•A) が構文論的に矛盾している rFApLA
B. 練習間題解答 415 真理値割り当てが存在しない I* kA 82 【証明】△を論理式の構文論的に無矛盾な集合とする。このとき , 次の 2 つの条件が同値であるこ とを言えばよい。 ( 1 ) 任意の論理式 A について , A △△ U{A) は構文論的に矛盾 ( 2 ) 任意の論理式 A について , Ae △または一 lAe △ ( 1 ) ( 2 ) の証明 背理法を用いる。 ( 1 ) が成り立つが ( 2 ) は成り立っていないとしよう。そうすると , B △かっ—IB △なる論理式 B が存在する。このとき , ( 1 ) より , △ U { B } も△ U { B } も構文論的に矛盾している。 定理 40 より , △ U {—nB) が矛盾している△ト B であるから , この B については△ト B である。 さて , 一方 , △ U { B } が構文論的に矛盾しているということは , △ ,BFC, △ , B ト c , なる論理式 C が存在するということである。しかしいま , △ト B であるから , △だけを前提して , C もも provable であることになる。これは△が無矛盾であるという前提に反する。したがって ( 2 ) が成り立 たないとしたのはまちがいだった。■ ( 2 ) ( 1 ) の証明 任意の A について Ae △または•Ae △であるとする。 このとき , (a) Ae △の場合 , ( 1 ) の前件は偽 , したがって ( 1 ) は成立する。 (b) •Ae △の場合 , Ae △とすると , △は矛盾してしまうので , AG △である。 このとき , △ ,AFA △ , A ト A ( なぜなら Ae △だから ) となり , △ U{A) は構文論的に矛盾する。したがって ( 1 ) は成立する。■ 83 B ト A → B は D3 に他ならない。これは証明済みである。ーート A → B の方は演繹定理により , ¯lAh—A → B •A,Ak-B この右辺はすでに 263 ページで証明済みである。 84 ( 1 ) A V B A △ B Ae•B 11 11 11 1 L.O LO LC 0 0 1 0 0 1 1 0 0 0 0 0 A 0 . 5 A 0 . 5 A 0 . 5 1 0 . 5 1 1 1 1 1 0 1 1 ( 2 ) A も B も真理値が 0.5 の場合を考える。 このとき A → B の真理値は 1 である。これに対し , —nA v B の真理値は 0.5 になる。したがって , この 2 つの式はつねに同じ真理値をとるわけではな 1 A 0 ¯IA A ^ ¯IA 0 0 1 1 0 1 1 よ 1 0 1 1 0 1 1 0 ( 5 ) A の真理値が 0.5 のとき -•A も 0.5 。 したがって•A ← A は 1 になる。つまり—•A ← A は
278 部は , 第Ⅲ部論理をもう 1 つの目で見る こうした概念を式の形だけに注目した変形によって捉えようとする立場に立っている。 この 2 つの立場はどちらが優れているというようなものではなく , 両者が補いあって論理学 を支えていると考えるべきだ。そして , この 2 つの捉え方は , 概念的にはルーツを異にするが , その広がりにおいては一致することを示すことができる。つまり , から A が構文論的に帰結 するならばから A は意味論的にも帰結するし , その逆も成り立つ。また I* が構文論的に矛盾 しているなら , 意味論的にも矛盾しているし , その逆も成り立つ。 A が theorem ならば A は トートロジーだし , その逆も成り立つ。これらはみな完全性定理から導くことができる。この意 味で完全性定理は , セマンティクスとシンタクスの架け橋となる定理であり , 山の両側から掘っ てきたトンネルが確かに真ん中で出会うことを保証してくれる定理でもある。 ・第 10 章の後半では完全性定理を証明した。証明法はヘンキンによるものを用いた。その一 番重要なアイディアは , 構文論的に無矛盾な式の集合 IÄが充足可能だということを言うために を拡大して都合のよい集合 ( 極大無矛盾集合 ) をつくり , そこから真理値割り当てを派生させ るというところにある。そしてこれは , すでにコンパクト性定理の証明 , ヒンティッカ集合の充 足可能性の証明などを通じて読者にはおなじみの証明法だったはずだ。