Lower bounds for tree(4) and tree(5)

H. Friedman's finite miniaturization of Kruskal's tree theorem

Hey, guys. You like large numbers, don't you?

Today's topic is about a huge number related to Kruskal's tree theorem in graph theory. This is an important theorem that leads to Nash-Williams' BQO theory, Robertson–Seymour's graph minor theorem, and so on.

Kruskal's tree theorem is, of course, a theorem about trees. A tree is a connected acyclic graph. A rooted tree is a tree with a distinguished vertex called a root. A rooted tree can be thought of as a lower semilattice. A sequence of rooted finite trees $T_1,T_2,\dots,T_\ell$ is called bad if there is no infimum-preserving injection from $T_i$ to $T_j$ whenever $i\lt j$.

Kruskal's tree theorem states that the length of a bad sequence of rooted finite trees must be finite.

Okay, that's good to know. It's finite. So, how large is this finite number? How long can a bad sequence be?

The answer is ... unimaginably large. A mathematical logician, Harvery Friedman, introduced the following number:

Definition. The number ${\bf tree}(n)$ is defined as the length of a longest bad sequence of rooted trees where the $i$th tree $T_i$ in this sequence has at most $n+i$ vertices.

Friedman found that this yields extraordinary huge numbers. For instance, it is known that:

${\bf tree}(3)$ is greater than $10000000000$.

And,

${\bf tree}(4)$ is greater than Graham's number.

Here, Graham's number is known as "the largest number ever used in a serious mathematical proof" which is published in the 1980 Guinness Book of World Records.

ビジービーバー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. 年表とまとめ

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

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

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

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

　さて，ハーフ・コーエン実数問題とはなんでしょうか．もちろん，コーエンとは，連続体仮説を解決したことで知られる数学者ポール・コーエン (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): 零次元の強制法から無限次元の強制法へ

ヴォート予想とは何か：寄り道だらけの偏った解説

▼ ヴォート予想

　仕事で疲れたとき．心が荒んでいるとき．そんなときには，可算構造の数を数えてみてはいかがでしょうか．

• 標数 $p$ の可算な代数閉体は，超越次数ごとにあるので，同型を除けば，可算無限個．
• $\mathbb{Q}$ 上の可算ベクトル空間は，次元ごとにあるので，同型を除けば，可算無限個．
• 終点を持たない稠密全順序で可算なものは，同型を除いて $\mathbb{Q}$ ただひとつしかない．
• 可算ランダムグラフは，同型を除いて，ラドー・グラフひとつしかない．
• 可算な実閉体の数は，ええと，同型を除いて連続体濃度個．

　どうですか．心は安らいできましたか．

　というわけで，本日は，次のような形の文章を考えてみましょう：

「可算ナントカは，同型を除いて，ちょうど $X$ 個存在する」

　上の例では，$X$ の部分は「ひとつ」か「可算」か「連続体濃度」でした．そうすると，ナントカの部分が 《普通》 な構造のクラスだったら，$X$ の部分に該当するものは，有限の数か，可算か，あるいは連続体濃度のいずれかしか出てこないんじゃないかという気分になってきます．

　ところで，みんなだいすき連続体仮説とは

「可算濃度と連続体濃度の真に中間となる無限は存在しない」

というものでした．実際，それを裏付けるかのように，19世紀末から20世紀初期にかけての連続体仮説を証明または反証せんとする数学者の試みの過程で得られた定理の多くが，「《良い》可算生成な集合の濃度は，高々可算か，さもなくば連続体濃度であって，中間的な濃度は決して現れない」という類のものでした．
　歴史を遡れば，そのような最初の定理は，1883年のカントールによるもので， $\mathbb{R}$ の閉集合は高々可算であるか連続体濃度を持つというものです．その後，1910年代には，ボレル集合がそのような性質を持つこと，さらには解析集合（標準ボレル空間の射影となる空間）がそのような性質を持つことが示されました．このように，20世紀最初期までには，具体的な記述を持つ《良い》集合に対する連続体仮説が次々に示されていったのです．

　さて，ここでは，《普通》というものを，可算言語の完全な一階理論のモデルとして記述できる構造のクラスということにしましょう．ヴォート予想 (Vaught conjecture) とは，1961年にロバート・ヴォート (Robert Lawson Vaught) によって提示された予想で，モデル理論における連続体仮説とでも言うべき，可算構造の数に関する未解決問題です．

■ ヴォート予想
可算言語の完全な一階理論の可算モデルの数は，高々可算個であるか，さもなくば連続体濃度である．

　ちなみにヴォート予想が最初に提示されたとするヴォートの原論文を眺めてみたところ，「既にたくさんの人がおなじ予想を提示しているっぽいけど，一応ここでも言及しとくね」みたいな感じのノリの文章がつづられていたので，最初にこの問題を予想したのが誰なのかは不明瞭なようです．

