2015年6月14日日曜日

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

▼ ヴォート予想

 仕事で疲れたとき.心が荒んでいるとき.そんなときには,可算構造の数を数えてみてはいかがでしょうか.
  • 標数 $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 で観る国際数学者会議
それでは,ここから,ヴォート予想の解決のためにどんなアプローチがなされてきたかを見ていきましょう.

モデル理論から:スコット階数とモーレーの定理

 1970年,マイケル・モーレー (Michael D. Morley) は「可算モデルの数」と題する論文を発表しました.この論文の内容はヴォート予想に対する最初の特筆すべき仕事で,連続体仮説とは異なり「可算モデルの数」は有限,可算無限, $\aleph_1$, 連続体濃度のいずれかの値しか取らないというものでした.
■ モーレーの定理
$\mathcal{L}_{\omega_1\omega}$-公理化可能な理論の可算モデルの個数は,高々可算であるか,さもなくば $\aleph_1$ または連続体濃度のいずれかに限る.
 ちなみに現代的には,この定理の様々な拡張が知られていますが,モーレーの定理のオリジナルの証明には,単に可算モデルの個数を数えるという以上の情報があるので,証明のあらすじに少し触れておきます.
 まず,モーレーのアイデアは,モデルのタイプの数に注目することでした.一階論理であれば,タイプのなすストーン空間 (Stone space) のコンパクト性からいろいろと状況が簡単になります.より一般に,モーレーの手法は,無限論理 $\mathcal{L}_{\omega_1\omega}$ の可算断片におけるタイプの空間を標準ボレル空間として扱うことでした.

 この発想に基づいた簡単な記述集合論的分析と,非可算解析集合は連続体濃度を持つことを述べる1917年のニコライ・ルージン (Nikolai Luzin) の有名な定理を利用して,理論の可算モデルの個数が連続体濃度未満であれば,その理論がモーレーが散在型と呼ぶ性質を満たすことに着目しました.ここで,理論が散在 (scattered) とは,無限論理 $\mathcal{L}_{\omega_1\omega}$ の任意の可算断片 $A$ について,その理論のモデルで実現される $A$ での $n$-タイプの種類が高々可算であることとします.

 この観測の下でモーレーが用いた道具は,モデルのスコット階数 (Scott rank) と呼ばれる不変量です.これは1964年にデイナ・スコット (Dana Scott) が発見したモデルの不変量で,各可算構造は同型を除いて一つの $L_{\omega_1\omega}$-文で特徴付けられるのですが,凡そ,その文の複雑性がスコット階数になります.モーレーは,散々型理論とは,各可算順序数 $\beta$ に対して,スコット階数 $\beta$ 未満のモデルの数は高々可算個であるようなものに他ならないと気づきました.可算モデルのスコット階数は高々 $\aleph_1$ なので,散在型理論のモデルは高々 $\aleph_1$ 個しか存在しないことが導かれます.

 以上の証明の流れを簡単にまとめると,こんな感じです:
可算モデルの数が $2^{\aleph_0}$ 個未満 $\Rightarrow$ 散在型 $\Rightarrow$ 可算モデルの数は $\aleph_1$ 個以下
 さらに,モーレーの分析から分かる重要な帰結は,理論がヴォート予想の反例であるということは,散在型であり,かつ,どんな可算順序数よりもスコット階数が大きい可算モデルを持つことに他ならない,ということです.
 話を一階理論に戻しますと,モーレーの仕事の少し後,ドナルド・マーティン (Donald A. Martin) は,一階完全理論のモデルの数が連続体濃度より少ないのであれば,非同型な可算モデルは,それらが実現するタイプによって区別されるのではないかと予想しました.これは,その理論のスコット階数の上限が $\omega+\omega$ 以下であることを導くので,ヴォート予想よりも強い主張となります.

 さて,これらの議論から,タイプの数というものに着目するのが自然に思われます.モデル理論で,一階理論が $\omega$-安定 ($\omega$-stable) とは,任意の可算集合上の完全タイプが可算個であるようなもののことでした. $\omega$-安定理論というのは,代数閉体であるとか,標数 $0$ の微分閉体であるとか,そういうものです.
 このようなモデル理論的観点からの最初の大きな進展は,1984年に訪れました.その年,サハロン・シェラハ (Saharon Shelah) は $\omega$-安定理論についてヴォート予想が成り立つことを示したのです.その直後には, $\omega$-安定理論について,ヴォート予想だけでなく上述のマーティンの予想も成立することもまた示されました.その後,いくつかの限定されたモデル理論的条件の下でヴォート予想が証明されていき,たとえば1988年に証明されたものとしては,順序極小 (o-minimal) 理論の可算モデルの数は,連続体濃度個であるか,さもなくば,ある非負整数 $a,b$ についてちょうど $6^a3^b$ 個である,というようなことが知られているそうです.

 その後のモデル理論の大きな目標として,超安定 (superstable) 理論についてヴォート予想を示すという方向に向かいました.しかし,これについては現在に至っても,有限ランクの超安定理論といった,限定的な条件付きの結果しか得られていないようです.その他,具体的な代数構造に対するヴォート予想を順々に潰していくという方向性の地道な研究も多数あるようです.具体例としては,たとえば可算serial環上の加群の完全理論についてはヴォート予想が成り立つ,といったようなもののことです.その手の研究もそれはそれで興味深いのですが,ここでは割愛します.

 そんなわけでモデル理論的なアプローチで興味深い話は他にも色々あるのですが,この程度の紹介で留めておいて,ここから先は,モデル理論の外からのヴォート予想へのアプローチを見ていきましょう.

記述集合論から:バージェスとシルバーの二分法

 さて,モーレーの結果は記述集合論を援用するものでしたので,記述集合論の目線からヴォート予想を眺めていくのがよさそうです.最初に述べたように,可算構造のクラスの同型分類は,無限対称群 $S_\infty$ のロジック作用による軌道同値関係として表され,これを用いて,位相群に対するヴォート予想というものを考えることができたのでした.

 一般に,このような標準ボレル空間へのポーランド群の連続作用が誘導する軌道同値関係は,解析的になります.1978年にジョン・バージェス (John P. Burgess) は,一般の解析的同値関係について成り立つ二分法を発見しました.
■ バージェスの二分法
標準ボレル空間上の任意の解析同値関係は,高々 $\aleph_1$ 個または完全個の同値類を持つ.
 これはモーレーの定理を大幅に一般化する強力な二分法ですが,ヴォート予想に関しては,モーレーの定理以上の結果を導くことはできません.位相ヴォート予想に対する次の武器は,1980年に発表されたジャック・シルバー (Jack H. Silver) の二分法です.
■ シルバーの二分法
標準ボレル空間上の余解析同値関係(よって,特にボレル同値関係)の同値類の個数は高々可算であるか,さもなくば,完全個の同値類が存在する.
 結論として,もし群作用から誘導される軌道同値関係がボレルであれば,その群作用に対する位相ヴォート予想は成立することがわかります.しかし,残念ながら,ポーランド群作用の誘導する軌道同値関係は解析的であり,一般にボレルにはならず,その場合にはシルバーの二分法は無力です.
 ちなみに余談ですが,シルバーの論文が出版されたのは1980年となるものの,1970年代前半には既にこの二分法は証明されていたようで,実際はバージェスの二分法よりシルバーの二分法の方が先に証明されたものだそうです.

 ところで,シルバーの二分法の技術的な側面を振り返りますと,シルバーの証明は,強制法や絶対性などのメタ数学的手法を駆使した難解なものだったのですが,1976年に,レオ・ハーリントン (Leo A. Harrington) は,計算理論を応用したエレガントな別証明を与えます.ハーリントンの手法は,現在,ガンディ-ハーリントン位相 (Gandy-Harrington topology) として知られるもので,元々,アラン・チューリングの唯一の弟子,ロビン・ガンディ (Robin Gandy) によって,1962年頃に現在ガンディの基底定理として知られる定理を証明した際に使われていたようです.
 ガンディの基底定理自体は今や遥かに簡単な手法で証明できると知られていますが,ガンディが培った武器である,この計算可能な $\Sigma^1_1$ 集合の生成する位相は,ハーリントンによるシルバーの二分法の明快な別証明の発見に始まり,後に,様々な応用が発見されるに至ったのです.

 その代表的な応用例として,1980年にアレン・ルヴォー (Alain Louveau) がガンディ-ハーリントン位相を用い,ルジンの分離定理の計算論的拡張であるルヴォーの分離定理を証明しました.ルヴォーはこの強力な分離定理を利用し,ジャン・ブルガンらの定理を拡張し,ボレル・セクション問題を鮮やかに解決したことによって注目を浴びます.
 そして,それのみならず,その後,ガンディ-ハーリントン位相は,次に語る,グリム-エフロスの二分法を大発展させる道具へとなっていくのです.

