数理論理学とは何か

要約

この課では、数理論理学の対象を画定する。その対象は、各科学の領分である個々の言明の真偽ではなく、推論の形式と妥当性、すなわち前提の真が結論へ移ることを保証する、前提と結論の関係である。命題、論証、前提、結論、形式、反例を定義し、結論が偽である妥当な論証と、結論が真である妥当でない論証とによって、妥当性を真から区別する。また、多義的で自分自身について語ることのできる自然言語が、妥当性を厳密に研究するには足りない理由を示し、コース全体を支配する対象言語とメタ言語の区別を立てる。続いて、明示した仮定と証明を添えて、嘘つきのパラドックス、ベリーのパラドックス、床屋のパラドックス、そして床屋が先取りするラッセルのパラドックスを述べ、形式言語がそれらをどのように避けるか、あるいは定理に変えるかを説明する。最後に、数理論理学の四つの柱とコースの地図を示す。

学習目標

論証の妥当性を前提と結論の真から区別し、反例を構成して妥当でない形式を論駁する。
自然言語の多義性に気づき、多義的な言明の各読みを明確にする。
対象言語とメタ言語を区別し、表現の使用と言及を区別する。
パラドックスを分析する。すなわち、その仮定を取り出し、矛盾を導き、どの仮定を捨てるべきかを決める。

論理学は何を研究するか

直接の観察によらずに得られる知識は、すべて推論によって得られる。受け入れたいくつかの主張から、それらから帰結する別の主張へと移るのである。幾何学では、三角形の内角の和が二直角であることを知っている人は、鈍角を二つもつ三角形はないと結論する。医学では、ある病気が発熱を起こすことを知り、診察を受けている人に熱がないことを知っている人は、その病気を除外する。論理学は、この移行がいつ正当であるかを研究する学問であり、数理論理学はそれを数学の方法で研究する論理学である。すなわち、その対象である言語、論理式、演繹を正確に定義し、それらについての定理を証明する。

何を研究するのかを正確に述べるために、まず用語を定めておく。命題とは、真であるとも偽であるとも言うことに意味のある平叙文である。「 $7$ は素数である」は真な命題であり、「すべての偶数は $5$ より大きい」は偽な命題である。これに対し、疑問文（「いま何時か」）、命令文（「ドアを閉めよ」）、そして「 $x$ は偶数である」のように自由変数を含み、その値が $x$ の指すものに依存する表現は、命題ではない。

論証とは、命題の並び、すなわち前提と、それらの帰結として示されるもう一つの命題、すなわち結論との組である。前提はどんな命題でもよい。真でも偽でも、既知でも単なる想定でもよい。それらを前提にしているのは、論証の中で占める位置だけである。論証は、前提を一行ずつ書き、結論の前に「ゆえに」を置いて書くことにする。

例論証

ある数が $4$ の倍数ならば、それは偶数である。数 $28$ は $4$ の倍数である。ゆえに、 $28$ は偶数である。

前提は「ある数が $4$ の倍数ならば、それは偶数である」と「 $28$ は $4$ の倍数である」であり、結論は「 $28$ は偶数である」である。

論理学は真理の理論ではない

そうであれば、論証の前提が真かどうかを確かめることは論理学の仕事ではない。 $28$ が $4$ の倍数かどうかは算術が決め、ある人に熱があるかどうかは体温計が決め、ある戦いがある年に起きたかどうかは歴史が決める。真理とは何かを定義することも論理学の役目ではなく、それは哲学に属する問題である。論理学は、命題が何であれ真理値をもつことを認め、それらの値が互いにどう関係するか、特に、いくつかの命題の真がいつ別の命題の真を強いるかを研究する。言い換えれば、論理学は真理の理論ではなく、真理の伝達の理論である。

ところで、真理を伝えるものは論証の主題にではなく、その構造に依存する。先の論証を次の論証と比べてみよう。「ある動物が哺乳類ならば、それは空気を呼吸する。クジラは哺乳類である。ゆえに、クジラは空気を呼吸する」。両者は同じ形式をもつ。「あるものが $A$ ならば、それは $B$ である。 $c$ は $A$ である。ゆえに、 $c$ は $B$ である」。論証の形式とは、論理語（「でない」「かつ」「または」「ならば」「すべての」「ある」）を残したまま、論理語でない項（数、動物、性質）を文字で置き換えたあとに残るものである。形式の文字に内容を与えて得られる論証は、どれもその形式の代入例である。

形式が妥当であるとは、その代入例のどれ一つとして、前提がすべて真で結論が偽になることがないときをいう。論証が妥当であるとは、その形式が妥当であるときをいう。前提が真で結論が偽である代入例を、その形式の反例という。したがって、形式が妥当でないのは、ちょうどそれが反例をもつときである。

この課の証明では、日本語の速記を用いる。 $V(A)$ は「 $A$ は真である」の略記であり、 $F(A)$ は「 $A$ は偽である」の略記である。 $\neg$ は「でない」、 $\wedge$ は「かつ」、 $\vee$ は「または」、 $\Rightarrow$ は「ならば」、 $\Leftrightarrow$ は「のとき、かつそのときに限る」の略記である。 $\forall$ は「すべての」、 $\exists$ は「存在する」と読む。これらの記号はここではメタ言語の語の略記にすぎず、二重線の矢印はコース全体を通じてこの用法のために取っておく。次の課では、一重線の記号 $\rightarrow$ と $\leftrightarrow$ が、 $\neg$ 、 $\wedge$ 、 $\vee$ とともに、形式言語の略記として現れ、その意味はコースが正確に定める。矢印の線の違いが、どの水準で語っているかを思い出させてくれる。

