第Ⅳ部のまとめ 347 記号そのものに求めた。これもまた , 第 II 部でヒンティッカ集合の充足可能性を証明した際に用 いたやり方と同じだった。 ・公理系 AFOL の完全性証明の副産物として , コンパクト性定理とレーヴェンハイム・スコー レムの定理が導かれる。 言語 FOL を用いることによって , ある分野の基本的知識を公理系のかたちで与えることが できる。それは , AFOL の公理 ( 論理公理 ) に , さらにその分野に特有の公理 ( 固有公理 ) を付 け加えることによってなされる。こうした公理系を理論と呼ぶ。 ・理論の例として , ロビンソン算術 Q を紹介した。 Q は自然数とその上の足し算 , かけ算に ついての基本的知識を公理化したものである。 Q はその作り方からして , 自然数の世界をモデル にもっことは当然だが , 自然数とは同型でない構造もモデルにもってしまう。こうしたモデルを 非標準的モデルと言う。ある理論が同型のモデルしかもたない場合 , その理論を範疇的と言う が , 0 は範疇的ではない , ということだ。 ・それどころか FOL で書くことのできる算術の理論はかならず , 自然数全体の集合に同型で ないようなモデルをもってしまうことが証明できる。これにはコンパクト性定理が使われる。 ・第 12 章の最後に , FOL をこれまでとは異なった方向に拡張することを試みた。ギーチ・カ プラン文や「無限にたくさんのものがある」のような文は , FOL の論理式として表すことがで きない。こうした文も翻訳しようとすると , 論理式で述語記号が占めている位置を量化しなけれ ばならない。こうした量化を許す論理を第 2 階の論理と言う。 ・述語への量化を許す第 2 階の言語を用いると , 数学的帰納法の公理が表現可能になる。この 公理を Q に付け加えると , 第 2 階のペアノ算術という公理系になる。第 2 階のペアノ算術 PA2 は範疇的である。つまり , PA2 のモデルはすべて自然数全体の集合に同型なものばかりであ レーヴェンハイム・スコーレムの定理などの性質を失ってしまう。 ・しかしながら , 第 2 階の論理は表現力の高さと引き替えに , 第 1 階の論理がもっていたコン パクト性 , 完全性 ,

第 12 章古典論理にもまだ学ぶことがたくさん残ってる レーヴェン / 、イム・スコーレムの定理 329 完全性定理の証明で構成したモデル M について振り返ってみよう。 M の論議領域は , そもそ ものに含まれていた項とそれに付け加えた可算無限個の個体定項からっくれるだけっくった 項の全体からなっている。付録 A の 4.4 で確認したように , FOL に含まれる項の数は可算無限 個だから , M の論議領域は可算無限の濃度をもっている。そして , M をある意味で縮めて最終 的につくったモデル M' の論議領域の濃度は明らかに M の濃度と同じかそれよりも小さい。 を可算モデル countable model と言う ) が存在する。 のとき , △を充足するモデルで高々可算個の個体からなる論議領域をもつようなものにれ 【定理 53 : レーヴェンハイム・スコーレムの定理】論理式の集合△は充足可能だとする。 のことから , 次の定理が導かれる。 Q の文法 おこう。ロビンソン算術 (Robinson arithmetic) と呼ばれる理論だ。この理論を Q で表す。 と論理 (logic) をごっちゃにしないように。実例が手つ取り早いので , 理論の例を次に挙げて の形でまとめることができる。これを第 1 階の理論 (first order theory) と言う。理論 (theory) FOL で許される語彙と FOL で定義できる論理式とを使って , ある分野の基本的知識を公理系 公理的理論とは 12.3 第 1 階の理論 充足可能である。したがって , △も可算モデルによって充足可能である。■ る極大無矛盾集合が存在する。完全性定理の証明から明らかなように , I** は可算モデルによって 【証明】△が充足可能なら , △は構文論的に無矛盾である ( 健全性による ) 。そうすると△ IÄ* な ( 1 ) ( 1 ) ( 2 ) ( 3 ) ( 4 ) 語彙 原子項 個体定項 0 個体変項 x, y, z, 述語記号はつかわない 関数記号 1 変数関数記号 2 変数関数記号 論理定項 ーロ「コ → , ▽ 十 , △ ,

