とりマセ

■[数学基礎論] ゲーデルの不完全性定理を代数学を使って表現してみた

　

　『代数学は得意だけど，数学基礎論とかさっぱり分からない．論理とかマジイミフ』

そんなアナタを対象に，ゲーデルの不完全性定理を解説してみよう！　のコーナーです．

　

　

論理学と代数学（可換環論）との対応については，檜山さんによる素晴らしい記事があります：

　古典論理は可換環論なんだよ - 檜山正幸のキマイラ飼育記

　

ただ，『論理学といえばまずコレ！』とも言うべき『ゲーデルの不完全性定理』の代数学的表現については書かれていないようなので，

ちょっぴり魔が差して，ここでゲーデルの不完全性定理の代数学的な表現を与えることにしました．

　

だが，単にゲーデルの不完全性定理を代数学で表現するだけじゃあつまらない……倍プッシュだ……！

というわけで，プラスアルファとして，その他色んな分野との関わりを含めて紹介します．

　

　

0. 理論は対応する代数を持つよ！： リンデンバウム代数

　

まず，論理学と代数学を対応させる第一の架け橋は，リンデンバウム代数 (Lindenbaum algebra) と呼ばれるものです．

　

論理学を学んだ人には常識なのだけれど，一般にはあまり知られてない，それがリンデンバウム代数！

この概念に初めて出会ったときは非常に衝撃的で，なおかつ面白い代物なので，せっかくの機会なので，ここでしっかり解説します．

　

理論 のリンデンバウム代数 というのは，文というものに順序構造を入れたものです．

順序の入れ方は単純で，もし理論 で を証明できるならば にしよう，というものです．

　

そして， と の順序が等しい，すなわち理論 で が証明できるんだとしたら， と を同一視してしまいます．

　

これがリンデンバウム代数です．簡単ですね！

　

　

しかし，これだけだと「だから何？」って感じなので，もうちょい詳しく見てみましょう．

　

で無条件に証明可能な文 は，この順序で一番下に来ます．

逆に， で を証明できるとき， はこの順序の頂点に来ます．

　

大雑把な言い方ですが，偽に近い文ほど順位が上で，真に近い文ほど順位が下という感じですね．

　

　

肯定を証明できる文は一番下，否定を証明できる文は一番上に来るので，中間に来ることが出来るのは独立命題だけです．

　

したがって，もし理論 のリンデンバウム代数が 点しか無いならば，

はありとあらゆる文について，肯定か否定を証明できるということです．

言い換えれば，理論 は完全ってことですね！

　

逆に，不完全な理論のリンデンバウム代数は 点以上の元を持ちます．

　

　

具体例として，ZFC集合論のリンデンバウム代数を見てみましょうか．

たとえば，

　　: 連続体仮説

　　: 到達不可能基数の存在

　　: ZFCの無矛盾性

は ZFCでは証明できないので，ZFCのリンデンバウム代数の一番下の順序でないことは確かです．

　

さらに，ZFCが無矛盾であるという仮定の下で，次が成立します：

　

　

　

しかし，リンデンバウム代数の何処が代数なんだよ！　とお思いかもしれません．

でも，リンデンバウム代数には自然に束構造が入り，

事実，もし古典論理上の理論を考えているならば，そのリンデンバウム代数にはブール代数の構造が入り，

直観主義論理上の理論を考えているならば，そのリンデンバウム代数にはハイティング代数の構造が入ります．

（後々の都合上，順序の入れ方を反転しているので，正確にはブラウワー代数と言うべきかもしれない）

　

0. のまとめ

　

理論	リンデンバウム代数
が矛盾
が完全
が不完全
古典論理	ブール代数
直観主義論理	ブラウワー代数

　

ここまで読んで何のことやらさっぱり分からなかった人へ：

　

今回扱うのは，古典述語論理のリンデンバウム代数 なので，ただの自由ブール代数です．

以後，リンデンバウム代数という言葉が出てきたら，

　 「ああ、ブール代数のことね．知ってる知ってる」

と読み進めましょう！

　

とにかく，「論理とか理論には，こういう風に何かしらの代数が対応するんだ」っつーことです！

　

1. 論理学の概念を代数学を使って書こう！

　

を，一階古典述語論理の（固定した言語上の）リンデンバウム代数とします．

このとき，古典述語論理上のどんな理論のリンデンバウム代数 についても，あるイデアル が存在して， と表されます．

実際に，理論に対し，一意にこのようなイデアルが定まります．

　

したがって，ここでは，『理論ってのはイデアルのことなんだよ！』と思っても差し支えは無いでしょう．

　

ただ，実際には，イデアルは公理系の演繹閉包，つまり，公理系が生み出す定理全体がイデアルをなすと考えた方が自然かもしれません．

この観点の下では，理論とは の部分集合です．

