言語：まとめと挑戦課題

要約

この課は、命題論理の言語を扱う単元を締めくくる。妥当性と真理の区別およびパラドックスの分析から、論理式の一意読み取り可能性と、言明と論証の形式化へと至る演繹の鎖を組み立て直し、各環でどの原理が使われ、それがどの課で証明されるかを示す。達成したことをコースの計画に照らして位置づけ、すでに構成した言語が、演繹を扱う次の単元の問いをなぜ提起するのかを説明する。まとめテストでは導入テストの技能を繰り返し、最後に、各課の問題より難しく、複数の課の道具を組み合わせることを求める六つの挑戦課題で終わる。

学習目標

単元の結果の論理的な順序を組み立て直し、各結果がよりどころとする原理と、それが証明される課を特定する。
閉包原理、語への分解、重みの補題、一意読み取り可能性がどのようにつながるか、そしてなぜ再帰的定義と形式化どうしの比較が一意読み取り可能性に依存するのかを説明する。
単元が証明したことを、仮定として認めたこと（二値原理、真理図式、帰納法の原理、否定論理和の読み）と、後の単元に残したことから区別する。
対角化補題、記号列の数え上げ、論理式に関する帰納法、重みの議論、略記の展開を組み合わせる問題を解く。

単元で達成したこと

この単元は、二つの記号からなるアルファベットから出発して、どの論理式もただ一通りに読める言語を構成し、その言語の性質を厳密に証明し、それと私たちが推論に用いる言語との間に橋を架けることを目指した。この目的は、いくつかの留保つきで果たされた。留保はそれぞれその場で明言してある。二値原理と真理図式は、第一の課が真理としてではなく明示的な仮定として認め、両者を同時に保つと何が起こるかを調べた。自然数に関する帰納法の原理は、ペアノの第五公理として認める。否定論理和の非形式的な読みは規約として定め、意味論の単元がそれを定義に変える。そして集合論のうち欠かせないもの（所属、包含、和集合）は、必要になった場所で教えた。これらの留保のもとで、たどってきた道は、四つの区間からなる一本の演繹の鎖として読める。

推論すること、言語について語ること

数理論理学とは何かの課は、コースの対象を定めた。それは言明の真理ではなく（それは各科学の仕事である）、真理の伝達である。論証が妥当であるのは、その形式が前提が真で結論が偽となる代入例を一つも許さないときであり、この定義から、妥当性が保証する唯一のことが導かれた。前提が真ならば、結論も真である。したがって、結論が偽である妥当な論証はどれかの前提が偽であり、形式が妥当でないのは、ちょうどそれが反例をもつときである。同じ結果が、パラドックスの分析を一つの手続きに変えた。矛盾に終わる推論の各段階が妥当ならば、どれかの仮定が偽であり、パラドックスを解くとはそれがどれかを見つけることである。嘘つきはこのように扱われた。そこでは、自分自身を偽だと言う文について、二値原理と真理図式を同時に保つことができない。ベリーのパラドックスと形容詞「非自己記述的」も同じように扱われた。床屋からは一般的な補題、すなわち対角化補題が取り出され、それは床屋が存在しないこと、そして制限のない内包原理が矛盾していることを証明する。最後にこの課は、対象言語とメタ言語の区別、そして表現の使用とその言及の区別を確立した。この区別が以後のすべてを支配する。論理式についての単元の結果は論理式ではなく、メタ定理である。

白丸と黒丸の言語

命題論理の言語の課は、集合と記号列を導入し、各長さの記号列を数え（ $2^{n}$ 個が長さ $n$ であり、 $2^{N + 1} - 2$ 個が長さ $1$ から $N$ までである）、基本言語を構成した。変数 $v_n = \sigO^{n}\sigI$ と、二つの論理式 $\varphi$ と $\psi$ から $\sigI\varphi\psi$ を作るただ一つの規則である。「それ以外に論理式はない」という条項は、論理式をすべての閉じた集合に属する記号列として定義することで厳密になり、この定義から閉包原理が導かれた。閉包原理によって、どの論理式も変数であるか $\sigI\varphi\psi$ であるかのどちらかで、その両方ではないこと、どの論理式も黒丸で終わること、そして奇数個の黒丸を含むことが証明された。変数と単独の黒丸が接頭符号をなすという観察から語への一意分解が得られ、それとともに重みの概念が得られた。この課はまた、以後用いるメタ言語も構成した。メタ変数、 $(\varphi \downarrow \psi)$ と書く否定論理和、そして六つの公式の略記である。各略記はそれより前の略記からただ一度だけ定義されるので、略記を用いたどの表現もただ一つの記号列を表す。