命題妥当性が保証すること

論証が妥当で、その前提がすべて真ならば、その結論は真である。したがって、妥当な論証の結論が偽ならば、その前提のどれかが偽である。

証明

$\dato{p}{V(A_1) \wedge \cdots \wedge V(A_n)}$
前提が $A_1, \ldots, A_n$ 、結論が $C$ である妥当な論証をとり、前提がすべて真であると仮定する。
$\resaltar{A_1, \ldots, A_n, C}$
どの論証も自分自身の形式の代入例である。形式の文字に、論証の中でもっていた内容を与えればよい。
$\dato{v}{\neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \wedge \resaltar{\neg V(C)} \right)}$
妥当性の定義により、この形式のどの代入例も、前提が真で結論が偽になることはない。特に、論証そのものもそうはならない。
$\resaltar{V(C)}$
前提は真なので、否定された連言の中で成り立たなくなりうるのは結論の偽だけである。よって、結論は真である。
$\neg V(C) \Rightarrow \neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \right)$
逆に結論が偽ならば、前提がすべて真であることはありえない。そうであれば結論も真になるからである。

この命題は、妥当性が保証することを述べている。同じくらいはっきりと、妥当性が保証しないことも見ておくとよい。論証の妥当性、すべての前提の真、結論の真を組み合わせると、八通りの組合せのうち排除されるのはただ一つ、前提が真で結論が偽である妥当な論証の組合せだけであり、残りはすべて起こる。

例妥当で、結論が偽

すべての素数は奇数である。数 $2$ は素数である。ゆえに、 $2$ は奇数である。

形式はこの課の最初の論証と同じなので、この論証は妥当である。それにもかかわらず、結論は偽である。先の命題が欠陥の場所を示している。どれかの前提が偽であり、実際、最初の前提が偽である。 $2$ は素数で偶数だからである。妥当な論証は真理を生み出さない。受け取った真理を保つだけである。

例妥当でなく、結論が真

ある数が $4$ の倍数ならば、それは偶数である。数 $8$ は偶数である。ゆえに、 $8$ は $4$ の倍数である。

前提も結論も真であるが、それでもこの論証は妥当でない。その形式「あるものが $A$ ならば、それは $B$ である。 $c$ は $B$ である。ゆえに、 $c$ は $A$ である」には反例がある。数 $6$ を $8$ の代わりに置くと、前提は真のままであり（「ある数が $4$ の倍数ならば、それは偶数である」「 $6$ は偶数である」）、結論「 $6$ は $4$ の倍数である」は偽である。もとの結論の真は前提からではなく算術から来ている。 $8 = 4 \cdot 2$ である。日常の推論でよく見られるこの妥当でない形式を、後件肯定という。

ここから、この課で練習する実際的な規則が導かれる。論証が妥当でないことを示すには、どれかの前提や結論が偽であると指摘するだけでは足りず、妥当であることを示すには、その中のすべてが真であるだけでは足りない。前者には、その形式の反例を示すことが必要であり、後者には、すべての代入例に通用する推論が必要である。

自然言語と形式言語

妥当性の定義は二つの操作に依拠している。論証の形式を見分けることと、命題が真か偽かを決めることである。どちらも、各文がただ一通りに読めることを前提とする。自然言語、すなわち日本語、中国語、アラビア語のように、人間が正式な教育なしに身につけ、意思疎通に使う言語は、この条件を満たさない。詩や会話や含みに適した柔軟さが、同時に自然言語を多義的にもしているのである。

語彙的多義性：一つの語がいくつかの意味をもつ。話し言葉の「はしで待っている」は、橋のことも端のことも指しうる。
統語的多義性：一つの文がいくつかの構造を許す。「二かける三足す四」は $2 \cdot 3 + 4 = 10$ とも $2 \cdot (3 + 4) = 14$ ともとれる。
作用域の多義性：論理語が文のどの部分に作用するかがはっきりしない。「学生は全員合格しなかった」は、だれも合格しなかったという意味にも、全員が合格したわけではないという意味にもとれる。
不正確な結合子：「または」は、両方の選択肢が成り立つことを許す場合もあれば（「学位または職務経験が必要」）、それを排除する場合もある（「コーヒーか紅茶」）。「ならば」は、原因を表すこともあれば、規則を表すことも、単なる前後関係を表すこともある。

多義性に加えて、もっと深い特徴がある。自然言語は自分自身について語ることができるのである。自然言語には「文」「真である」「定義する」という語があり、それらを使って、「この文は九文字です」のように自分自身を指す文を作ることができる。この自己言及は一般には無害である。しかし、後で見るように、真理の概念と組み合わさると、真でも偽でもありえない文を生み出す。

形式言語は、この二つの困難の源を取り除くように設計される。記号の集まりであるアルファベットと、どの記号の並びが整式の表現であるかを解釈の余地なく定める形成規則とを定め、各表現の意味は、そのあと同じく正確な定義によって定める。こうして、記号の並びがその言語に属するかどうかは、規則を確かめることで機械的に解ける問題となり、各表現はただ一通りに読める。このコースの言語は、命題論理の言語についての課で構成されるが、そのアルファベットは白丸 $\sigO$ と黒丸 $\sigI$ のわずか二つの記号からなり、形成規則もただ一つである。

その代償は柔軟さである。形式言語は会話には使えず、それぞれの形式言語は、その規則が許すことしか表現できない。しかし、表現力がすべて犠牲になるというのは正しくない。一階論理の形式言語で、数学のほとんどすべてを書くことができる。犠牲になるのは多義性と制御されない自己言及であり、得られるのは、言語そのものについての定理を証明できる可能性である。