そして，理論 に対して， が生成するイデアル こそが が生み出す定理全体です．

このとき，理論 のリンデンバウム代数とは，つまり剰余代数 のことですね．

　

注意点として，理論 が素イデアルを生成するとき， となります．

したがって，このような理論 は完全な理論を表すものとして考えられます．

　

また， のときは，リンデンバウム代数が のように潰れ，これは が全ての文を定理とする，つまり， が矛盾しているっちゅーことですね！

　

　

さて， の部分集合が理論を表すならば，

　再帰的公理化可能理論（何が公理であって何が公理でないかを機械的に判定できる理論）

とは，どのような集合なのでしょうか．

　

実は，それは，再帰的可算イデアルを生成するような集合です！　

再帰的可算（帰納的可算）とは，いわゆる複雑性クラス RE のことです．

　

事実，先ほどの は再帰的可算自由ブール代数となり，一階古典述語論理上の公理化可能理論のリンデンバウム代数は， を再帰的可算イデアルで割った剰余代数として表現できます．

　

　

さらに，もし理論 に対して， が生成するイデアル が計算可能であれば，それは決定可能な理論を表します．

たとえば， を実閉体の理論を表すものとすれば，これは完全かつ決定可能なので， は計算可能な素イデアルであり， となります．

　

　

では，まずはこの観点の下で，不完全性定理を表現してみましょう．

理論とは の部分集合だったので，（ロビンソン）算術に対応する の部分集合が存在するはずです．

それを と書くことにしましょう．

　

このとき，ゲーデルの第一不完全性定理は次のようにして表現されます．

　

ゲーデルの不完全性定理

を含む再帰的可算素イデアル は存在しない．

　

1. のまとめ

　

論理	代数
理論	部分集合
の定理	の生成するイデアル
が完全	が素イデアル
が矛盾
が公理化可能	が再帰的可算
が決定可能	が計算可能

　

2. ストーン双対からの眺め： スペクトルとザリスキ位相

　

しかし，再帰理論や記述集合論などでは，このストーン双対の下での対応物の方に，多くの研究がなされてきました．

なので，これを更に別の観点から見てみましょう．

　

は可換環として表現できるので，そのスペクトル （つまり， の素イデアル全体の集合）を考えることにします．

には，ザリスキ位相と呼ばれる位相が入れられます．

これは，各イデアル に対して， を閉集合とするような，閉集合系から定まる位相です．

　

この観点では，閉集合と理論が同一視されます．

これは何故かというと，任意の理論 について， のリンデンバウム代数 のスペクトル と が位相同型だからです．

つまり，理論とイデアルが同一視できて，イデアルと閉集合の間に一対一対応があるので，理論と閉集合を同一視することができるんです．

　

さらに，理論 に対応する閉集合 は， の完全化全体を表します．

同時に，これを のモデル空間ともみなすことができます．

つまり， のモデル全体 を構造の基本同値性 で割った空間 が， ないし に対応します．

　

完全性定理（ゲーデル）

任意の について， が生成するイデアル が を満たすならば， である．

　

もし，閉集合 が，ある再帰的可算イデアル に対して の形となるならば，それは実効的閉集合(effectively closed set)と呼ばれます．

この実効的閉集合という概念を用いて，ゲーデルの不完全性定理は次のように表現できます．

　

ゲーデルの不完全性定理

任意の実効的閉集合 について， が成立する．

　

さて，この完全性定理と不完全性定理が示唆することは何でしょう．

先ほどぼそっと書きましたが，各点 は実は を含む完全な理論となっています．

を取れば，点 は算術を含む（無矛盾かつ）完全な理論です．

　

しかし，点 は再帰的公理化可能でないので，これはゲーデルの不完全性定理に反するものではありません．

事実， が再帰的公理化可能でないなら， は の素イデアルですが再帰的可算ではないです．

したがって， かつ は成り立つし は閉集合だけど，実効的閉集合ではありません．

　

2. のまとめ

　

論理	代数	（ストーン双対）
理論	部分集合
の定理	の生成するイデアル	の閉集合
が完全	が素イデアル
が矛盾
が公理化可能	が再帰的可算	が の実効的閉集合
が決定可能	が計算可能
が本質的決定可能	を含む計算可能イデアルが存在	計算可能な点 が存在
が本質的完全	を含む素イデアルが存在	なる実効的閉集合 が存在

　

ノート：

理論のリンデンバウム代数と準同型の圏と，そのスペクトルの空間と連続写像の圏の双対性は，いわゆるストーン双対と呼ばれる，1936年のストーンによるものが原点だと思います．

ただし，当時は可換環のスペクトルというものは導入されていなかったので，実際のストーン双対性は，こことは異なる用語で記述されます．

　

また，ストーン双対の公理化可能バージョン，すなわち，