作用素環論から:グリム-エフロス二分法

 作用素環論の研究において,ジェームス・グリム (James G. Glimm) は局所コンパクト・ポーランド群の連続作用に対する二分法を,その後,エドワード・エフロス (Edward Effros) は軌道同値関係が $F_\sigma$ であるようなポーランド群の作用に対する二分法を証明しました.

 歴史を辿ると,1950年代,局所コンパクト群のユニタリ表現の研究をしていたジョージ・マッケイ (George_Mackey) は,可分局所コンパクト群が $\mathrm{I}$ 型であることと滑らかな双対を持つことが同値であるか否か尋ねたそうです.1961年にグリムは,これを可分 $C^*$-環の *-表現のユニタリ同値類の空間の問題に置き換え,「可分 $C^*$-環が $\mathrm{I}$ 型であることと滑らかな双対を持つことは同値である」ということを示し,系としてマッケイ予想を解決したようです.
 そして,同年,グリムは,局所コンパクト・ポーランド群作用が滑らかであることと,非エルゴード的測度を受容しないことが同値であることを示します.これは,滑らかでないならば,最大の超有限同値関係 $E_0$ を連続的に埋め込める,と言い表せますが,グリム自身は,この結果を,作用素環論における「$\mathrm{II}_1$ 型因子は $\mathrm{II}_1$ 型超有限因子を含む」という事実の類似物だとコメントしています.
 さて,ポーランド空間への局所コンパクト・ポーランド群作用の誘導する軌道同値関係は必ず $F_\sigma$ になるのですが,1965年,エフロスは,この軌道同値関係のボレル複雑性が本質であると見抜き,グリムの定理を拡張することによって,可分 $C^*$-環に関するマッケイ予想の別証明を与えました.

 1990年になって,レオ・ハーリントンとアレン・ルヴォーは,アレキサンダー・ケクリス (Alexander S. Kechris) と共に, 計算理論の落とし子であるガンディ-ハーリントン位相を応用すると,グリムとエフロスの二分法の大規模な拡張を得られることに気づきました.
■ ボレル同値関係に対するグリム-エフロスの二分法
標準ボレル空間上の任意のボレル同値関係は滑らかであるか,さもなくば非原子的エルゴード測度を受容する.
 滑らかというのは,大まかに言えば,実数値の完全不変量を持つということで,商空間が標準ボレル空間をなすことと同値です.後者の条件は,通常は,ボレル還元に関して最大の超有限 (hyperfinite) 同値関係である $E_0$ (カントール空間上のヴィタリ同値関係)の連続埋め込みが存在することとして表されることも多いです.超有限同値関係 $E_0$ は,ボレル還元の下で,ボレル $\mathbb{Z}$-作用の誘導する軌道同値関係の中でも最大となります.

 ところで,実は,ある群作用がグリム-エフロス二分法を満たすならば,その群作用に対する位相ヴォート予想が真であることが容易に導かれます.このため,グリムの定理は,局所コンパクト群作用に対する位相ヴォート予想が真であることを導きます.しかし,ヴォート予想までの道程はまだ遠く,我々が考えたい一般のポーランド群作用の誘導する軌道同値関係は,一般には解析的であって,ボレルになるとは限りません.それでも,この流れで何か新しい洞察を得られるのではないかと,1990年代頃には,どんな群作用に対する位相ヴォート予想なら成立するか,ということが調べられていたようです.

 たとえば,1994年に,ラメズ・サミ (Ramez L. Sami) はアーベル群作用に対する位相ヴォート予想が真であることを証明しています.1995年にスラウォミール・ソレッキ (Slawomir Solecki) によって,野性的 (wild) なアーベル群作用が存在する(軌道同値関係がボレルにならないアーベル群作用が存在する)と示されているので,サミの結果は,ここまでに述べた二分法からは導くことの出来ない非自明な結果であることが分かります.1999年には,ソレッキはグレッグ・ヨルト (Greg Hjorth) と共に,冪零群作用に対する強いグリム-エフロス二分法を示し,したがって,冪零群作用に対する位相ヴォート予想が真であることを結論しました.最終的に,この種の結果は,ハワード・ベッカー (Howard Becker) によって,両立可能な完備左不変距離を受容する群 (cli群) の作用に対する位相ヴォート予想が証明されることによって統一されました.

 実のところ,ここで挙げた特殊な群に対する位相ヴォート予想は,主張内の不変ボレル集合を不変解析集合に変えても成立します.しかし,肝心の無限対称群 $S_\infty$ に対して,不変解析集合に強化された位相ヴォート予想は成立しません.事実,ヨルトが示したことは,不変解析集合に強化された位相ヴォート予想を成立させる群とは,如何なる閉部分群の連続準同型像も $S_\infty$ には成り得ないものに他ならない,ということでした.つまり,位相ヴォート予想の真に困難な部分は,結局のところ,ロジック作用,つまりオリジナルのモデル理論的ヴォート予想の部分に凝縮されているようです.

アーベル群論から:ウルム不変量

 ところで,ヴォート予想は可算構造の同型分類に関連する問題なのですから,数学者の日常の活動で発見された,何らかの数学的構造の分類の折に $\aleph_1$ が現れる現場に注目すれば,ヴォート予想に対する何かの洞察が得られるのではないでしょうか.

 ここでは,そんな具体例を紹介しましょう.去る1933年,ヘルムート・ウルム (Helmut Ulm) は順序数を用いて可算アーベル $p$-群の分類を行いました.後にマッケイらによってもう少し整理された形式で,ウルム不変量は,有限または $\infty$ を値に取る長さ $\aleph_1$ 未満の超限列として与えられました.
 さて,1970年には,ジョン・バーワイズ (Jon Barwise) とポール・エクロフ (Paul Eklof) がウルム不変量を無限論理の手法と結び付けた論文を発表しました.これが発端となり,その後,不変量記述集合論にもウルム不変量の影が忍び寄ります.

 ところで,グリム-エフロス二分法に現れる「滑らか」というのは,ボレル可測な方法で実数値の完全不変量を割り当てられるということでした.しかし,グリム-エフロス二分法はボレル同値関係に関する定理ですので,ポーランド群作用が誘導する軌道同値関係などといった解析同値関係にグリム-エフロス二分法を拡張したくば,この「滑らか」という条件を弱めることを考える必要があるかもしれません.

 1995年にヨルトとケクリスは,ウルム不変量による分類を $2^{<\aleph_1}$-値分類として抽象化しました.そして,「滑らか(実数値分類可能)」という条件を「 $C$-可測写像*2によってウルム分類可能」という条件に弱めてさえしまえば,なんとボレルでない解析的軌道同値関係に対してさえ,グリム-エフロスの二分法の類似物が成立することに気づきました.