対象言語とメタ言語

ある言語を研究するには、それについて語らなければならず、それについて語るには別の言語が必要である。対象言語とは研究される言語であり、メタ言語とはそれを研究するための言語である。日本語で書かれたラテン語文法では、ラテン語が対象言語で、日本語がメタ言語である。このコースでは、対象言語は白丸と黒丸の形式言語であり、メタ言語は日本語である。ただし、数学記号と、対象言語の任意の論理式を表しながらそれ自身は対象言語に属さないギリシア文字 $\varphi$ 、 $\psi$ とで補われている。

この区別が中心的であるのには、はっきりした理由がある。このコースが形式言語について証明する主張（どの論理式もただ一通りに読めること、導出可能なものはすべて真であること）は、形式言語の論理式ではなく、メタ言語の文である。そのため、それらはメタ定理と呼ばれ、演繹体系が対象言語の内部で生み出す定理と区別される。

この区別の初歩的な形は、表現の使用とその言及とを分けるものである。「ローマは都市である」では、その語は都市について語るために使用されている。「『ローマ』は三文字である」では、その語は言及されており、括弧がそれを示している。この文が語っているのは語であって、都市ではない。両者を混同すると、「ローマは三文字である」のような不合理な言明や、「ローマは都市である。『ローマ』は三文字の語である。ゆえに、都市は三文字の語である」のような誤った論証が生まれる。

例三つの水準

対象言語としてラテン語をとろう。文「Roma aeterna est」は対象言語に属する。文「『Roma aeterna est』は三語からなる」はメタ言語、すなわち日本語に属し、真である。文「前の文は日本語で書かれている」はメタ言語の文について語っている。それは第三の水準、すなわちメタ言語のメタ言語に属する。同じ言語で書かれているにもかかわらず、である。同じ一つの言語がいくつもの水準で用いられることを妨げるものは何もない。大切なのは、何について語っているかを見失わないことである。

言語のパラドックス

矛盾とは、主張とその否定とを合わせたもの、たとえば $V(A) \wedge \neg V(A)$ である。パラドックスとは、受け入れられそうな仮定から出発し、妥当に見える段階を踏んで、矛盾に行き着く推論である。命題『妥当性が保証すること』により、段階が本当に妥当ならば、どれかの仮定が偽である。パラドックスを解くとは、それがどれかを見つけることである。パラドックスを、読みが複数あるにすぎない多義性と混同してはならず、また単に意外なだけのことと混同してもならない。

嘘つき

この種のパラドックスで最も古いものは、紀元前4世紀のミレトスのエウブリデスに帰される。その正確な形では、欺く意図を前提とする嘘ではなく、偽について語る。 $m$ を文「文 $m$ は偽である」とする。矛盾を得るには二つの仮定で足りるので、それらを明示的に書いておこう。

二値原理 (B)：すべての命題は真か偽かであり、その両方ではない。偽であることは、真でないことと同値である。
真理図式 (T)：文が真であるのは、その文の言うことが成り立つとき、かつそのときに限る。たとえば、「雪は白い」が真であるのは、雪が白いとき、かつそのときに限る。

定理嘘つきのパラドックス

二値原理と真理図式の仮定を文 $m$ に適用すると、矛盾に至る。両者を守るような真理値を $m$ に割り当てる方法はない。図では、文 $m$ が自分自身を指し、矢印が二つの可能性をたどっている。

証明

$\dato{B}{F(m) \Leftrightarrow \neg V(m)}$
二値原理により、 $m$ は真か偽かであり、その両方ではない。偽であることは真でないことである。
$\dato{T}{V(m) \Leftrightarrow \resaltar{F(m)}}$
$m$ が言うのは、 $m$ が偽であるということである。真理図式により、 $m$ が真であるのは、ちょうどその言うことが成り立つときである。
$V(m) \Leftrightarrow \resaltar{\neg V(m)}$
二つの同値をつなぐと、 $m$ の真はそれ自身の否定と同値になる。
$V(m) \Rightarrow \neg V(m), \quad \resaltar{\neg V(m)}$
$m$ が真だとすると、同値を左から右に読めば、それは真でない。この想定は自分自身を論駁するので、 $m$ は真でない。
$\resaltar{V(m) \wedge \neg V(m)}$
しかしそうなると、同値を右から左に読めば、 $m$ は真である。主張とその否定とが同時に得られる。

この定理は、論理学が矛盾しているとは言っていない。文 $m$ を含む言語では、二つの仮定を同時に保てないと言っているのである。したがって、出口は三つある。二値原理を捨てて真理値をもたない文を認めること、真理図式を制限すること、あるいは言語が文 $m$ を作れないようにすることである。三つめは、1933年のアルフレト・タルスキの出口である。ある言語の述語「真である」は、その言語ではなく、そのメタ言語に属する。そのような言語では、 $m$ は整式の文ではなく、パラドックスを述べることさえできない。

ベリーのパラドックス

このパラドックスは、1906年にバートランド・ラッセルが発表し、オックスフォードの図書館員ジョージ・ベリーに帰したもので、「真である」という語ではなく「定義する」という語を用いる。日本語の語句が自然数を定義するとは、その数を曖昧さなく特定できるように記述することをいう。たとえば、「十より大きい最小の素数」は $11$ を定義する。語句「定義に二十字以上要る最小数」を考え、これを書かれたとおりに読むことにし、それが定義しようとしている数を $b$ と呼ぶ。このコースでは、自然数は $1, 2, 3, \ldots$ である。

