第１００話

　数理論理の話　〜第 １００話記念特大号〜

　

「本稿の目的」

今回は、第１００話記念号として、入門までを体系的に書いてみようという試みです。前回に引き続き、予想を立てて、それを確認するという方向で展開します。ただし、将来への布石として、外れの予想も行いました。また、最後の方では、自然数の上で、不等号を完全には特徴付けられないということにも触れました。何でもかんでもやればできるというものでもなく、手に負えないもののあることを認識しましょう。

　

　

本　文　目　次

　１．はじめに

　２．命題論理

　３．演繹定理

　４．述語論理

　５．充足定理

　６．コンパクト性定理

　７．おわりに

　

著者　坂田　明治

　

　

　

第１００話　数理論理の話　〜第 １００話記念特大号〜

　

１．はじめに

　理科好き子供の広場も、ついに１００話を達成しました。

　

　ということで、第１００話記念特大号になります。今回は数理論理の話ですが、いつものように、あまり予備知識を必要としません。普通に、数理論理の入門となる内容なので、「激ムズでいーから。」という意見（第９９話）に副（そ）えないかもね。でも、気にしないもんね。

　

　また、途中で飽きたため、かなりいい加減なところもあります。毎度のことですが、頭から正しいと信じたりせず、自分でよく考えて判断しましょう。

　

　最初に注意を一つ。程度の悪い教師にありがちな問題行動を述べておきます。

　

　

　式（２）を式（１）へ代入しましょう。

　

　

　式（３）のような回答を書く生徒がいます。すると、程度の悪い教師は、正解を式（４）として、式（３）を間違いだと。

　

　

　何も説明しないか、せいぜい説明しても、（ ）の中を先に計算するとか何とか。この説明で間違っている訳ではないけれども、式（３）のように書いてしまった理由が考えられていません。正解が書けさえすればいいのか。

　

　今度は、式（２）の代入先として式（５）を考えてみましょう。

　

　

　代入すると、式（６）のようになり、y をただ置き換えただけで何の問題もありませんね。

　

　

　更に、式（７）を代入元として、式（１）、式（５）へ代入してみましょう。

　

　

　この場合、式（８）、式（９）は、y をただ置き換えただけで何の問題もありません。いや、ここまで来ると、むしろ、式（４）の（ ）はどこから出てきたのかが問題となります。つまり、そのまま文字を書き換えてうまく行く場合と、それではうまく行かず、どこから出てきたのかが解らない（ ）を付けなくてはならない場合があり、この違いは何かということです。

　

　代入するというのは、代入前に、代入元の式が計算されており、その結果を代入するということです。そして、式（６）、式（８）、式（９）が正しいのは、それぞれ、順に、加法結合法則、乗法結合法則、乗算は加算に優先という計算順序の約束事があるからです。そう考えると、代入時に（ ）が付いており、それが、何らかの法則や約束事によって省略されていると解釈できますね。

　

　こう考えてくると、最初から式に、計算の順序が付いていれば問題ないはずです。元々　

（ ）は計算の優先順位を付けるものでした。これは、（ ）の中が外より先という優先順位です。であれば式にキチンと（ ）を付けて優先順位を表すなら置き換えただけでうまく行くはずです。

　

　式（１）と式（２）を（ ）付きで書き直すと、

　

　

　となります。式（１１）を式（１０）へ代入するに際して、ただ単に文字を書き直すだけで、

　

　

　が出てきます。ついでに、式（５）も書き直して、

　

　

　式（１３）に式（１１）を代入して、

　

　

　となり、 ただ単に文字を書き直すだけで正しい式が出てきます。

　

　これで、形式的に文字を書き直すだけで正しい式を出すことができました。つまり、式を形式的な文字の書き直しだけで正しく代入が行われた形にすることはできます。

　

　しかしながら、（ ）がやたら出てくると見難くてうっとーしくなります。その上、項が増えると、色々な（ ）のつけ方が出てきて式まで増え（カッコが干渉するため、多数の式を用意しなければならない）、益々、見難くて、面倒でうっとーしくなります。これが、誤解が生じない限り（一通りに解釈でき、しかも見やすくなるように）、カッコを省略するとの意味です。

　

　「カッコ付けるとカッコ悪くなる。」という教訓ですね。

　

　

２．命題論理

　この章では命題論理を公理的に取り扱います。等号は出てきません。その代わりが同値記号です。毎度のことだけど、記号や文字が文字化けしたりして、書きにくいったらありゃしない。そこで、式を書くときは記号を使って画像で作り、文章中では文字で書くことにします。

　

　まずは、論理記号を導入しましょう。

　

　

　一応、日本語と英語の読み方と、作用する順序を書いておきました。順序を決めておくと、（ ）の省略ができて式が見やすくなります。なお、「でない」を「否定」と呼ぶことも多々あります（どっちを使うかは書いてるときの気分による）。

　

　

ところで、公理系Lで一般に、式（５７）が成り立つ（当然読者の宿題）。

　

　

これを使って、式（５６）を書き直すと、

　

　

となる。ここで、式（２３）を使うと、

　

　

式（５８）と式（５９）から、

　

　

が成り立つ。一方、公理系Lで一般に、式（６１）が成り立つ（当然読者の宿題）。

　

　

これから、

　

　

となって、三段論法のときも公理系Lで証明可能になります。

　