帰納法と一意読み取り可能性

自然数と論理式に関する帰納法の課は、前の課が「以下同様に」で済ませた数え上げを正当化し、単純な帰納法から累積帰納法を導き、それを長さに適用して構造帰納法を得た。構造帰納法は、論理式に移された自然数に関する帰納法そのものであることがわかる。この道具によって重みの補題が証明された。すべての論理式の重みは $+1$ であり、空でない真の語単位の接頭辞の重みはどれも高々 $0$ である。このことから、順に、どの論理式もほかの論理式の真の接頭辞ではないこと、そしてどの複合論理式もただ一通りに読めることが導かれる。一意読み取り可能性は、単元の残りすべてがぶら下がる環である。それは、言語の課が返していく借りとして記述した決定手続きを正当化し、再帰的定義（長さ、変数と結合子の黒丸の個数、部分論理式、深さ、代入）を正当なものにする。それがなければ、これらの定義は一つの論理式に二つの異なる値を割り当てかねない。

日本語から論理式へ

自然言語の形式化の課は、私たちが話す言語への橋を架けた。文字 $p$ 、 $q$ 、 $r$ 、 $s$ 、 $t$ を五つの決まった変数の名前とする規約を定め、どの形式化にも辞書を明示することを求め、否定論理和の規約上の読みだけから、各略記の読みを導いた。一意読み取り可能性によって、同じ結合子の二通りの異なるまとめ方が異なる論理式であることを証明し、長さの再帰的定義によって、展開した略記の長さを計算した。これは形式化を見分ける速い基準を与える。実質含意が偽になるのは前件が真で後件が偽のときだけであること、そしてそれが、部分の真偽だけに依存する読みのうちで、数学の条件つきの定理を真にする唯一の読みであることを示した。形式化が失うもの（量化子、時間、因果性、様相）を指摘し、最後に論証全体を前提の集合 $\Gamma$ と結論として形式化した。

次の図は、四つの区間を一本の鎖にまとめたものである。列の各節点は定義か結果で、論理的な順序で番号が付き、その証明が用いる前の環と弧で結ばれている。そのまわりに浮かぶのが支え、すなわち鎖が何度も立ち返る原理であり、それぞれはよりかかる環と実線で、確立される環と点線で結ばれる。ただし証明なしに認めるものは輪として描かれる。支えを押すと、それを使うすべての環が強調され、各環はそれが証明される課へのリンクになっている。決定手続きは言語の課で述べられているが、その論理的な位置は、よりどころとする一意読み取り可能性の後であることに注意しよう。

鎖の支え

A二値原理. すべての命題は真か偽かであり、その両方ではない。偽であることは、真でないことと同値である。パラドックスの分析において明示的な仮定として認める。この単元では証明なしに認める。
B真理図式. 文が真であるのは、その文の言うことが成り立つとき、かつそのときに限る。明示的な仮定として認める。タルスキの解決はこれを保つが、自分自身の真理述語を含まない言語の文に対してだけである。この単元では証明なしに認める。
C帰納法の原理. ある性質が $1$ について成り立ち、自然数 $k$ について成り立つたびに $k + 1$ についても成り立つならば、その性質はすべての自然数について成り立つ。これはペアノの第五公理であり、認めるものとする。この単元では証明なしに認める。
D対角化補題. 集まりのどの対象 $b$ も、 $R(b, x) \Leftrightarrow \neg R(x, x)$ を、その集まりのすべての $x$ について満たすことはない。確立される環: 3. 対角化補題.
E閉包原理. すべての変数がもち、 $\varphi$ と $\psi$ から $\sigI\varphi\psi$ へ受け継がれる性質は、すべての論理式がもつ。確立される環: 5. 閉包原理.
F構造帰納法. 長さに関する累積帰納法から導かれる、論理式の複雑さに関する帰納法。基底は変数であり、帰納段階はただ一つの形成規則である。確立される環: 9. 構造帰納法.
G一意読み取り可能性. $\sigI\varphi\psi = \sigI\varphi'\psi'$ であり、四つの記号列がすべて論理式ならば、 $\varphi = \varphi'$ かつ $\psi = \psi'$ である。確立される環: 11. 一意読み取り可能性.
H否定論理和の読み. 論理式 $(\varphi \downarrow \psi)$ が真であるのは、ちょうど $\varphi$ と $\psi$ がともに偽であるときである。これは規約として定める唯一の読みであり、ほかの読みはそこから導かれ、意味論の単元がそれを厳密にする。この単元では証明なしに認める。