定理ベリーのパラドックス

日本語で用いうる文字の種類が有限であり、関係「語句がその数を定義する」が確定しているならば、矛盾に至る。数 $b$ が存在し、しかも二十字未満で定義できると同時に定義できない。図では、短い語句が、それらの定義する数へと送られており、それらの数は少ない。最初に空いたまま残る数が $b$ である。

証明

$\dato{N}{N \leq k + k^2 + \cdots + k^{19}}$
$k$ を用いうる文字の種類の数とする。一字の語句は高々 $k$ 個、二字の語句は高々 $k^2$ 個であり、以下同様に十九字の語句まで続く。したがって、二十字未満の語句は有限個であり、その個数を $N$ とする。
$\dato{D}{D = \{ d_1, \ldots, d_r \}, \quad r \leq N}$
各語句が定義する数は高々一つである。 $D$ を、二十字未満のどれかの語句が定義する自然数の集合とする。その要素は高々 $N$ 個である。
$(\exists n \leq N + 1)\,(n \notin D), \quad \resaltar{b \notin D}$
$N + 1$ 個の数 $1, 2, \ldots, N + 1$ の中には、 $D$ に属さないものがある。それらを順にたどると、 $D$ に属さない最初の数が、二十字未満では定義できない最小の自然数である。それより前の数はすべて $D$ に属する。
$13 < 20, \quad \resaltar{b \in D}$
ところが、語句「定義に二十字以上要る最小数」は十三字であり、まさに $b$ を定義している。
$\resaltar{b \in D \wedge b \notin D}$
主張とその否定とが同時に得られる。

語句が二十字未満であることを指摘するだけのよくある説明は、論証の半分を省いている。数 $b$ が存在することであり、それには文字の種類の有限性と、最初に欠ける数を選ぶことが必要である。破れるのは二つめの仮定である。「定義する」は日本語の正確な関係ではない。 $b$ を定義する語句が「定義」という語そのものを用いており、その意味は、どの語句を定義とみなすかに依存するからである。形式言語 $L$ においては、「 $L$ で定義可能」が何を意味するかを正確にできるが、その概念はメタ言語でしか表現できない。 $b$ を定義する語句は $L$ に属さず、矛盾は消える。 $b$ は $L$ では少ない記号で定義できないが、メタ言語では定義できるのである。

床屋とラッセルの集合

床屋のパラドックスは、ふつう次のように語られる。ある村に床屋がいて、その村の男であり、自分でひげを剃らない村の男全員のひげを剃り、しかもその人たちだけのひげを剃る。床屋は自分のひげを剃るか。「その人たちだけ」という言葉は欠かせない。この制限なしに、自分でひげを剃らない人全員のひげを剃る床屋なら、何の矛盾もなく自分のひげも剃ることができる。このパラドックスは、対角線的な形をした一般的な補題の特別な場合であり、その補題を一度証明しておく価値がある。

補題対角化補題

$D$ を対象の集まり、 $R$ をそれらの間の関係とし、対象の各対 $x$ 、 $y$ について、それらが $D$ の対象であるとき、主張 $R(x, y)$ が真か偽かであるとする。このとき、対象 $b$ であって、 $D$ に属し、しかも $x$ が $D$ のどの対象であっても $R(b, x)$ が成り立つのは $R(x, x)$ が成り立たないとき、かつそのときに限る、というものは存在しない。図では、各行が対象 $x$ 、各列が対象 $y$ であり、 $R(x, y)$ が成り立つときにそのマスが塗られている。 $b$ のために探している行は対角線を反転させなければならず、そのため各行と、その行の対角線上のマスで異なる。

証明

$\dato{b}{(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)}$
そのような $b$ が $D$ にあると仮定する。
$R(b, \resaltar{b}) \Leftrightarrow \neg R(\resaltar{b}, \resaltar{b})$
条件は $x$ が $D$ のどの要素であっても成り立ち、 $b$ はその一つである。よって $x = b$ ととれる。
$R(b, b) \Rightarrow \resaltar{\neg R(b, b)}$
$R(b, b)$ が成り立つならば、同値によりそれは成り立たない。矛盾である。
$\neg R(b, b) \Rightarrow \resaltar{R(b, b)}$
$R(b, b)$ が成り立たないならば、同値によりそれは成り立つ。これも矛盾である。
$\neg (\exists b \in D)\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
二つの場合のどちらかが起こらなければならないので、この想定は維持できない。そのような $b$ は存在しない。

系床屋は存在しない

どの村にも、自分でひげを剃らない村の男全員のひげを剃り、しかもその人たちだけのひげを剃る、その村の男はいない。

証明

