分類理論(モデル理論)

同義語:Shelahの分類理論classification theory (model theory)

概要

分類理論(モデル理論)(classification theory)とは、完全な一階理論を、モデルの全体が整理できるか、各濃度で最大個数のモデルをもつかで分ける S. Shelah の計画である。境目となる性質を分割線といい、$\omega$ 安定、超安定、安定、NIP が代表的である。安定な理論は、モデルの上の型がすべて論理式で定義できる理論、型の個数が $\lvert M\rvert^{\aleph_0}$ 以下に収まる理論として特徴づけられる。到達点の主ギャップ定理によれば、モデルの個数はすべての非可算濃度で最大になるか、濃度の添字だけで決まる上界で抑えられるかのどちらかである。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: モデル理論, 安定性理論, 型(モデル理論), コンパクト性定理(一階論理)

モデル理論の 分類理論(classification theory)は、完全な一階理論を、そのモデルの全体が「整理できる」か「手に負えないほど多い」かで分ける S. Shelah の計画である。境目になる性質を 分割線(dividing line)といい、分割線の片側の理論にはモデルの構造論があり、反対側の理論には各濃度で最大個数のモデルがある、という形の定理を目標にする。代表的な分割線は、安定性理論 の安定性、超安定性、NIP理論 の NIP である。
この記事は分類理論の入口として、分割線の一覧と、計画の到達点である主ギャップ定理の主張を述べる。中心に置くのは、安定性が「型の個数が少ない」ことと「型が論理式で定義できる」ことの同値として捉えられるという定理(thm-ct-definable)で、これを証明する。この定理から、安定な理論が安定になる濃度の範囲も分かる。安定性の定義と基本的な例は 安定性理論 に、NIP の詳しい理論は NIP理論 にある。
以下、$L$ は可算な一階言語、$T$ は無限モデルをもつ $L$ の 完全な理論 とし、選択公理 を仮定する。$\mathcal U$ は $T$ の十分大きなモデルで、それより小さいパラメータ集合の上の型をすべて実現するものとし、モデルや集合はその中でとる。$A$ 上の $1$ 変数の完全型の全体を $S(A)$ と書く。$x$ は $1$ つの変数、$y$ は変数の有限組である。

分割線の一覧

安定性理論 の定義どおり、$T$ が $\lambda$-安定 とは $\lvert A\rvert\le\lambda$ なら $\lvert S(A)\rvert\le\lambda$ となることで、ある無限基数で $\lambda$-安定な理論を 安定 という。$2^{\aleph_0}$ 以上のすべての $\lambda$ で $\lambda$-安定な理論を 超安定 という(Sh71 §0、p. 273)。論理式の定義可能集合の族の VC 次元が有限であることを NIP という(NIP理論)。

分類型の個数・論理式による条件例主な結果
$\omega$-安定可算集合の上の型が可算個無限集合、標数 $0$ の代数閉体非可算濃度で範疇的なら $\omega$-安定(Morleyの範疇性定理)
超安定$\lambda\ge2^{\aleph_0}$ で $\lambda$-安定$\omega$-安定な理論可算モデルの個数の研究(Vaught予想)
安定ある $\lambda$ で $\lambda$-安定細分する同値関係の理論 $T_1$thm-ct-definable、主ギャップ定理
NIPVC 次元が有限稠密な線形順序、実閉体不変型の数え上げ(NIP理論)

上の行ほど狭い。$\omega$-安定な理論はすべての無限基数で安定である(安定性理論 の定理「$\omega$-安定性から $\kappa$-安定性へ」)。安定な論理式は NIP である(Sim14 p. 31)。稠密な線形順序は NIP だが不安定で(安定性理論 の例、NIP理論 の例)、$T_1$ は安定だが超安定でない(ex-ct-t1)。NIP でない理論の典型はランダムグラフの理論である(NIP理論)。
分割線の向こう側は「悪い」理論ではなく、別の道具が働く領域である。安定性の外では順序が、NIP の外ではランダムグラフが写し取られる。安定な理論の中では、型が論理式で定義できることがモデルの構造論の出発点になる。