■ ヨルトとケクリスの二分法
ポーランド位相群の標準ボレル空間へのボレル作用が誘導する任意の軌道同値関係は $C$-可測写像によってウルム分類可能であるか,さもなくば非原子的エルゴード測度を受容する.
 実際には,ヨルトとケクリスの原論文ではもう少し精密な計算がなされていて,前者の条件をニコディムの $C$-階層の階数 $2$ 程度の可測写像によってウルム分類可能である,としても成立します.

 ところで,実は,グリム-エフロス二分法を拡張することによって位相ヴォート予想を帰結しようとする試みには限界があります.たとえば,可算アーベル $p$-群(のなす空間への無限対称群 $S_\infty$ のロジック作用)に関する(位相)ヴォート予想は自明に成立しますが,一方で,ウルム不変量に関する議論から,この群作用(によって誘導される非ボレル軌道同値関係)はグリム-エフロス二分法に反する例となることが知られています.そういうわけで,結局,無限対称群 $S_\infty$ のロジック作用に対する位相ヴォート予想である,真のヴォート予想には,グリム-エフロス二分法は通用しないという結論になります.

位相ヴォート予想から連続モデル理論へ

 ここまでにもそれとなしに触れてきましたが, $\mathcal{L}_{\omega_1\omega}$-ヴォート予想は, $S_\infty$-作用に対する位相ヴォート予想と同値です.この同値性の背後にあるものは,1965年頃のモデル理論において示された,ある種の補完定理で,それは $\mathcal{L}_{\omega_1\omega}$-文における定義可能性と $S_\infty$ のロジック作用による不変ボレル集合との同一性と解釈することができます.
 先に述べたように,位相ヴォート予想の本質的に難しい部分は $S_\infty$-作用に集中しているようです.とはいえ,形式的には $S_\infty$-作用に対する位相ヴォート予想は真の位相ヴォート予想の極一部に過ぎないかもしれません.そう考えると,真の位相ヴォート予想をモデル理論に再翻訳したときに $\mathcal{L}_{\omega_1\omega}$ より大きな世界のヴォート予想を得られそうですが,それは何になるのでしょうか.

 ここで現れるのがモデル理論の連続化です.論理学の連続化と聞いて瞬時に思いつくものは,真理値の連続値への拡張などですが,これは数理論理学が誕生した直後には行われた最古の試みだと思われます.それを足台にして,その数段先の発展系として1966年に提示されたものが,チャーン (Chen Chung Chang) とキースラー (H. Jerome Keisler) による連続モデル理論 (continuous model theory) です.これは純粋な理論単独としては興味深かったのですが,定義が一般的すぎたためか,有用な結果をあまり導けない理論となってしまい,具体的な応用を見つけ損ねてしまったそうです.そのため,その後,長きにわたってあまり人々の関心を惹くことがなく,しばしの衰退のときを迎えてしまったようです.
 しかし,今世紀になって,状況が一変しました.記述集合論とモデル理論を跨ぐ研究者たちが,連続モデル理論の枠組みを縮小し,適用範囲を解析学に狭め,距離構造のモデル理論として特殊化することにより,この理論は成功をおさめることとなったようです.

 距離構造のモデル理論において,モデルとは有界距離空間であり,真理値は $[0,1]$-値を取ります.また,各記号は一様連続関数として解釈されることとなり,記号自体に,引数の数 (arity) と連続率 (modulus of continuity) が備わっています.ここでは,万有空間として,ウリゾーン球 $\mathbb{U}$, つまり,ウリゾーンの万有距離空間の単位球,あるいは同値な定義として,直径 $1$ の万有超等質 (ultrahomogeneous) 可分距離空間を用い,モデルはその内側で考えましょう.このため,$k$-引数,連続率 $\Delta$ の関係記号は,ウリゾーン球の直積空間 $\mathbb{U}^k$ から $[0,1]$ への連続率 $\Delta$ の一様連続関数のなす各点収束位相による位相空間と同一視します.可算言語が固定されたとき,その言語の連続構造のなす空間は,このような位相空間の可算直積として表されます.

 大昔に考察されていたものを掘り起こしてきただけあって,かなり埃のかぶった道具立てですので,一体これでどんな新しいことが出来るのだろう,と疑問に思われるかもしれません.もっと抽象的で恰好いい現代数学を用いた 《一般モデル理論》 なんて幾らでも思いつくと思いますが,しかし,先に述べたように,この 《距離構造のモデル理論》 という適度な具体性が,逆に成功の秘訣となったようです.たとえば,距離構造のモデル理論の現代的な作用素環論との関わりは,2014年国際数学者会議のイリヤス・ファラー (Ilijas Farah) による招待講演ビデオや,国際数学者会議プロシーディングス「論理学と作用素環論」などをご参照ください.
 さて,ヴォート予想の話に戻りましょう.可算モデルの同型は,無限対称群 $S_\infty$ のロジック作用から誘導されたわけですが,連続モデル理論の同型を誘導する群作用は,ウリゾーン球上の等長写像のなすポーランド群 $\mathrm{Iso}(\mathbb{U})$ によるロジック作用です.この位相群 $\mathrm{Iso}(\mathbb{U})$ が万有ポーランド群になることはよく知られていますので,連続論理とこのような作用の関係を丁寧に調べ上げていくと,結論として,位相ヴォート予想を無限論理に対する連続モデル理論的ヴォート予想として解釈することが可能となります.
位相ヴォート予想と,連続 $\mathcal{L}_{\omega_1\omega}$-論理に対するヴォート予想は同値である.

記述集合論から (2):分類を分類する

 さて,ヴォート予想を語るにあたって重要な理論として不変量記述集合論があるわけですが,不変量記述集合論のひとつの源流は,先に述べたようにマッケイ,グリム,エフロスの一連の研究にあったようです.エドワード・エフロスの随筆によれば,彼が1979年にカリフォルニア大学ロサンゼルス校に異動し,そこでとある数理論理学者のグループと出会ったそうです.そこに居たのは,数理論理学者の中でも異彩を放つ,カバル (Cabal) という異名を持つ,知る人ぞ知るアヤシイ数学者集団でした.このエフロスとカバルの邂逅によって,分類の理論に記述集合論の強力な武器がもたらされ,1990年頃からのボレル分類の理論の急速な発展につながることとなります.

 さて,数学的な話に戻りましょう.標準ボレル空間 $X$ と $Y$ 上にそれぞれ同値関係 $E$ と $F$ があるとします.ここで同値関係として想定しているものは,何かの数学的構造の同型性などです.ここで考えたいものは「 $X$ の要素の $E$-分類より $Y$ の要素の $F$-分類の方が複雑である」という主張が何を意味するかということを数学的に形式化することです.
$(X,E)$ が $(Y,F)$ にボレル還元可能とは, $(X,E)$ から $(Y,F)$ へのボレル還元が存在することを意味する.つまり,あるボレル可測写像 $f:X\to Y$ が存在して,任意の $x_0,x_1\in X$ に対して,次が成立することである.
$x_0 E x_1$ $\iff$ $f(x_0) F f(x_1)$
 たとえば, $(X,E)$ が $(\mathbb{R},=)$ にボレル還元可能であったとしたら, $X$ の $E$-分類に対して,ボレル可測な方法で実数値の完全不変量を割り当てることが可能である,ということになります.
 もし equilogical space などに造詣があるようでしたら,あれのボレル空間バージョンだと思って頂ければ問題ないと思います.いや,歴史的にはボレル還元の方が圧倒的に古い概念ですが.

 定義をよく眺めると分かりますが,このボレル分類の理論は,ボレル濃度 (Borel cardinality) の理論とみなすこともできます.つまり, $(X,E)$ が $(Y,F)$ にボレル還元可能ということは,商 $X/E$ のボレル濃度が $Y/F$ のボレル濃度以下であることを意味している,と考えられます.
 各分類同士のボレル濃度は一般には比較不可能で,プレ半順序構造にしかならないのですが,このボレル濃度のアイデアは,モデルの個数のより精密で有用な数え方を提供してくれます.つまり,ここでは構造のクラスが与えられたとき「同型を除いて,濃度が幾つか」ではなく,「同型分類のボレル濃度はどうか」という問題を考えてみましょう.

 ここでは同値関係として,構造の同型問題しか考えないので,固定した可算言語の可算構造全体のなす標準ボレル空間におけるボレル還元に制限して,次の状況だけを考えます.