342 第Ⅳ部論理学はここから先が面白い ! 進んだ話題のロードマップ いてしか語らない第 1 階の論理は許せる。しかし第 2 階の論理は明らかに集合の存在について 語っているので論理じゃない , ということになる。存在論的にヘビーなのだ。 12.5.3 第 2 階のペアノ算術 限個しかない。だから MII の図式は高々可算無限個の性質をカバーしているにすぎない。 すべてをカバーしている。一方 , PA 1 の開論理式に対応する性質は , どんなに多くても可算無 ( 付録 A の定理 64 を見よ ) 。だから M ドの「すべての性質について・・・・・・」は非可算無限個の性質 N と考えてよいだろう。 N の部分集合は全部でどれだけあるかと言うと非可算無限個もある よれば , D の部分集合に他ならない。いまは自然数論を考えているから , D は自然数全体の集合 マンとある。 M12 の X が量化している「性質」とは , 第 2 階の論理に与えたセマンティクスに M ドの X が量化の対象としている性質には , PA 1 の論理式が対応していないようなものが , ゴ ・・つてことは , PAI の言語じや表現できないような性質があるってこと ? そうである。 ているのだ。 現できようができまいが , とにかくありとあらゆる性質について数学的帰納法が成り立っと言っ ついて , 図式が成り立っと言っているにすぎない。これに対し , M ドは PAI の言語によって表 ついて図式が成り立っと言っている。ということは , PA 1 の言語で表現できるすべての性質に それが違うんだなあ。 M ドは M ll よりもずっと強いことを述べている。 M ll は任意の論理式に 立つってことでしょ ? 」 り立つってことは , ようするにすべての性質 X について ( X0 △ Vx ( Xx → XSx ) ) → VxXx が成り 「ん ? M II と M ドって同じことじゃないの ? 任意の論理式について M II の図式の代入例が成 の公理じたいは第 1 階の論理式だ。ここで , 注意深い読者は次のような疑問をもつだろう。 これは , PA 1 でつくることのできる無限個の公理を一括して表す図式である。でもその個々 → V xAx MII x を自由変項としてもっ PAI の任意の論理式 Ax について (AOAVx(Ax → ASx)) 階のペアノ算術 (PAI) の固有公理は Q の固有公理に次の公理図式を加えたものだ。 第 2 階のペアノ算術があるなら , 第 1 階のペアノ算術もあるのだろうか ? それはある。第 1 とになる。 ことを述べている。これを公理として認めれば , 自然数に数学的帰納法が使えることを認めたこ を持っ (Vx(Xx → XSx)), のであれば , 圃すべての自然数が性質 X をもっ (Vxxx) 」という ち (XO) , (ii) 任意の自然数 x について , それが性質 X をもっと仮定すると , その後者も性質 X induction) と呼ばれるからだ。これは , 「どんな性質 X についても , ( i ) もし 0 がその性質 X をも M ドという名前がついているのは , この公理が第 2 階の数学的帰納法の原理 (mathematical M12 VX((XOA Vx()x → XSx)) → VxXx) だ。 PA2 の固有公理はロビンソン算術 Q の固有公理に次の公理を加えたものである。 theory) という。その代表選手は第 2 階のペアノ算術 (second order peano arithmetics : PA2) SOL に与えられた表現手段を使って公理系の形にまとめた理論を第 2 階の理論 (second order

430 排中律 背理法 索引 ( 事項 ) 44 , 232 70 , 296 フレームにおいて妥当な式 文 1 25 分析タブロー 93 分析的真理 46 分配律 44 , 51 文法形式 16 ー 分離規則 249 閉鎖経路 98 閉鎖タブロー 99 閉論理式 125 , 137 ー 38 ベキ集合 355 巾等律 44 , 51 ヘンキンの定理 268 , 323 変形規則 248 ( アサインメントの ) 変種 ( 付値関数 V の ) 変種 143 ( モデル M ) の変種 143 方針 S 141 方針 S における真理の定義 3 14 146 148 命題論理 メタ言語 メタ定理 1 1 2 88 2 2 2 派生規則 259 パースの法則 45 裸の個体定項 124 反証モデノレ 152 , 303 開いた式 125 , 137 表現定理 76 評価手続き 214 非排他的選言 39 否定式 44 , 63 否定 2 。 必然的真理 47 必然性演算子 3 。 5 必然化規則 3 。 6 非単調論理 7 。 ( 論証の ) 非妥当性 非古典論理学 28 。 非可算集合 36 。 反例 62 範疇的 335 反対対当 159 メタ論理的変項 26 メレディスの公理系 260 モデノレ 136 ー 37 , 152 モデル M の変種 143 モデノレ集合 105 モデルにおいて妥当な式 313 ー 14 モデルのもとでの真理 138 10 方針 T 141 枚挙 365 ま 行 ( タブローが ) 開いて終わる ヒンティッカ集合 105 , 194 フアジーな述語 287 99 ( モデル M はアサインメントびに よって論理式 A を ) 満たす 145 無限基数 364 無限集合 359 矛盾 4 , 58 , 151 ( シンタクス的に ) 矛盾している ( セマンティクス的に ) 矛盾してい 262 唯名論者 341 有限基数 364 有限充足可能 84 有限小数 351 郵便はがきのパラドクス 有理数 35 。 様相オペレータ 3 。 5 様相論理 3 。 5 様相論理の完全性 318 ライプニツツの原理 2 。 4 理性の真理 46 リテラノレ 34 理諞 329 理言侖のモデノレ 331 リンデンバウムの補助定理 や・ら・わ行 90 269 , フアジー言侖王里 286 付加律 44 不完全記号 210 複合命題 19 含み 381 付値関数 55 , 136 復活規則 2 1 8 復活はいつでも OK 部分集合 352 部分順序集合 299 部分論理式 34 普遍量化子 1 16 普遍例化 1 29 負リテラノレ 34 プール関数 75 フレーゲの公理系 フレーム 31 1 2 2 1 249 る 262 矛盾記号 234 矛盾規則 293 矛盾式 43 矛盾対当 158 矛盾の導出 227 矛盾の見つけ方 228 レモン・コード 309 連言 2 。 連言肢 34 連鎖推論のパラドクス 連続体仮説 364 連続体濃度 363 ロビンソン算術 329 論議領域 134 誦言正 3 論証の形式 13-15 論証の妥当性の判定 論証の内容 13-15 論理形式 16-17 論理結合子 2 。 323 287 101 矛盾律 44 無矛盾 4 , 263 無理数 350 命題関数い 4 , 166

330 ( 5 ) ( 2 ) 第Ⅳ部論理学はここから先が面白い ! 量化子▽ , ヨ 同一性記号 補助記号 項 , 論理式の定義 進んだ話題のロードマップ これらの語彙から , FOL の項の定義 , 論理式の定義に沿ってつくられる記号列が , 0 の項 , 論理式である。「 0 の論理式」と言ったとき注意してほしいのは , これは 0 で provable な式と か , Q の公理になっている式という意味ではなく , Q の語彙でつくることのできる式 , という意 味だということだ。 Q の公理 0 の公理は次の 2 つのグループからなる。 ( 1 ) 論理公理 (logical axiom) これはどんな第 1 階の理論も共通にもっている公理だ。具体的には AFOL の 6 つの公理を Q の論理公理とすればよい。ただし , AFOL の図式文字 (), 穹 , 了 ) に代入して考えてよい記号 は , Q の語彙とそれに基づいてつくられる Q の項と論理式に限られる。 ( 2 ) 固有公理 (proper axiom) これはそれぞれの理論に固有な公理であって , これによりその理論に固有な記号 ( 関数記号や 個体定項 , 述語記号 ) に「意味」が与えられる。当然のことながら , この部分は理論ごとに異な る。ロビンソン算術 0 では次の 7 つの公理を置く。 Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7 V V ぐは手ぐ→ S 穹手 S の V 穹 ( 0 手 S の V 穹は手 0 →ヨぐは = S V は十 0 = の V 穹▽ぐは + S ぐ = S は + の ) V 穹は・ 0 = の V 穹 V ぐは・ s ぐ = ( は・ぐ ) + の ) Q のモデル 数学で「算術」と言ったとき , それは「読み書き算盤」のことではなく , 自然数と加法 , 乗法 という演算についての理論を意味している。 Q はその意味での算術を公理的理論の形に整備した ものだ。だから , Q の固有公理は次のモデルで真になる。というより , そもそもそうなることを 意図してつくられている。

