2018年11月4日日曜日

ビジービーバーQ&A: 計算不可能の鳥瞰図

 昨今いかがお過ごしでしょうか。こちらは、ほんとビジーなので、無限に時間が欲しいと毎日天に祈っています。

 ビジーといえば、ところで、ビジービーバー関数と呼ばれる関数をご存知でしょうか。自然数上で定義された、大体こんなかんじの関数です。
\[BB(n)=1+\sum_{i=0}^{n}\lim_{s\to\infty}\psi(i,n,s).\]

 この $ \psi $ については、あとで説明しますが、 $ \psi $ は具体的な原始再帰関数で、 $ s\to\infty $ での極限はちゃんと収束します。なので、当然ながら、 $ BB $ も自然数上の well-defined な全域関数です。というか、仮に $ \psi $ が具体的に何かということを知らなくても、上に書いたような極限がしっかり収束するような自然数上の関数 $ \psi $ であれば何であろうとも、上の定義が well-defined な自然数上の全域関数を与えるということは(よほどラディカルな思想をお持ちでない限り)誰しも認めるところでしょう。まあつまりは、ビジービーバー関数とは、よくある標準的な数学的関数です。むしろ、具体的な原始再帰関数から作られている分、数学に出てくるほとんどの関数よりも遥かに地に足の着いた定義ですね。

 さて、そういうわけで今日は、計算不可能性に関する正しい勘を身につけよう、のコーナーです。

目次

  1. ビジービーバー関数とはなにか
  2. 急増加階層とゲーデルの夢
  3. 急増加階層におけるビジービーバー関数
  4. 無限の彼方へ
  5. ジャンプ、ハイパージャンプ、スーパージャンプ
  6. 無限ゲームの決定性
  7. 再帰的マーロ順序数を越えて
  8. 無限時間チューリングマシン
  9. 年表とまとめ


2018年6月15日金曜日

ハーフ・コーエン強制法と無限次元トポロジー

▼ ハーフ・コーエン実数問題

みなさん,ハーフは好きですか.ハーフという言葉で何を思い浮かべるでしょうか.

 はい,そうですね.ハーフといえばハーフ・コーエン実数ですね.

 さて,ハーフ・コーエン実数問題とはなんでしょうか.もちろん,コーエンとは,連続体仮説を解決したことで知られる数学者ポール・コーエン (Paul Cohen) です.この解決のために,ポール・コーエンは強制法 (forcing) と呼ばれる手法を編み出したわけですが,これを使って,たとえば $\mathrm{ZFC}$ のモデルに $\aleph_2$ 個の実数を付加した拡大を作ることによって, $2^{\aleph_0}=\aleph_2$ の無矛盾性(連続体仮説の否定の無矛盾性)などを示すことができます.
 さて,コーエン強制法は,数ある強制法のうちでも,最も簡単なもののひとつですが,この手の強制法は,基底モデルに(複数の)実数を付加する,という特徴を持ちます.こうやって,(コーエン強制法に対する)ジェネリック・フィルターから直接抽出される実数たちがコーエン実数 (Cohen real) です.より正確には,基底モデルにボレル・コードを持つ如何なる痩集合にも属さない実数のことを指すのが普通だと思われます.

 と,このような感じに,集合論やその周辺分野の主要な研究対象のひとつとして,このような様々な実数の分析があります.集合論の応用というと,アーベル群のホワイトヘッド予想の独立性やカルキン環の外部自己同型の存在の独立性といったような華やかな話題の方が興味のある方も多いでしょうけれど,華やかな話題の陰には地味な努力の積み重ねあり,ということで,今回は地味な話題にスポットライトを当てていこうと思います.

 そんなこんなで, 集合論の研究者デヴィッド・フレムリン (Devid Fremlin) は,尋ねました.
 「$1$ 回使っただけではコーエン実数を付加しないけれど, $2$ 回累積するとコーエン実数を付加する,ハーフ・コーエン強制法というものは存在するだろうか……?」

 この問題は長きに渡り未解決だったのですが,ついに昨年2014年,ジンドリック・ザプルタル (Jindrich Zapletal) による「次元論と強制法」と題された論文において,ハーフ・コーエン強制法の発見が発表されました.

さて,ザプルタルの《ハーフ・コーエン強制法》とは一体どのようなものなのでしょうか.彼が用いたものは,無限次元トポロジーにおいてヘンダーソン・コンパクト空間 (Henderson compactum) として知られる異常な空間です.この空間は遺伝的強無限次元空間とも呼ばれ,自身は無限次元コンパクト距離空間であるにもかかわらず,任意の(コンパクト)部分空間は零次元または無限次元である,つまり, $1$ 次元以上の有限次元部分空間は含まないという謎空間です.
■ ザプルタルの定理
$\mathbb{P}_I$ をヘンダーソン・コンパクト空間の有限次元コンパクト部分空間全体の生成する $\sigma$-イデアル $I$ から生成される強制法とする.この強制法 $\mathbb{P}_I$ は,《ハーフ・コーエン強制法》である.
ちょっと集合論の話になるけど,出てくるのは強制法くらいなもので,現代的な集合論のむずかしい話はまったく出てこないので,大丈夫です.

▼ 目次

  1. 集合論から:強制法といろいろな超越数
  2. 無限次元トポロジーから (1): 遺伝的無限次元空間とコホモロジー次元
  3. 無限次元トポロジーから (2): ロマン・ポルの弱無限次元空間
  4. 無限次元トポロジーから (3): 弱無限次元空間から被覆の性質 $C$ へ
  5. 数学基礎論から: ロマン・ポルの弱無限次元空間・再訪
  6. 集合論から:イデアル強制法と一対一オア定数性
  7. 集合論から (2): 零次元の強制法から無限次元の強制法へ