$(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
$D$ を村の男たちの集まり、 $R(x, y)$ を関係「 $x$ は $y$ のひげを剃る」とする。床屋 $b$ は村の男なので $D$ に属する。彼が述べられたとおりの床屋であるとは、村の各男のひげを、ちょうどその男が自分でひげを剃らないときに剃るということである。
$\resaltar{\neg (\exists b \in D)}\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
対角化補題により、村のどの男もこの条件を満たさない。述べられた床屋は存在しない。この話はパラドックスではなく、その主人公がありえないことの証明である。

床屋についての結論は無害である。そのような床屋がいると主張した人はだれもいなかった。集合論におけるその変種では、事情が違う。1902年、ラッセルはゴットロープ・フレーゲに手紙を書き、算術を論理学に基礎づけようとしたフレーゲの体系が、次の内包原理を認めていることを指摘した。どんな性質に対しても、その性質をもつ対象をちょうど要素とする集合が存在する。自分自身に属さないという性質にこの原理を適用すると、次の集合が存在することになる。

Z = \{ x : x \notin x \}

系ラッセルのパラドックス

制限のない内包原理は矛盾している。

証明

$\dato{Z}{(\forall x \in D)\,\left( x \in Z \Leftrightarrow x \notin x \right)}$
$D$ をすべての集合の集まり、 $R(x, y)$ を関係「 $y$ は $x$ に属する」とする。内包原理を性質 $x \notin x$ に適用すると、集合 $Z$ が存在し、その要素は自分自身に属さない集合である。
$(\forall x \in D)\,\left( \resaltar{R(Z, x)} \Leftrightarrow \resaltar{\neg R(x, x)} \right)$
選んだ関係のもとでは、 $Z$ の条件はちょうど対角化補題の条件であり、 $Z$ が $b$ の位置にある。 $x \in Z$ は $R(Z, x)$ であり、 $x \notin x$ は $\neg R(x, x)$ である。
$\resaltar{Z \in Z \Leftrightarrow Z \notin Z}$
集合 $Z$ は集合なので $D$ に属する。対角化補題により、そのような $Z$ は存在せず、 $x = Z$ とおくと不可能な同値が得られる。ところが、原理はそれが存在すると主張する。したがって、原理は矛盾を含意する。

床屋とは違い、ここでの $Z$ の存在は物語の中の想定ではなく、理論の原理であった。ラッセルのパラドックスは、 $Z$ が存在しないと宣言することによってではなく、理論を作り直すことによって解決される。1908年のツェルメロの公理的集合論は、性質を用いて、すでに与えられた集合の部分集合を作ることしか許さず、この制限のもとでは矛盾は導かれない。

パラドックスでないもの

空集合は要素をもたないのに存在するという観察が、ときに「空集合のパラドックス」と呼ばれてきた。あたかも、存在する対象は存在する対象からできていなければならないかのように。ここには何の矛盾もない。集合は、壁がれんがでできているようにその要素でできているのではなく、要素によって定まるのであり、集合の要素の集まりは一つも要素を含まないこともありうる。空の箱がやはり箱であるのと同じである。ある事実が意外であっても、それでパラドックスになるわけではない。パラドックスには矛盾を導くことが必要であり、ここでは何の矛盾も導かれない。

形式言語はそれらをどう扱うか

以上から、形式言語がパラドックスを避けるのは魔法によるのではなく、二つの正確なやり方によることがわかる。一つめは、それらを生み出す手段を欠くことができるということである。このコースが構成する命題論理の言語には、自分自身を指す文も真理述語もない。そこでは嘘つきの文を書くことができず、その意味論は、変数への各付値において、各論理式にただ一つの真理値を割り当てる。二つめは、より豊かな言語では、パラドックスが定理に変わるということである。嘘つきの推論を厳密に行うと、十分な表現力をもつ言語の真理は、その同じ言語の中では定義できないことが証明される（タルスキ）。床屋とラッセルの推論は、ある集まりが集合でないことを証明する。そして、ベリーの論証に近い論証が、1931年のクルト・ゲーデルの不完全性定理の核心にある。こうして、自然言語では当惑であるものが、形式言語では情報となる。

数理論理学の四つの柱

数理論理学は、19世紀末から20世紀初めにかけて、フレーゲ、ペアノ、ラッセル、ダフィット・ヒルベルトとともに、正確な問いへの答えとして生まれた。数学はどんな基礎の上に立っているのか、そしてその基礎は矛盾を含まないのか、という問いである。今日、数理論理学は四つの大きな分野に分けられ、それらはたえず絡み合っている。

証明論：形式的な証明を数学的対象として、すなわち明示的な規則に従う論理式の有限列として研究する。体系の中で何が証明できるか、体系が無矛盾かどうか、証明が互いにどう変換されるかを問う。このコースの単元「演繹」は、その最初の手ほどきである。
モデル理論：形式言語と、それを解釈する構造、すなわちそのモデルとの関係を研究する。どんな構造が論理式の集合を充足するか、構造のどんな性質が与えられた言語で表現できるかを問う。単元「意味論」は、真理値の付値をもつ点で、その最も初等的な形である。
集合論：ツェルメロとフレンケルの公理のような正確な公理によって集合を研究する。その中で数学のほとんどすべてを書くことができる。集合論は、かなりの部分、ラッセルのパラドックスを避ける必要から生まれた。
計算可能性理論：どの問題が機械的な手続きで解け、どの問題が解けないかを研究する。コースで見るように、命題論理は決定可能である。論理式が恒真かどうかを有限回の手順で決める手続きが存在する。これに対し、述語論理は決定可能でない。

どの柱も、ほかの柱に触れずに深く研究することはできない。このコースの中心的な結果である完全性は、証明論の定理であると同時にモデル理論の定理でもあり、そこから得られる決定可能性は計算可能性理論に属する。

コースの地図

このコースは、論理学の最も単純な言語である命題論理の言語について、論理学の理論がたどる道筋の全体を、四つの単元で進む。

言語：構文論。二つの記号からなるアルファベットと形成規則をもつ対象言語を構成し、どの論理式もただ一通りに読めることを証明し、帰納法による証明を学び、自然言語の言明や論証を形式言語に翻訳して、翻訳が何を保ち何を失うかを指摘する。
演繹：公理と推論規則の体系を定め、論理式 $\varphi$ が論理式の集合 $\Gamma$ から導出されるとはどういうことかを定義する。これを $\Gamma \vdash \varphi$ と書く。これは妥当性の構文論的な側面であり、記号をその意味に注意を払わずに規則に従って操作することである。
意味論：各付値において各論理式に真理値を割り当て、 $\varphi$ が $\Gamma$ の帰結であるとはどういうことかを定義し、 $\Gamma \models \varphi$ と書く。すなわち、 $\Gamma$ の論理式を真にする付値はすべて $\varphi$ を真にするということである。これは妥当性の意味論的な側面であり、この課の定義を正確にしたものである。
メタ理論：二つの側面が一致することを証明する。健全性は導出可能なものはすべて帰結であると述べ、完全性はすべての帰結が導出可能であると述べる。続いて、コンパクト性と、論理式の集合が充足可能かどうかを決める機械的な方法である融合法とを研究する。

そうであれば、このコースは、推論そのものを対象とする数学的理論の最初の完全な例である。そして、この課で見たように、形式言語についてのコースの主張はすべて、数学の厳密さで証明されたメタ言語の文となる。

例題

以下の問題は、難しさの順に、この課の区別を練習する。すべての文が真である論証を論駁すること、多義的な言明の読みを分けること、対象言語とメタ言語の表現を分類すること、そしてパラドックスに見える二つの推論を分析して、それらが本当にパラドックスかどうかを決めることである。

例題 1すべて真なのに、妥当でない

次の論証は、前提も結論も真であるが、妥当でないことを示せ。「 $6$ の倍数はすべて偶数である。数 $12$ は偶数である。ゆえに、 $12$ は $6$ の倍数である」。

解答

$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(12), \quad S(12)$
「 $x$ は $6$ の倍数である」を $S(x)$ で、「 $x$ は偶数である」を $P(x)$ で略記する。前提と結論は真である。 $12 = 6 \cdot 2$ だからである。
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{c}), \quad S(\resaltar{c})$
形式は、名前 $12$ を文字 $c$ で置き換えると得られる。前提が二つ、結論が一つである。
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{4})$
前提が真になる代入例を探す。最初の前提は $c$ によらず、二つめの前提は偶数を求める。 $c = 4$ ととる。
$\neg S(\resaltar{4})$
この代入例の結論は偽である。 $4$ は $6$ の倍数ではないからである。
$\resaltar{12 = 6 \cdot 2}$
形式には反例がある。したがって形式は妥当でなく、論証も妥当でない。結論の真は前提からではなく、算術から来ている。