目 9.5 同一性記号を含む自然演繹 246 シンタクスの視点から論理学のゴールに迫る 第 10 章 10. 1 公理系という発想 248 10.2 シンタクスとセマンティクス 260 10.3 命題論理の公理系の完全性証明 265 第Ⅲ部のまとめ 第Ⅳ部論理学はここから先が面白い ! 進んだ話題のロードマップ 第 11 章めくるめく非古典論理の世界にようこそ ! 11.1 11.2 11.3 11.4 古典論理は神の論理である 2 値原理と排中律のいかがわしさ 多値論理 284 直観主義論理 292 古典論理の拡張としての様相論理 3 。 4 281 第 12 章古典論理にもまだ学ぶことがたくさん残っている 12.1 12.2 12.3 12.4 12.5 完全武装した述語論理の言語 FOL 319 AFOL の完全性とそこから得られるいくつかの結果 322 第 2 階の論理 338 モデル同士の同型性 332 第 1 階の理論 329 第Ⅳ部のまとめ C . A. 付 ブックガイド 422 B . 練習問題解答 366 A little bit of mathematics ・ 248 ・ 349 ・ 345 319 280 ・ 277 350

第 10 章シンタクスの視点から論理学のゴールに迫る 267 ( 4 ) B は公理と r の要素を出発点として , MP を有限回当てはめて得られたものであるから , B も V のもとで真である。以上により , I* を充足する任意の真理値割り当てのもとで B も真で あるから , kB であることが言えた。・ 難しいのは , IÄ kB ト B の方向だにつちの方向だけを指して完全性と言うことも多い ) 。 これを次に証明しよう。 完全性の証明法 完全性を証明する方法にはいろいろなものがある。これから紹介するのはレオン・ヘンキン (Leon Henkin) が 1949 年に行った証明である。これは次の 2 つの点で優れた証明だと思う。 ( 1 ) rFB は , 仮定 I' から B への deduction があることを述べているが , deduction という 概念はどの公理系での deduction なのかを抜きにしてはじつは意味がない。そうすると , 本来は異なる公理系があれば , I*kB っ rFApLB, rkB r ト、 DB ・・・という具合に そのつど完全性を証明しなくてはならないはずなのだ。これはちょっと・・ とすると , 完全性の証明はどんな公理系についても応用できるもの , つまり個々の公理系の特殊事情 に左右される箇所ができる限り少ないような証明であることが望ましい。ヘンキンの証明 はそうした特質を持っている。 ( 2 ) ヘンキンの証明は , 拡張性に富んでいる。述語論理の公理系 , 第 IV 部で紹介する様相 論理などの様々な論理の公理系に対する完全性の証明にすぐに応用がきく。 10.3.2 ヘンキンの証明のアウトライン ヘンキンの定理 以下では APL の完全性を証明するが , これはごくわずかな手直しで ND の完全性証明に書き 換えることができる。まず , 次の 2 つの定理から出発して証明すべきことがらをもう少し証明し やすい形に変えておく。 【定理 43 】いかなる論理式の集合と論理式 A についても , 次が成り立つ。 IAI=A IÄU{—•A} は充足可能でない ( 意味論的に矛盾する ) 。 【定理 40 】いかなる論理式の集合と論理式 A についても , 次が成り立つ。 FA IACJ{•A) は構文論的に矛盾する。 定理 43 は定理 40 のセマンティクス版と言える。定理 40 は練習問題 80 ですでに証明済みだ。 また , 定理 43 はごく簡単に証明できるから練習問題にしておく ( 一 ) 。 さて , 証明すべき完全性は , IÄ kA つト A だった。定理 43 によりこれは I*CJ{¯IA) は充足可能でないっ I*FA と同じことである。そしてこれはさらに , 定理 40 により