こうして、n + 1 でも成り立つことが解り、公理系Lで、PならばQが証明できました。

　

　以上から、式（４９）が成り立ちます。こうして、我々はお釈迦様の掌から外へ出られました。よっかたね。

　

　なお、式（４９）（命題変数に対する置換制限を付ける）のことを演繹定理と呼びます。

　

　

４．述語論理

　いよいよ述語論理です。命題論理よりも、かなりごちゃごちゃしてやっかいです。

　

　ネットで「述語」を検索すれば、文章を主語と述語に分けてどうとかこうとか、というのが沢山引っかかってきます。とにかく、命題を主語と述語に分けて扱うのだけれども、通常の国語の文章よりもやっかいなことが付きまといます。

　

　大体、ネットの解説サイトでは、例えば「俺は食い意地が張ってる。」というような例で出てきて、「俺」が主語で、「食い意地が張ってる」が述語というような説明です。誰が、とか何がというようなところが「主語」で、状態とか動作とかを表しているのが「述語」と説明されています。日本語では、主語を省略していることが多いため（対偶漫談でも出てきましたね）、既に、面倒を背負い込んで解りにくくなっています。述語がどこにかかるのかを考えなくてはなりませんからね。

　

　ところで、述語論理では、多変数を扱うため、その逆の意味でやっかいなことになってきます。各変数が主語と考えると、主語が多数あって、述語がそれら全部にかかるというような解釈が必要になってきますから。例えば、「アヒルとアイガモは食い意地が張ってる。」という文章を考えてみましょう。主語は、「アヒル」と「アイガモ」ですね。この両方に「食い意地が張ってる」という述語がかかります。とにかくやっかいですね。

　

　さて、命題論理では、論理式の形式的な意味を考えるとしても、内容までは考えずに真偽を考えていました。こんなこともあって、真偽表がお釈迦様の掌になっていました。これにならい、論理式の内容的な意味は考えず、その真偽を扱うことの方が妥当でしょう。

　

　つまり、n 個の主語がある述語Pを以下のように考えます。

　

　n 個体変数の述語Pを、x₁ ,x₂ ,・・・,x_n に対して、その真偽値を対応させるものとする。ただし、各個体変数は、それぞれの個体変数の変域内にあるとする。

　

　要するに、P( x₁ ,x₂ ,・・・,x_n ) は真と偽の2値しか取らない関数（写像）のことです。

　

　そうすると、それはそれで色々とやっかいなことが出てきます。命題論理では、真偽が決まっており、真偽表を簡単に書けましたが、述語論理では、そううまくは行きません。

　

　例えば、1 、2 、3 、の三つを変域として、「x は偶数だ」というのを考えましょう。このとき、x は三つの値しか取らないので、これを全部書き下して真偽を付けます。「 1 は偶数だ」（偽）、「 2 は偶数だ」（真）、「 3 は偶数だ」（偽）となりますね。つまり、取り得る値によって真偽が変わってきます。これはまだ３個しかないので書き下せましたが、変域が無限集合になると書き下せません。こうして、一般的に、真偽表は書けないということになります。

　

　更に、個体変数によって文章が決まっており、その個体変数を変域上で動かしたときにできる文章を束ねていることが解ります。先の例で、「x は偶数だ」は、「１は偶数だ」、「２は偶数だ」、「３は偶数だ」の三つを束ねていましたね。これから、述語論理では、論理式を束ねたもの、いい換えると、論理式の型を扱うものと推測されますね。そのつもりでかからないと痛い目にあいそうです。（命題論理では実体を扱っていた）

　

　次に、述語論理で新たに導入される論理記号について考察しましょう。新たに導入されるのは、以下の二つです。

　

　

　これらは、今までのどの論理記号とも扱いが異なり、優先度がなく、（ ）がない限り、並んでいるものは左から順に個体変数と結びつきます。また、個体変数を束縛するためのものなので、そのつもりで扱わないといけません。

　

　

　式（６３）は、「全ての x についてP (x) 」と読みます。x の変域Dを明示したい場合は、「Dの全ての x についてP (x) 」とか、「Dの任意の x についてP (x) 」などと読みます。

　

　式（６４）は、「ある x についてP (x) 」とか、「P (x) となる x が存在する 」とか、「適当な x についてP (x) 」と読みます。x の変域Dを明示したい場合は、「Dのある x についてP (x) 」などと読みます。

　

　また、式（６３）や式（６４）の中で x は束縛されているとか、x は束縛個体変数などといいます。それに対し、「全て」や「存在する」という記号に束縛されていない個体変数は自由であるとか、自由個体変数などといいます。

　

　ここで、述語の例を書くために、色々な分野から記号や概念をかっぱらってきます（述語は関数なので、関数を書くには、色々な記号や概念を使った方が解りやすい）。こういうとき、みんな借りてきてとかいいますが、返すのを見たことはありません。

　

　そう、あれは忘れもしないウン十年前のことだった（完全に忘れている）。小学校の引き算で、繰り下がりの話のときだ。例えば、25 − ７ を計算しようとすると、一の位の 5 から 7 は引けないため、最初に、一の位が十の位から 1 を借りる。十の位は 2 から 1 が引かれるので 1 。一方、一の位は十の位から 1 を借りるが、位が一つ上のところから借りたので、実は 10 を借りたことになる。次に、一の位は、借りた 10 から 7 を引いて残り 3 を求め、その 3 をどうするかというと、一の位に繰り込んでしまう。これは、5 に 3 を足して 8 とすることだ。こうして、十の位が 1 で、一の位は 8 だから、そのまま読んで、引き算の結果は 18 。これを計算結果としていた。しかし、一の位は決して借りた 10 を返すことがなかった。

　

