2015年11月23日

巨大基数とは何か(2)


前回の記事では、弱到達不能基数と強到達不能基数の定義をして、これは巨大基数の例であると言いました。そして巨大基数とは「ZFCでその存在が示せないほど」大きな基数を指すと言いました。この意味するところについて説明します。前回と同様、この記事においてはすべての結果がZFCからの帰結です。ですから、定理で単に「示される」といえばZFCから帰結されることを意味します。まず1930年にゲーデルによって示された不完全性定理によって次が成り立つことを断っておきましょう。

定理1. ZFCが無矛盾ならば、ZFCから証明も反証もできないような命題が存在する。特にZFC自身の無矛盾性はZFCからは証明することができない。実は同様のことがZFCについてだけでなくZFやその拡大についても成り立つ。

以降しばしば「ZFCが無矛盾ならば」という仮定をしなくてはなりません。ZFCが無矛盾であることは、定理1によりフォーマルには証明できないにしても、これまでの歴史や諸結果によってかなり保証されているので、この仮定は単なる枕詞だと思ってくれてかまいません。また、以降ある公理系Tが無矛盾であることを表す文をCon($T$)と書くことにします。弱(強)到達不能基数と無矛盾性に関しては次が示されます。

定理2. Con(ZFC)$\to$Con(ZFC+弱(強)到達不能基数が存在しない)
系. ZFCが無矛盾ならば、弱(強)到達不能基数の存在を示すことはできない。

巨大基数という言葉はフォーマルな定義を伴ったものではなくて、この系で主張しているような意味でZFCでは存在を示せないほど大きい基数のことを指しています。いままでにいろいろな巨大基数が考えられましたが、それらは全て弱(強)到達不能基数
になっているので、ZFCからその存在が証明できないことがわかります。ということで実は弱(強)到達不能基数というのは巨大基数のなかでも最小の部類なのです。

次に問題になるのは巨大基数の存在の無矛盾性は示すことができるのかということです。

定理3. 弱(強)到達不能基数が存在すれば、Con(ZFC)が示される。

定理1と3を使って次のような議論ができます。ZFCにおいてCon(ZFC)$\to$Con(ZFC+弱(強)到達不能基数の存在)が示されたとします。すると定理3から「ZFC+弱(強)到達不能基数の存在」という公理系においてCon(ZFC+弱(強)到達不能基数の存在)が示せたことになりますが、定理1より「ZFC+弱(強)到達不能基数の存在」は矛盾します。最初の仮定よりZFCも矛盾します。ゆえに次が言えました。

定理4. ZFCが無矛盾であるとする。このときCon(ZFC)$\to$Con(ZFC+弱(強)到達不能基数)は示せない。

つまり、巨大基数の存在が矛盾しないことを確かめるのはあきらめなくてはなりません。

以上をまとめましょう。ZFCが無矛盾だとすれば、
・「ZFC+巨大基数が存在しない」は無矛盾なので、巨大基数の存在はZFCから示すことができない。というよりそういうものを巨大基数という。
・「ZFC+巨大基数の存在」が無矛盾であることはZFCから示せない。

この結果だけみれば巨大基数は存在すらあやしく考える意味が分からないかもしれませんが、実際のところ現代集合論では巨大基数の理論は必須です。その理由はまた次回。
続きを読む


ラベル:集合論
posted by Eureka GAP at 17:18| 数学 | このブログの読者になる | 更新情報をチェックする

2015年11月16日

巨大基数とは何か(1)

ブログに数式を挿入できるようになって俄然ブログ記事を書くやる気がわいてきました。ということで、何回かに分けて巨大基数とはなんぞやという話をしてみようと思います。

まずは巨大基数の例を見ることにします。順序数と基数の一般論をここで展開するのは大変すぎるので省略することにしますが少し復習します。以降はZFCにおいて議論します。特に選択公理は断りなく使います。

可算基数は$\omega$または$\aleph_0$で表します。最小の不可算基数は$\aleph_1$、次に大きな基数は$\aleph_2$というように無限基数は順序数によって小さい順に並べることができます。つまり、無限基数は$\aleph_0,\aleph_1,\ldots,\aleph_{\omega},\aleph_{\omega+1},\ldots$というようにリストアップされるわけです。後続基数とは$\aleph_1,\aleph_2,\aleph_{\omega+1}$のようにある基数の次に大きなものとなっている基数を指します。また、そうでない不可算基数を極限基数といいます。例えば$\aleph_{\omega}$がそうです(ここで$\omega$は極限基数に含めないことに注意)。