索引 ( 事項 ) 接続詞 14 セマンティクス 36 , 103 , セマンティクスの形式化 124 ー 25 136 26 ー 第 2 階の理論 代人規則 249 互いに素 350 高々可算集合 ロ 9 多重様相 3 。 5 多重量化 167 「だけ」 342 360 , 131 同一性記号 2 。 3 同一性を含む述語論理 同一律 44 閉じた式 125 い 37 特称否定判断 121 特称肯定判断 121 同濃度 359 同等 359 同値類 356 同値関係 51, 188 , 355 到達可能性 31 導出線 216 導出 216 統語論 35 同型なモデル 334 同型性定理 334 同型写像 333 202 漸化式 27 前イ牛 34 選言 20 , 39 選言肢 34 選言的三段論法 44 , 全射 358 全称肯定判断 121 全称否定判断 121 全称量化子 16 全単射 358 前十是 3 前提規則 217 前提棒 216 像 356 双射 358 双条件法 42 63 多値論理 38 , 284 妥当式 151 ( 論証の ) 妥当性 1 。 , 62 タブロー 93 タブロー構成の攻略法 タブローの信頼性 1 。 2 , 189 100 段階 299 単射 357 単純命題 1 9 ターンスタイル 単調性 69 値域 356 254 429 99 ( タブローが ) 閉じて終わる トロジー 43 , 46 トロジーの判定 1 。 1 束縛されて現れている 束縛変項 124 存在記号 1 1 7 存在措定巧 5 存在量化子 17 存在例化 128 ー 29 チャーチのテーゼ 200 中概念 161 206 「ちょうど」 直観主義論理 292 直観主義的に妥当 3 。 3 直観主義数学 292 直積 354 超限基数 364 チューリングマシン 2 。。 展開規則の制約条件 128 展開規則 96 , 126 ー 29 デカルト積 354 停止問題 199 定義域 356 強い完全性定理 266 , 322 強い置き換えの定理 52 , 71 直観主義論理の決定手続き 3 。 4 直観主義論理の完全性 3 。 4 303 直観主義論理における意味論的帰結 ド・モルガンの法貝リ 44 , 51 , 117 トリビアルに成立する 83 第 1 階の衄 「コロロ 第 1 階の量化 第 1 階の理論 対応理論 3 1 5 大概念 161 339 340 329 た行 対角線論法 363 対偶 5 。 対偶律 44 , 51 対象言語 88 大小対当 159 大前提 161 代替案としての非古典論理 内包的文脈 181 中への写像 358 「ならば」 39 ー 40 2 項関係 166 2 項結合子 33 2 項述語 166 2 次下位導出 217 2 重ターンスタイル 2 重否定律 44 , 51 2 値原理 38 , 28 。 2 変数関数 357 認識史分析 3 。 4 濃度 36 。 どん詰まり 313 67 305 対当関係 158 第 2 階の ロロロ 339 第 2 階のペアノ算術 342 添加律 44 伝統的論理学 121, 158 同一者不可識別の原理 ー 63 204 は行 場合分けによる証明 64 排他的選言 39