　まあ、手元資金が５千万円しかないときに、７千万円の催促がきたら、どっかから１億円借りて支払い、余りの３千万円を手元資金に繰り入れて、手元資金を８千万円にし、借金を踏み倒すのと全く一緒です。まるでどっかの国の悪徳企業がよくやっているような話です。

　

　「借りる」というウソはやめて、正しく「かっぱらってきた」ということにしましょうね。（カツアゲで「借りる」といったら返さないことだから、そういう意味では正しいともいえるが）

　

　元へ戻って、述語は関数だと書きましたが、関数のままだと、やっぱり書きにくいし解りにくいので、関数化のちょっと前で表現することにします。

　

　何をいっているのかというと、 0 を真で、1 を偽として、x = a を表現する述語は、式（６５）を使って、式（６６）と書けます。

　

　

　それよりも、x = a を述語とみなした方が解りやすいでしょう。

　

　さて、変域を 1 、2 、3 の三つからなるものとして、述語P (x) を考えます。少し前でやったように、P (x) はP (1) 、P (2) 、P (3) の三つの命題を束ねたものになります。そして、「全ての x についてP (x) が成り立つ（つまり真）」ということを考えましょう。これは明らかに、P (1) が成り立つ（真）、P (2) が成り立つ（真） 、P (3) が成り立つ（真）ですね。したがって、「P (1) かつP (2) かつP (3) 」が成り立ち（真）ます。よって、変域が有限集合であれば、「全て」は「かつ」で表現でき、命題論理から外へ出ていません（またしてもお釈迦様の掌に捕らわれてしまいました）。でも大丈夫だもんね。変域が無限集合のときは、有限個の記号で書き下せなくなって、「かつ」になんか帰着させられないもんね。これを本当の面白さは無限にあるといいます。

　

　同様に、変域を 1 、2 、3 の三つからなるものとして、述語P (x) を考えます。「P (x) が成り立つ x が存在する」ということは、P (1) が成り立つ（真）か、P (2) が成り立つ（真）か 、P (3) が成り立つ（真）かの少なくとも一つが成り立つことですね。したがって、「P (1) またはP (2) またはP (3) 」が成り立ち（真）ます。これも、変域が有限集合であれば、「存在する」は「または」で表現でき、命題論理から外へ出ていません。それでも、変域が無限集合のときは、有限個の記号で書き下せないので大丈夫です。

　

　なお、新しい概念や観点などが出てきたときは、常に、今までの知識と比べ、どこが外へ出ているのかを考えましょうね。（要するに、お釈迦様の掌から外へ出ているかどうかということ）

　

　ここで、ちょっとだけ論理記号の使い方を練習してみましょう。x と y の変域を実数として、原点を中心とする単位円は式（６７）と書けます。

　

　

　論理記号は使いこなせると便利なので、色々と自分で書いて練習してみましょう。

　

　次に、論理式を考えましょう。命題論理で論理式を定義したときのことから、論理式は、述語変数と個体変数に論理記号を適用していけばよいと予想されます。この予想に従って帰納的に定義すると次のようになりますね。

　

　

　しかし、この定義によって論理式を書いていくと、例えば、式（６８）や式（６９）のようなものが出てきてしまいます。

　

　

　式（６８）は無意味ですね。式（６９）は個体変数 x が、束縛個体変数になっているところと、自由個体変数になっているところのちゃんぽんになっています。ということは、この論理式の定義はあまりよくないことになりますね。またしても予想は外れましたが気にする必要はありません。外れたら、その修正を考えればいいのです。そこで、もう少し注意書きを付けて複雑にし、式（６８）や式（６９）のようなものが発生しないようにした論理式の定義を考えることを読者の宿題としましょう。

　

　なお、ここでは、どっかの国でよくやっているように、都合の悪いものは無視し、問題が生じたら「想定外」といってごまかすことにします。

　

　ところで、命題論理のときは、公理化とは関係なく、真偽表があり、そこからトートロジーが定義でき、これが後々重要になってきました。そうすると、述語論理でも、同じような状況が考えられると予想されますね。それなら、これらと同じ概念を用意しておく方が良さそうです。しかし、前に書いたように、変域が無限集合のときは、真偽表が書けないで、真偽表抜きでトートロジーみたいな概念を扱わねばなりません。

　

　まず、述語論理と、命題論理と比べてみましょう。こういう比較は重要です。

　

　命題論理では、命題変数だけでしたが、述語論理では述語変数と個体変数が出てきます。命題変数では、論理式の真偽は、命題変数の真偽から真偽表によって決まりました。そして、真偽表は、全ての命題変数に真偽値を入れて作ったものです。

　

　この真偽の決定方法を述語論理に適用しましょう。変域Dと、論理式Aが与えられたとします。命題論理では、全ての命題変数と、全ての真偽値を使っていました。これは、全ての述語と、変域内の全ての個体と読みかえられます。少しかっこ良くいうと、任意の述語と、変域内の任意の個体です。これに気をつければ、命題論理のトートロジー相当の概念として、「論理式Aが変域Dで恒真」というのを、「述語変数に、変域D上の任意の述語を割り当て、自由個体変数に変域D内の任意の個体を割り当てたときに、つねに真になる」ことと定義できます。

　