定義可能な型

定義可能な型

モデル $M$ の上の型 $p\in S(M)$ が 定義可能 であるとは、各論理式 $\varphi(x;y)$ について、$M$ の元をパラメータにもつ論理式 $d_p\varphi(y)$ があって、$M$ の組 $b$ について
$$ \varphi(x;b)\in p\iff M\models d_p\varphi(b) $$
となることをいう。$d_p\varphi$ を $p$ の $\varphi$ の 定義 という。

型 $p$ は $M$ の元 $b$ ごとに $\varphi(x;b)$ を含むかどうかを決めるので、$M$ の部分集合 $\{b\mid\varphi(x;b)\in p\}$ を与える。定義可能とは、この部分集合が $M$ で定義可能集合になることである。$b\in M$ の型 $\operatorname{tp}(b/M)$ では $d_p\varphi(y)=\varphi(b;y)$ が定義になる。
次の階数が証明の道具である(Sh71 Definition 2.4、Lemma 2.7、Sim14 Definition 2.54 の二分木の性質の有限版)。

論理式の二分木の階数

$\varphi(x;y)$ を論理式、$\pi(x)$ をパラメータをもつ論理式の有限集合とする。$\varphi^1=\varphi$、$\varphi^0=\lnot\varphi$ と書く。長さ $n$ 未満の $0,1$ 列 $s$ で添字づけた組 $(b_s)$ で、長さ $n$ のどの $0,1$ 列 $f$ についても
$$ \pi(x)\cup\{\varphi(x;b_{f\restriction i})^{f(i)}\mid i< n\} $$
が $\mathcal U$ で満たされるものを、$\pi$ の上の高さ $n$ の $\varphi$ の二分木 という。それがある最大の $n$ を $R_\varphi(\pi)$ と書く(いくらでも高いものがあれば $R_\varphi(\pi)=\infty$、$\pi$ が満たされなければ $-1$)。

階数の性質
  1. $\pi\subset\pi'$ なら $R_\varphi(\pi')\le R_\varphi(\pi)$。
  2. $k\ge0$ で $R_\varphi(\pi\cup\{\varphi(x;b)\})\ge k$ かつ $R_\varphi(\pi\cup\{\lnot\varphi(x;b)\})\ge k$ なら $R_\varphi(\pi)\ge k+1$。
  3. $\pi=\pi(x;c)$ と書くと、各 $k$ について「$R_\varphi(\pi(x;c)\cup\{\varphi(x;b)\})\ge k$」は $c,b$ についての $1$ つの一階の論理式 $\psi_k(c,b)$ で表せる。

1 は $\pi'$ の上の二分木が $\pi$ の上の二分木でもあることによる。2 は、根に $b$ を置き、$1$ の側に $\pi\cup\{\varphi(x;b)\}$ の上の木、$0$ の側に $\pi\cup\{\lnot\varphi(x;b)\}$ の上の木をつなげばよい。3 は、高さ $k$ の木の $2^k-1$ 個の組の存在と、$2^k$ 本の枝それぞれでの $x$ の存在を書き並べた論理式
$$ \exists(b_s)_s\ \bigwedge_f\ \exists x\Bigl(\textstyle\bigwedge\pi(x;c)\land\varphi(x;b)\land\bigwedge_{i< k}\varphi(x;b_{f\restriction i})^{f(i)}\Bigr) $$
である。$\square$

高い木の作り方

すべての $n$ で $R_\varphi(\{x=x\})\ge n$ なら、任意の基数 $\mu$ について($\mathcal U$ は $2^\mu$ 個の元の組の型も実現する大きさにとる)、長さ $\mu$ 未満の $0,1$ 列で添字づけた組 $(b_s)$ と、長さ $\mu$ の $0,1$ 列 $f$ ごとの元 $c_f$ で、すべての $i< \mu$ で $\mathcal U\models\varphi(c_f;b_{f\restriction i})^{f(i)}$ となるものがある。

