レーベンハイム・スコーレムの定理までの大急ぎのまとめ
(Rapid Summary from Syntax of Logic to Löwenheim-Skolem Theorem)
某勉強会で今年(2018年)の10月に
その解説の中で
レーベンハイム・スコーレムの定理(レーベンハイム発表 1915年,スコーレムによる厳密な証明 1920年)は,一階の記号論理体系(一階述語論理)の
19世紀の終わりから20世紀にかけて,数学の 世界では,数学的な推論過程の正しさを確信するために,それ自身を数学的対象として研究 する必要に駆られていた.その枠組みが下記のようなものである.図の左側は,数学での言葉と 推論過程の枠組みで Syntax の世界と言われる.ここでは,数学で使う表現の道具立て( 定数,関数,述語などの記号)を用意し,その上に色々な命題を書けるようにする.それらの 命題の一部分を公理として,それからある規則を適用し「正しい」命題を導出していくのが 数学の推論であるとするのである.
この Syntax の世界は記号とその操作の世界である.それに対して,図の右側は,
その記号が表す実体と操作の意味を定める世界で Semantics の世界と呼ばれている.
左側の Syntax の世界で提供された
レーベンハイム・スコーレムの定理は,このときの記号を解釈するための「実体の集合 M」の 大きさに関する命題である.より詳しく言うと, 記号論理の体系がモデルを持つと 分かったとき,そのモデルを非常に巨大な大きさにしたり,またはその逆に, 非常に小さくしたりできると いう定理である.
上でも述べたように,記号論理のある公理の集合Aがモデルを持つ,つまり,その公理集合を満たす数学的な実例が あるということは,その公理集合が無矛盾であるとみなせることを意味する.
レーベンハイム・スコーレムの定理でモデルを 小さくするときは,自然数の集合のサイズ(可算無限 ℵ0)まで小さくできる.
我々は,自然数の集合サイズの集合については 直観もけっこう働くし,また,ノウハウも 溜まっている.したがって, ある公理系Aにモデルがあるときは レーベンハイム・スコーレムの定理で 自然数の集合レベルのサイズのモデルまで 小さくして,扱いやすくして, 加工することで別の公理系A’のモデルを 作るということができる. 10月の勉強会での連続体仮説の独立性証明も この方法を使う予定である.
ということで,(私が)レーベンハイム・スコーレムの定理を手短に説明しなければ ならないという動機が出てきたのである.
上で非常に簡単に述べたように,この定理を説明しようと思うと,一階の記号論理の体系(の Syntax)とモデルの説明をしなければならない.ここでは,次の3つ
まず,記号論理の体系とそのモデルについて説明する.
いきなり細部の定義からはじめると分からなくなりそうなので,概要を話して, 次に詳細なイメージについて記述する.
もともと,これは,19世紀の終わりから20世紀の初めにかけて,集合論が 現れ,カントールのパラドックス,ラッセルのパラドックスなど数々のパラドックスが 発見され,人々が自分たちのロジックに疑いを持ち始めたことから始まる. つまり,それらのパラドックスが集合論のせいなのか,もしかしたら, そもそも我々の数学的推論自身に欠陥があるものなのか自信がなくなってきた のである.
ということで,記号論理学のそのころの目的の一つとして,数学で我々が行っている 数学的推論をきちんと書き出し,それが正しいことを証明することだった.
その枠組みが次の図(冒頭の Syntax & Semantics の絵をもう少し詳細に書いたもの)のようなものである.
図の左側(Syntax と書かれている側)が, 我々の数学的推論を記述しようとする体系である.ここでは下半分の 「数学的推論のメカニズム」というところに書かれているように,まず, 公理の集合を定めて,三段論法などの数学的推論を何段階か続けて,定理に 至るという我々が数学で通常行っているプロセスを記述したいという欲求がある. このための前提として 左上の方に書かれているような,ものや関数の記号,関係を表す記号などを 定め,0 とか 0+1 とか 空集合 ∅ などの数学的対象の記述,また,それを使った 0+1 ≤ 0 などの命題を記述する仕掛けを作る.この道具立てとして導入した関数記号や 述語記号の集合をシグニチャと呼ぶ.ここではσというシグニチャが導入されたとする. 公理や定理はシグニチャσが与えられたとき,その上に作られた 命題の集合の部分集合になる.
こうして命題の集合が厳密に定められ,そのうちのいくつかが公理として設定され,そこから あらかじめ決められた推論ルールを何度も適用しながら,定理となるべき 命題を証明していく.
こういう我々が数学で行っているらしいプロセスを記述する ことはできたが,今度はこれが真理にたどり着く正しい方法だろうかという判断方法が 必要になってくる.それを判断するのが,図右側の部分(Semantics と書かれた部分)である.
左側で命題と言っているものは,あくまで,単に文字列である.推論規則は文字列の 集合から新たな文字列を作り出す規則である.例えば,1+1+0 と書いてあれば,これは イチ,プラス,イチ,プラス,ゼロという文字列であって,2 を表しているという 意味付けはここではまだ無い.もちろん,公理系をうまく選んでやれば, 0+1+1=1+0+1, 1+0+1=1+1+0, 1+1+0=2 などの等式はこの記号論理の体系で証明できる だろう.しかし,これはこの記号論理の中のいくつかの記号列がお互いに等号で結ばれる 関係になっているということを表すに過ぎず,これが我々の意図と同じということは 言えない.したがって,我々がこの記号論理の体系に込めた意図を表す仕掛けが 必要になって来る.図の右側の仕掛けはそのために左側の文字列に数学的な意味を 与えるためのものである.
右側の一番基本的な部分は
大急ぎで概念説明を進めてきたので,未消化だったり,疑問を持たれる方も多いと 思う.例えば,私は最初にこの定式化を勉強した時,次のような疑問を持った.
そもそも,我々の数学的推論のプロセスが正しいかどうかを検証するために このような記号論理の体系を作ったのではないか? では,右側のモデルに 翻訳された個々の命題の真偽はどのようにして判断するのか? これは,もしかしたら,間違っているかもしれないと疑っている, 普通の数学的推論で判定するのではないか? これは本当に我々の 数学的推論の検証になっているのか? 議論がサイクルになっているのでは ないか?
結論から言うと右側での命題の正しさの判定は普通の数学的推論で行う.「十分注意しながら」 という但し書きが付くとは思うが.
この状況をある人はサイクルでないという.私はサイクルだと思う.ただし, 「十分注意しながら」だし,一度,我々の推論がどんなものがきちんと書き下して あるので,このサイクルも意味のあるサイクルなのじゃないかなと感じている.
サイクルかそうでないのかを議論しはじめると,たぶん,サイクルとはなにか, どうなればサイクルなしで説明したことになるのか,など実りの多い議論になるとは 思うが,私は疲れるので,上の,「一度数学的推論」を机の上において眺めたという 実績を評価して,この枠組みを使わせてもらうことにしている.
前節で,記号論理とそのモデルのおよそのところは話した.ここでは,このページの 本題であるレーベンハイム・スコーレムの定理を説明できる程度に 記号論理とモデルの詳細に入る.
レーベンハイム・スコーレムの定理はモデルの 大きさに言及する定理である.したがって,記号論理で指定できる「もの」がどれだけ 多いかということを無視しては成り立たない定理である.ここでは,主に,この部分, つまり,どのような記号とそれらの組み合わせで記号論理の中の命題ができているかを 中心に上での説明を詳細化して話す.
いままで左の世界を記号論理の体系と呼んでいた.また,時々,「一階の」記号論理と
いうように「一階の」という修飾子を付けたりしていた.多少,用語が乱れているが,
これから話す体系は
こういう記号論理の体系には,大きく
では,次の図を使って一階述語論理の体系とそのモデルについて説明する.
まず,左のシンタクスの世界から説明する.命題を記述するための基盤となる記号の集合 σ は 関数記号の集合と関係記号の集合の2つからなる.関係記号は述語記号とも言われる. モデルの大きさがどのくらいになるかは,σ に含まれる記号の多さに依存する.
関数記号も関係記号もそれがいくつの引数を取るかが予め決められているとする.通常, この数を関数記号の arity ,関係記号の arity という.arity は 0 でも良い.arity 0 の関数記号は引数を取らないである値を返す関数を表すので,これは定数と同一視される. 図の中で関数記号の中に点線で囲われた部分がそれを表している.
シンタクス側のもう一つの道具立ては,その下に書かれている変数記号の集合である.この
意図としては,命題の中で色々な元を取り得るものを表す.
関数記号の集合と変数記号の集合が決まると,「もの」を指し示す
「もの」を指し示す「項」の概念が定義出来たら,次は,それらの項がある関係にあるという 言明を定義することができる.つまり,t1, ..., tn を項とし,P を arity n の 関係記号とするとき,
を
さらに,α ∧ β は ¬(α ∨ β) の略,α → β は, ¬α ∨ β の略, ∃x.α は ¬(∀x.(¬α)) の略であるとしておく.
また,論理式に現れる変数についての用語として束縛変数,自由変数という用語を
定義しておく.論理式 ∀x.P や ∃x.P において,P の中で x は
以上で,一般的な言明を記述するための論理式を定義することができたので, つぎは,これを推論していく機構を定義する.
まず,公理という用語から定義する.その体系で選ばれた論理式を
シンタクス側の最後の道具立ては,推論ルールである.先に述べたように, ヒルベルト流の証明システムでは, この推論ルールを非常に少なるとるのが流儀みたいで,通常,次の2つが使われる.
シンタクスの世界での推論は上の二つの推論規則を公理や,すでにそれらの規則で 導かれた論理式に適用して,新た論理式を導くことを意味する.こうやって導かれた 論理式を定理と言う.
セマンティクスの世界は,上で定めたシンタクスの世界で作られた項を なにか「もの」に対応させ,論理式の真偽を解釈する機構である.
まず,シンタクスの世界で作られる項を解釈するための
次に,シンタクスの世界での関数記号 f の
M の上の関数への対応
これにより,再帰的に項を表す M を決定することができる.例えば,g(a, f(b)) に対しては,
となる.m(g(a, f(b))) = m(g)(m(a), m(f)(m(b))
述語記号 P については,M の上の関係
今述べた,M, m(f), m(P) がシンタクスの世界の解釈の基本になる.これをシグニチャーσの構造
という意味で,
σ-構造はが決まると,変数を含まない原子式の解釈ができるようになる.つまり, t1, ..., tn の項に変数が含まれないとき, P(t1, ..., tn) の 解釈を次のように定める.
これらをもとに自由変数を含まない論理式,つまり閉論理式 P に対しては次のように再帰的に真偽を決めていく.
以上で,閉論理式については,真偽が定められた.問題は,自由変数を含む論理式であるが, これは,
と言う方法で真偽を定める.要は,それらの自由変数には ∀ が掛かっているのと 同じである.その自由変数が M のどんな要素をとっても成立するとき,その論理式を真とし, それ以外の場合は偽とする
以上でシンタクスの世界で作られた論理式の解釈の方法を述べた.
次にシンタクスの世界で独自の
以上で,シンタクスの世界を解釈するセマンティクスの世界の機構について説明し終わった. こちらも導入した概念のまとめを作っておく.
ここでは,「ダウンワード・レーベンハイム・スコーレムの定理」 (あるいは可算レーベンハイム・スコーレムの定理)と呼ばれるものを説明する. 定理の内容は次の通りである.
シグニチャー σ が可算無限個の一階述語論理が,無限基数のモデルを持てば, 可算無限の基数のモデルも持つ.
ただし,変数記号の集合は可算無限個であるとする.
レーベンハイム・スコーレムの定理としては,もう一つ,アップワード・レーベンハイム・スコーレムの定理というものがあり,こちらはσの基数以上ならとんな基数 k のモデルも存在すると いうものである.
まず,定理の文章だけでは何を主張しているのか掴みにくいので,一番最初の単純な図に 戻って,この定理の言っていることを解釈してみよう.
つまり記号の集合σが可算無限個の述語論理がモデルを持てば,図右側に おける,その述語論理での項を解釈する集合 M も 可算無限個(基数 ℵ0)で済むということを意味する.
レーベンハイム・スコーレムの定理は,それが発表された当時(1915年, 1920年)は,
いま,記述しようとしている体系が集合論で,ZFC のような体系で記述されているとする. シグニチャは論理記号の = と ∈ だけである(記述を見やすくするために ∅ など, 「もの」を表す記号を加えても良いが,無くてもよい).このとき,右側の M は,ZFC の 理論体系で作られ得るすべての集合を含んだ集合である.レーベンハイム・スコーレムの定理は, この M が可算集合で十分であるというのである.
この帰結は,少し加工すると,
集合論 ZFC のモデルとして,すべての無限集合が可算集合であるモデルが存在するという形にできる.一方,左側の ZFC の公理からは,依然として,
集合 X から,すべての部分集合の集合 P(X) へは全単射は存在しないが証明できる.つまり,ZFC で定めた公理系からは非可算集合の存在が証明できて,一方, それを解釈するモデルとしては可算集合だけしかないモデルが存在するということである. 当初,これはパラドクスと捉えられていた.
(|X| < |P(X)|).従って,非可算集合 P(ω) が存在する(ωはすべての自然数の集合).
しかし,これは次のような解釈で,パラドクスでは無いということが分かってきた. つまり,「冪集合P(X) はもとの集合 X より真に大きい」という命題は,実は,
P(X) から X へは単射 (injection) が存在しないということを言っているのである.例えば,モデル M に次の図のような単射 g を 加えなければ,そのような状況になる.つまり,可算集合が集まって,それらの集合の 間の関数をモデルに加えるか加えないかで,それぞれの集合の大きさを演じるような モデルを作ることができるという訳である.
もちろん,関数個別に好き勝手にモデルに追加する/しないを決められるわけではない. 例えば,f1 : X →Y, f2 : Y→Z がモデルに入っていたら,関数 f2・f1 : X→Z は モデルに入っている必要がある.こういう制約を守りつつも,全部が可算無限集合で, 非可算無限を演じることができると言っている訳である.
参考までに,連続体仮説の解説のとき作成したこの状況を表す絵をのせておく.
連続体仮説およびその否定の ZFC 集合論からの独立性証明は,それぞれが
成り立つ/成り立たないような ZFC 集合論のモデルを作ることによってなされる.
これにはいろいろな証明方法があるようであるが,一つの方法として,
レーベンハイム・スコーレムの定理で保証される可算モデルを使う方法がある.
つまり,すべての無限集合が可算無限のモデルを持ってくれば,その間の単射として
何を加えるかで,それらの大小を決めることができる訳である.すべてが可算集合で
あるから,原理的には中への単射は作りたい放題である.都合のよい単射を加えて,
連続体仮説が成立する/しないモデルを作ればよい.もちろん,そうして作ったモデルが
実際に ZFC の公理系を満たすことを確認しなければならない.ここらあたりの保証が
この定理は単独で証明してある本もあるし,また,完全性定理(Kurt Gödel 1929年)の系という扱いの本も ある.実際,完全性定理の証明は,その体系が無矛盾であるとき,シグニチャ σから生成される 項の集合にある同値律を入れて,その商空間として作成される.したがって,基数 |σ| の モデルが得られるわけである.ここでは,たった今述べた第二完全性定理との関係で証明される ということをもう少し詳しく書いておく.直接の証明は,もしかしたら,元気がでていつか書くかもしれないが,当面は書かないと思う.
まず,完全性定理を書いておく.これは一階述語論理において,
を述べている定理である.
φ を論理式とするとき,
|- φ ⇔ |= φ
つまり,φが証明できるための必要十分条件はφがすべてのモデルで成立することである.
この定理には同値な別の述べ方(第2形)がある.
Σ を論理式の集合とするとき,
Σが無矛盾 ⇔ Σのモデルが存在する
つまり,Σから矛盾が証明されなければ,Σはモデルを持つ.また,逆にΣがモデルを 持てば,Σは無矛盾である(こちら側の含意はほぼ当たり前である).
レーベンハイム・スコーレムの定理は,こちらの完全性定理の第2形と関係が深い.
第2形完全性定理の <= の含意はほぼ当たり前で,もし,矛盾が証明されるならば, モデルを持つことはできない.証明が難しいのは => の含意で,
という命題である.この証明には,与えられたシグニチャσと論理式の集合Σから, 具体的にそのモデルを作ることによってモデルの存在を示している.その体系から矛盾が証明されないなら,その体系はモデルを持つ
次の図に完全性定理(第2形)とレーベンハイム・スコーレムの定理の関係を示す.
まず,前提として,シグニチャσは可算集合であるとする.シグニチャとは, その体系の項や述語を記述するための関数記号の集合と関係記号(述語記号)の集合 のことであった.関数記号には特に 0 引数の関数として定数記号も含まれる.
完全性定理(第2形)は赤く横長の四角で囲まれた部分であり,与えられた論理式の 集合Σが無矛盾ならΣのモデルが存在することを主張し,その逆にモデルがあれば Σは無矛盾であることも主張している.先にも述べたようにモデルがあれば無矛盾で ある(①)は自明である.難しいのは,Σが無矛盾であるときモデルがある(②)であるが, これは実際に,モデルを作成することにより証明される.それが③のラインである. ここで作るモデルは項モデルと呼ばれ,σの関数記号(含む定数記号)を組み合わせて,項の集合 Termσを 作成し,それを同値関係~Σ
t1 ~Σ t2 iff Σ |- t1 = t2
(つまりΣで t1 = t2 が証明できるとき,t1 と t2 は同値)
で商空間 Termσ/~Σ を取ったものである. 商空間 Termσ/~Σ は,項を作る元になった集合σが 可算集合であることから,可算集合になる. 実際は,この項モデルが∑のモデルになるためには,元のσと∑に次の条件が必要になる.
以上,論理式の集合Σにモデルがあれば,Σは無矛盾になり(①),Σが無矛盾なら Σはモデルを持つ(②)が,そのモデルは可算集合に取ることができる(③). この①と③の2つを合成すれば,図の右側に縦に青色で囲んだ命題になり,これが丁度,レーベンハイム・スコーレムの定理である.
当然のことながら証明は厳密にしなければならないのだが,レーベンハイム・スコーレムの 定理が成り立つ本質的な理由は,
ことによる.これは上の証明の中の Termσ/~Σ を 考えればわかる.有限,あるいは可算無限個の関数記号や述語記号から 作り出すことができる要素の総体は可算無限個である
ちなみに我々の自然言語も有限のアルファベットあるいはかななどからなるので, それらの言葉で直接指し示すことができる数学的概念も,高々可算無限個である. 我々が直接言葉で表すことができるものは結構少ないのだ. 2019.01.17 (木)
レーベンハイム・スコーレムの定理は一階述語論理で成立する定理である.二階以上では 成立しない(らしい).二階述語論理とは,関数や述語に限量子(∀, ∃)を 使うことができる記号論理である.一階述語論理では対象の要素に対してだけ限量子を 使うことが許されている.
一階述語論理でレーベンハイム・スコーレムの定理が成立するということは,一階述語論理では 無限集合の実際の大きさを論理式で限定できないことを意味する.もし,これが出来たとしたら, 自由にモデルの大きさを可算無限から任意の無限基数に変えられないはずである.これは 自然数論に関して考えると奇妙な帰結を得る.我々は,自然数の集合 N は可算無限個の 要素からなっていると思っているが,ZFC のモデルの中には自然数の集合 N が非可算無限集合であるものも存在するということである.しかし,数学的帰納法は成り立つので,ある述語 P(n) がすべての自然数で成り立つためには,P(0) と P(n) → P(n+1) を証明しさえすればよい. 本来我々が自然数と思っている 0, 1, 2, ... 以外の非可算無限個の要素は 0, 1, 2, ... と同時に P(n) を成立させてしまう.
一階述語論理では,レーベンハイム・スコーレムの定理が成立して,このような奇妙な 現象が起こるので,もしかしたら,一階述語論理では我々の数学は記述できないのでは ないだろうかという気がしてくる.そうすると二階以上の論理に期待してしまうが, 世の中を見渡したところ,二階以上の記号論理はまだそれほど整備されていない.私は 二階以上の数理論理学に関して包括的に書いてある成書は知らない.どちらかというと, 論文をたくさん集めることによってはじめて,二階数理論理学の姿が見えてくると いった状況のように思う.
二階数理論理学について私が聞きかじった部分だけを書くと,次のようになる.
Willard van Orman Quine(1908年6月25日 - 2000年12月25日)は1930 年代に 新基礎集合論(New Foundation) を提案したアメリカの数学者/哲学者である. New Foundation では,すべての集合の集合が(クラスではなく)集合である 集合論 NF である.これが無矛盾であるかどうかはまだわかっていない.これを 多少修正した NFU と呼ばれる集合論は ZFC が無矛盾ならこちらも 無矛盾であるという相対的無矛盾性を持つことが証明されている.
以上のような理由もあって,私はまだ二階以上の論理学について真面目に勉強していない. ただ,いくつか読もうと思っている資料は集めたので,以下,それを列挙しておく.
二階数理論理学の勉強用の私の積読(つんどく)
検索すれば PDF が見つかります(Wikipedia 以外).
- ETHAN JERZAK : "SECOND-ORDER LOGIC, OR: HOW I LEARNED TO STOP. WORRYING AND LOVE THE INCOMPLETENESS THEOREMS", 2009, pp1-22
- Marcus Rossberg : "First-Order Logic, Second-Order Logic, and Completeness", 2004, pp303-321
- J Väänänen : "Second order logic or set theory?", 2012, pp1-26
- Wikipedia の second-order logic
この定理をレーベンハイムが最初に発表したのが1915年であるから,これを書いて いる今(2018年9月29日),すでに 100年以上がたっている.この定理は, Gödel の完全性定理と非常に関係が深いのだが,完全性定理や不完全性定理ほど 有名ではないと思う.しかし,集合論における解釈はとても深遠である. なにしろ,言ってみれば,人間の思考は,可算無限の集合の世界で,それぞれの関係を 使って,可算無限でない集合があるように振舞っていれば,それを「本当の」 非可算無限と区別できないと言っているのである.
いま, 応用としての人工知能(AI)がもてはやされているが,時々は基礎に戻って, もうすこし,このような定理にも注意を向けて,人間の思考について再考することは 意味のあることではないだろうか.
同時に,語句の強調で使っていた赤のボールドがまぶしかったので, 少しくすんだ色にした.
集合,位相,論理など へ
圏論を勉強しよう へ
束論を勉強しよう へ
半群論を勉強しよう へ
ホームページトップ(Top of My Homepage)