　公理化可能理論のリンデンバウム代数と再帰的準同型の圏と，そのスペクトルの空間と再帰的連続写像の圏の双対性

に最初に言及したのは，おそらく1983年のウィリアム・ハンフ (William P. Hanf) とデイル・マイヤーズ (Dale Myers) だと思います．

　

ただし，その双対性は既に『みんな知っていたが，誰もちゃんと証明を書いてなかった』的なポジションであったと思われます．

　

事実，1961年にエーレンフォイヒト (Ehrenfeuht) がそれっぽいことを証明していますし，

1970年代前半のジョカシュ (Jockusch) とソーア (Soare) の一連の研究は，この双対性を知っていたからこそでしょう．たぶん．

　

3. スペクトルの空間： 記述集合論，再帰理論，位相と測度

　

さて，単に を見るのではなく，そのスペクトルの空間を観察する有難みを少しだけ見ていきましょう．

もちろん，最大の有難みは，スペクトルの空間には位相が入っているので，位相空間論の道具が色々と適用できる，というものがあります．

更には，実は， よりもう少し一般の位相空間についての閉集合や実効的閉集合は，ここで述べたような背景の内からも外からも深く研究されていた，ということが大きいです．

　

再帰的可算自由ブール代数 のスペクトルの空間 はカントール空間と同相になります．

カントール空間（一般に，ポーランド空間）の閉集合は，記述集合論においては，位相空間のボレル階層の第 ランク，太字 集合(boldface set)として研究されてきたものであり，

実効的閉集合は，細字 集合(lightface set)として研究されてきたものです．

　

細字 集合，すなわち公理化可能理論 に対応する実効的閉集合に関しては，

たとえば，ペアノ算術 PA のスペクトルに対応する概念であるPA次数，クライゼルの反基底定理，ジョカシュ-ソーアの低基底定理(low basis theorem)が有名です．

これらの定理は，ここで述べた背景の延長上にあるものにも関わらず，ゲーデルの不完全性定理とかとはあまり関係の無い様々な分野（逆数学，アルゴリズム的ランダム性，計算可能性解析学など）で応用されています．

　

さらに，理論 のスペクトル の位相的性質，たとえば，孤立点に関する性質（カントール-ベンディクソン・ランクなど）が のモデル理論性質と対応しているらしいですよ！

実際，モデル理論ではタイプの空間としてストーン空間をよく用いるし，モデル理論とスペクトルとの相性は非常に良いんだと思います．

でも，詳細については知らないので，省略します！

　

他には，マーティン/プール-エルの極大理論 というものを次の位相的性質によって特徴付けることができます．

　『 は孤立点を持たず，任意の実効的閉部分集合 に対して，

　　ある開かつ閉な集合 が存在して， が成立する』

　

　

また，このスペクトルの空間には自然に測度が入るので，測度論の方面からの研究も可能にします．

たとえば，理論 について，

　もし の測度 ならば，任意のマルティン-レーフ・ランダム実数 について，

　 を有限桁シフトしたもの が， を満たす

という定理があります．

　

これは何を意味しているかというと，実数を二進小数展開したとき，

　小数点以下 桁目が であれば， 番目の文は証明可能，

　小数点以下 桁目が であれば， 番目の文は証明不可能

と解釈することにより，実数を理論とみなすことができます．

　

このとき，

　『どんなランダム実数も高々有限桁シフトするだけで， を含むある無矛盾完全理論を表すよ！』

というビックリ定理なわけです．

　

ただし，ペアノ算術 PA や ZFC 集合論などは，残念ながら となるので，この定理は適用できません．

　

4. 拡大理論と部分理論の束構造

　

この観点の下で，ある公理化可能理論にどのような拡大が存在し得るか，どのような部分理論が存在し得るか，というのをスペクトルの空間の実効的閉集合の束構造から調べることができます．

　

定義：

を の実効的閉集合全体の集合とする．

（あるいは， としても，同等の定義を得る．）

　

には，集合演算により自然に束構造が入ります．（ただし，ブール代数にはならないことに注意）

公理化可能理論 の拡大理論の束とは， の区間 を指し， の部分理論の束とは， の区間 を指します．

　

を用いると，ゲーデルの不完全性定理は次のように表現できます．

　

ゲーデルの不完全性定理

任意の に対して，もし ならば， .

　

は再帰理論において，そこそこ研究されていて，特に面白い定理は，

　　部分理論の束 が本質的に パターンしか無い

というものです．

　

しかも，その一方の同型タイプは，有限生成の差で割ることによって，再帰理論が何十年と掛けて深く研究してきたとある構造と同型になる，

という2007年にレベッカ・ウェーバーが証明した定理があるのですが，長くなるので，これについては機会があればいつか紹介するかもしれません．

Permalink | コメント(4) | トラックバック(4)