要点:コンパクト性で高さ $\mu$ の木を作る。有限個の条件は、関係する枝を分ける有限個の高さだけを見れば、高さ有限の木に移せる。

詳しい証明を開く

$b_s$ と $c_f$ を新しい定数とし、$T$ に $\mathcal U$ の初等図式と条件 $\varphi(c_f;b_{f\restriction i})^{f(i)}$ をすべて加える。有限部分が充足可能であることを示せば、コンパクト性定理(一階論理) と $\mathcal U$ の飽和性から主張を得る。有限部分に現れる相異なる $f_1,\dots,f_r$ と、条件に現れる高さ、および $f_j$ と $f_{j'}$ が初めて食い違う高さを全部集め、$l_1< \cdots< l_q$ とする。$g_j(t):=f_j(l_t)$($1\le t\le q$)とおくと、$f_j$ どうしは集めた高さのどれかで食い違うので $g_j$ は相異なる。$f_j\restriction l_t=f_{j'}\restriction l_t$ と $g_j\restriction(t-1)=g_{j'}\restriction(t-1)$ は同値である。前者なら $l_t$ より前で食い違わず、後者が成り立たなければ $l_t$ より前の集めた高さで食い違うからである。よって $b_{f_j\restriction l_t}$ に高さ $q$ の木の $b'_{g_j\restriction(t-1)}$ を、$c_{f_j}$ に枝 $g_j$ を満たす元を割り当てれば矛盾なく定まり、有限部分は満たされる。$\square$

安定性と定義可能性

安定性の同値な言い換え

次は同値である。

  1. $T$ は安定である。
  2. すべての論理式 $\varphi(x;y)$ について $R_\varphi(\{x=x\})$ は有限である。
  3. すべてのモデル $M$ について、$S(M)$ の型はすべて定義可能である。
  4. すべての無限のモデル $M$ について $\lvert S(M)\rvert\le\lvert M\rvert^{\aleph_0}$ である。
  5. $\lambda^{\aleph_0}=\lambda$ となるすべての無限基数 $\lambda$ について、$T$ は $\lambda$-安定である。

1 ⇒ 2:$T$ が $\lambda$-安定で、ある $\varphi$ について $R_\varphi(\{x=x\})=\infty$ だとする。$2^\mu>\lambda$ となる最小の基数を $\mu$ とすると、$\mu\le\lambda$ で、$\nu< \mu$ なら $2^\nu\le\lambda$ である。lem-ct-tree の $(b_s)$、$(c_f)$ をとり、$A=\{b_s\}$ の成分の全体とする。添字 $s$ は $\sum_{\nu< \mu}2^\nu\le\mu\cdot\lambda=\lambda$ 個なので $\lvert A\rvert\le\lambda$ である。$f\ne g$ が高さ $\delta$ で初めて食い違えば、$\varphi(x;b_{f\restriction\delta})$ は $\operatorname{tp}(c_f/A)$ と $\operatorname{tp}(c_g/A)$ の一方にだけ入る。よって $\lvert S(A)\rvert\ge2^\mu>\lambda$ となり、$\lambda$-安定性に反する。
2 ⇒ 3:$p\in S(M)$ と $\varphi(x;y)$ をとる。2 と lem-ct-rank の 1 により、$p$ の有限部分集合 $\pi$ の階数はどれも $0$ 以上 $R_\varphi(\{x=x\})$ 以下の整数なので、階数が最小になる $\pi$ がとれる。その値を $k$ とし、$\pi=\pi(x;c)$($c$ は $M$ の組)と書く。$b\in M$ について
$$ \varphi(x;b)\in p\iff R_\varphi(\pi\cup\{\varphi(x;b)\})\ge k $$
を示す。$\varphi(x;b)\in p$ なら $\pi\cup\{\varphi(x;b)\}$ は $p$ の有限部分集合なので、$k$ の最小性から階数は $k$ 以上である。$\varphi(x;b)\notin p$ なら $\lnot\varphi(x;b)\in p$ で、同じ理由で $R_\varphi(\pi\cup\{\lnot\varphi(x;b)\})\ge k$ である。もし $R_\varphi(\pi\cup\{\varphi(x;b)\})\ge k$ でもあれば、lem-ct-rank の 2 により $R_\varphi(\pi)\ge k+1$ となり、$R_\varphi(\pi)=k$ に反する。lem-ct-rank の 3 の $\psi_k(c,y)$ をとると、右辺は $\mathcal U\models\psi_k(c,b)$ と同じで、$M$ は $\mathcal U$ の初等部分モデルなので $M\models\psi_k(c,b)$ と同じである。よって $d_p\varphi(y)=\psi_k(c,y)$ が定義である。
3 ⇒ 4:$p\in S(M)$ は、論理式 $\varphi(x;y)$ の全体から定義 $d_p\varphi$ への写像で決まる。$L$ は可算なので $\varphi$ は可算個で、$M$ の元をパラメータにもつ論理式は $\lvert M\rvert$ 個である。よって $\lvert S(M)\rvert\le\lvert M\rvert^{\aleph_0}$ である。
4 ⇒ 5:$\lvert A\rvert\le\lambda$ とし、Löwenheim–Skolemの定理 で $A\subset M$、$\lvert M\rvert=\lambda$ のモデル $M$ をとる。$A$ 上の型は $\mathcal U$ のある元 $a$ で実現され、$\operatorname{tp}(a/M)$ の制限になるので、$\lvert S(A)\rvert\le\lvert S(M)\rvert\le\lambda^{\aleph_0}=\lambda$ である。
5 ⇒ 1:$\lambda=2^{\aleph_0}$ は $\lambda^{\aleph_0}=\lambda$ を満たす。$\square$

出典と一般の言語

1 と 3 の同値は、論理式ごとの形で Sh71 Theorem 2.13(pp. 304–305)と Theorem 3.1(pp. 306–308)にあり、Theorem 3.1 の証明も階数の最小値で定義を作る。全体の形は Sim14 Proposition 2.55、Theorem 2.60 にある。言語が可算でないときは、4 の $\aleph_0$ を $\lvert T\rvert$ に替えた形が Sim14 Theorem 2.60 の (iii) である。2 の木の階数が有限であることを Sim14 は「二分木の性質をもたない」と言い表している。

5 から、安定な理論は $2^{\aleph_0}$、$\beth_{\omega_1}$ のように $\lambda^{\aleph_0}=\lambda$ を満たす濃度ではいつも安定である。1 ⇒ 2 の証明は、不安定性が「パラメータの木の枝の数だけ型ができる」ことから来ることを示している。安定性理論 の定理「順序性をもつ理論は安定でない」の順序の切れ目が、ここでは木の枝に替わっている。

安定性スペクトル

$T$ が安定なら、基数 $\kappa(T)\le\aleph_1$ と $\lambda(T)\le2^{\aleph_0}$ があって、$T$ が $\lambda$-安定であることは $\lambda\ge\lambda(T)$ かつ $\lambda^{< \kappa(T)}=\lambda$ と同値である。

出典と読み方

Sh71 §0 の結果の一覧 A 1)(p. 273)を可算な言語に当てはめたものである(一般には $\kappa(T)\le\lvert T\rvert^+$、$\lambda(T)\le2^{\lvert T\rvert}$)。この記事では証明しない。無限基数 $\lambda$ について $\lambda^{< \aleph_0}=\lambda$ はいつも成り立ち、$\lambda^{< \aleph_1}=\lambda^{\aleph_0}$ である。$\kappa(T)=\aleph_0$ なら $T$ は $\lambda(T)$ 以上のすべての濃度で安定で、とくに超安定である。$\kappa(T)=\aleph_1$ なら $\lambda^{\aleph_0}>\lambda$ となる $\lambda$(たとえば $\beth_\omega$)で安定でなく、超安定でない。thm-ct-definable の 5 は、どちらの場合も $\lambda^{\aleph_0}=\lambda$ かつ $\lambda\ge2^{\aleph_0}$ なら安定であることを示している。