　「任意の」とか、「全て」とくれば、今度は、それを「存在する」とか「ある」とか「適当に」と置き換えたものも考えられますね。そこで、「論理式Aが変域Dで充足可能」というのを、「述語変数に、変域D上の適当な述語を割り当て、自由個体変数に変域D内の適当な個体を割り当てたときに、真にできる」ことと定義します。

　

　更に、どんな変域の上でも恒真であるような論理式は「恒真」、なんらかの変域の上で充足可能となるなる論理式は「充足可能」といいます。

　

　少し、恒真な論理式を考えましょう。恒真な論理式は、変域によらないということで、後で出てくる公理と推論だけから出てくるものになります。例えば、式（７０）です。

　

　

　式（７０）で、P (x) をQ (x , y) で置き換えてみましょう。このとき、P (y) はQ (y , y) で置き換えられます。そして、

　

　

となります。

　

　ところで、変域を 0 、1 として、その上でQ (x , y) を解釈した述語を同じQ (x , y) で表し、

　

　

とすれば、式（７１）は恒真でないことが解ります。つまり代入によって恒真は崩れます（恒真の定義を読み返すこと）。第１章では、代入を行うに際し、文字の書き換えだけで済まそうとしたら色々と問題が発生するので、（ ）によって何とか回避しました。しかし、今度はその手が通用しません。

　

　原因を考えましょう。式（７０）と式（７１）、Q (x , y) をよく眺めると、束縛個体変数と自由個体変数がごっちゃになって使われていることが解ります。この点をよく考えると、束縛個体変数と、自由個体変数をごっちゃににするような代入をしてはいけないということに気づきます。

　

　束縛個体変数と、自由個体変数をきちんと分離しましょう。ここで、論理式Aの述語変数P( x₁ ,x₂ ,・・・,x_n ) に論理式Bを代入するものとします。

　

　まず、論理式Bが x₁ ,x₂ ,・・・,x_n に対応する n 個の自由個体変数を含んでいなくてはなりません。そこで、その個体変数を x₁ ,x₂ ,・・・,x_n と書き換えます。すると、論理式BはB( x₁ ,x₂ ,・・・,x_n ) と書けます。ただし、Bはその他にも自由個体変数を含んでいるかも知れません。ここがミソになります。この上で、以下の条件（１）、（２）が満たされるならば、代入が許されます。

　

（１）　Bに含まれる x₁ ,x₂ ,・・・,x_n の他の自由個体変数は、Aの中で束縛個体変数ではない。

　

（２）　PがAの中で、P( y₁ ,y₂ ,・・・,y_n ) という形で表れるならば、全ての y₁ ,y₂ ,・・・,y_n はBの中で束縛変数として表れない。

　

　ここまで準備して、いよいよ公理化です。基本的に、命題論理の公理に、束縛変数に関する公理を追加すればよいはずですね。しかし、述語論理では、論理式を束ねたもの、あるいは、論理式の型を扱うものなので、公理を束ねたもの、すなわち、公理型となります。また、慣例によって、論理式を表す変数を、超変数と呼びます（論理式変数でもいいと思うが）。

　

　

推論規則は、置換と三段論法に束縛記号の導入規則を付け加えたものです。ただし、置換について、代入はこの直前で書いた代入規則を満たす必要があり、また、変数の書き換えを行う場合も含みます。

　

　

（３）、（４）で論理式の間にある線は、上の式が成り立てば、下の式が成り立つという意味です。解りやすくするためのもので、実際には書く必要もありません。

　

　また、証明については以下です。

　

　

　以上のように定式化した体系をLと書くことにします。ちょっと複雑で、やっかいなところはあるけれども、大体命題論理と同じようなことが成り立ちます。

　

　例えば、公理型は恒真であるとか、推論規則によって恒真が保存されることが成り立ちます。簡単なので、読者の宿題です。また、これから、証明可能な論理式は恒真であることが解ります。

　

　ところで、命題論理のときは、トートロジーと証明可能とは同じになっていたこと（真偽表に関して完全）から、恒真であれば証明可能であると予想されますが、今度は、そうそう簡単には確かめられそうもありません。こんなときは、しばらくプラプラしてみるのも手です。（これ、どっかの国でよくやる「先送り」というやつだ）

　

　あと、命題論理では演繹定理が成り立ったので、述語論理でも成り立つと予想されます。実際、成り立ちますが、多少複雑で面倒です。しかし、よい練習なので読者の宿題です（次の章を少し読んでからの方がいいかも）。

　

　

５．充足定理

　今度は、述語論理で論理式の集合を考えましょう。この集合内の各々の論理式が、ある変域で共通の解釈のもとに真であるとき「充足可能」といいます。つまり、各々の論理式は、述語変数に、変域上の適当に共通な述語を割り当て、自由個体変数に変域内の適当に共通な個体を割り当てたときに、真にできるということです。また、このときに、もとの論理式の集合を、充足可能な論理式の集合ともいいます。

　

　では、充足可能な論理式の集合Mを考えましょう。Mの要素は、ある変域Dで、述語変数に、変域上の適当に共通な述語を割り当て、自由個体変数に変域内の適当に共通な個体を割り当てると真になっています。このときに、Mは無矛盾かどうかを考えましょう。

　

