ゲーデルの不完全性定理の怪

ゲーデル文：正しいけど証明できない命題

完全性定理との「見かけ上の矛盾」の解消

内容

• まえがき
• 前提知識
  • 不完全性定理とゲーデル文
  • 完全性定理
• ゲーデル文と完全性定理との「矛盾」の解決
• 「矛盾」の解決
• 付録
  • 一階述語論理とモデルについて
  • AI との対話で有用な依頼
  • 完全性定理の概要
  • 不完全性定理に関する感性的な絵

まえがき

ゲーデルの不完全性定理の証明では「正しいが証明できない命題」があると言う．
一方，ゲーデルの完全性定理 は「正しい命題は証明できる」と言っている．
これらは矛盾するように見えるが，実はそうではない

私は，ここ２週間くらい，ゲーデルの不完全性定理を調べたり，考えたりしていました． 不完全性定理は 40年以上前，私が大学４年生（本当は留年して５年生）の時にゼミの輪講でやって，やはり，難しいやら， 扱うことに細心の注意が必要であることやらで，証明を追いかけていくだけが精一杯で，あまり分かった気にならなかったのです．

それで，ときどき分からなくなる疑問がありました．それは，冒頭に挙げた疑問です．

不完全性定理の証明の中で用いられる，所謂，ゲーデル文 G，つまり

今までに 何回か不完全性定理を読み直したり，考えたりして，納得したことがあるような気も するのですが，また，よくわからなくなっていたので，ここ２週間で 調べたり，考えたりしていました．

それで，なんとか分かった気になりましたので，忘れないように，ここに書き留めておきます．

でも，ただ，メモを残していくのでは芸がないので， 最近，流行りの生成 AI を使って， 感性的な絵などを駆使した作品として残したいと思います．

たぶん，見かけ上の矛盾解決のメカニズムを端的に書くよりは，感性に寄った絵や蛇足が入り，かえって，かなり分かりにくくなると思いますが，人生，ショートカット（近道）だけでは面白くないのでご容赦ください．

このページの内容には蛇足があるの絵

前提知識

First, there is something you should know

不完全性定理とゲーデル文

「（第一）不完全性定理」は，簡単に言うと次のような定理です．

算術を含む（自然数の加減乗除ができる）一階述語論理で，

• 全公理を計算機で次々に列挙していく方法がある体系で，
• その体系が矛盾を含まないなら，

命題 G も命題 ￢G も証明できないような命題 G が存在する

この G は，ゲーデル文と言われるのですが，別名

「正しいけれど証明できない命題」

G = (G は証明できない)

私を証明することはできない by Gödel Statement

ここから，次のように，G は正しいけれど証明できないことが導かれます．

G の内容から， G が正しくなければ，「G は証明できない」が嘘になって，