345 第Ⅳ部のまとめ ・第Ⅲ部までで学んできた古典論理学は , ある理想化が施されていて , そのために学びやすい 美しい体系になっていた。その理想化は , 次の 2 つの点に見られる。 ( 1 ) 結合子はすべて真理関数 的である。 ( 2 ) 2 値原理を採用する。 ・第 11 章では , まず 2 値原理の採用にまったをかけてみた。まず , 2 つの会話を通じて , 2 値原理を採用することに異議がありうることを示した。次に , 2 値原理あるいはそのダイレクト な表現である排中律を認めない論理学をつくるにはどのようにすればよいかということを考え ・論理学から 2 値原理や排中律を取り除く仕方は 1 つではない。まず , 論理式のとりうる真理 値を真と偽の 2 つだけに限るのではなく , 真・可能・偽という具合に第 3 の真理値を認めるとい うやり方がある。この路線に従ってつくられる論理が多値論理だ。その代表的なものとして , ウ カシエヴィッツの 3 値論理を紹介した。第 3 の真理値を認めた結果 , 排中律だけでなく , 矛盾律 など古典論理では論理的真理とされていたいくつかの式も論理的真理の座を失うことになった。 ・次に , 曖昧な述語のもつ論理を扱うためのフアジー論理を多値論理の 1 種と位置づけて紹介 した。曖昧な述語を無理矢理に 2 値原理のもとで扱おうとすると , 連鎖推論のパラドクスが生じ る。フアジー論理のセマンティクスをやや立ち入って展開し , フアジー論理によればそうしたパ ラドクスが生じないことを示すことができた。 ・以上のやり方は , セマンティクスの視点に立って論理学から 2 値原理や排中律を取り除こう としたものと考えることができる。しかし , 排中律を取り除くためのやり方はこれだけではな い。そこで , 公理系 ( 自然演繹 ) から theorem として導出できなくなるようにすることによっ て , 排中律を捨てるというシンタクス的なやり方を考えてみた。この結果得られたのが直観主義 論理である。 ・直観主義論理においても , theorem でなくなるのは排中律だけではない。 2 重否定をはず すことができなくなる , 背理法を使うことができなくなる , ド・モルガンの法則や対偶律が成り 立たなくなるといった副次的な結果が生じるということが分かった。 ・どのような論理体系を考える場合でも , セマンティクスとシンタクスの両面から攻めていく ことが重要だ。本書では多値論理の扱いはセマンティクスの面からのものに留まったが , もちろ ん多値論理の公理系をつくることはできる。直観主義論理に関しては , セマンティクスも紹介し