　その前に、論理式の集合Mが無矛盾というのは、公理にMの要素を全部追加したものが無矛盾ということです。忘れた人は第３章を読み返しましょう（第３章では１個追加しただけだった）。

　

　充足可能な論理式の集合Mといっているので、当然ですが、Mは証明可能な論理式の集合とは限りませんね。それで、うっかり追加すると矛盾になってしまいます。第３章では、それを避けるために、置換禁止の処置を行いました。

　

　そのことを念頭に置くと、置換禁止が必要ですね。では、何を置換禁止にすればよいのでしょうか。第３章では、命題変数を一切置換禁止としました。とすれば、まずは、述語変数を一切置換禁止にすることが思いつきます。

　

　しかし、述語論理では、その他に個体変数が出てきます。そうすると、これも一切置換禁止にした方がよさそうです。それで充足可能の定義をよく見てみると、自由個体変数に変域上の適当な個体を割り当てていました。したがって、自由個体変数を一切置換禁止にすればよさそうですが、注意が必要です。述語論理で、自由個体変数を束縛するような推論が導入されていたので、これも禁止にします。つまり、自由個体変数については、一切の置換を禁止し、更に束縛する推論も禁止にします。

　

　これらの処置を、簡単に、述語変数と自由個体変数を「定数とみなす」といいます。

　

　元へ戻って、ここで考えているのは、充足可能な論理式の集合Mに対して、Mの要素に表れる述語変数と自由個体変数を全て定数とみなしたとき、無矛盾になるかという問題ですね。早速、試してみましょう。

　

　述語論理の公理に、Mの全ての要素を付け加えて、論理式Aが証明できたとします。もちろん、これは、Mの要素は公理みたいに扱うけれども、定数とみなした変数の置換は禁止して、推論規則を使うことです。

　

　それで、Aの証明に表れる述語変数と自由個体変数で、Mの要素に含まれるもの全てを、変域Dで、真となるように、共通に割り当てた述語と個体を代入します。このとき、定数とみなしたのに、代入していると考えて混乱する人がいます。推論規則を使う際に定数とみなして置換禁止にしたのであって、解釈禁止としてはいません。この点を、よく読み返して考えましょうね。

　

　とにかく、共通の解釈によって、証明の途中に出てくる論理式は全て真になります（公理はもちろん真だったもんね）。そうすると、Aも真となり、Aは充足可能ですね。ところで、矛盾は偽であり、充足可能になりませんから（充足可能から充足可能しか出てこないから）、充足可能な論理式の集合Mは無矛盾です。

　

　充足可能な論理式の集合は無矛盾となるのが解りました。当然、この逆を考えてみたくなりますね。つまり、無矛盾な論理式の集合は充足可能になるかどうかということです。これは、適当な変域を持ってきて、その上で、述語変数に、変域上の適当に共通な述語を割り当て、自由個体変数に変域内の適当に共通な個体を割り当てたときに、真にできるかということです。

　

　実は、自然数の集合の上で充足できるということが知られています。詳しく書くと、以下の様になります。

　

　「論理式の集合Mに対し、その要素にあらわれる述語変数と自由個体変数を定数とみなしたときに無矛盾であるとすれば、自然数全体の集合の上で充足可能である。」

　

　これは充足定理と呼ばれ、述語論理の入門となるものです。

　

　このままの形で扱うと少々面倒なので、ちょっと制限を付けて、以下の場合で考えましょう。

　

　「閉じた論理式の集合Mに対し、その要素にあらわれる述語変数を定数とみなしたときに無矛盾であるとすれば、自然数全体の集合の上で充足可能である。」

　

　閉じた論理式というのは、自由個体変数を含まない論理式のことです。要するに、もう飽きてきて面倒になってきたので、自由個体変数の部分をサボって手抜きをするということです。まあ、ちゃんと自由個体変数込みの証明が載っている書籍は沢山あるので（手に入るかどうかは知らんもんね）、自分で探してみるとよいでしょう。以下を参考に、自力で証明するなら、なおよいと思います。ちなみに、ヘンキンの「飽和法」というものを使って証明します。やり方が決まっているので、誰がやっても同じような感じになります（以下もこの方法による）。

　

　それでは、閉じた論理式の集合Mに対し、その要素にあらわれる述語変数を定数とみなしたときに無矛盾ということを仮定して考察を進めましょう。

　

　まず、述語論理の体系をLを、次のように修正してL₀⁺ とします。

　

（１）　述語変数をMの論理式に表れるものだけに制限し、全て定数とみなす。

（２）　Lの公理の自由個体変数を全て、「全て」という束縛記号によって束縛する。

（３）　Mの論理式を公理として追加する。

（４）　述語変数P( x₁ ,x₂ ,・・・,x_n ) の x₁ ,x₂ ,・・・,x_n のところへ、自然数の代入を許す。

（５）　推論規則として、以下の二つを付け加える。

　

　

　さて、L₀⁺ は無矛盾でしょうか。

　

　とりあえず、L₀⁺ で矛盾が証明できたとします。つまり、式（７３）が導けたとします。

　

　

　それでは、これから何をするかを考えましょう。L₀⁺ で式（７３）が証明できたということは、Lで考えると、Mから式（７４）が導けるということですね。

　

　