次に正則という概念を定義します。$\kappa$を基数、$\alpha<\kappa$を順序数として、写像$f:\alpha\to\kappa$を考えます。$f$が共終であるとは$f$の値域が$\kappa$内で非有界であること、すなわち$\forall\beta<\kappa\exists\gamma<\alpha(\beta<f(\gamma))$であることとします。そして基数$\kappa$が正則であるとは、ある順序数$\alpha<\kappa$と共終写像$f:\alpha\to\kappa$が存在しないことだと定めます。また、正則でない基数を特異基数と定義します。簡単な議論によって、$\kappa$が正則であることと$\kappa$が濃度が$\kappa$未満である集合の$\kappa$未満個の和集合で表せないことは同値だとわかるので、この同値な言い換えを用いると、可算集合の可算和は可算集合であることから$\aleph_1$は正則であることが示せます。同様の議論によって後続基数はすべて正則であることが示せます。一方、$\aleph_{\omega}$は特異基数です。なぜなら$f:\omega\to\aleph_{\omega}$を$f(n)=\aleph_n$で定めると、$f$は共終写像になっているからです。結局正則というのはある意味「下から追いつけない」という性質だと思えます。

では、正則であるような極限基数は存在するのでしょうか?もし存在するなら、そのような基数$\aleph_{\alpha}$は少なくとも$\alpha=\aleph_\alpha$を満たさなくてはならないことが先の$\aleph_{\omega}$についての議論と同様にしてわかります。$\alpha=\aleph_\alpha$という条件を満たす基数の例として$\omega,\aleph_{\omega},\aleph_{\aleph_{\omega}},\ldots$の極限が挙げられますが、明らかにこれは正則ではありません。こう考えると正則極限基数は非常に大きな基数であることが予想されます。ここで次のように定義します。

定義. 正則極限基数のことを弱到達不能基数(weakly inaccesible cadinal)という。さらに、正則かつ強極限、すなわち$\kappa$未満の任意の基数$\lambda$に対して$2^{\lambda}<\kappa$となるような不可算基数$\kappa$のことを強到達基数(strongly inaccessible cardinal)という。

ここで強到達不能基数はつねに弱到達不能基数であることは明らかです。そしてこれらの基数こそが「巨大基数」の例になっています。

確かに弱・強到達不能基数は(もし存在するなら)非常に大きな基数であろうと予想できますが、何をもって巨大と言っているのでしょうか?具体的に基準が定まっていてそれより大きな基数を巨大と言っているのでしょうか?実はそうではなくて、「ZFCでその存在が証明できないほど」大きな基数が「巨大基数」とよばれるのです。次回はこの意味するところについて説明します。

(続く)
続きを読む
ラベル:集合論
posted by Eureka GAP at 12:42| 数学 | このブログの読者になる | 更新情報をチェックする

2014年12月24日

決定不能問題


12月23日の都数1年クリスマスゼミにおいて「決定不能問題」というタイトルで発表をしました.

以下がそのアブストラクト:

『今回の発表のテーマは決定不能問題(undecidable problem)です.決定不能問題とはそれを解くための機械的なアルゴリズムが存在しない問題のことです.しかし,そもそもアルゴリズムが存在するということを数学的にどう定式化するのでしょうか?さらに,アルゴリズムが存在しないということはどう証明できるのでしょうか?プログラムの停止性問題をはじめとした決定不能問題の証明を目標として,再帰理論の基礎の基礎を紹介したいと思います.』

こういった再帰理論(計算理論)の基礎的な話を知ったのは9月ぐらいのことで,そこで用いられている定義や証明のアイデアがとても面白いと感じました.今回はその面白さを伝えようと思って発表したのですが,2時間にしてはかなりてんこ盛りの内容になってしまいました(これでも削ったのに).発表って大変ですね……

当日の配布資料(≠発表内容)がこちらです.ページ数の都合など色々と考えた挙句これといって特徴のない無難なものになってしまったのが不満なので,今度もう少し好き勝手に書いてみてもいいかもしれません.

unsolvable_resume.pdf
ラベル:PDF 再帰理論
posted by Eureka GAP at 22:02| 数学 | このブログの読者になる | 更新情報をチェックする
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。