例題 2作用域の多義性

$L$ を数 $4$ 、 $6$ 、 $7$ のリストとする。文「 $L$ の数はすべて素数でない」に二つの読みがあり、このリストでは一方が真で他方が偽であることを示せ。

解答

$\dato{a}{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)}$
「 $x$ は素数である」を $Q(x)$ で略記する。第一の読み：否定が各数に作用し、文はどれも素数でないと言っている。
$\dato{n}{\neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)}$
第二の読み：否定が主張全体に作用し、文はすべてが素数であるわけではないと言っている。
$Q(7), \quad \neg\left( \neg Q(4) \wedge \neg Q(6) \wedge \resaltar{\neg Q(7)} \right)$
$7$ は素数なので、第一の読みの最後の項は偽であり、それとともに連言全体も偽である。第一の読みは偽である。
$\neg Q(4), \quad \neg\left( \resaltar{Q(4)} \wedge Q(6) \wedge Q(7) \right)$
$4$ は素数でないので、第二の読みの連言は偽であり、その否定は真である。第二の読みは真である。
$\resaltar{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)} \Rightarrow \neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)$
二つの読みは同値ではない。第一の読みは第二の読みを含意するが、逆は成り立たず、このリストがそれを示している。数学では、第二の読みは「 $L$ の数がすべて素数であるわけではない」と書き、第一の読みは「 $L$ のどの数も素数でない」と書く。

例題 3対象言語とメタ言語

対象言語として記号 $\sigO$ と $\sigI$ の列をとり、メタ言語として日本語をとって、任意の列をギリシア文字で表すことにする。次の各表現を分類し、意味のある場合には真かどうかを決めよ。(a) $\sigO\sigO\sigI$ 。(b)「 $\sigO\sigO\sigI$ は三つの記号からなる」。(c)「すべての列 $\varphi$ について、列 $\sigI\varphi$ は黒丸で始まる」。(d)「 $\sigO\sigO\sigI$ は真である」。

解答

$\resaltar{\sigO\sigO\sigI}$
表現 (a) は対象言語に属する。それは記号の列であって日本語の文ではなく、真でも偽でもない。それについて語ることはできるが、それ自身は何も主張しない。
$\sigO \; \sigO \; \sigI \quad (3)$
表現 (b) は、列 (a) に言及し、その記号を数えるメタ言語の文である。それは真である。
$\resaltar{\sigI}\varphi$
表現 (c) はメタ言語の文である。文字 $\varphi$ は対象言語の記号ではなく、対象言語の列を動くメタ言語の変数である。この文は真である。 $\sigI\varphi$ は構成上、黒丸で始まるからである。
$v_2 = \sigO\sigO\sigI$
表現 (d) はメタ言語に属するが、まだ真理値をもたない。列 $\sigO\sigO\sigI$ はコースの言語の変数となり、変数はそれ自身では真でも偽でもなく、単元「意味論」で付値が値を与えたときにはじめて真か偽かになる。次の課では、それは $v_2$ と呼ばれる。

例題 4エピメニデスは嘘つきではない