　そうすると、L₀⁺ 用に修正した部分、つまり、（１）から（５）までが、Lで正当化できればよいことになります。（１）、（３）、（４）は問題ないので、（２）、（５）が正当化できればよいでしょう。これを調べましょう。

　

　まずは、追加した推論規則（５）です。

　

　式（７３）で、証明は、有限個の論理式だから、自然数も有限個しか出てきません。これらを証明のどこにも出てこない変数で置き換えます。それを、y₁ ,y₂ ,・・・,y_k （代表で書くときは y ）としましょう。もちろん、異なる自然数は異なる変数で置き換えます。そうすると、式（７５）の様になります。

　

　

　これは、Lの公理（５）と公理（６）のそれぞれに三段論法を適用すれば出てくるので、式（７５）はLで正しい推論になります。

　

　次に、（２）です。つまり、Lの公理の自由個体変数を全て、「全て」という束縛記号によって束縛したものがLで証明可能かどうかです。これは、推論規則（４）で、AとBのところに公理を代入すれば、推論規則（４）の下の式が導け、Aは公理であることに注意して三段論法を使えば証明できます。

　

　これで、L₀⁺ での式（７３）の証明から、LでMから式（７４）が導けた訳ですね。しかし、Mは無矛盾としていたので、これは無矛盾に矛盾します。つまり、L₀⁺ は無矛盾ですね。

　

　次に、論理式を並べることを考えましょう。まず、L₀⁺ で用いる記号は高々可算個です。高々可算個というのは、有限個か、無限個あったとしても、自然数と１対１対応（全単射）が付くものです。まあ、記号といったって、論理記号と、カッコと、変数記号位ですね。これらはせいぜい可算個程度です。

　

　そして、論理式は記号の有限列なので、やっぱり高々可算個です。これは、記号が１個だけのものを１行目に並べ、記号が２個だけのものを２行目に並べ、記号が３個だけのものを３行目に並べ、・・・、以下の様に順序を付けると解ります。図を見てよく考えましょう。

　

　

　なお、無意味な記号列は飛ばしても差し支えありません。

　

　とにかく、L₀⁺ の論理式を、番号を付けて１列に並べます。そして、番号順に見て行き、式（７６）の形をした閉じた論理式を全部取り出し、取り出した順に番号を付け式（７７）とします。

　

　

　次に、自然数列を作りましょう。

　

　式（７８）に表れるどの自然数よりも大きい最小の自然数を i₁ とします。

　

　

　更に、帰納的に、式（７９）に表れるどの自然数よりも大きく、かつ i_n より大きい最小の自然数を i_n+1 とします。

　

　

　いま、L₀⁺ に、式（８０）を公理として付け加えた体系をL_n⁺ とします。

　

　

　このとき、L_n⁺ は無矛盾でしょうか。こういうときは、最初に矛盾であると仮定して調べ、それでうまく行かないときは、直接無矛盾であることを調べます。

　

　もし、矛盾であるとすると、L_n⁺ が矛盾するような n があります。その最小のものを k+1 とします。こういうとき、１個戻ったものに対してどうのこうのと考察するので、最小のものを k とすると k-1 について考察することになり、ちょっと面倒になります。それで最初から k+1 としておいた方が楽です。

　

　さて、仮定から、L_k⁺ は無矛盾です。そして、式（８１）を公理として追加すると矛盾が発生します。

　

　

　ということは、追加した公理の否定、つまり、式（８１）の否定はL_k⁺ で証明可能ですね。式（８１）の否定は式（８２）です。これは「かつ」で結ばれているので、結局、式（８３）と式（８４）がL_k⁺ で証明可能になります。

　

　

　ここで、L_k⁺ の作り方を見れば、i_k+1 はL_k⁺ の公理には表れません。したがって、式（８４）の証明に表れる論理式において、i_k+1 を証明に表れない変数 y で置き換えてしまいましょう。そうすれば、式（８４）の証明は、式（８５）の証明になります。

　

　

　式（８５）が証明できれば、前にやった方法を使って、「全て」という束縛記号によって束縛した論理式も証明可能となります。すなわち、

　

　

が証明可能となります。

　

　しかし、式（８６）は、式（８３）の否定ですから、式（８６）と式（８３）が導けたL_k⁺ は矛盾です。これはL_k⁺ が無矛盾だといってたことに矛盾します。つまり、L_n⁺ は無矛盾です。

　

　体系の拡大を続けましょう。今度は、L_n⁺ ( n ＝ 1 , 2 , ・・・ ) の公理を全てL₀⁺ に付け加えた体系をL⁺⁺ とします。ちなみに、証明は有限個の論理式ですが、公理は有限個などという制限はありません。

　

　さて、L⁺⁺ は無矛盾でしょうか。仮に、矛盾である式（８７）が証明できたとします。

　

　

　そうすると、証明は有限個の論理式だから、適当なL_n⁺ で式（８７）が証明できることになります。しかし、L_n⁺ は無矛盾なので、やっぱり矛盾します。こうして、L⁺⁺ は無矛盾であることが解りました。

　

　いよいよ、飽和法を使うときがきました。L⁺⁺ に論理式を追加して行って飽和させましょう。どのような論理式を追加するかというと下記のような論理式です。

　

　