G は証明できる
→ G は正しい
→(最初の仮定「G は正しくない」と） 矛盾

になって，「G が正しくない」という選択肢はなくなります．

したがって，G は正しくなければならず，かつ，証明できないという訳です．

こういう命題 G を作る方法としては，論理式や証明の概念をその体系の中の数で ゲーデル数とよばれる数にエンコードして，その体系内の数の性質として G を 表現します．このエンコードの必要性から，不完全性定理の前提には，算術を含み（加減乗除ができる）という条件があるのです．ゲーデル数は素因数分解の一意性を利用して論理式をエンコードします．

ゲーデルのころはまだコンピュータは無かったのですが，現在は，コンピュータが あり，任意の文字列がコンピュータの中のメモリーの内容として表されることを 私たちは知っています．で，それらの文字列は長い２進数と思うことができるので， 命題が数で表現できるのは当たり前と受け止められると思います．

コンピュータの中では文字列が数で表現されている

ゲーデルの不完全性定理の証明の流れを理解するのはあまり難しくありません．

ゲーデルの不完全性定理の証明の流れ

• ①算術を含む
• ②公理をすべて列挙していく手段がある
  公理は一般に無限個ありますから，列挙し終わる必要はありません． ずっと列挙していって，どの公理も，いつか，その列挙の中に現れれば十分です．
• ③無矛盾である

①から，素因数分解の一意性を使って，論理式を構成する記号を自然数としてエンコードすることで，論理式や論理式の列を自然数としてエンコードできるようになります（④）．先ほども言いましたように，現代の計算機に慣れた人なら，素因数分解ではなく，二進数のコード体系を考えても良いです．

②から，すべての公理を列挙していく手段がありますから，論理式の列に対して，それを構成する論理式が，公理であるか，あるいは，それより前のいくつかの論理式から推論規則を使って導出されたものかを 判定する論理式が書けます（⑤）．つまり，論理式の列をエンコードした自然数に対して，それが証明をエンコードしたものかどうかを判定する論理式が書けるということです．

そうすると，ちょっとした技法（対角化技法）を使って，「G = (G は証明できない)」という論理式を作ることができます（⑥）．

この論理式は，前に書いたように，証明できると仮定しても，反証できる（￢Gが証明できる）と仮定しても矛盾がおきます（⑦）．

公理系 T は無矛盾でしたから（③），G は証明も反証もできない論理式でなければなりません（⑧）．

これで，不完全性定理の証明の流れの説明は終わりです．

もう一つ，補足として，不完全定理の意義について述べておきます．

「不完全性定理」の意義について説明します

皆さんの中には

「公理系に証明も反証もできない論理式があったら，どうなんだ？　なにか悪いことでもあるのか？」

• 正しいのに証明できない論理式がある．
  当時，正しい論理式はすべて証明できるかということが問題に なっていましたから，これは楽観論者にとっては痛手でした． 実は，このページの主題でもあるのですが， どういう意味で「正しい」のかは大いに問題になるところです．

• 計算機による証明が停止しない場合がある．
  私は計算機の分野の人間ですから，これは興味があります． 証明も反証もできない論理式の存在は，自動証明の可能性の 限界を意味します．ただし，これは，機械ができないだけでなく， 「チャーチの提唱」を受け入れる限り，人間もできないということを 意味します．

• 公理系の無矛盾性を，その公理系の強さ以下の強さの理論で証明できない．
  今まで述べたのは第一不完全性定理ですが，この帰結として，第二不完全性定理が導かれ，公理系の無矛盾性は，その公理系より強い公理系でないと証明できないことが示されます．

  公理系に公理を追加していくと，ますます矛盾する可能性が高くなってきます．もともと，こういう公理系を考え始めたのは，我々が行っている数学的推論を一階述語論理で厳密に定式化して，それが無矛盾であることを示したかったからです． それが，より強くて，矛盾しているかもしれない公理系からでないと証明できないというのは，がっかりな訳です．

これらが，不完全性定理が意味する，たぶん，一般の人も関心の強い事柄です．

以上，不完全性定理のイメージが持てるように，ちょっとだけ補足しておきました．

あと，ここまで書いてきて，「命題」と「論理式」が入り乱れて使われていることに 気が付きました．きちんとした意味を定義するのは煩雑なので，ここでは，私は， ほぼ同じ意味で使っていて，形式的にあまり意味を込めないときには論理式と使って， 何か人間にとって意味のある重要性があるときは命題と言っていることが多いくらいに受け取ってください．ただし，これは一般的な使い分けではなく，ここだけの使い分けです．

Gödel Statement "I CAN NOT BE PROVED!"
"BE" が抜けましたけど

完全性定理

G: 正しいけれど証明できない命題

ゲーデルがこの不完全性定理を証明する前に証明したものに，「完全性定理」が あります．この完全性定理と，前に述べたゲーデル文が矛盾するように見えるのです．

ここでは，その矛盾っぽいもの理解のために，準備として 完全性定理について簡単に説明しておきます．

完全性定理は

一階述語論理においては，すべてのモデルで正しい命題は証明できる

「モデル」という言葉がでてきましたが，数理論理学に不慣れな人は，ここで出てきた「モデル」という言葉に途惑っているかもしれません．

簡単に言うと，ある公理系のモデルとは，その公理系に出てくるすべての記号に何か数学的なものを割り当て，公理をすべて満たすようにしたもののことです．

一階述語論理の公理系とそのモデル

上の図の左側が一階述語論理の枠組みで何らかの理論を表現したものです． その理論の内容は公理系（公理，つまり，その理論で成り立つことが要請される論理式の集合）で決まります．

論理式は，定数記号，変数，関数記号，述語記号，論理記号（∨，∧，→，￢，∀，∃など）から，ある文法にしたがって組み立てられます．

モデルは，この一階述語論理を解釈する枠組みのうち，公理を満たすもののことです． まず，変数や定数が取りえる値となる要素の集合，各定数がどの要素に対応するかの マッピング，関数記号や述語記号がその要素の集合上のどんな関数や述語に対応するかのマッピングからなります．これらのマッピングが決まると，左側の述語論理の論理式を解釈することができるようになります． モデルは，そのような解釈のうち，公理を満たすものです．

一般に公理系を満たすモデルは無数にあります． 完全性定理は，その公理系で証明できるものは，それらモデルで成り立つものの共通集合だと言っているわけです．

あっさりした説明でしたが，これで準備は終わりです．次は，ゲーデル文と完全性定理の「矛盾」について見ていきます．

ゲーデル文と完全性定理との「矛盾」

完全性定理が成り立つとすると，ゲーデル文 G

G: 正しいけれど証明できない命題

ということで，Gは，

証明できないけれど，証明できる命題

ちょっと，今までの議論の中の重要な部分を振り返ってみましょう．

私たちは，これまで，ゲーデル文 G について，「正しい」と表現してきて，「すべてのモデルで正しい」とは書いていませんでした． これがあるモデルでだけ「正しい」なら，完全性定理は適用できませんから，別に矛盾はおきません．

しかし，振り返ってみると，どのモデルでも，

G が偽
= (Gは証明できない) が偽
→ G は証明できる
→ G は正しい
→ 矛盾

ですから，上で，「すべてのモデルで正しい」という仮定のもとに，完全性定理の適用は妥当だろうと思う訳です．そして，上のように考えると，矛盾が起こってしまいます．

ゲーデル文 G はすべてのモデルで正しいような気がするんだけど， 違うのかしら？

これが，私がときどき分からなくなる疑問です．記述が少し長かったかなと思うので，もう一度，疑問を端的にまとめます．

1. 不完全性定理の証明では，ゲーデル文という「（たぶん，すべてのモデルで）正しいけれど証明できない命題」が出てくる．

2. 完全性定理は，すべてのモデルで正しい命題は証明できると言っている

3. そうすると，ゲーデル文は証明できるはずだが，その内容から証明できないはず．

それで，ここ２週間，これを調べたり，考えたりして，分かった（ような気になった）ので， 今度はしっかり書き留めておこうと思ってこのページを書いています．

また，世間（啓蒙書やそれらを読んだ人々の間）にも，ゲーデル文は，簡単に，

G = 「正しいけれど証明できない命題」

世の中には，正しいけれど，計算機が証明することができない命題がある． 人間はその正しさが分かるので，人間は，機械より優れている． 機械はどうやっても人間にかなわない．

世の中には正しいのに証明できない命題がある．人間にはどうしても 到達できな真実があるのだ．これが神の絶対性を示している．

哲学者も宗教者も，立派な人は，きちんと理解するまで勉強して，とても示唆に富む 書き物をしている人たちがいて，すごいなと思うのですが，一方，多くの哲学者さんたち，宗教者さんたちは，表面だけなぞって我田引水し，自分たちの見かけ上の権威を保つのに使っています．

だから，これをもう少し誤解のない表現にするのが良いのだろうなと思います．

アンドロイドの聴衆に人間の方が機械より優れていると力説している学者さんの図

「矛盾」の解決

まず，前回の復習をして，「矛盾に見える」ことが何だったかを思い出しておきます．

• A: 不完全性定理の概要
  

  　不完全性定理では，公理と推論システムからなる一階述語論理の体系で

  • 算術を含み，その体系についての論理式を数でエンコードできて，
  • 公理は計算機で（無限の時間がかかろうとも）全部を列挙可能で，
  • 矛盾のない体系である

  なら，ゲーデル文と呼ばれる，次の命題 G が存在して， G も￢G も証明できない．

  G = (G は証明できない)

• B: 「ゲーデル文 G」... 正しいけれど，証明できない命題
  ゲーデル文 G は，一般に

  正しいけれど，証明できない命題

  と呼ばれている．

  これは，もし，G があるモデルで偽なら，G = (G は証明できない) の 内容から，G が証明できることになり，G は正しくなり，矛盾が生じるので，偽であり得ない   ことによる．

• C: 一階述語論理の完全性定理
  一方，完全性定理によれば

  一階述語論理では，すべてのモデルで正しい命題は証明可能である

  が成り立つ．

D: 見かけ上の矛盾

不完全性定理（の証明）から，G は証明できない命題であることが示されており，また， Gの内容はすべてのモデルで正しいが，完全性定理からは すべてのモデルで正しい命題は 証明されなければならない．これは矛盾である．

結論からいうと，次の文章の下線部が嘘です．

「ゲーデル文:「G = (G は証明できない)」」は，（すべてのモデルで）正しいけれど，証明できない命題である

ここの「すべての」は先ほど念を入れて確かめたところなのですが，実は，G を偽にする モデルがあります．

G が偽のモデルでは，G に証明があることになります．証明があるなら，G が真になりそうなのですが， モデルによっては，「証明」があっても真にならないこともあるのです．

ここでいう「証明」というのが，我々が行う証明ではなく，G にエンコーディングされた 証明，つまり，そのモデルの中でいう証明であるというのがポイントです．

G は，自然数の集合が我々の知っているような ℕ = {0, 1, 2, 3, ...}という モデルでは常に真になるのですが，ℕを含んではいるけど，もっとたくさんの 我々の知らないような自然数が含まれるモデルも可能で，そのようなモデルの中で G を偽にするモデルも存在するのです．

このことを理解するために，算術の理論のモデルの種類について述べます．

標準モデルと超準モデル

例えば，自然数 ℕ の定義は，

(0 を含んでいて)，(x 含むなら x+1 も含む)

ℕ = {0, 0+1, 0+1+1, 0+1+1+1, ...}

ℕ2 = {0, 0+1, 0+1+1, 0+1+1+1, ..., ω, ω+1, ω+1+1, ω+1+1+1, ...}

自然数が最初のℕであるようなモデルを「標準モデル」と言います．私たちが 普通に想像する自然数の理論です．

それに対して，ℕ2 やそのほか，自然数がℕの要素以外のものも含むモデルを 「超準モデル」と言います．

（注意）一階述語論理の限界：
よく，計算機科学などでの帰納的な定義で

1. ... は「項」である．
2. ... も「項」である．
3. 「項」は，これらのルールで作られたものだけである．

のように，「項」となるものを列挙していって，最後に，「項」はこれらのルールで作られたものだけであるという断りを置くことがあります．

しかし， 一階述語論理は，変数は対象領域のオブジェクトだけを指すことができて，関数や述語などを指すことはできません．

上の「これらのルールで作られたものだけ」という文言は，対象領域のオブジェクトでは無いので，一階述語論理では表現できないのです．

AI に書いてもらった感性的な超準モデル

「見かけ上の矛盾」の解消

・ある自然数 m があり，

m は，証明となる論理式の列をエンコードしたものであり，
・その最後の論理式は，証明すべき論理式である

証明可能であるという述語 Provable(Q) の内容

標準モデルでは，m は普通の自然数から作られますから，普通に有限列の証明ができるのですが， 超準モデルでは，ω+1 というような自然数があり， それは，モデルの中では証明の要件は満たしているかも しれませんが，我々から見て有限列であるとは限りません．したがって，このような証明があったとしても， 最終的な論理式が真であることを保証するとは限らないのです．

まとめると，G が任意のモデルで正しいとの推論は

• G が偽と仮定
• →「Gは証明できない」が偽
• →G は「証明」できる．
  この「証明」はそのモデル内での証明
• →G は正しい(?)
  超準モデルでは，これが成立しない場合がある

ゲーデル文G は，我々のなじみのある自然数からなる標準モデルでは正しいが，
超準モデルでは必ずしも正しいとは言えず，
完全性定理が 適用できないので，証明があるという結論には到達せず，
矛盾は起こらない

つまり，ある命題が，超準モデルの中の言葉で「証明」できたとしても，
その命題が正しいとは限らないのだ

付録

一階述語論理とモデルについて

本文中では，一階述語論理については説明せずに，モデルについては

ある公理系のモデルとは，その公理系に出てくるすべての記号に何か数学的なものを割り当て，公理をすべて満たすようにしたもののことです．一般に公理系を満たすモデルは無数にあります．完全性定理は，その公理系で証明できるものは，それらモデルで成り立つものの共通集合だと言っているわけです．

一応，一階述語論理（数理論理）とモデルについては，私が書いた簡単な解説も

レーベンハイム・スコーレムの定理までの大急ぎのまとめ
記号論理の文法 (Syntax) と意味 (Semantics)

ここから，AI サーチとの対話の抜粋

• 一階述語論理とモデル
  私： 一階述語論理とモデルについて，ごく簡単に，また直感的な言葉で教えてください．
  
  

  AI さんに頭を下げて，「モデル」について教えてもらうの図

  AI さん：
  一階述語論理とモデルの関係を、直感的に言うと、 「一階述語論理」が現実世界について述べるための言葉（文法）であり、「モデル」はその言葉が指し示す具体的な現実世界そのものです。

  一階述語論理：言葉（文法） 一階述語論理は、以下のような要素を持つ形式的な言語です。 

  • 定数記号： 特定のものを指す名前。「サザエさん」「カツオ」など。
  • 述語記号： 対象の性質や、対象間の関係を表す言葉。「〜は男である」「〜と〜は親子である」など。
  • 変数： 不特定のものを指す言葉。「x」「y」など。量化記号：変数の範囲を指定する言葉。
  • 全称量化子 (∀)：「すべての〜について」
  • 存在量化子 (∃)：「ある〜について」
  • 論理記号：「かつ」「または」「ならば」など。 
  具体例：「すべての男はカツオの親ではない」という文は、一階述語論理の言葉で表現できます。

  ∀x (男(x) → ¬親(x, カツオ))

  モデル：言葉が指し示す具体的な世界
  モデルは、一階述語論理で記述された文が「真」か「偽」かを判断するための、具体的な世界のことです。モデルには、以下の要素が含まれます。

  • 領域（ドメイン）：議論の対象となるものの集合。たとえば、「磯野家の人々」というモデルなら、ドメインは {サザエ, カツオ, ワカメ, 波平, フネ, タマ} となります。
  • 解釈：論理の言葉が、その具体的なドメイン上で何を意味するかを定義するもの。
    • 定数記号の解釈：「カツオ」という記号を、ドメイン内の人物「カツオ」に対応させます。
    • 述語記号の解釈：「〜は男である」という述語を、ドメイン内の人物のうち、男である者の集合 {カツオ, 波平} に対応させます。

  両者の関係：言葉と現実のチェック
   一階述語論理とモデルは、以下のような関係で結びついています。 

  • 論理式は、モデルの中で真偽が決まる
    「∀x (男(x) → ¬親(x, カツオ))」（すべての男はカツオの親ではない）という論理式は、先述の「磯野家の人々」モデルの中では真です。なぜなら、男である波平は、カツオの親ではないからです（波平はサザエの親ですが、カツオの親ではありません）。
  • モデルが変われば、論理式の真偽も変わる
    もし、ドメインが {太郎, 花子} で、太郎が花子の親であるような別のモデルを考えれば、先ほどの論理式は偽になります。
  • モデル論は、この関係性を数学的に探求する分野
    モデル論は、「どのようなモデルでも常に真となる論理式は何か？」「ある論理式が真となるモデルはどのような特徴を持つか？」といった問いを探求する分野です。 

  まとめ：
  一階述語論理は、数学的構造や現実世界について厳密に記述するための「文法」であり、モデルは、その記述が適用される「具体的な世界」です。この2つがあることで、論理的な推論が具体的な事柄に対応できるようになります。

  私：
  AI に書いてもらうと楽ですね．

  しかし，「サザエさん」が例に出てくるとは思いませんでした．これを インターネットに公開することにより，別に著作権は犯すことにはなりませんよね．

  それで，一階述語論理とモデルについては，およそ，上のようなことです．理解を深めるためには，ご自分で，Google の AI モードにでも，上の質問を投げかけて，読んでも分からないことや，自分が思うことを AI モードに問うてみるというのが良い勉強になると思います．

  例えば，「一階述語論理の欠点はなんですか？」とかを聞いてみると良いと思います．私もやってみましたが，沢山出てきたので，ここに書き写すことはしません．皆さんでやってみてください．分からないことについて教えを乞うことも，人と対話しながら発想を刺激するということも大切なことだと思います．

  
  

  AI さんとの対話で理解を深めるの図

AI との対話で有用な依頼

• ゲーデル文が正しくならないモデルを整理してもらう
  不完全性定理の証明にはゲーデル文 G が使われます．ゲーデル文 G は簡単に言うと，自然数により，論理式をエンコードできる性質を利用して作成したG = (G は証明できない) 相当の論理式です．これは，「正しいが証明できない式」と言われています．しかし，これがすべてのモデルで正しければ，完全性定理から証明できるはずです．したがって，これが正しくないモデルが存在するはずです．そのようなモデルは自然数の集合が我々が考える自然数よりはるかに多い超準モデルのうちのどれかです．G が正しくなければ，G は証明できることになります．そこで証明できるのに正しくない論理式ができるのですが，この状況をうまく整理することができますか？

• 超準モデルの構造を教えてもらう
  その超準モデルには普通の自然数のほかにどのような自然数が存在するのですか？普通の 0, 1, 2, 3, ... の後にまた自然数があるのでしょうか？ それとも， 0, 1, 2, 3, ... のようなものが他にも，例えば，a0, a1, a3, a3, ... のような，何本もの自然数の上昇列があるのでしょうか？

  この二つ目の問いの後の，AIモードさんの回答を以下に書いておきます．

  AI モードさんの回答

  ご指摘のとおり、超準モデルには、私たちが直感的に考える自然数（標準自然数）の無限の上昇列「0, 1, 2, 3, ...」の「後」に、さらに「超準自然数」と呼ばれる無限の列が存在します 。超準モデルの構造は、驚くほど奇妙で複雑です。

  超準自然数の存在と構造

  1. 無限に大きい自然数
     
     • 超準モデルには、どんな標準自然数よりも大きい「無限大」の自然数が存在します。
     • これらの無限大の自然数は、標準自然数と同様に、足し算や掛け算などの算術の公理を満たします。

  2. 自然数の列の構造
     
     • 超準モデルの要素を順序付けして見てみると、その構造はあなたの予想に近いものです。
     • まず、0, 1, 2, ... という、私たちが知っている標準自然数の列が無限に続きます。
     • この列の「後」に、ある無限大の超準自然数 ω が現れます。
     • この ω から、ω+1, ω+2, ω+3, ...という形で、標準自然数と同じように後者が適用された無限の列が続きます。
     • さらに、ωの前に、ω-1, ω-2, ω-3,...という無限の後退列も存在します。
     • このように、超準自然数は ω, ω・2, ω²などのように無限に大きい数を持ち、その前後にℤと同じ型の構造（正の整数と負の整数の構造）が張り付いた形になっています。

  3. 無限に多くの自然数
     
     • さらに驚くべきことに、超準モデルには ω のような列が、私たちが考える自然数以外の無限大の超準自然数の背後に、何本も、無限に存在します。
     • これらの異なる超準自然数の列は、順序的には互いに隔たっており、その間には別の超準自然数が入ることができません。
     • 超準モデル全体の順序構造は、標準自然数ℤと、両端のない稠密な順序集合 θ にℤの列を張り付けたものの和 ℕ+ℤ・θ で表せることが知られています。
     • つまり、標準自然数という一本の列の後に、整数の列が無数に散らばっているような構造です。

  なぜそのような奇妙な構造になるのか

  • 超準モデルが生まれる理由は、一階述語論理の限界にあります。
  • 一階述語論理では、「0, 1, 2, ... 以外には存在しない」ということを直接記述できません。
  • ペアノ算術の公理系は、標準自然数ではもちろん満たされますが、超準自然数を含むモデルでも満たすことができるのです。
  • これが、不完全性定理の背景にある、モデルの多様性です。どんなに多くの公理を追加しても、その体系を一階述語論理で記述する限り、超準モデルの存在を排除することはできません。

  私のコメント
  なんか，超準モデルは不思議な構造をしているようですね． AI さんにその不思議さが分かるような絵を描いてもらうように頼んでみました．

  私の依頼：

  自然数の超準モデルは不思議な構造をしています．その不思議さがよくわかるように，宇宙に出発して未知の文明に触れて，その文明には超準モデルの図があって，その図を見て恐れおののいている人類の絵を生成したいので500文字くらいの自然語で表してください．超準モデルの図の内容もある程度書いてください．

  AI モードさんの回答：

  遠い未来、人類は未知の宇宙へ旅立ち、ついに見知らぬ惑星で高度な文明と遭遇しました。その異星文明の聖なる広間には、巨大な壁画が飾られていました。その中央には、Wikipediaによると、算術の超準モデルにおける自然数の超準モデルの構造が描かれています。それは、まるで蛇のように無限に連なる環の連鎖として表現され、それぞれの環はこれまで人間が知る数直線とは異なる、しかし確かに自然数と呼べる要素で構成されています。 その図の隅々には、人間には理解できない記号で、しかしその文明の言葉では明確に、「標準数と全く同じ性質を持つものの、我々が定義する通常の自然数とは決定的に異なる」という解説が添えられているように見えました。その非標準的な無限の連なりは、人間の直感を大きく逸脱したものであり、その異質な構造を目の当たりにした人類の探査隊員たちは、深遠なる宇宙の真理の一端に触れたかのような畏敬の念と、未知の数学的深淵への恐怖に震えおののいています。

  

  確かに不思議で神秘的な感じはしますが，自然数の超準モデルのような気が全然しません．

  
  こちらは少し自然数らしさは出てきたかもしれません． でも，恐れおののいている人類がでてきません．スクリプトが長すぎたのかもしれません． 途中を少し梳いてみました．

  
  今度は人が出てきました．これくらいにしましょうか．

  これも，皆さん，実際に AI モードと対話して知見を広めてみてください．

完全性定理の概要

私の依頼

ゲーデルの完全性定理について，理系の大学２年生に理解できるように概要を教えてください．

完全性定理について教えてください

AIの回答

ゲーデルの完全性定理は、一階述語論理という最も基本的な論理体系において、「真であるものは必ず証明できる」ということを保証する、数学基礎論における極めて重要な定理です 。
• まず理解しておくべき基本概念
  
  1. 構文論と意味論
     完全性定理を理解する上で、この2つの概念の区別が最も重要です。
     • 構文論 (Syntax): 証明に関する議論です。
       • 証明可能（provable） とは、公理から定められた推論規則（公理や定理を導き出すためのルール）を有限回適用することで導出できることです。
       • 記号「⊢ φ」は、「φ が証明可能である」ことを表します。
     • 意味論 (Semantics): 真理に関する議論です。
       • 恒真（logically valid） または 論理的に真（logically true） とは、考えられるすべてのモデル（解釈の仕方）において常に真となることです。
       • 記号「⊧ φ」は、「φ が恒真である」ことを表します。

  2. 健全性（Soundness）
     健全性定理は、完全性定理と表裏一体の関係にある、より直感的に理解しやすい定理です。
     • 内容: 「もしある命題が証明可能なら、それは恒真である」というものです。
     • 記号: ⊢ φ → ⊧ φ
     • 意味: 正しい推論規則を用いて証明された命題は、絶対に論理的に真となります。これは形式的な証明手順が真理を保つことを保証しており、論理体系が破綻していないこと（矛盾したことを証明しないこと）を示します。
     [逞しいボディビルダーの絵]

     
     

     健全な論理は健全な肉体に宿る
     「健全性」とは，
     「ある命題が証明されるならそれは真である」
     という性質のことである

• ゲーデルの完全性定理の核心
  完全性定理は、健全性定理のちょうど逆の向きの主張をします。
  • 内容: 「もしある命題が恒真ならば、それは必ず証明可能である」というものです。
  • 記号: ⊧ φ → ⊢ φ
  • 意味: 一階述語論理においては、モデル（真理の解釈）の世界で常に真となるような命題は、必ず公理系と推論規則だけで証明できるということです。つまり、論理的に真であるものを見逃すことなく、すべて形式的な手続きで捉えることができる、という驚くべき結論を導きます。 

• 完全性定理が意味すること
  • 理論と現実の一致: 構文論的な「証明」と、意味論的な「真理」が完全に一致していることを示します。一階述語論理の形式体系は、論理的な真理をすべて網羅できるほど強力で、不足がないことが明らかになったのです。
  • 論理体系の信頼性: これによって、一階述語論理は非常に信頼性の高い論理体系であることが保証されました。私たちが数学の証明で行っている形式的な推論は、真理を正しく導いていることが理論的に裏付けられたのです。
  • 不完全性定理との違い: 混同されがちですが、完全性定理と不完全性定理は全く別の定理です。
    • 完全性定理: 一階述語論理自体の性質について述べています。
    • 不完全性定理: 算術（数の性質） を含むより複雑な形式体系には、証明も反証もできない真なる命題が存在することを示しました。
    • 両者は、一階述語論理の「完全性」と、算術を含む体系の「不完全性」を対比させることで、形式的体系の限界を浮き彫りにしました。

• まとめ
  ゲーデルの完全性定理は、一階述語論理の形式体系が、その体系で表現できるすべての論理的真理を証明するのに十分な能力を持っていることを証明したものです。

私の追加質問

確か，完全性定理の証明は構成的では無かったと思います．つまり，ある命題が恒真のときに証明を構成する具体的な方法を与えるのではなく，無矛盾ならばモデルがあることを証明していたように思います．そのモデルの構成方法も，その体系をまず完全にするまで追加の公理を加えていく手法であったように思います．完全性定理の証明に選択公理は必要なんでしたか？

たしか，完全性定理の証明は構成的では無かったですよね？
選択公理も使うんでしたっけ？

AIモードの回答

ご指摘の通り、一階述語論理の完全性定理の証明は一般に非構成的であり、その証明には選択公理が必要となります。ただし、言語が可算（無限集合だが要素が列挙可能）な場合は、証明の構成性を高めることが可能です。

証明が非構成的である理由

一階述語論理の完全性定理は、「理論が無矛盾であれば、その理論のモデルが存在する」ことを示します。これは、モデルを具体的に構成する手続きを提示するものではありません。

モデルの存在を示す一般的な証明（ヘンキンによる証明など）は、以下の段階を経ます。

1. 最大無矛盾集合の構成（リンデンバウムの補題）: 無矛盾な理論 T に対して、あらゆる文 A について「A を証明できる」か「¬ A を証明できる」のどちらかが成り立つような、より大きな「最大無矛盾理論」T^* を構成します。
2. ヘンキン的な充足性の付加: T^* に、存在記号 ∃ の文が成り立つときには、それを満たす「ヘンキン定数」と呼ばれる新しい定数を付加する手続きを繰り返します。
3. モデルの構築: 最大無矛盾でヘンキン的な充足性を持つ理論から、論理式の同値関係に基づいてモデルを構築します。 

この過程で非構成的な要素が入ってきます。

• 最大無矛盾集合を構成する際: 無矛盾集合を拡張して最大無矛盾集合を得る際、すべての文を整列順序付けし、一つずつ追加していくという方法がとられることがあります。集合に整列順序を入れるためには選択公理が必要です。
• 非可算な言語の場合: 言語が非可算（列挙できないほど無限に多い）な場合、文全体を整列順序付けして手続きを行うため、選択公理が必要不可欠となります。

選択公理との関連

選択公理は、非空集合の族から各集合の元を1つずつ選んで新しい集合を構成できるという公理です。
• 完全性定理と選択公理の同値性: 一般的な一階述語論理の完全性定理は、ブール代数の素イデアル定理と同値であることが知られています。この素イデアル定理は、ツェルメロ＝フレンケル集合論（ZFC）から選択公理（AC）を除いたZF集合論では証明できず、ACよりも弱いものの、やはり非構成的な原理です。
• リンデンバウムの補題と選択公理の同値性: また、上述の「すべての無矛盾集合が最大無矛盾集合に拡張できる」というリンデンバウムの補題も、一般には選択公理と同値です。

まとめ

• 非構成性: 一階述語論理の完全性定理の一般的な証明（ヘンキン証明など）は、モデルの存在を証明するものであり、モデルを具体的に構成する手続きを与えるものではないため、非構成的です。
• 選択公理の必要性: 非可算な言語の場合、証明の過程で文の整列順序付けを行うため、選択公理が必要になります。可算な言語の場合は選択公理を回避できますが、一般的な完全性定理は選択公理（またはそれと同値な弱い公理）に依存しています。
• 命題論理の場合: ちなみに、命題論理の完全性定理は構成的に証明することが可能です。これは、真理表という決定可能な方法があるためです。



これで，洗濯はぜんぶ終わったかしら？

不完全性定理に関する感性的な絵

• 超準モデルの絵
  私の依頼： 自然数の超準モデルをファンタジー風の絵にしたいと思います．画像生成AI に描かせるためのプロンプトを 500文字くらいの自然語の文章で書いてください．

  AI の回答： 自然数の超準モデルとは、通常の自然数（0, 1, 2, ...）の列の先に、無限大の数や、そのさらに先に続く無限の列が存在するような不思議な自然数の世界のことです 。この数学的概念をファンタジー風に描くプロンプトを作成します。

  画像生成AIへのプロンプト例：
  幻想的な光に満ちた夜空の下、無限に続く螺旋階段を描いてください。階段の一段一段が、きらめく石でできた自然数の世界を表しています。手前の、普通の大きさと形の階段は、私たちが知る自然数0, 1, 2...です。しかし、階段は遥か遠くまで続き、視界の彼方で突然、通常の階段とは全く異なる、奇妙な形状の階段群へと変化します。この超準的な階段群は、巨大な結晶や、宙に浮く浮島のような形をしており、それぞれの段には未知の幾何学模様が刻まれています。無限大を表す、ひときわ巨大で輝く惑星のような階段が、その世界の中心に浮かんでいます。この超準的な自然数の世界を旅する、ローブをまとった数学者の冒険者たちが、不思議な光に包まれながら、その未知の領域を探索している様子を、詳細で美しいファンタジーアートスタイルで描いてください。色彩は、紫、青、金など、神秘的で深みのあるトーンを基調に。

  
  

• 超準的な証明の絵
  不完全性定理を大学１年生に，感性的な表現で教えようと思います．超限自然数で表された証明の絵を自然語500文字くらいの文章で表現してください．

  大学1年生向けに、超限自然数を用いた不完全性定理の証明イメージを、感性的に表現します 。

  無限に続く図書館の謎
  あるところに、自然数のすべてを収めた「無限図書館」がありました。この図書館は、あらゆる数学の真実が書かれた本で埋め尽くされています。私たちは、この図書館の書物だけを使って、数学のあらゆる真実を証明できると信じていました。 しかし、ゲーデルという名の司書は、ある不思議な本を発見しました。それは、「この図書館にあるどの本を使っても、この本の真実を証明することはできない」と書かれた本です。

  
  

  この本を「G」と呼びましょう。もし「G」が本物の書物なら、その内容は真実でありながら、図書館のルール（証明体系）の中では証明できないことになります。つまり、図書館には証明できない真実がある、ということです。 もし「G」が嘘の書物だとすると、その内容は嘘であるのに、図書館のルールで証明できることになってしまいます。それは図書館の無矛盾性を壊してしまうので、私たちはその可能性を認めません。

  そこでゲーデルは、自然数の果てにある超限自然数たちの助けを借りました。彼は、図書館の本を自然数で番号付けし、無限に続く超限自然数で、さらに高度な図書館を想像しました。超限自然数たちは、無限の彼方から、無限図書館の限界をはっきりと示しました。それは、どれだけ多くの本（証明）を集めても、すべての真実を網羅することはできない、という無限の視点からの証明だったのです。 私たちは、無限の彼方からやってきた超限自然数というメッセンジャーによって、「無限図書館」が完全ではないという真実を知ることになりました。それは、数学の限界を告げる、静かで、しかし、決定的な物語なのです。

  うん，読み物としては良いと思うのですが，これ全体で画像生成しても面白い絵ができません．最後の，段落だけで生成した絵をおいておきます．

  

  

  目次に戻る