第 1 区間推論すること、言語について語ること
- 妥当性と真理を区別し、妥当でない形式を反例で論駁する。
- 自然言語の曖昧さを見抜き、言明の読みを分ける。
- 対象言語とメタ言語を区別し、表現の使用とその言及を区別する。
- パラドックスを、その仮定を切り分け、どれを捨てるべきかを決めることで分析する。
1. 妥当性が保証すること. 論証が妥当で、その前提がすべて真ならば、その結論は真である。したがって、結論が偽である妥当な論証はどれかの前提が偽であり、形式が妥当でないのは、ちょうどそれが反例をもつときである。
  証明される授業: 数理論理学とは何か.
2. 嘘つきのパラドックス. 文 $m$ 、すなわち「文 $m$ は偽である」に適用すると、二値原理と真理図式は $V(m) \Leftrightarrow \neg V(m)$ を与える。 $m$ を含む言語では、二つの仮定のどちらかを捨てなければならず、タルスキの出口は、どの言語も自分自身の真理述語を含まないようにすることである。そうすれば $m$ は作れない。
  使う結果: 1. 妥当性が保証すること. 支え: A (二値原理), B (真理図式). 証明される授業: 数理論理学とは何か.
3. 対角化補題. $R$ が集まり $D$ の対象の間の関係で、各 $R(x, y)$ が真か偽かであるならば、どの $b$ も（ $D$ に属するものは）、 $R(b, x) \Leftrightarrow \neg R(x, x)$ を、すべての $x$ （ $D$ に属するもの）について満たすことはない。
  支え: A (二値原理). 証明される授業: 数理論理学とは何か.
4. 床屋とラッセル. 自分でひげを剃らない村の男たちだけの、ちょうどそのひげを剃る村の男は存在しない。また制限のない内包原理は矛盾している。集合 $Z = \{ x : x \notin x \}$ の存在を主張するからである。
  支え: D (対角化補題). 証明される授業: 数理論理学とは何か.
第 2 区間白丸と黒丸の言語
- 記号列の集合を記述し、各長さの記号列を数える。
- 論理式を最小の閉じた集合として定義し、そこから閉包原理を導く。
- すべての論理式の性質を証明し、それを使って記号列を退ける。
- 記号列を語に分解し、略記を基本言語まで展開する。
1. 閉包原理. 論理式の集合 $\mathcal{F}$ は、変数 $v_n = \sigO^{n}\sigI$ を含み、 $\varphi$ と $\psi$ とともに $\sigI\varphi\psi$ を含む、記号列の最小の集合である。したがって、変数がもち、 $\varphi$ と $\psi$ から $\sigI\varphi\psi$ へ受け継がれる性質は、すべての論理式がもつ。
  証明される授業: 命題論理の言語.
2. 論理式の形. どの論理式も、変数であるか、 $\sigI\varphi\psi$ （ $\varphi$ と $\psi$ は論理式）であるかのどちらかであり、その両方ではない。どの変数も $\sigO$ で始まり、どの複合論理式も $\sigI$ で始まる。
  支え: E (閉包原理). 証明される授業: 命題論理の言語.
3. 最後の記号と黒丸の個数. どの論理式も黒丸で終わり、奇数個の黒丸を含む。したがって、二つの論理式の連結も、記号列 $\sigI\varphi$ も、論理式ではない。
  支え: E (閉包原理). 証明される授業: 命題論理の言語.
4. 語への分解. 黒丸で終わる記号列はどれも、語、すなわち変数 $\sigO^{n}\sigI$ と単独の黒丸に、ただ一通りに分解される。各語はそのただ一つの黒丸で終わり、どの語もほかの語の真の接頭辞ではないからである。
  証明される授業: 命題論理の言語.
第 3 区間帰納法と一意読み取り可能性
- 単純な帰納法と累積帰納法で証明し、それらから論理式の複雑さに関する帰納法を導く。
- 重みの補題を証明し、一意読み取り可能性を導く。
- 記号列が論理式かどうかを判定し、その形成を組み立て直す。
- 論理式上の関数を再帰によって定義し、それらの間の関係を証明する。
1. 構造帰納法. 累積帰納法は単純な帰納法から導かれ、長さに適用すると、複雑さに関する帰納法の原理を与える。変数がある性質をもち、その性質が $\varphi$ と $\psi$ から $\sigI\varphi\psi$ へ受け継がれるならば、すべての論理式がそれをもつ。
  使う結果: 6. 論理式の形. 支え: C (帰納法の原理). 証明される授業: 自然数と論理式に関する帰納法.