$\mathcal{A}$ と $\mathcal{B}$ を可算構造のクラスとする.$\mathcal{A}$ (の分類問題)が $\mathcal{B}$ (の分類問題)にボレル還元可能とは,あるボレル可測写像 $f:\mathcal{A}\to\mathcal{B}$ が存在して,任意の可算構造 $A_0,A_1\in \mathcal{A}$ に対して,次が成立することを意味する.
$A_0$ と $A_1$ が同型である $\iff$ $f(A_0)$ と $f(A_1)$ が同型である.
 念のためコメントしておけば,これは数学的構造の分類の完全不変量をボレル可測な方法で還元可能かという意味で難易度の順序を入れているのであって,必ずしも,実践的な意味での分類の難易度,たとえば分野としての難しさといったようなものを反映しているわけではありません.

 さて,この意味での可算構造の同型分類の分類理論を最初に考察したのは,1989年のハーヴェイ・フリードマン (Harvey Friedman) とリー・スタンリー (Lee Stanley) の論文だと思われます.彼らは, $\mathcal{L}_{\omega_1\omega}$-公理化可能な可算構造族の同型分類問題を上述のボレル次数(ボレル濃度)によって分類しました.可算構造の分類問題の中で最もボレル次数が高いものを構造完全問題とでも呼ぶことにすれば,可算有向グラフの分類,可算順序の分類,可算体の分類,可算ブール代数の分類,ランク $2$ の可算冪零群の分類などが構造完全問題に該当します.一方,可算 $p$-群や可算捩れアーベル群の分類などは,分類がボレルでないけれども構造完全問題ではないような例となります.

 他には,たとえば, $p$ を $0$ または素数とすると,標数 $p$ の代数閉体は,超越次数だけで構造が決まるので,標数 $p$ の可算代数閉体の分類問題は,$(\omega+1)$-値の完全不変量が割り当てられます.実際には $\omega+1$ を並び替えてしまえば,ボレル次数の意味では,自然数値の完全不変量を持つということとなります.また,終点を持たない稠密全順序など, $\aleph_0$-範疇的と呼ばれる種の理論については,値 $1$ による分類が割り当てられます.一般に可算モデルが有限個しか存在しない理論の分類問題は,当然ながら,有限値の完全不変量が割り当てられます.
  その他の具体例としては,超越次数が有限の可算体の分類は, $2$ つの元が生成する自由群 $F_2$ による $2^{F_2}$ 上のシフト作用が誘導する軌道同値関係 $E_\infty$ (万有可算ボレル同値関係)と等しいボレル次数になる,などのことが知られています.

 このようなボレル不変量の理論において,そのボレル次数の尺度として有用な道具のひとつがフリードマン-スタンリーの塔 (Friedman-Stenley tower) と呼ばれるものです.
 この塔の地下には,有限値分類の世界があり,第 $0$ 層に相当するものは,自然数分類です.第 $1$ 層は,実数値分類(ボレル可測な方法で実数値不変量を割り当てる)となり,第 $n+1$ 層は,第 $n$ 層からフリードマン-スタンリー・ジャンプ (Friedman-Stenley jump) と呼ばれる方法によって得られる,より複雑な分類となります.
 これをモデル理論的に見ると,スコット階数は $\alpha$-往復 ($\alpha$-back-and-forth) の階層として定義する方法がありますが,一般に $\alpha$-往復同値関係は,フリードマン-スタンリーの塔の第 $\alpha$-層とボレル同値になる,などの結果が知られています.