細分する同値関係

言語を二項関係 $E_0,E_1,\dots$ とし、$T_1$ を「各 $E_n$ は無限個の類をもつ同値関係で、類はどれも無限、$E_{n+1}$ は $E_n$ を細分し、各 $E_n$ 類は無限個の $E_{n+1}$ 類に分かれる」という理論とする。$T_1$ は安定で、超安定でない(Sim14 Example 4.24、Remark 4.25、Example 4.36)。
$T_1$ が $\omega$-安定でないことは直接分かる。可算なモデル $M$ で、$E_0$ 類 $C_0$、それに含まれる $E_1$ 類 $C_1$、… と入れ子の列を選ぶ。各 $C_n$ の元 $c_n$ をとると、$\{xE_nc_n\mid n< \omega\}$ の有限部分は $c_n$($n$ が最大のもの)で満たされるので、この集合は型に延びる。選び方は各段で可算無限通りあるので $\aleph_0^{\aleph_0}=2^{\aleph_0}$ 通りあり、異なる列は異なる型を与える。よって $\lvert S(M)\rvert\ge2^{\aleph_0}$ である。

主ギャップ定理

濃度 $\kappa$ の $T$ のモデルの同型類の個数を $I(\kappa,T)$ と書く。$I(\kappa,T)\le2^\kappa$ はいつも成り立つ($\kappa$ の上の $L$ 構造の個数による)。分類理論の到達点は、この個数がすべての非可算濃度で最大になるか、濃度 $\aleph_\alpha$ では $\alpha$ だけで決まる上界で抑えられるかの二者択一である。