422 C. ブックガイド パズルで入門しちゃおうという本。 [ 1988 ] は演繹的でない様々な推論について詳しく知るには格 しろい。ただし , ギャグ感覚は相変わらずかなりディープ。 [ 1987 ] もゲーデルの不完全性定理に した本。ゲーデルの不完全性定理への導人にもなっている。扱われている題材はどれも深く , おも [ 1989b ] はルイス・キャロルの不思議の国のアリスを題材にして論理学とはどんなものかを解説 ・内井惣七 [ 1989b ] 『パズルとパラドックス』講談社現代新書 ・内井惣七 [ 1988 ] 『シャーロック・ホームズの推理学』講談社現代新書 ・内井惣七 [ 1987 ] 『うそとパラドックス』講談社現代新書 ギャグセンスに耐えることが必要。 最良の入門書。ただし , 自然演繹を開発した「ゲンツェン」を「ゲリべン」と洒落る , オヤジな グマシン , 決定不可能性などについてさらに進んだ話題を勉強したい人にはまず第一にお勧めする 機械的手続き , という観点から書かれたユニークな論理学のテキスト。アルゴリズム , チューリン ・内井惣七 [ 1989a ] 『真理・証明・計算 : 論理と機械』ミネルヴァ書房 を知るために , これ以上よい本はちょっと見あたらない。 様相論理と可能世界意味論が言語と世界についての考え方にどのような影響を与えたかということ ・飯田隆 [ 1995 ] 『言語哲学大全Ⅲ : 意味と様相 ( 下 ) 』勁草書房 の優れた解説書。ラッセルの記述理論についても詳しく触れられている。 か , 現代論理学の創始者たちがどのような問題意識で言語と論理の問題にとりくんだのかについて フレーゲに始まる現代論理学がそれまでの伝統的論理学と比べてどのような点ですぐれているの ・飯田隆 [ 1987 ] 『言語哲学大全 I : 論理と言語』勁草書房 なのか ! と驚くことだろう。 非古典論理に興味を持ったら , ぜひ覗いてもらいたい本。非古典論理ってこんなにバラエティ豊か ・赤間世紀 [ 1992 ] 『計算論理学入門』啓学出版 ◎日本語で読める本 十音順に並べて紹介しておく。 で触れることのできなかったトピックを含んでいる本 , などのうち , 比較的手に入れやすいものを , 五 以下に , 本書を読んでさらに勉強したい人が読むべき本 , 私が本書を書くときに参考にした本 , 本書 好の本。ホームズの推理は本書で扱う演繹的推論とはちょっと違う。親しみやすく思えて , レベルは相当高いとみた。 ・内田種臣 [ 1978 ] 『様相の論理』早稲田大学出版部 真理様相だけでなく , 認識論理 , 義務論理などにも触れていて , 様相論理の幅広さを知る ' きる。 ・大出晃 [ 1991 ] 『自然な推論のための論理学』勁草書房 じつは とがで