$$(1,=)<(2,=)<\dots<(n,=)<\dots<(\mathbb{N},=)\equiv\mathrm{FS}_0<(\mathbb{R},=)\equiv\mathrm{FS}_1<E_0<E_\infty<\mathrm{FS}_2<\dots$$
 もう少し興味深い具体例を挙げますと,ランク $1$ 捩れなし可算アーベル群の同型分類があります.これは1937年にラインホルト・ベーア (Reinhold Baer) によって完全に分類されており,彼の定理を精密に分析すると,この同型分類はヴィタリ同値関係 $E_0$ (フリードマン-スタンリーの塔の第 $1$ 層と第 $2$ 層の中間の複雑性)とボレル次数が等しいことが分かります.
 それでは,ベーアの結果をランク $2$ 捩れなしアーベル群に拡張可能かどうか,ということが気になります.実のところ,これは不可能で,1999年,グレッグ・ヨルトは,ランク $2$ 捩れなし可算アーベル群の分類問題のボレル次数は,ランク $1$ のときより真に高いことを示しました.
 2000年,アレクサンダー・ケクリスは,スコット・アダムス (Scot Adams) と共に,ジマーのコサイクル超剛性定理 (Zimmer's cocycle superrigidity) を用いて,リジッド(自明な自己同型のみを持つ)有限ランク捩れなし可算アーベル群の分類問題,その捩れなしランクが大きければ大きいほど,ボレル次数が真に大きいことを示しました.そして,事実,2001年にシモン・トーマス (Simon Thomas) は,超剛性定理を本質的に用い,アーベル群の捩れなしランクが上がるにつれ,その分類難度のボレル次数も真に増大することを示しました.これはそれなりに衝撃的な結果だったようで,その時期に様々な分野の人に注目されたようです.

 ちなみに,この有限ランク捩れなし可算アーベル群の分類問題の階層は,どのランクも,フリードマン-スタンリーの塔の第 $1$ 層と第 $2$ 層の真に中間に収まることが分かります.それでは,有限ランクでない場合の捩れなし可算アーベル群の分類問題のボレル次数はどうなるでしょうか.こうなってしまうと,この分類問題はフリードマン-スタンリーの塔の全階層を駆け上がり,その上に飛び出すことをグレッグ・ヨルトは証明しました.特に,一般の捩れなし可算アーベル群の同型判定はボレルでないことが導かれます.
 ランク $n$ 捩れなし可算アーベル群の分類問題を $\mathrm{TAG}_n$ と書いて,上述の結果をまとめると以下のようになります:
$$(\mathbb{R},=)<E_0\equiv \mathrm{TAG}_1<\mathrm{TAG}_2<\dots<\mathrm{TAG}_n<\mathrm{TAG}_{n+1}<\dots<\mathrm{FS}_2<\dots<\mathrm{FS}_\alpha<\dots<\mathrm{TAG}$$
 一方,もう少しモデル理論的な方向性からは,近年になって示された非常に興味深い定理があります.この定理によると,任意の順序極小 (o-minimal) 理論の可算モデルの分類は,同型を除いて有限個しか存在しないか,さもなくば,フリードマン-スタンリーの塔の第 $1$ 層または第 $2$ 層と等しいボレル複雑性を持つか,最大ボレル複雑性になるか,のいずれかしか有り得ないのだそうです.

 また,タイプの数とボレル次数が何らかの相関を持ちそうだと予想できますが,第一回ヴォート予想会議の後,デヴィッド・マーカー (Devid Marker) は,空集合上のある $n$-タイプが非可算である理論の可算モデルの分類がフリードマン-スタンリーの塔の第 $2$ 層以上のボレル複雑性を持つことを示したそうです.
 逆に,$\omega$-安定理論だったらどうなるかというと,興味深いことに,フリードマン-スタンリーの塔の各 $\alpha$-層に対し,それと分類問題のボレル複雑性が等しい $\omega$-安定理論が存在するのだそうです.また,分類が最大ボレル複雑性の $\omega$-安定理論や,ボレル複雑性は最大ではないけれども分類がボレルではない $\omega$-安定理論なども存在するようです.

 この手のボレル濃度の話題は,ここに述べた話題以外にも,概念的にも技術的にも深い話題が頻出しています.ヴォート予想とは独立に,価値のあるトピックかな,と思いますので,興味がある方は,更に発展的な話題をご自身でいろいろ調べてみると楽しめるかな,と思います.

余談: 分類を分類する(非可算構造の場合)

 ちなみに,ここまでは可算構造の分類問題に注目してきましたが,一般に,ボレル次数の理論の大きな活躍の場は,むしろ非可算構造を含めた,より広い分類問題の分類となります.

 そのようなものの具体例として,無条件シャウダー基底の置換的同値関係,ポーランド距離空間の一様同相分類,可分バナッハ空間の同型分類あるいはリプシッツ同型分類などは,解析同値関係の中で最大のボレル次数を持つ(解析完全)ということが知られているようです.
 
 また,ポーランド距離空間の等長分類でもさまざまな興味深いことが知られており,たとえば,ミハイル・グロモフ (Mikhail Gromov) は,コンパクト距離空間の等長問題は実数値分類可能(滑らか)である,つまり, $(\mathbb{R},=)$ にボレル還元可能であることを示しています.一方,アレクサンダー・ケクリスと高速 (GAO Su) は,空間の範囲を広げてポーランド距離空間全体の等長分類を考えてしまうと,実数値分類可能からは程遠くなって,ポーランド群軌道同値関係の中で最大のボレル次数を持ってしまう(群軌道完全)ということを示しました.なお,零次元局所コンパクト・ポーランド距離空間の等長分類にすると,その複雑性を構造完全問題と同値な程度におさえられることも分かるようです.また,グレッグ・ヨルトは,連結局所コンパクト・ポーランド距離空間の等長分類であれば,もう少し複雑性を下げることができ,万有可算ボレル同値関係 $E_\infty$ とボレル同値となることを指摘しています.

 ちなみに分類問題のボレル次数の順序としては次のようになっています:
$$\text{実数値分類} < E_\infty < \text{構造完全} < \text{群軌道完全} < \text{解析完全}$$
 このような研究の過程で,グレッグ・ヨルトは,群の乱流 (turbulent) 作用の理論を築き上げ,可算構造の同型分類問題にボレル還元できないけれどもポーランド群軌道同値関係に還元可能であるような分類問題の構造を明かしていくこととなります.
 ヨルトの乱流の理論の早期の応用としては,可分ヒルベルト空間上の無限次元ユニタリ作用素の同型分類問題が可算構造分類不可能であること,保測変換の共役作用による同値分類が可算構造分類不可能であることの証明などがあるようです.もう少し最近の話では,フォン・ノイマン因子の分類の可算構造分類不可能性にまつわる様々な結果に応用されているようです.

 他に近年の作用素環絡みの話を紹介しますと,1990年頃からジョージ・エリオット (George A. Elliott) によって進められているエリオット・プログラムというものがあるそうで,これは単純核型単位的可分 $C^*$-環を $K$-理論 ($K$-theory) によって分類しようという試みのようです.このプログラムは現在までに部分的に成功を収めているようで,詳細は知りませんが, $C^*$-環のかなり広範なクラスが $K$-理論的に分類可能,つまりエリオット不変量の分類問題に還元可能であることが分かっているらしいです.
 近年は,イリヤス・ファラーを中心とした研究者たちが,ボレル次数や連続モデル理論などをはじめとした数理論理学の視点でエリオット・プログラムを眺めていこうという方向性で研究を進めているようです.
 
 ところで,昨年2014年12月に,第7回「記述集合論イン・パリ」に招待されたので参加してきたのですが,その研究集会の参加者の発表内容とはいえば,やはり九割方が数理論理学の解析学への応用といった風味で,その中でも特に連続モデル理論のバナッハ空間論への応用のような話題が多かったのを覚えています.そこで,マーチン・サボク (Marcin Sabok) が可分作用素系の分類への記述集合論の応用について話していたのですが,それが少々興味深かったので,関連する話題を紹介しておこうと思います.

 ごく近年になってのことですが,エリオットやファラーらが名を連ねる共著論文の中で,可分(核型) $C^*$-環の分類問題がポーランド群軌道同値関係にボレル還元可能であることが示されていたそうです.そうすると,可分 $C^*$-環の分類問題のボレル次数がどの辺りに位置するかに興味が沸きます.それに答えたのがサボクの結果であり,可分(核型) $C^*$-環の分類問題は群軌道完全であるというものでした.そして,さらに言えば,実際,単純可分 $\mathrm{AI}$ $C^*$-環の分類の時点で既に群軌道完全問題となるそうです.
 ちなみに余談の中の更なる余談ですが,サボクの論文を覗いてみると,そこでは「完全問題ってのはNP完全みたいなやつのことだよ」という感じの説明がなされていたのですが,NP完全なんて「ナントカ完全」という類の定義の中では数学的にはかなり後出の部類だと思われるのに,これを例に出さないといけないなんて,世の中は世知辛いなあ,と思ったのでした.

 さておき,このサボクの結果を利用すると,エリオット不変量について少し興味深いことが分かります.まず,単純 $\mathrm{AI}$ 環がエリオット不変量によって分類可能であることは,既にエリオット自身によってなされていたようです.また,ファラーと共に Andrew S. Toms と Asger Törnquist は,可分 $C^*$-環が与えられたときにそのエリオット不変量をボレル可測な方法で計算できることを示しているので,単純可分 $\mathrm{AI}$ $C^*$-環の分類問題はエリオット不変量の同型判定にボレル還元されます.また,彼らはエリオット不変量の同型性はポーランド群の軌道同値関係にボレル還元可能であることも示しているので,前述のサボクの結果と併せてみれば,エリオット不変量の同型分類は群軌道完全問題と等しいボレル次数であることが帰結されます.

 そんなこんなで,むしろボレル次数の理論における最近の主流は,可算構造の分類よりも,作用素環における分類問題などの方向にシフトしてきている気はしますが,ヴォート予想とは特に関係のない話なので割愛します.

計算理論から:軌道のボレル複雑性とチャーチ-クリーネの順序数

 ところで,2014年の国際数学者会議 (ICM2014) の招待講演者として,アントニオ・モンタルバン (Antonio Montalban) は,「計算可能性理論におけるヴォート予想」という題目で講演を行いました*3.計算可能性理論とは,ゲーデル,チャーチ,チューリングらを始祖とする,現代的に言えば,コンピュータの数学的モデルの理論および,それに基づく計算概念の数学的構造を探る分野です.はてさて,そのような理論が,全くコンピュータ概念とは無関係なヴォート予想とどう関わってくるのでしょうか.

 結論を先に述べれば,ヴォート予想の最初期の研究から,計算理論はその深みに侵入していました.これを説明するために,時代を遡り,再びモーレーの時代に話を戻しましょう.

 モーレーの定理の証明は,ある種のモデル論的対象のボレル構造とスコット階数に関する分析を行うものでした.その後,1974年,マーク・ナデル (Mark Nadel) は,モデルのスコット階数と,ロジック作用による軌道のボレル複雑性が殆ど同一であることを明らかにしました.たとえば,モーレーの証明をボレル複雑性で言い換えれば,「位相ヴォート予想の反例において,各可算順序数 $\alpha$ に対して,加法的ボレル複雑性が高々 $\alpha$ である軌道は高々可算個しか存在しない」というものになります.その他,理論のモデルのスコット階数の上界が $\omega_1$ 未満であることと,モデルの同型判定の複雑性がボレルであることが同一であり,したがって,そのような理論に対するヴォート予想が真であるなどことが導かれます.しかし,これ以上の結果を得るためには,群作用の軌道のボレル複雑性を,ボレル階層の内部に踏み込んで分析することが必要になりそうです.

 さて,1950年頃から良く知られ始めたように,ボレル集合のボレル階層 (Borel hierarchy) と計算論における超算術的階層 (hyperarithmetical hierarchy) には深い結び付きがあり,実際,20世紀中期の記述集合論と計算論は,当時は一般再帰理論 (Generalized Recursion Theory) という名の下に,ほとんど同一の理論として研究されていたのでした.1960年代には,一般再帰理論の意味での「計算とは何であるか」を規定する公理として,クリプキ-プラテク集合論 (Kripke-Platek set theory) が提唱され,再帰理論といえばゲーデルの構成可能宇宙 $L$ の階層あるいはその一般化の分析を指すような時代が訪れるのですが,それはまた別の話なので省略します.

 さて,1974年のナデルの研究は,スコット階数の認容順序数 (admissible ordinal) による分析を行うものでした.まず,可算構造 $M$ に対して,順序数スペクトルと呼ばれる次の順序数 $\omega_1^{\mathrm{CK},M}$ を割り当てます.

$\omega_1^{\mathrm{CK},M}:=\min\{\omega_1^{\mathrm{CK},x}:x$ を神託 (oracle) に用いて $M$ の複製をチューリング機械によって表示可能である$\}$

 ここで, $\omega_1^{\mathrm{CK},x}$ を神託に用いてチューリング機械によって計算可能な順序数の上限を表すものとします.この $\omega_1^{\mathrm{CK},x}$ は, $x$ を始点とするゲーデルの構成可能宇宙の第 $\alpha$ ランク $L_\alpha[x]$ がクリプキ-プラテク集合論のモデルとなる最小の $\alpha$ として定義しても同値です.ナデルは任意の可算モデル $M$ のスコット階数が必ず $\omega_1^{\mathrm{CK},M}+1$ 以下になることを指摘しました.
 ちなみにこれはナデルのオリジナルの定義とは少々違いますが,誤差の範囲なので気にしないこととします.その後,マイケル・マッカイ (Michael Makkai) によって,順序数スペクトルとヴォート予想に関するモデル論的結果があるのですが,ここでは位相ヴォート予想の文脈で解説します.

 ロジック作用の軌道複雑性は,ナデルによるモデルのスコット階数の解析によって,ボレル複雑性の上界を導き出すことができます.具体的には,可算構造のロジック作用による軌道の乗法的ボレル複雑性は, $\omega_1^{\mathrm{CK},M}+2$ 以下,つまり $\mathbf{\Pi}^0_{\omega_1^{\mathrm{CK},M}+2}$ です.1994年にサミは,一般のポーランド群作用においても,同様の事実を証明しました.

 まず,位相ヴォート予想の計算論的分析を行うためには,ボレル空間や位相群に対する適切な計算概念が必要です.これに関しては,連続的な空間に対するチューリング計算の理論は1950年代末にはほぼ確立しており,また,正確な年代は分かりませんが(再帰的に表現された)ポーランド空間上の計算理論も前世紀のかなり早い時代から展開されていたようです*4.そういうわけで,ポーランド空間に関する各概念の計算可能性は,数学的に厳密に定義されていることに注意しましょう.
 1994年にサミが用いた発想は,順序数スペクトルの位相的対応物として,軌道がどれくらいの順序数を計算するほどに神託として賢いかによって,軌道の複雑性を測ろうというものです.つまりは,各点 $x$ の軌道 $G\cdot x$ に次の順序数 $\min_{y\in G\cdot x}\omega_1^{\mathrm{CK},y}$ を割り当てます.
$$\omega_1^{\mathrm{CK},G\cdot x}=\min\{\omega_1^{\mathrm{CK},y}:(\exists g\in G)\;g\cdot x=y\}$$ この順序数は,軌道 $G\cdot x$ に属す如何なる点を神託に用いてもチューリング計算可能な順序数の上限を意味します.

 点 $x$ の軌道の乗法的ボレル複雑性が $\omega_1^{\mathrm{CK},G\cdot x}+2$ 以下であることを述べるサミの証明の概略を述べると,軌道の中の神託として最も愚かな点たちを取り出し,この神託からチューリング計算可能な順序数の上界を利用して,軌道の愚かな点への制限のボレル階数の上界を得た後,軌道内の愚かな点全体のヴォート変換によって元の軌道を復元する,というものとなります.
 関連して,ヴォート予想の反例には,スコット階数が順序数スペクトル以上になるモデルが存在することや,位相ヴォート予想の反例には,任意に賢い軌道が存在するということ,つまり,任意の可算順序数に対して,それ以上の数値を計算できる軌道が存在するということなどが示されます.

 マッカイとサミによる興味深い結果は,軌道の神託としての賢さの値(順序数スペクトル)が軌道のボレル複雑性の値に勝つならば,その群作用に対する位相ヴォート予想は成立するということです.
■ 定理(軌道のボレル複雑性 vs 軌道の神託としての賢さ)
ポーランド群 $G$ が標準ボレル空間へ連続に作用しているとする.もし,任意の点 $x$ の $G$-軌道の乗法的ボレル複雑性が $\omega_1^{\mathrm{CK},G\cdot x}$ 以下ならば, $G$ に対する位相ヴォート予想は成立する.
 その後,ジョン・スティール (John R. Steel) は,解析集合に対する決定性公理の下で,この結果を解析的同値関係まで拡張可能であることを示しました.

 さて,ここまでは,認容順序数の分析と言ったような,初歩的な計算論しか用いない内容ですが,ここからはもう少し計算論の深みを見ていくことにしましょう.

計算理論から (2):計算可能構造の同型判定問題

 ここから話題として浮かび上がるのは,計算可能構造理論 (computable structure theory) あるいは計算可能モデル理論 (computable model theory)と呼ばれる,主に代数的構造,あるいは一般的にモデル理論的対象の計算理論的分析を行う分野です.

 このような代数構造の計算理論の起源が何であったかを述べるのは,少し難しい部分があります.というのも,計算可能性やアルゴリズムの明確な定義を与えないまま代数学における計算可能性やアルゴリズムを語る時代があり,たとえば,ファン・デルヴェルデンなどは,代数学の様々な場面におけるアルゴリズムの存在を問う問題や,アルゴリズムの存在を主張する結果などを幾つか述べていたようです.
 チューリングの時代を経て,計算可能性の数学的定義が誕生し,しばしの時を経て,計算理論が青年期を迎え,非自明な結果が出現し始めた1950年代に移りましょう.この頃になると,数学的に厳密な意味での代数構造の計算可能性理論が誕生します.この時代にファン・デルヴェルデンの主張は再検証され,1960年代以降,代数構造の計算可能性理論は急速に発展していくこととなります.

 さて,計算理論における主対象の一つは,決定問題の計算複雑性ですが,計算可能構造理論において近年注目され始めたのは,計算可能構造の同型判定問題の計算複雑性です.この種の問題の計算複雑性の比較に関する還元可能性は,エカテリーナ・フォキナ (Ekaterina Fokina) とサイ・フリードマン (Sy Friedman) によって導入されました.
$\mathcal{A}$ と $\mathcal{B}$ を構造のクラスとする.$\mathcal{A}$ が $\mathcal{B}$ にチューリング計算可能還元可能であるとは,あるチューリング計算可能関数 $f:\mathcal{A}\to\mathcal{B}$ が存在して,任意の計算可能構造 $A_0,A_1\in\mathcal{A}$ に対して,次が成り立つことを意味する.
$A_0$ と $A_1$ が同型である $\iff$ $f(A_0)$ と $f(A_1)$ が同型である.
 この後で,チューリング次数に関して共終個の神託による相対化(あるいはマーティン測度で殆ど全ての神託による相対化)の下でのチューリング計算可能還元を考えます.  ところで,この定義を見た限りでは,ただのボレル還元の計算理論バージョンじゃないか,と思われるかもしれません.しかし,よく見ると実は様子が異なります.共終神託チューリング計算可能還元を可測性の言葉で解釈しようとすると,その正体は,非可算個の連続還元のボレル可測とは限らない貼り合わせのような代物になっており,共終神託チューリング計算可能還元可能にも関わらずボレル還元不可能である,という状況が多々発生します.

 このチューリング計算可能還元の定義は,構造の同型判定問題だけではなく,任意の同値関係に対して定義することが可能です.この意味で $\Sigma^1_1$-完全な問題の具体例として, $p$-群の同型判定問題,捩れ無しアーベル群の同型判定問題,順序構造としての木の同型判定問題などが挙げられます.
 これは不変量記述集合論におけるボレル次数による可算構造の同型判定の分類とは様子が大きく異なることが分かります.なぜかといえば,1989年にハーヴェイ・フリードマンとリー・スタンリーが示したように,あるいは,後にグレッグ・ヨルトの乱流の理論によって解明された事実より,如何なる可算構造の同型判定問題もボレル還元完全な $\Sigma^1_1$-同値関係にはなり得ないからです.また,ボレル次数の場合,上に述べた結果とは対照的に,可算 $p$-群の同型判定問題は,可算構造の同型判定問題の中でさえボレル還元完全にならないことは,先に述べたとおりです.

 実は,この計算可能性構造の同型判定問題のチューリング計算可能還元複雑性は,可算構造の同型判定問題のボレル還元複雑性が決して持ち得ない,ヴォート予想との繋がりを持つということが近年になって発見されました.ジュリア・ナイト (Julia Knight) とアントニオ・モンタルバンは,計算可能モデル理論のアイデアに基づき,そして独立にハワード・ベッカーは不変量記述集合論のアイデアに基づき,ヴォート予想と計算可能性理論の関連性を明かしたのです.

 ベッカーのアイデアを解説すると,位相ヴォート予想と大きく関わる問題は,与えられた群作用が如何に計算論的に異常な軌道を持つか,という問題になります.ポーランド空間の計算可能点全体の集合は超算術的ボレル,つまり $\Delta^1_1$ だとします.ある軌道が反例的であるとは,計算可能点の軌道であって,そこに入る計算可能点全体の集合が $\Delta^1_1$ でないこととします.たとえば,ハリソンの偽整列順序 $\omega_1^{\rm CK}\cdot(1+\eta)$ の同型類のなす軌道が反例的軌道の具体例となります.
 モデル理論の言葉でこれを再解釈すると,ある可算モデルが反例的ということは,計算可能モデルであって,どんな計算可能 $L_{\omega_1\omega}$-文によっても範疇化されないもののこととなります.

 ベッカーの第一の着目点は,反例的な軌道の数は,軌道同値関係のチューリング計算可能還元に対して単調であるということでした.そして,たとえば可算アーベル $p$-群の空間へのロジック作用には反例的な軌道が無限個あるので,反例的な軌道が有限個しかない群作用の軌道同値判定問題は, $\Sigma^1_1$-完全になり得ないことが分かります.

 ベッカーの発見は,もし位相ヴォート予想が偽ならば(十分多くの神託への相対化の下で)反例的軌道を丁度一つだけ持つ群作用が存在するということでした.ベッカーのアイデアは,再び各点の神託としての賢さ,すなわち順序数スペクトルに着目し,先の述べたサミとは少し異なる意味で賢い軌道を考えるというものです.そして,そのような賢い軌道は必ず反例的な振る舞いをするということを示しました.以上の議論をまとめることによって,次の定理が導かれます. 
■ 定理 (ベッカー; ナイト-モンタルバン)
仮定: 如何なる $\mathcal{L}_{\omega_1\omega}$-公理化可能な構造のクラス $\mathbb{K}$ に対しても,チューリング次数に関して非有界の神託の下で $\mathbb{K}$ に属す $2$ つの計算可能構造が同型か否かを判定する問題の計算複雑性は, $\Delta^1_1$ であるか $\Sigma^1_1$ 完全であって,中間難度にはなり得ないとする.
結論:このとき,ヴォート予想は真である.
 より一般に,これを位相群の言葉で解釈すれば,位相ヴォート予想を証明するためには,如何なるポーランド群作用に対しても,(非有界の神託の下で)与えられた2つの計算可能点が同じ軌道に属す否かを判定する問題が $\Delta^1_1$ であるか $\Sigma^1_1$ 完全である,と示せばよいということです.

 この定理をヴォート予想の解決に有効活用するためには,軌道同値関係が $\Sigma^1_1$ 完全であるための条件を分析する必要がありそうです.現在までに得られている結果として,アントニオ・モンタルバンは,優先度法 (priority argument) の超限入れ子構造を取り扱う枠組みであるアッシュの $\eta$-の手法を拡張することによって,群作用がある種の軌道分岐条件を満たしているならば,その群軌道同値関係が $\Sigma^1_1$ 完全であることを示しています.

計算理論から (3): 超算術的イズ計算可能

 ところで,皆さんも薄々勘付いておられるかもしれませんが,可算整列順序(可算順序数)は同型を除いて $\aleph_1$ 個しか存在しません.それなら,何故これがヴォート予想の反例と言えないのでしょうか.その答えは簡単で,整列順序は順序の言語で一階公理化可能でも $\mathcal{L}_{\omega_1\omega}$-公理化可能でもないのでヴォート予想の解としてはノーカンです.

 ちなみに, $\mathcal{L}_{\omega_1\omega}$-公理化可能な理論であっても,同値性の概念を構造の同型性から少し緩めることによって,分類の数に $\aleph_1$ を出現させることが出来ます.たとえば, $2$ つの構造が互いに埋め込める(双埋め込み可能)ならば,それらは同値であるとみなした場合を考えてみましょう.
 1971年にリチャード・レーバー (Richard Laver) は可算全順序の双埋め込み可能性による同値類の数はちょうど $\aleph_1$ 個になることを証明しました.また,バーワイズとエクロフは可算 $p$-群の双埋め込み可能性による同値類の数もまた,ちょうど $\aleph_1$ 個になることを証明しました.前者はハウスドルフ階数 (Hausdorff rank) を利用するもので,後者はウルム階数を利用するものとなります.

 さてさて,ここで現れた例は,可算整列順序,ハウスドルフ階数,ウルム階数といった $\aleph_1$ が本質的に現れるものたちですが,これらが共有するものとは何でしょうか.

 まず,整列順序(順序数)の様子を見てみましょう.時代を遡ると,計算可能構造の理論の最初期の対象は順序数の計算可能性でした.これは構造の一般論の計算可能性に対する興味というよりは,計算の超限再帰的手続きを定式化するために必要に迫られて発生した研究だと思われます.
 そんな中,1955年にクリフォード・スペクター (Clifford Spector) によって示された有名な定理は,超算術的な可算整列順序に対して,必ず同型な計算可能順序があるというものでした.これは極めて重要な定理で,その後数十年の計算可能性理論を支える基本定理となります.

 2000年代になって,モンタルバンは,スペクターの定理の類似物が様々な構造に見られることに気づきました.彼が示したことは,超算術的な可算全順序は必ず,ある計算可能な可算全順序に双埋め込み可能であるし,超算術的な可算 $p$-群は必ず,ある計算可能な可算 $p$-群に双埋め込み可能である,ということでした.
 つまり,上に述べた可算整列順序の同型分類,可算全順序の双埋め込み可能性分類,可算 $p$-群の双埋め込み可能性分類といった,同値類の個数が $\aleph_1$ になる例はいずれも,「超算術的な可算ナントカは計算可能な可算ナントカとほげほげ同値である」という性質を満たすというものです.

 モンタルバンの洞察は,この超算術的イズ計算可能 (hyperarithmetic-is-recursive) こそが分類における $\aleph_1$ の出現に本質的であり,したがって,これこそがヴォート予想の核心だと見抜いたことです. 
■ モンタルバンの定理 十分な射影決定性の下で,非可算個の可算モデルを持つ $\mathcal{L}_{\omega_1\omega}$-理論 $T$ に対して,次の $2$ 条件は同値である.
  • $T$ がヴォート予想の反例となる.
  • 殆ど全ての神託の下で, $T$ は超算術的イズ計算可能を満たす.
 ちなみに,モンタルバンは次数スペクトル (degree spectrum) を用いたもう一つの同値条件も与えていますが,ここでは割愛します.また,モンタルバンは,この定理が解析的同値関係に拡張できることを示しており,つまり,解析的同値関係 $E$ が非可算個の $E$-同値類を持つとすると,次の $2$ 条件が同値であることが言えます.
  •  $E$-同値類の個数がちょうど $\aleph_1$ 個である.
  • (殆どの神託の下で)どんな超算術的点に対しても,それと $E$-同値な計算可能点が存在する.
 スペクターの定理は,1950年代に始まる超限的計算理論の嚆矢であり,そして一般再帰理論の基本定理,というような風情の代物ですが,全くもってモデル理論とは関係ないものです.そんな定理から得られる「超算術的イズ計算可能」というエッセンスがモデル理論のヴォート予想と繋がるというのは,個人的には,なかなか衝撃的なできごとでした.

集合論から:非可算モデルの数とスコット階数

 さて,モーレーが証明したように,ヴォート予想の反例となる理論の可算モデルの個数は,同型を除いてちょうど $\aleph_1$ 個なわけですが,そういうモデルは非可算モデルをどれくらい持っているか,ちょっと気になりませんか.

 すぐに分かることとしては,初めに述べましたように,シェラハは $\omega$-安定理論についてヴォート予想を示していますので,反例となる一階完全理論は $\omega$-安定でないはずです.ところが,シェラハは $\omega$-安定でない一階完全理論の濃度 $\aleph_1$ のモデルの数は同型を除いてちょうど $2^{\aleph_1}$ であることを示しています.
 まとめると,連続体仮説が偽ならば,一階完全理論については,以下の性質が成り立ちます.
可算モデルの個数が $\aleph_1$ 個 $\Longrightarrow$ 濃度 $\aleph_1$ のモデルの個数が $2^{\aleph_1} 個$

 さて,レオ・ハーリントン (Leo A. Harrington) は,1970年代中頃に,ヴォート予想の反例は $\aleph_2$ の下に任意に大きいスコット階数のモデルが存在することを示したそうです.その後,グレッグ・ヨルトは,ヴォート予想に反例が存在するとすれば, $\mathcal{L}_{\omega_1\omega}$-ヴォート予想の反例で,濃度 $\aleph_2$ のモデルを持たないものが存在することを示しました.
 なにやらハーリントンの定理とヨルトの定理は対立しているように見えるので,この濃度 $\aleph_2$ のモデルの状況を考察することによって,ヴォート予想の反例が存在し得ないことを導けるのではないかという期待が沸きあがります.しかし,最近の研究で,その戦略は燻製ニシンの虚偽 (red herring) であると警告されてしまったのでした.

 ここではそれは置いておいて,余談がてらハーリントンの定理に少し触れておきます.ハーリントンの定理は,オリジナルの証明の他,ジェネリック・モーレー木を使うもの,ジェネリック表示を使うものが知られていますが,ここではジェネリック表示の研究について紹介しておきます.ジェネリック表示の研究の動機は,元々は非可算構造の《良い》計算理論を構築したい,というものです.

 非可算的対象に対する計算理論として,まず,「可分」あるいは「可算生成」といったような「表面的に非可算なだけで本質的には可算」なもの(たとえばユークリッド空間やポーランド空間などの第二可算公理を満たす空間や,そうでなくても,高階連続汎関数空間など)に対するチューリング計算理論は,20世紀中期には既に《良い》計算理論が構築されており,現代に至るまで中心的な研究対象です.
 一方,そのような可算近似性を持ち得ない,本質的に非可算な対象に対するチューリング計算理論の一般化もまた,1960年代の $\alpha$-再帰理論 ($\alpha$-recursion theory) に始まり, $\beta$-再帰理論 ($\beta$-recursion theory), $E$-再帰理論 ($E$-recursion theory) へと拡張され,1980年頃までには高度な理論が発展していました.

 そういうわけで,本質的に非可算な代数構造に対する計算可能構造理論として, $\alpha$-再帰理論の類を用いるという研究も少しばかり行われてきています.しかし,可算近似可能な対象におけるチューリング計算理論と比較すると,強力な計算機構を要求し,その計算論は若干粗いものとなるという難点がありました.
 そこで,近年,代替案として,モンタルバンの学生の Noah S 氏ことノア・シュウェーバーは,ジェネリック表示による構造の計算理論を提案しました.これは一言で述べれば,強制法によるジェネリック拡大によって,非可算構造を可算に潰してから無理やり計算構造を入れて計算理論を展開すればよい,というものです.

 なかなか豪快なアイデアですが,これを使って,わりと非自明なことも示すことができるようです.それなら,とりあえずジェネリック表示というものを研究してみよう,という過程の副産物として,シュウェーバーは,ジュリア・ナイトとアントニオ・モンタルバンと共に,ジェネリック表示の手法を用いたハーリントンの定理の別証明を得たようです.
 なお,この別証明の部分に関しては,あくまでジェネリック表示の概念を用いただけで,特に計算理論的な手法は使われていないようです.

おまけ: YouTube で観る国際数学者会議

本文中でも紹介しましたが,2014年国際数学者会議の全体講演と招待講演のビデオはYouTubeで公開されています.
 2014年の国際数学者会議における招待講演者のうち,本文中で名前が登場した人物としては,再帰理論のアントニオ・モンタルバン (Antonio Montalban),記述集合論のイリヤス・ファラー (Ilijas Farah),記述集合論のスラウォミール・ソレッキ (Slawomir Solecki) の $3$人がいます.2014年の国際数学者会議で,「論理学と基礎論」分野として招待されていたのはこの $3$ 人を含む合計 $6$ 人ですが,残り $3$ 人はモデル理論のようです.
  何はともあれ,上記リンクから,論理学に限らず幅広い分野の最先端のトークを見れるので,いろんなトークを鑑賞してみると楽しいと思います.

▼ というわけで

 以上,いろいろと書きましたが,筆者はヴォート予想もモデル理論も,その他,本文中で触れた様々な理論に対してもド素人ですので,間違ったことを書いておりましたら,優しく指摘して頂けると助かります.なお,これはかなり偏った変則的アプローチのみを紹介しておりまして,実際は,モデル論的な正統な方向性からヴォート予想を調べるという研究も多数あるということを念のためコメントしておきます.

おしまい.


*1 完全個の軌道が存在するとは,孤立点を持たない空でない閉集合 $P$ で, $P$ のどの二点も異なる軌道に属している,というようなものが存在することを意味します.
*2 ルジンの $C$-集合族とは,開集合全体を含み,ススリンの $A$-演算で閉じた最小の $\sigma$-加法族であり,ある写像が $C$-可測であるとは,各 $C$-集合の原像が $C$-集合になることを意味します.
*3 2014年国際数学者会議の招待講演プログラム上は,「構造のクラスの計算可能性理論的分類」という題目でしたが,実際の講演スライドでは「計算可能性理論におけるヴォート予想」となっておりました.
*4 位相構造と両立的なチューリング計算理論(任意精度計算の理論)は,現代的には,第二可算 $T_0$ 空間の商となる $T_0$ 空間全体のなすカテゴリー上に拡張されています.これより,全てのポーランド空間はもちろん,ある種の距離化不可能空間,ハウスドルフでない空間の上での計算理論も展開できます.また,これはデカルト閉圏を形成するので,たとえば,局所コンパクトでない空間をベースにした高階汎関数空間などのような,第二可算でない空間にも計算理論が展開できます.(もちろん,このような空間のクラスは,二階算術の内部で扱える空間のクラスにおおよそ対応します.)なお,高階汎函数空間上のチューリング計算理論は,1950年代の時点でよく知られていましたが,その位相的側面が研究され始めたのは1970年代以降のようです.

0 件のコメント:

コメントを投稿