主ギャップ定理

次のどちらか一方が成り立つ。

  1. すべての非可算基数 $\kappa$ について $I(\kappa,T)=2^\kappa$。
  2. すべての順序数 $\alpha\ge1$ について $I(\aleph_\alpha,T)< \beth_{\omega_1}(\lvert\omega+\alpha\rvert)$。
出典と仕組み

Shelah の著書 Classification Theory(改訂版、1990 年)の定理で、主張は PT25 §1(p. 3)による。ここで $\beth_\alpha(\mu)$ は $\beth_0(\mu)=\mu$、$\beth_{\alpha+1}(\mu)=2^{\beth_\alpha(\mu)}$、極限では上限で定める。この記事では証明しない(定理の細かい形と例は Shelahの主ギャップ定理 にある)。PT25 の説明では、不安定な $T$ はつねに 1 の側に入る。そのため安定な理論に絞り、モデルの個数が再び最大になる場合と、モデルの分類・記述が得られる場合とに分ける。後者が 2 の側である。

主ギャップ定理の前史には Morley の範疇性定理がある。$T$ がある非可算濃度で範疇的なら、すべての非可算濃度で範疇的である(Morleyの範疇性定理)。そのような $T$ は $\omega$-安定である(安定性理論 の定理「Morley の $\omega$-安定性定理」)。さらに Baldwin と Lachlan は(Baldwin–Lachlanの定理)、そのような $T$ の各モデルに次元とよばれる基数を対応させた。次元はモデルを同型を除いて決め、モデルの濃度は次元と $\aleph_0$ の大きいほうに等しい。この結果、$T$ は $\aleph_0$-範疇的であるか、可算モデルをちょうど $\aleph_0$ 個もつ(PT25 §1、p. 3)。次元を測るのは、無限で、定義可能な部分集合がどれも有限か補集合が有限になる 強極小 な集合である。
可算モデルの個数 $I(\aleph_0,T)$ については、それが可算か $2^{\aleph_0}$ であろうという Vaught予想 が 2025 年の時点で未解決である。$\omega$-安定な理論では証明されているが、超安定な理論の一般の場合は未解決である(PT25 §1、pp. 2–4)。