2. 重みの補題. 変数の各出現の重みを $+1$ 、結合子の黒丸の重みを $-1$ とすると、すべての論理式の重みは $+1$ であり、論理式の空でない真の語単位の接頭辞の重みはどれも高々 $0$ である。特に、どの論理式でも、変数の出現は結合子の黒丸より一つ多い。
  使う結果: 8. 語への分解. 支え: F (構造帰納法). 証明される授業: 自然数と論理式に関する帰納法.
3. 一意読み取り可能性. どの論理式もほかの論理式の真の接頭辞ではない。したがって、 $\sigI\varphi\psi = \sigI\varphi'\psi'$ であり、四つの記号列がすべて論理式ならば、 $\varphi = \varphi'$ かつ $\psi = \psi'$ である。
  使う結果: 7. 最後の記号と黒丸の個数, 8. 語への分解, 10. 重みの補題. 証明される授業: 自然数と論理式に関する帰納法.
4. 決定手続き. $\sigO$ で終わる記号列は論理式ではない。 $\sigI$ で終わるならば、語に分解する。最初の語が変数ならば、その記号列が論理式であるのは、その変数が唯一の語であるとき、かつそのときに限る。最初の語が黒丸ならば、その後から借りを数える。借りが一度もゼロにならなければ、記号列は論理式ではない。ゼロになるならば、 $\varphi$ と $\psi$ の切れ目は借りが初めてゼロになるところにあり、各部分を同じ方法で調べる。ただし、空の記号列は論理式ではない。
  使う結果: 6. 論理式の形, 7. 最後の記号と黒丸の個数, 8. 語への分解. 支え: G (一意読み取り可能性). 証明される授業: 命題論理の言語.
5. 再帰による定義. 各変数の値と、 $\sigI\varphi\psi$ の値を、 $\varphi$ 、 $\psi$ とそれらの値から計算する規則が与えられれば、それらを守る論理式上の関数がちょうど一つ存在する。こうして長さ、部分論理式、深さ、そして常に論理式を生む代入が定義される。
  使う結果: 6. 論理式の形. 支え: C (帰納法の原理), F (構造帰納法), G (一意読み取り可能性). 証明される授業: 自然数と論理式に関する帰納法.
第 4 区間日本語から論理式へ
- 明示的な辞書を用いて言明を形式化し、各結合子の作用域を決める。
- 略記を展開して、二つの形式化が同じ論理式かどうかを判定する。
- 実質含意を日常言語の「ならば」から区別し、形式化が失うものを指摘する。
- 論証全体を前提の集合と結論として形式化する。
1. 略記の長さ. $L(\varphi) = a$ 、 $L(\psi) = b$ ならば、 $\neg\varphi$ 、 $(\varphi \vee \psi)$ 、 $(\varphi \rightarrow \psi)$ 、 $(\varphi \wedge \psi)$ の記号列の長さは $2a + 1$ 、 $2a + 2b + 3$ 、 $4a + 2b + 5$ 、 $8a + 8b + 15$ である。長さの異なる二つの形式化は異なる論理式である。
  使う結果: 13. 再帰による定義. 証明される授業: 自然言語の形式化.
2. 作用域と異なる論理式. まとめ方 $((p \wedge q) \vee r)$ と $(p \wedge (q \vee r))$ は異なる記号列である。もし一致すれば、一意読み取り可能性を二度適用することで、変数 $r$ が複合論理式 $(p \wedge q)$ と一致しなければならなくなる。
  使う結果: 6. 論理式の形. 支え: G (一意読み取り可能性). 証明される授業: 自然言語の形式化.
3. 実質含意. 含意 $(\varphi \rightarrow \psi)$ は $(\neg\varphi \vee \psi)$ の略記であり、偽になるのは $\varphi$ が真で $\psi$ が偽のときだけである。これは、部分の真偽だけに依存する読みのうちで、数学の条件つきの定理を真にする唯一の読みである。
  支え: H (否定論理和の読み). 証明される授業: 自然言語の形式化.

演繹へ. 鎖は、言語が構成され、論証が前提の集合と結論として形式化されたところで止まる。残るのは、ある論理式がいつほかの論理式から導かれるかを決めることである。まず次の単元で規則に従って記号を操作することによって、そして後にそれらの真理に注目することによって。