黒板に文 $e$ 「この黒板に書かれた文はすべて偽である」が書かれている（ほかの文もあるかもしれない）。二値原理と真理図式を認めて、 $e$ が偽であり、黒板にはほかに真な文があることを証明せよ。また、パラドックスになるのは黒板のほかの文がどれも真でないとき、かつそのときに限ることを導け。 $e$ が黒板の唯一の文である場合がそうである。

解答

$\dato{T}{V(e) \Leftrightarrow (\forall x \in O)\,F(x)}$
$O$ を黒板の文の集合とする。 $e$ はその一つである。真理図式により、 $e$ が真であるのは、 $O$ のすべての文が偽であるとき、かつそのときに限る。
$V(e) \Rightarrow \resaltar{F(e)} \Rightarrow \neg V(e)$
$e$ が真だとすると、 $O$ のすべての文は偽であり、 $e$ は $O$ に属するから、 $e$ は偽となり、二値原理により真でないことになる。この想定は自分自身を論駁する。
$\resaltar{F(e)}$
したがって、 $e$ は真でない。二値原理により、それは偽である。
$(\exists x \in O)\,\left( x \neq e \wedge V(x) \right)$
真理図式により、 $e$ が偽であることは、 $O$ の文がすべて偽であるわけではないことを意味する。ある文は真であり、それは偽である $e$ ではない。
$\neg (\exists x \in O)\,\left( x \neq e \wedge V(x) \right) \Rightarrow \resaltar{V(e) \wedge \neg V(e)}$
黒板に別の真な文があれば、すべては整合的である。 $e$ は単に偽である。これに対し、ほかの文がどれも真でなければ、 $x$ で $e$ と異なり $O$ に属し真であるものは存在せず、嘘つきの場合と同じく矛盾が得られる。とくに、 $e$ が黒板の唯一の文であるときがそうである。したがって、パラドックスが現れるかどうかは経験的な事実、すなわち黒板に何が書かれているかに依存する。

例題 5非自己記述的

形容詞は、自分自身にあてはまるとき自己記述的（「短い」は短い語である。「日本語の」は日本語の語である）、あてはまらないとき非自己記述的（「長い」は長い語ではない。「英語の」は英語の語ではない）という。「非自己記述的」が形容詞であり、関係「あてはまる」がすべての形容詞について確定しているならば、矛盾に至ることを証明せよ。また、どの仮定を捨てるべきかを決めよ。

解答

$\dato{R}{R(x, x)}$
$D$ を日本語の形容詞の集まり、 $R(x, y)$ を関係「形容詞 $x$ は語 $y$ にあてはまる」とする。形容詞 $x$ は、 $R(x, x)$ のとき自己記述的、 $\neg R(x, x)$ のとき非自己記述的である。
$\dato{h}{(\forall x \in D)\,\left( R(h, x) \Leftrightarrow \neg R(x, x) \right)}$
$h$ を形容詞「非自己記述的」とする。その定義により、それがある形容詞にあてはまるのは、ちょうどその形容詞が自分自身にあてはまらないときである。
$R(\resaltar{h}, \resaltar{h}) \Leftrightarrow \neg R(\resaltar{h}, \resaltar{h})$
$h$ が形容詞ならば、それは $D$ に属し、その条件は対角化補題の条件である。 $x = h$ とおくと、不可能な同値が得られる。
$h \in D \Rightarrow \resaltar{h \notin D}$
対角化補題により、 $D$ のどの対象も $h$ の条件を満たさない。 $h$ が $D$ に属するなら、矛盾が生じる。
$\resaltar{h \notin D}$
破れるのは二つめの仮定である。「非自己記述的」のように、それ自身がこの同じ関係によって定義される形容詞については、「あてはまる」は正確な関係ではない。形式言語では、関係 $R$ はメタ言語で定義され、形容詞 $h$ は対象言語に属さないので、条件 $h \in D$ は偽となり、矛盾は生じない。

練習問題

最初の二問は妥当性と多義性を、三問めは使用と言及を練習する。最後の二問では、新しいパラドックスを分析し、言語学の外で対角化補題を適用する。各問にはヒントがあり、自分で試みたあとで開くのがよい。

演習問題 1よく似た二つの形式

次の二つの形式を考えよ。(a)「 $p$ ならば $q$ 。 $q$ でない。ゆえに、 $p$ でない」。(b)「 $p$ ならば $q$ 。 $p$ でない。ゆえに、 $q$ でない」。どちらが妥当でどちらが妥当でないかを決めよ。妥当でないほうについては、数についての言明で反例を構成し、妥当なほうについては、どの代入例も反例になりえない理由を説明せよ。

ヒント

形式 (b) については、「 $n$ が $4$ の倍数ならば偶数である」のような、数の性質の間の真な含意と、第一の性質はもたないが第二の性質はもつ数とを探せ。形式 (a) については、前提が真であると仮定し、 $p$ が真だとしたら何が起こるかを考えよ。

答え

形式 (a) は後件否定式（モドゥス・トレンス）と呼ばれ、妥当である。前提が真で $p$ が真だとすると、 $q$ も真となり、二つめの前提に反する。形式 (b) は前件否定であり、妥当でない。「 $6$ が $4$ の倍数ならば、 $6$ は偶数である。 $6$ は $4$ の倍数ではない。ゆえに、 $6$ は偶数ではない」は、前提が真で結論が偽である。

演習問題 2パスポート、身分証明書、ビザ

ある掲示に「入国にはパスポートか身分証明書とビザが必要である」とある。その二つの読みを文字 $p$ （パスポート）、 $d$ （身分証明書）、 $v$ （ビザ）で書き、一方の読みでは入国でき、他方の読みでは入国できない旅行者を述べよ。