安定性の外

分類理論の考え方は、安定な理論の外にも広がった。NIP 理論では、型の個数を数える代わりに、不変型や不可識別列の上の論理式のふるまいで理論を調べる(NIP理論)。そこでは $o$-minimal な理論や $p$ 進体の理論が中心的な例になる。安定な理論のもう一つの一般化に単純な理論がある。単純な理論では、型の「分岐しない拡大」が対称で推移的な独立性の関係になる(Sim14 第 5 章の冒頭、p. 69)。NIP 理論ではこの対称性は成り立たないが、別の性質が成り立つ(同)。

反例の表

外す条件反例成り立たなくなること
thm-ct-definable の 1 の安定性稠密な線形順序 $(\mathbb Q,<)$ と $\sqrt2$ の型型が定義可能であること
prf-ct-definable の 2 ⇒ 3 で $\pi$ の階数を最小にとること無限集合の理論、$\varphi(x;y)=(x=y)$、$c\in M$ の型式が $p$ の定義になること
thm-ct-definable の 5 の $\lambda^{\aleph_0}=\lambda$($\lambda=\aleph_0$ とする)ex-ct-t1 の $T_1$$\lambda$-安定であること
表の確かめ

1 行目:$M=(\mathbb Q,<)$、$p=\operatorname{tp}(\sqrt2/M)$(実数の中で考える)、$\varphi(x;y)=(x< y)$ とする。$\{b\in\mathbb Q\mid x< b\in p\}=\{b\mid b>\sqrt2\}$ である。稠密な線形順序の理論の定義可能集合は有理数を端点とする区間の有限和なので(o-minimal構造)、この集合は定義可能でない。
2 行目:$\varphi(x;y)=(x=y)$ では $R_\varphi(\{x=x\})=1$ である。高さ $1$ の木は $x=b$ と $x\ne b$ がともに満たされればよく、高さ $2$ の木は、根 $b$ の $1$ の側の子 $b'$ について $x=b\land x=b'$ と $x=b\land x\ne b'$ がともに満たされる必要があり、不可能である。$p=\operatorname{tp}(c/M)$($c\in M$)について、最小でない $\pi=\{x=x\}$(階数 $1$)を使うと、式は「$R_\varphi(\{x=b\})\ge1$」となる。$\{x=b\}$ の上の高さ $1$ の木は $x=b\land x=b'$ と $x=b\land x\ne b'$ を同時に満たせないので、これはどの $b$ でも偽で、$x=c\in p$ を捉えない。最小の $\pi=\{x=c\}$(階数 $0$)なら、式は「$\{x=c,x=b\}$ が満たされる」で、$b=c$ と同値になり正しい。
3 行目:$\aleph_0^{\aleph_0}=2^{\aleph_0}\ne\aleph_0$ で、ex-ct-t1 により $T_1$ は安定だが $\aleph_0$-安定でない。

関連項目

参考文献

[1]
Saharon Shelah, Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory, Annals of Mathematical Logic, 1971, §0 の定義(超安定)と結果の一覧 A 1)(p. 273)、Definition 2.4(p. 299)、Lemma 2.7(p. 301)、Theorem 2.13(pp. 304–305)、Theorem 3.1(pp. 306–308)
[3]
Anand Pillay, Predrag Tanović, The number of countable models of first-order theories, arXiv:2508.06854v1, 2025, §1 Vaught's conjecture(pp. 1–4:Vaught 予想の現状、主ギャップ定理の主張と不安定な理論の扱い、Morley と Baldwin–Lachlan の結果、超安定な場合)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する