　ところで，「数理論理学の話はさっぱり分からん！」という人にもご朗報です．実は，この問題は，可算構造のなすポーランド空間へのロジック作用 (logic action) と呼ばれる無限対称群 $S_\infty$ の連続作用を考えることで，次の位相ヴォート予想と呼ばれる，群作用の軌道の数に関する問題に一般化されます．

■ 位相ヴォート予想
ポーランド位相群 $G$ がポーランド空間に連続に作用しているとき，任意の $G$-不変ボレル集合には，高々可算個の $G$-軌道しか存在しないか，または完全個の $G$-軌道が存在する^*1．

　というわけで，ヴォート予想から数理論理学っぽさが消えて，位相群の作用の問題となりました．数学基礎論は数学を数学によって研究する，とスローガン的にしばしば言われるものですが，公理系の可算モデルの個数の問題をただの位相群の問題にすり替えるこのスタイルは，まさにその良い具体例かもしれません．ちなみに，上の予想は，ポーランド位相群の標準ボレル空間へのボレル可測な作用に対する予想に変えても同値になります．
　ただ，位相ヴォート予想はモデル理論的ヴォート予想を少し一般化したものになっていて，一階公理化可能な可算構造のクラスだけではなく，可算無限論理 $\mathcal{L}_{\omega_1\omega}$ によって公理化可能な可算構造のクラスに対するヴォート予想を更に一般化したものです．ちなみに，一階公理化可能でないけれども $\mathcal{L}_{\omega_1\omega}$-公理化可能なものとして，たとえば，捩れアーベル群，有限生成群，アルキメデス体，連結グラフなどなどがあります．

　さて，1985年，ダニエル・ラスカー (Daniel Lascar) は「ヴォート予想に熱狂している人々がいるわけ」と題する論文において，その動機を次のように説明しています（意訳）

質問： 一体ぜんたい，なんだってあんたは，可算モデルの数なんかに興味があるんだい？ ――とくに，連続体仮説を仮定してしまえば，問題が完全に消滅してしまうってのに．
ラスカー： 答えはシンプルで，ぶっちゃけて言えば，おれは可算モデルの数にも，どんな濃度のモデルの数にも興味なんてないんだよね．説明はするつもりだけど，ちょっとテクニカルで，これは2つの名前に基づいている．スコットとモーレイだ．…（中略）…皆には，ヴォート予想が単なるモデルを数えるだけの問題なんかじゃないと納得してもらいたい．そうじゃなくて，可算言語のモデルの絶対的な不変量の存在に関する我々の直観を正確に数学の言葉で表現する方法なんだ．（後略）

　ラスカーの前半の文は，ヴォート予想の重要性は，それ自身ではなく，その解決のために幾多の重要なモデル論的概念が発掘されたことだと強調している様子です．
　一方，最後の一文は若干テクニカルで，ラスカーは可算濃度に限らない一般濃度の構造を考えており，構造の同型性が絶対的な概念でなく，強制法によるジェネリック拡大などによって揺れ動く不安定な概念であることを注意しています．そんな中でも，無限論理的同値性は，構造の同型性の絶対的閉包のような役割を持ち，ヴォート予想の研究の過程で発見された様々な概念，たとえばスコット階数といったものが，そのような状況にも関わらず絶対的な不変量になるとかいったそんな文脈での発言です．
　そんなこんなでラスカーは主にモデル理論の技術的発展を重視しており，一方で位相ヴォート予想については，あれは別の問題だとしてさほど重要視していなかったようです．

　ただ，ラスカーのこの発言から時代を経て，1990年代からの目まぐるしい急転回を経た現在から考えると，ヴォート予想の最大の副産物は，むしろ，位相ヴォート予想によってもたらされた面が大きいように思います．この位相群の作用に対する予想が，黎明期の不変量記述集合論 (invariant descriptive set theory) への研究者の流入を促し，記述集合論という分野自体の姿をすっかり変貌させてしまうほどの影響を与えました．その結果として，記述集合論は，関数解析，エルゴード理論，作用素環論などの様々な分野と結びついた研究へと変遷していったのだと個人的には思うのですが，とにかく良い予想は，解決されようがされまいが，人を惹きつけ，新しいアイデアの出現を促進し，分野の発展を導いていくのでした．

▼ 目次

1. モデル理論から：スコット階数とモーレーの定理
2. 記述集合論から：バージェスとシルバーの二分法
3. 作用素環論から：グリム-エフロス二分法
4. アーベル群論から：ウルム不変量
5. 位相ヴォート予想から連続モデル理論へ
6. 記述集合論から(2)：分類を分類する
7. 余談：分類を分類する（非可算構造の場合）
8. 計算理論から：軌道のボレル複雑性とチャーチ-クリーネの順序数
9. 計算理論から(2)：計算可能構造の同型判定問題
10. 計算理論から(3)：超算術的イズ計算可能
11. 集合論から：非可算モデルの数とスコット階数
12. おまけ： YouTube で観る国際数学者会議

それでは，ここから，ヴォート予想の解決のためにどんなアプローチがなされてきたかを見ていきましょう．