Shelahの主ギャップ定理(Shelah's main gap theorem)とは、可算な言語の完全な理論 $T$ について、濃度 $\kappa$ のモデルの同型類の個数 $I(\kappa,T)$ が、すべての非可算な $\kappa$ で最大値 $2^\kappa$ をとるか、すべての $\alpha\ge1$ で $I(\aleph_\alpha,T)<\beth_{\omega_1}(\lvert\alpha+\omega\rvert)$ となるかのどちらかである、という定理である。前者は $T$ が分類可能でないか深い場合、後者は浅い場合で、浅い理論のモデルは可算な部分モデルの木と次元で決まる。無限個の無限類をもつ同値関係の理論は後者、整数の順序の理論は前者の例である。
前提知識: モデル理論, 完全な理論, 安定性理論, 分類理論(モデル理論)
Shelah の主ギャップ定理(main gap theorem)は、可算な言語の完全な理論 $T$ について、非可算濃度 $\kappa$ のモデルの同型類の個数 $I(\kappa,T)$ が、すべての非可算濃度で最大値 $2^\kappa$ をとるか、濃度 $\aleph_\alpha$ では $\alpha$ だけで決まる量でずっと小さく抑えられるかの二者択一になる、という定理である。前者の理論にはモデルを不変量で記述する構造論がなく、後者の理論のモデルは可算な部分モデルの木と次元とよばれる基数で決まる。S. Shelah は 1970 年から、非可算モデルの個数の問題を中心に置いてモデル理論の分類の計画(分類理論(モデル理論))を進めた(HHL00 §1、pp. 208–209)。
分類理論(モデル理論) の記事は、分割線の一覧と、安定性と型の定義可能性の同値を扱い、主ギャップ定理は主張だけを述べている。この記事は、主ギャップ定理を、二分法を決める性質(分類可能・深い・浅い)とともに述べる。研究水準の定理なので、主張は Hart–Hrushovski–Laskowski の論文の整理によって引用し、証明はしない。そのうえで、個数 $I(\kappa,T)$ の一般の上界と、二つの側にそれぞれ入る具体的な理論の個数の計算に完全な証明をつける(prop-mg-equivalence、prop-mg-integers)。
以下、$L$ は可算な一階言語、$T$ は無限モデルをもつ $L$ の完全な理論とし、選択公理 を仮定する。
無限基数 $\kappa$ について、濃度 $\kappa$ の $T$ のモデルの同型類の個数を $I(\kappa,T)$ と書く。$\kappa$ を非可算基数全体に動かした関数 $\kappa\mapsto I(\kappa,T)$ を $T$ の 非可算スペクトル という。基数 $\mu$ と順序数 $\alpha$ について、$\beth_0(\mu)=\mu$、$\beth_{\alpha+1}(\mu)=2^{\beth_\alpha(\mu)}$、極限順序数 $\delta$ では $\beth_\delta(\mu)=\sup_{\alpha<\delta}\beth_\alpha(\mu)$ と定める。
すべての無限基数 $\kappa$ について $1\le I(\kappa,T)\le2^\kappa$ である。
下界:$T$ は無限モデルをもつので、Löwenheim–Skolemの定理 により濃度 $\kappa$ のモデルがある。
上界:濃度 $\kappa$ のモデル $M$ は、全単射 $h\colon M\to\kappa$ で構造を $\kappa$ の上に移せば、台集合が $\kappa$ のモデルと同型になる。よって台集合が $\kappa$ の $L$ 構造の個数が $2^\kappa$ 以下であることを示せばよい。$n$ 項の関係記号の解釈は $\kappa^n$ の部分集合で、$\lvert\kappa^n\rvert=\kappa$($n\ge1$)なので $2^\kappa$ 通りある。$n$ 項の関数記号の解釈は $\kappa^n$ から $\kappa$ への写像で $\kappa^\kappa=2^\kappa$ 通り、定数記号は $\kappa$ 通りである。記号は可算個なので、構造の個数は $(2^\kappa)^{\aleph_0}=2^{\kappa\cdot\aleph_0}=2^\kappa$ 以下である。$\square$
両端はどちらも実際に起こる。標数を固定した代数閉体の理論では、すべての非可算な $\kappa$ で $I(\kappa,T)=1$ であり、Peano算術 の完全な拡大では、すべての非可算な $\kappa$ で $I(\kappa,T)=2^\kappa$ である(HHL00 §1、p. 208)。ある非可算濃度で $I(\kappa,T)=1$ なら、すべての非可算濃度で $I(\kappa,T)=1$ である(Morleyの範疇性定理)。また Shelah は、非可算スペクトルがどの完全な理論でも広義単調増加であることを示した(HHL00 §1、p. 208)。
主ギャップ定理の二つの側を分けるのは、Shelah が導入した次の性質である。定義の細部は安定性理論の道具(独立性、重さ、素モデル)を要するので、ここでは HHL00 §2 の言い方で述べる。
$L$ を可算な言語、$T$ を無限モデルをもつ $L$ の完全な理論とする。
1 は Shelah の定理で、HHL00 Theorem 2.1(p. 210)と Theorem 2.5 の 1(p. 212)にある。超安定でない場合、DOP をもつ場合、OTOP をもつ場合、深い場合のそれぞれで、モデルが集合論的な対象を埋め込めるほど豊かになり、$2^\kappa$ 個の互いに同型でないモデルが作られる(同 pp. 208、210、212)。2 の $\operatorname{dp}(T)<\omega_1$ と等式は Shelah の定理で HHL00 Theorem 2.5 の 2(p. 212)、有限の深さの上界は分解の木に可算なラベルをつけて数えたもので、同 p. 212 にある。$d\ge1$ なのは、分解の頂点は可算なモデルなので、非可算なモデルの分解には根以外の頂点が要るからである。HHL00 は Abstract(p. 207)で、非可算スペクトルとして現れる関数の一覧を完全に与えている。
主ギャップ定理は、分類理論(モデル理論) の定理「主ギャップ定理」の形(すべての非可算な $\kappa$ で $I(\kappa,T)=2^\kappa$ か、すべての $\alpha\ge1$ で $I(\aleph_\alpha,T)<\beth_{\omega_1}(\lvert\omega+\alpha\rvert)$)でも述べられる(PT25 §1、p. 3)。この形は上の 1・2 から次のように出る。浅い $T$ で深さが無限なら、$\operatorname{dp}(T)+1<\omega_1$ から $\beth_{\operatorname{dp}(T)+1}(\mu)<\beth_{\omega_1}(\mu)$($\mu=\lvert\alpha+\omega\rvert$)である。深さが有限の $d$ なら、$\mu^{2^{\aleph_0}}\le(2^\mu)^{2^{\aleph_0}}=2^{\mu\cdot2^{\aleph_0}}\le2^{2^\mu}=\beth_2(\mu)$ なので、上界は $\beth_{d+1}(\mu)<\beth_{\omega_1}(\mu)$ である。
二つの側の違いは、「個数が $2^\kappa$ より小さい」ことではなく、「個数が濃度の添字 $\alpha$ の関数で抑えられる」ことである。prop-mg-equivalence の理論は 2 の側にあるが、$\alpha=\aleph_\alpha$ となる $\alpha$ では $I(\aleph_\alpha,T)=2^{\aleph_\alpha}$ になる(rem-mg-fixed-point)。
言語を 2 項関係記号 $E$ だけとし、$T_E$ を「$E$ は同値関係で、同値類は無限個あり、どの同値類も無限集合である」という公理($n=1,2,\dots$ について「相異なる類に属す $n$ 個の元がある」「どの元の類にも $n$ 個の元がある」)の理論とする。
$T_E$ は完全である。$I(\aleph_0,T_E)=1$、$1\le n<\omega$ で $I(\aleph_n,T_E)=\aleph_0$、$\alpha\ge\omega$ で $I(\aleph_\alpha,T_E)=2^{\lvert\alpha\rvert}$ である。
$M\models T_E$ とする。$\beta\le\alpha$ について、大きさ $\aleph_\beta$ の同値類の個数を $c_M(\beta)$ と書く。
不変量で決まること. $M\cong N$ なら、同型写像は同値類を同値類に全単射で移し、類の大きさを保つので $c_M=c_N$ である。逆に $c_M=c_N$ なら、各 $\beta$ について大きさ $\aleph_\beta$ の類どうしの全単射をとり、対応する類どうしの全単射を貼り合わせれば、$E$ を保つ全単射、すなわち同型写像になる。
可算の場合. 濃度 $\aleph_0$ のモデルでは、類はどれも可算無限で、類の個数も可算無限である。よって $c_M(0)=\aleph_0$ がただ一つの可能性で、$I(\aleph_0,T_E)=1$ である。$T_E$ は有限モデルをもたず $\aleph_0$-範疇的なので、Łoś–Vaughtの判定法 により完全である。
$\alpha\ge1$ の上界. $\lvert M\rvert=\aleph_\alpha$ なら $c_M$ は $\{\beta\mid\beta\le\alpha\}$ から集合 $V_\alpha:=\omega\cup\{\aleph_\gamma\mid\gamma\le\alpha\}$ への写像である。$\lvert V_\alpha\rvert=\lvert\alpha+\omega\rvert$ なので、$I(\aleph_\alpha,T_E)\le\lvert\alpha+\omega\rvert^{\lvert\alpha+1\rvert}$ である。
$\alpha\ge1$ の下界. 任意の写像 $m\colon\{\beta\mid\beta<\alpha\}\to V_\alpha$ について、大きさ $\aleph_\beta$ の類を $m(\beta)$ 個($\beta<\alpha$)、大きさ $\aleph_\alpha$ の類を $\aleph_0$ 個もつ集合を作り、類を $E$ の同値類とする。類は無限個あり、どれも無限なので $T_E$ のモデルである。濃度は、$\aleph_\alpha$ 以下の基数を $\aleph_\alpha$ 個以下足したものなので $\aleph_\alpha$ 以下で、大きさ $\aleph_\alpha$ の類を含むので $\aleph_\alpha$ である。異なる $m$ からは不変量の異なるモデルができるので、$I(\aleph_\alpha,T_E)\ge\lvert\alpha+\omega\rvert^{\lvert\alpha\rvert}$ である。
値. $1\le n<\omega$ なら上界と下界はともに $\aleph_0^{n+1}=\aleph_0^n=\aleph_0$ である。$\alpha\ge\omega$ なら $\lvert\alpha+\omega\rvert=\lvert\alpha+1\rvert=\lvert\alpha\rvert$ で、$\lvert\alpha\rvert^{\lvert\alpha\rvert}=2^{\lvert\alpha\rvert}$ なので、上界と下界はともに $2^{\lvert\alpha\rvert}$ である。$\square$
$\alpha\ge1$ で $I(\aleph_\alpha,T_E)\le2^{\lvert\alpha+\omega\rvert}=\beth_1(\lvert\alpha+\omega\rvert)<\beth_{\omega_1}(\lvert\alpha+\omega\rvert)$ なので、$T_E$ は thm-mg-main の 2 の不等式を満たす。とくに $I(\aleph_1,T_E)=\aleph_0<2^{\aleph_1}$ なので、thm-mg-main の 1 の対偶により $T_E$ は浅い。モデルが「類の大きさごとの個数」という基数の組で決まることが、構造の側の典型である。
$\alpha=\aleph_\alpha$ となる順序数 $\alpha$(たとえば $\aleph_0,\aleph_{\aleph_0},\dots$ の上限)では、$\lvert\alpha\rvert=\aleph_\alpha$ なので prop-mg-equivalence により $I(\aleph_\alpha,T_E)=2^{\aleph_\alpha}$ である。2 の側の理論でも、個数が $2^\kappa$ に達する濃度 $\kappa$ がある。主ギャップ定理の上界 $\beth_{\omega_1}(\lvert\alpha+\omega\rvert)$ は $\alpha$ の大きさで測られ、このような $\alpha$ では $2^{\aleph_\alpha}$ より大きいので矛盾しない。
$T_{\mathbb Z}:=\operatorname{Th}(\mathbb Z,<)$ とする。空でない線形順序 $J$ について、$\mathbb Z\times J$ に「$j< j'$、または $j=j'$ かつ $m< m'$ のとき $(m,j)< (m',j')$」という辞書式順序を入れたものを $\mathbb Z\times J$ と書く。$\{(m,j)\mid m\in\mathbb Z\}$ を $j$ の 区画 という。2 元 $x,y$ の 距離 $d(x,y)$ を、同じ区画にあれば $\lvert m-m'\rvert$、違う区画にあれば $\infty$ と定める。
空でない線形順序 $J,J'$ について、$\mathbb Z\times J$ と $\mathbb Z\times J'$ は初等同値である。とくに $\mathbb Z\times J\models T_{\mathbb Z}$ である。
要点:Ehrenfeucht–Fraïsséゲーム の定理「長い有限線形順序は区別できない」の証明と同じく、選ばれた点の組 $\bar a=(a_1,\dots,a_t)$、$\bar b=(b_1,\dots,b_t)$ について、条件 $C_r$「(a) $a_i< a_l\iff b_i< b_l$、$a_i=a_l\iff b_i=b_l$、(b) すべての $i,l$ で $d(a_i,a_l)=d(b_i,b_l)$ であるか、ともに $2^r$ 以上($\infty$ を含む)」を考える。$C_r$ ならば $\bar a\sim_r\bar b$(同記事の記号)であることを $r$ についての帰納法で示す。空の組は $C_r$ を満たすので、すべての $r$ で模倣者が勝ち、同記事の命題「模倣者の勝ちから n-同値へ」により初等同値である。$J'$ を 1 点にとれば $\mathbb Z\times J'\cong\mathbb Z$ である。
$r=0$ では (a) により $a_i\mapsto b_i$ は部分同型である。$r\ge1$ とし $q:=2^{r-1}$ とおく。同記事の補題「往復条件による特徴づけ」の(行き)を示す((帰り)は対称)。新しい点 $a$ に対し、$C_{r-1}((\bar a,a),(\bar b,b))$ を満たす $b$ を選べばよい。$a=a_i$ なら $b:=b_i$。$t=0$ なら $b$ は何でもよい。
$a$ が隣り合う $a_j< a< a_l$ の間にある場合:$d(a_j,a_l)=d(b_j,b_l)$(有限)なら、$a$ は $a_j$ と同じ区画にあるので、$b_j$ の区画で $b_j$ から $d(a_j,a)$ だけ先の点を $b$ とする。そうでなければ両者は $2q$ 以上である。$d(a_j,a)< q$ なら $b_j$ から $d(a_j,a)$ だけ先の点、$d(a,a_l)< q$ なら $b_l$ から $d(a,a_l)$ だけ手前の点、どちらも $q$ 以上なら $b_j$ から $q$ だけ先の点を $b$ とする。区画は $\mathbb Z$ と同型で端点がないので、これらの点はある。どの場合も $b_j< b< b_l$ で、組 $(a_j,a)$ と $(b_j,b)$、組 $(a,a_l)$ と $(b,b_l)$ の距離は、等しいか、ともに $q$ 以上である(たとえば $d(a_j,a)< q$ の場合、$d(b,b_l)$ は $b_l$ が $b_j$ の区画にあれば $d(b_j,b_l)-d(a_j,a)> q$、なければ $\infty$ で、$d(a,a_l)$ も同様に $q$ より大きい)。
$a$ がすべての $a_i$ より小さい場合は、最小の $a_j$ について、$d(a,a_j)< q$ なら $b_j$ から $d(a,a_j)$ だけ手前の点、そうでなければ $q$ だけ手前の点を $b$ とする。大きい場合も同様である。
残りの点との距離:$a_x\le a_j$($a$ の左隣が $a_j$)なら、区画は凸なので $d(a,a_x)=d(a,a_j)+d(a_j,a_x)$、$d(b,b_x)=d(b,b_j)+d(b_j,b_x)$ である($\infty$ を足すと $\infty$)。2 つの項の組はそれぞれ「等しいか、ともに $q$ 以上」なので(後者は $2^r\ge q$ による)、和も同じである。右側も同様で、(a) は $a$ と $b$ が対応する隙間にあることから従う。$\square$
すべての無限基数 $\kappa$ について $I(\kappa,T_{\mathbb Z})=2^\kappa$ である。
区画の並びは同型類で決まる. $\mathbb Z\times J$ で、2 元の間に有限個の元しかないという関係は区画が同じという関係で、順序だけで定まる。よって同型 $\mathbb Z\times J\cong\mathbb Z\times J'$ は区画を区画に移し、順序同型 $J\cong J'$ を引き起こす。
互いに同型でない $2^\kappa$ 個の順序. $X\subseteq\kappa$ について、$\beta<\kappa$ ごとに有理数の順序 $Q_\beta\cong(\mathbb Q,<)$ と、$\beta\in X$ なら 2 元、$\beta\notin X$ なら 3 元の鎖 $C_\beta$ をとり、$J_X:=\sum_{\beta<\kappa}(Q_\beta+C_\beta)$(順序和)とおく。$J_X$ で、2 元の間に有限個の元しかないという同値関係を考えると、その類で 2 元以上のものはちょうど $C_\beta$($\beta<\kappa$)である。実際、$C_\beta$ の 2 元の間は有限である。$Q_\beta$ の点 $x$ と別の点 $y$ の間には、$Q_\beta$ が稠密で端点をもたないので、$Q_\beta$ の無限個の点がある。$C_\beta$ の点と $C_\beta$ の外の点の間には、$Q_\beta$ か $Q_{\beta+1}$ の無限個の点がある。同型 $J_X\cong J_Y$ はこの同値関係を保つので、2 元以上の類どうしの順序を保つ全単射、すなわち整列順序 $\kappa$ からそれ自身への順序同型を引き起こし、それは恒等写像である。類の大きさも保たれるので $C_\beta$ の大きさが一致し、$X=Y$ である。
数える. $\lvert J_X\rvert=\kappa\cdot\aleph_0=\kappa$ なので $\lvert\mathbb Z\times J_X\rvert=\kappa$ で、lem-mg-blocks により $\mathbb Z\times J_X\models T_{\mathbb Z}$ である。前の 2 段により $X\ne Y$ なら $\mathbb Z\times J_X\not\cong\mathbb Z\times J_Y$ なので、$I(\kappa,T_{\mathbb Z})\ge2^\kappa$ である。prop-mg-bounds と合わせて等号が成り立つ。$\square$
論理式 $x< y$ は $(\mathbb Z,<)$ の元 $a_i=b_i=i$($i\in\mathbb N$)により順序性をもつので、$T_{\mathbb Z}$ は安定でない(安定性理論 の定理「順序性をもつ理論は安定でない」)。したがって超安定でも分類可能でもなく、thm-mg-main の 1 の側にある。証明の構成は、任意の線形順序(ここでは $J_X$)をモデルの中に写し取れることを使っている。順序が埋め込めることが非構造の典型である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-mg-main の 1 の「$\kappa>\aleph_0$」 | $\operatorname{Th}(\mathbb Q,<)$、$\kappa=\aleph_0$ | $I(\kappa,T)=2^\kappa$ |
| prop-mg-equivalence の公理「どの同値類も無限」 | 類が有限でもよい同値関係の理論 $T'_E$(同値類は無限個) | $1\le n<\omega$ で $I(\aleph_n,T)=\aleph_0$ |
| prf-mg-integers の添字の順序が整列順序であること | 添字を $\mathbb Z$ にした $J'_X:=\sum_{z\in\mathbb Z}(Q_z+C_z)$ | $X\ne Y$ なら $J'_X\not\cong J'_Y$ |
1 行目:$\operatorname{Th}(\mathbb Q,<)$ は端点のない稠密な線形順序の理論で、安定性理論 の定理「順序性をもつ理論は安定でない」により安定でないので、超安定でなく分類可能でない。しかし可算なモデルはすべて $(\mathbb Q,<)$ と同型なので(カテゴリー性 の定理「Cantor の定理」)、$I(\aleph_0,T)=1<2^{\aleph_0}$ である。
2 行目:$T'_E$ の濃度 $\aleph_1$ のモデルで、大きさ $\aleph_1$ の類を $1$ 個もち、各 $k\ge1$ について大きさ $k$ の類を $g(k)\in\{0,1\}$ 個、大きさ $\aleph_0$ の類を $\aleph_0$ 個もつものを考える。どれも $T'_E$ の公理を満たし、類の大きさごとの個数は同型で保たれるので、異なる $g\colon\omega\setminus\{0\}\to\{0,1\}$ から同型でないモデルが得られる。よって $I(\aleph_1,T'_E)\ge2^{\aleph_0}>\aleph_0$ である。
3 行目:$X\subseteq\mathbb Z$ と、それを 1 つずらした $Y:=\{z+1\mid z\in X\}$ では、$z\mapsto z+1$ が $Q_z+C_z$ を $Q_{z+1}+C_{z+1}$ に移す同型を貼り合わせて $J'_X\cong J'_Y$ となる。$X=\{0\}$ なら $Y=\{1\}\ne X$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する