　やり方は、まず、自由変数を含まないあらゆる論理式に番号を付けてならべます。それを、C₁ 、C₂ 、・・・ とします。そして、更に、L⁺⁺ をL₀⁺⁺ とおき、以下、帰納的にL₁⁺⁺ 、L₂⁺⁺ 、・・・ と体系の拡張列を作ります。

　

　まず、式（８８）のどちらか一方がL₀⁺⁺ で証明可能であるときは、L₁⁺⁺ ＝ L₀⁺⁺ とおきます。そうでない場合は、L₀⁺⁺ にC₁ を公理として付け加えたものをL₁⁺⁺ とおきます。

　

　

　次に、L_n⁺⁺ まで出来たとして、式（８９）のどちらか一方がL_n⁺⁺ で証明可能であるときは、L_n+1⁺⁺ ＝ L_n⁺⁺ とおきます。そうでない場合は、L_n⁺⁺ にC_n+1 を公理として付け加えたものをL_n+1⁺⁺ とおきます。

　

　

　こうして、L₁⁺⁺ 、L₂⁺⁺ 、・・・ と体系の列ができました。この体系列のあらゆる公理をL₀⁺⁺ に付け加えたものをL^* とします。

　

　もう解ったと思いますが、新しい体系を作ったら、まず、無矛盾かどうかを考えます。当然、ここでも、L^* が無矛盾かどうかを考えます。

　

　L^* における矛盾の証明は、有限個の論理式ですから、当然の様に公理も有限個しか使いません。したがって、適当な n があって、L_n⁺⁺ での矛盾の証明になります。これから、L_n⁺⁺ が無矛盾かどうかを考えればよくなります。

　

　もちろん、すべての n でL_n⁺⁺ が無矛盾であれば問題ありません。何度もやっているように、こういうときは、そうでないとして矛盾を導きます。

　

　L_n⁺⁺ が矛盾するような n があるとして、その最小のものを k+1 とします。つまり、L_k⁺⁺ は無矛盾で、L_k+1⁺⁺ は矛盾するということです。このとき、L_k⁺⁺ にC_k+1 を付け加えると矛盾となります。つまり、C_k+1 が矛盾となり、その否定はL_k⁺⁺ で証明可能ということです。これは、C_k+1 を付け加えられないことを示しており、L_k+1⁺⁺ の作り方に反します。

　

　これで、L^* が無矛盾ということが解りました。

　

　次に、L^* の性質を考えましょう。L^* は自由変数を含まない論理式の内、それ自身か、その否定が証明可能となるように論理式を公理として追加したものです。それゆえ、L^* では、「自由変数を含まない全ての論理式は、その論理式自身か、その論理式の否定が証明可能」ですね。ちゃんと示すには、今までなんどもやってきた方法を使えばできます（読者の宿題）。

　

　ここまでで、体系としてはできましたので、自然数との接点を探りましょう。自然数が絡んできたのは式（８０）です。この式を使うことを考えましょう。

　

　最初は、自由変数を含まない論理式として、式（９０）がL^* で証明可能であるときに、適当な自然数 n を取ると、D(n) がL^* で証明できるかどうかです。

　

　

　式（７７）で、式（９０）のような形の論理式は全て番号付けされています。なので、式（９０）が k 番目であるとできます。そして、式（９１）のように書けます。

　

　

　L^* の作り方を最初から読み直せば、

　

　

をL^* の公理として追加しているのが解ります。式（９１）と式（９２）とで三段論法を使えば、

　

　

　が導けます。つまりD(i_k) はL^* で証明可能です（要するにD(n) がL^* で証明できるということ）。

　

　もちろん、適当な自然数 n に対して、D(n) がL^* で証明可能であれば、式（９０）がL^* で証明可能であることは自明ですね。

　

　以上をまとめると、式（９０）がL^* で証明可能である必要十分条件は、適当な自然数 n に対して、D(n) がL^* で証明可能であることにです。

　

　今度は、「存在する」を「全て」に置き換えて考えましょう。もちろん、式（９４）は自由変数を含まない論理式とします。

　

　

　式（９４）がL^* で証明可能である必要十分条件は、D(0) 、D(1) 、D(2) 、・・・ が全てL^* で証明可能であろうと推定されますね。

　

　式（９４）がL^* で証明可能なら、D(0) 、D(1) 、D(2) 、・・・ が全てL^* で証明可能であるのは自明ですね。この逆が問題になります。

　

　いつものように、D(0) 、D(1) 、D(2) 、・・・ が全てL^* で証明可能であるにもかかわらず、式（９４）がL^* で証明可能でないとします。このとき、その否定は証明可能になるから、式（９５）がL^* で証明可能になります。

　

　

　これから、式（９６）がL^* で証明可能になります。

　

　

　こうなると、適当な自然数 n に対して、式（９7） がL^* で証明可能ですね。

　

　

　そうすると、D(0) 、D(1) 、D(2) 、・・・ が全てL^* で証明可能とはなりません。したがって、逆が成り立ちます。

　

　いよいよ最終段階に入るときです。L^* の自由変数を含まない証明可能な論理式を、全て真とする述語の集合を作りましょう。

　

　まず、L^* の自由変数を含まない証明可能な論理式は以下のどれかです。

　

　

　ここで、（１）から（３）の論理式に真偽値を付与しましょう。

　

　最初は（１）です。式（９８）がL^* で証明可能のとき、P( a₁ ,a₂ ,・・・,a_n ) の真偽値を真とします。

　

　