ヒント

問題は、ビザが身分証明書だけに伴うのか、二つの書類のどちらにも伴うのかである。書類を一つしかもたない旅行者で試してみよ。

答え

読みは $p \vee (d \wedge v)$ と $(p \vee d) \wedge v$ である。パスポートをもちビザをもたない旅行者は、第一の読みでは入国できるが、第二の読みでは入国できない。

演習問題 3括弧

各文が都市について語っているのか語について語っているのか、また真か偽かを決めよ。(a)「ローマは三文字である」。(b)「『ローマ』は三文字である」。(c)「『ローマ』はイタリアの首都である」。(d)「文『ローマはイタリアの首都である』は語『ローマ』を含む」。

ヒント

括弧は、表現をその表現の名前に変える。各場合について、文の主語がどんな対象を指しているか、すなわち都市か、語か、文かを考えよ。

答え

(a) 都市について語っており、偽である。都市には文字がないからである。(b) 語について語っており、真である。(c) 語について語っており、偽である。語は首都ではないからである。(d) 文と語について語っており、真である。

演習問題 4一枚のカードの両面

カードの一方の面には文 $A$ 「文 $B$ は真である」が、もう一方の面には文 $B$ 「文 $A$ は偽である」が書かれている。二値原理と真理図式を認めて、 $A$ と $B$ に真理値を割り当てる方法はないことを証明せよ。 $B$ が代わりに「文 $A$ は真である」と言うとしたら、どうなるか。

ヒント

各文について真理図式を書き、 $V(A)$ をそれ自身に結びつける同値が得られるまで同値をつなげよ。変形についても同じことをし、どんな値の割り当てがそれを満たすかを確かめよ。

答え

最初の形では、どの文も自分自身について語っていないのに、嘘つきと同じく $V(A) \Leftrightarrow \neg V(A)$ が得られる。変形では、 $V(A) \Leftrightarrow V(B)$ は、両方とも真か両方とも偽かという二つの割り当てを許す。矛盾はないが、そのどちらかを決めるものは何もない。

詳しい解答

解答

$\dato{A}{V(A) \Leftrightarrow V(B)}$
真理図式により、 $A$ が真であるのは、ちょうど $B$ が真であるときである。
$\dato{B}{V(B) \Leftrightarrow F(A) \Leftrightarrow \neg V(A)}$
真理図式により、 $B$ が真であるのは、ちょうど $A$ が偽であるときである。二値原理により、偽であることは真でないことである。
$V(A) \Leftrightarrow \resaltar{\neg V(A)}$
二つの同値をつなぐと、 $A$ の真はそれ自身の否定と同値になり、嘘つきの場合と同じように推論できる。 $A$ が真ならば真でなく、真でないならば真である。
$V(A) \Leftrightarrow V(B) \Leftrightarrow V(A)$
変形では、 $B$ についての真理図式は $V(B) \Leftrightarrow V(A)$ を与え、これは最初の同値と合わせても、二つの文が同じ値をもつことしか要求しない。整合的な割り当てが二つあり、矛盾はない。

演習問題 5カントールの対角線

$s_1, s_2, s_3, \ldots$ を、零と一からなる無限列の任意のリストとし、 $s_x(y)$ と書いて、第 $y$ 項、それも数列 $s_x$ の項を表すことにする。対角化補題を用いて、数列 $d$ 、すなわち $d(y) = 1$ （ $s_y(y) = 0$ のとき）および $d(y) = 0$ （ $s_y(y) = 1$ のとき）で定まる数列が、リストに現れないことを証明せよ。また、番号のついたどのリストも、零と一からなるすべての列を含むことはないことを導け。

ヒント

集まり $D$ として自然数を、関係 $R(x, y)$ として主張 $s_x(y) = 1$ をとれ。数 $b$ で $s_b = d$ となるものは、どんな条件を満たすか。

答え

$d = s_b$ であるとすると、数 $b$ は $R(b, y) \Leftrightarrow \neg R(y, y)$ をすべての $y$ について満たすことになり、これは対角化補題が禁じている。したがって、 $d$ は各 $s_b$ と少なくとも第 $b$ 項で異なり、どのリストもすべての列を含むことはない。

詳しい解答

解答

$\dato{R}{R(x, y) \Leftrightarrow s_x(y) = 1}$
$D$ を自然数の集合、 $R(x, y)$ を、第 $y$ 項（ $s_x$ の項）が $1$ に等しいという主張とする。
$\dato{d}{d(y) = 1 \Leftrightarrow \neg\left( s_y(y) = 1 \right)}$
定義により、 $d(y)$ が $1$ に等しいのは、ちょうど $s_y(y)$ が $1$ に等しくないときである。
$(\forall y \in D)\,\left( R(\resaltar{b}, y) \Leftrightarrow \neg R(y, y) \right)$
$d$ がリストの位置 $b$ に現れる、すなわち $d = s_b$ であると仮定する。このとき、すべての $y$ について、 $R(b, y)$ は $d(y) = 1$ と同値であり、それは $\neg R(y, y)$ と同値である。
$d(b) \neq s_b(b)$
対角化補題により、どの $b$ もこの条件を満たさない。数列 $d$ はリストに現れない。具体的には、 $s_b$ とは第 $b$ 項で異なる。
$(\forall b \in \mathbb{N})\,(d \neq s_b)$
リストは任意であったから、番号のついたどのリストも、零と一からなるすべての列を含むことはない。どのリストにも、少なくともそれ自身の対角線の列が欠けている。