　そして、式（９９）がL^* で証明可能のとき、P( a₁ ,a₂ ,・・・,a_n ) の真偽値を偽とします。

　

　

　次に、（２）の論理式は、A、Bの真偽値によって、真偽表を用いて真偽値を付与します。

　

　最後は（３）の論理式です。

　

　式（１００）はA(n) が真であるような n があるとき真とし、なければ偽とします。

　

　

　式（１０１）は、A(0) 、A(1) 、A(2) 、・・・ が全て真のとき真とし、そうでなければ偽とします。

　

　

　こうして、自由変数を含まない全ての論理式に真偽値を付与できましたね。

　

　このときに、L^* で証明可能な閉じた論理式は、自然数全体の集合の上で真になります。もちろん、L^* で証明可能な閉じた論理式の中にはMの論理式が全て入っています。つまり、Mは自然数全体の集合の上で充足可能になります。

　

　さて、充足定理を使うと、先送りにした問題が解決します。これは、第４章の終わりに書いてある通り、「恒真な論理式は証明可能か。」という問題です。

　

　まず、Aを恒真として、充足定理が使えるようにしましょう。充足定理では、自由変数を含まない形だったので、そのように変形しましょう。それには、Aの自由変数を「全て」で束縛することです。この束縛したものを、A^* とすれば、A^* も恒真ですね。

　

　いつものように、A^* をLで証明可能ではないとしましょう。そして、A^* に含まれる述語変数を定数とみなします。このときに、式（１０２）が述語論理の公理と矛盾しなければ（つまり無矛盾）、式（１０２）は自然数全体の上で充足可能になります。ところが、A^* は恒真なので、矛盾ですね。

　

　

　一方、式（１０２）が述語論理の公理と矛盾したとすると、式（１０２）を公理として付け加えて、矛盾した体系ができます。矛盾していると、全ての論理式が証明可能になるので、当然、A^* が証明可能ですね。そうすると、演繹定理によって、式（１０３）がLで証明可能になります。

　

　

　式（１０３）を変形するとA^* 自身なので、LでA^* が証明可能ということが解りました。これは、A^* がLで証明可能でないとしていたことに矛盾します。

　

　いずれにしても矛盾が生じます。これで、A^* がLで証明可能であることが解りました。

　

　A^* がLで証明可能であれば、当然、AもLで証明可能ですから、「恒真な論理式は証明可能。」ですね。

　

　

６．コンパクト性定理

　ここでの目的は、「こんなこともできないのか。」という限界を知ることです。具体的には、「自然数の上で、どんな公理系を用いても、不等号を完全に特徴付けられない。」という、有名な事実を見ます。そのために用いるのがコンパクト性定理です。

　

　コンパクト性定理というのは以下です。

　

　「論理式の集合の、いかなる有限部分集合も充足可能であれば、元の集合自身が充足可能である。」

　

　これ、論理式の集合の要素（論理式）で、述語変数と自由個体変数を全て定数とみなすと、無矛盾か矛盾かのどちらかになります。

　

　もし、無矛盾なら充足可能であるから問題ありませんね。（本当はサボった方が必要）

　

　そうすると、矛盾のときにどうなるかです。矛盾すれば、矛盾が導けます。まあ、何度も書いてますが、矛盾というのは、以下の式（１０４）です。

　

　

　そして、式（１０４）を導くのに、有限個の論理式しか使いません。そうすると、その有限個の論理式を要素とする集合を考えれば、「いかなる有限部分集合も充足可能」と矛盾しますね（矛盾だと充足可能にならない）。

　

　こうして、コンパクト性定理の成り立つことが解りました。

　

　さて、問題となる不等号についての考察をはじめます。自然数の上で、不等号を定義付ける公理系を用意しましょう（どんなものでも可）。もちろん用意するのは読者の宿題です。

　

　そして、a < b という述語を考えます。正しくは関数表現を行う必要があるけど、以前にも書いた通りそこまではしません。この上で、以下に記載の論理式の集合を考えましょう。

　

　

　明らかに、この内、どの有限個を取っても、自然数全体の上で充足可能ですね（ x に有限個の式に出てくる一番大きな自然数よりも大きな自然数を割り当てればいいから）。

　

　すると、コンパクト性定理によって、式（１０５）の全体が自然数全体の上で充足可能になります。ということは、式（１０５）全体の解となる自然数があるということです。つまり、どんな自然数よりも大きな自然数があるということですね。

　

　こうして、どんな公理系を用いても、不等号を完全には特徴付けられないということが解ります。とんでもないですね。

　

　

７．おわりに

　今回は、第１００話ということで、入門までを体系化して書いてみようという企画でした。案の定、途中で飽きてしまいました。こんなことなら、途中で分けて、何回かの連載にした方がよかったような気もします。

　

　また、今回の企画に先立って、第１００話は、「こんなこともできないのか。」というとんでもない結論に至るものにしようということがかなり前から予定されていました。もちろん、複雑な内容のものが「できない」というのでは、あまり衝撃にはなりません。簡単で解りやすく、常識と思っていたことが裏切られるようなものの方が面白いと考え、それには、「自然数の上の不等号が完全には特徴付けられない。」という話が丁度よいのではないかと思い選びました。多少はみなさんの刺激になったでしょうか。

　

完

　

平成29年6月10日

著作者　坂田　明治（あきはる）