Ryll-Nardzewskiの定理
概要
Ryll-Nardzewskiの定理（Ryll-Nardzewski theorem）とは、可算な言語の完全な理論 $T$ で無限のモデルをもつものについて、可算無限なモデルが同型を除いてただ 1 つであること（$\omega$-範疇性）が、各 $n$ について $n$ 変数の完全型が有限個であること、すべての完全型が孤立していること、$n$ 変数の論理式が $T$ のもとで同値を除き有限個であることと同値であるという定理である。可算なモデルの自己同型群の言葉では、各 $n$ について $n$ 個の元の組の軌道が有限個であることと同値になる。無限集合・稠密な線形順序・ランダムグラフの理論が例である。
可算な言語の完全な理論 $T$ が $\omega$-範疇的（可算範疇的、$\aleph_0$-範疇的）であるとは、$T$ の可算無限なモデルが同型を除いてただ 1 つであることをいう（カテゴリー性 の定義「カテゴリー性」）。端点のない稠密な線形順序の理論はその代表例である。Ryll-Nardzewski の定理（Ryll-Nardzewski theorem）は、この性質をモデルを見ずに理論の側だけで言い換える。$T$ が $\omega$-範疇的であることは、各 $n$ について $n$ 変数の完全型が有限個しかないこと、すべての完全型が孤立していること、$n$ 変数の論理式が $T$ のもとでの同値を除いて有限個しかないことと同値である。さらに、可算なモデルの自己同型群の言葉では、$n$ 個の元の組の軌道が各 $n$ について有限個であることと同値になる。
この記事では、これらの同値性を完全に証明する。型を数える条件から同型を作る向きには往復の議論を使い、逆向きには 省略型定理 を使う。例として、無限集合・稠密な線形順序・ランダムグラフの理論が $\omega$-範疇的であること、有理数体上のベクトル空間・標数 $0$ の代数閉体・整数の順序の理論がそうでないことを確かめる。
主張
以下、$L$ は可算な一階言語、$T$ は無限のモデルをもつ $L$ の完全な理論とする。$T$ のモデルはすべて無限であり（各 $k$ について「少なくとも $k$ 個の元がある」が $T$ のすべてのモデルで真になる）、初等部分モデル の定理「下向き Löwenheim–Skolem の定理」により $T$ は可算無限なモデルをもつ。型・孤立・型の空間 $S_n(T)$ の意味は 型(モデル理論) の定義「型」「型の空間」「孤立した型」のとおりである。
次の 4 条件は同値である。
- $T$ は $\omega$-範疇的である。
- 各 $n\ge1$ について、$S_n(T)$ は有限集合である。
- 各 $n\ge1$ について、$S_n(T)$ のすべての元は孤立している。
- 各 $n\ge1$ について、論理式 $\varphi(x_1,\dots,x_n)$ は $T$ のもとで同値なものを同一視すると有限個しかない。
この定理は 1959 年の Engeler、Ryll-Nardzewski、Svenonius の結果で、3 人の名を並べて Engeler–Ryll-Nardzewski–Svenonius の定理ともよばれる（CL25 §2、Theorem 2.1 の直前の説明）。CL25 Theorem 2.1 は 1・2 と自己同型群の条件（下の thm-rn-oligomorphic）をまとめた形で、PP13 Theorem 7.1 は可算無限な構造について 1 と自己同型群の条件の同値を述べている。証明はこの記事の中で完結させる。
条件 2〜4 は $T$ の論理式と型だけで書かれていて、モデルの同型を含まない。条件 4 は、$T$ の可算なモデル $M$ の上で「$n$ 個の元の組について一階の論理式で言えること」が有限個の性質の組み合わせで尽きることを意味する。
証明
往復の議論の 1 歩を補題にしておく。$T$ のモデル $M,N$ と $\bar a\in M^n$、$\bar b\in N^n$ について、$\operatorname{tp}^M(\bar a)=\operatorname{tp}^N(\bar b)$ のとき、$a_i\mapsto b_i$ は同じ論理式を満たす組の対応を与える。$n=0$ の場合は「$M$ と $N$ が同じ文を満たす」と読み、$T$ が完全なのでいつも成り立つ。
$M,N\models T$、$\bar a\in M^n$、$\bar b\in N^n$（$n\ge0$）で $\operatorname{tp}^M(\bar a)=\operatorname{tp}^N(\bar b)$ とする。$a\in M$ について $\operatorname{tp}^M(\bar a,a)\in S_{n+1}(T)$ が孤立しているならば、$\operatorname{tp}^N(\bar b,b)=\operatorname{tp}^M(\bar a,a)$ となる $b\in N$ がある。
$q:=\operatorname{tp}^M(\bar a,a)$ を孤立させる論理式 $\psi(\bar x,y)$ をとる。型(モデル理論) の命題「孤立した完全型と孤立点」により $\psi\in q$ なので、$M\models\psi(\bar a,a)$、したがって $M\models\exists y\,\psi(\bar a,y)$ である。論理式 $\exists y\,\psi(\bar x,y)$ は $\operatorname{tp}^M(\bar a)=\operatorname{tp}^N(\bar b)$ に属するので、$N\models\psi(\bar b,b)$ となる $b\in N$ がある。$\psi$ は $q$ を孤立させるので、$q$ の各元 $\chi$ について $T\models\forall\bar x\,\forall y\,(\psi\to\chi)$ であり、$N\models\chi(\bar b,b)$ である。よって $q\subset\operatorname{tp}^N(\bar b,b)$ で、どちらも完全型なので等しい（$\chi\in\operatorname{tp}^N(\bar b,b)\setminus q$ なら $\lnot\chi\in q$ となり矛盾）。$\square$
2 ⇔ 4． 型(モデル理論) の命題「型の個数と論理式の個数」そのものである。
2 ⇒ 3． $S_n(T)$ は Hausdorff 空間なので（型(モデル理論) の定理「型の空間は Stone 空間」）、有限なら各 1 点集合は有限個の閉集合の和の補集合として開集合であり、すべての点が孤立点である。孤立点である完全型は孤立している（同記事の命題「孤立した完全型と孤立点」）。
3 ⇒ 2． すべての点が孤立点なら、1 点集合の全体は $S_n(T)$ の開被覆である。$S_n(T)$ はコンパクトなので有限部分被覆があり、$S_n(T)$ は有限集合である。
3 ⇒ 1． $M,N$ を $T$ の可算無限なモデルとし、$M=\{a_0,a_1,\dots\}$、$N=\{b_0,b_1,\dots\}$ と番号を付ける。組 $\bar c\in M^k$ と $\bar d\in N^k$ の対 $(\bar c,\bar d)$ で $\operatorname{tp}^M(\bar c)=\operatorname{tp}^N(\bar d)$ を満たすものを順に伸ばしていく。最初は空の組の対である。$(\bar c,\bar d)$ ができたら、3 により $\operatorname{tp}^M(\bar c,a_m)$ は孤立しているので（$a_m$ はまだ $\bar c$ に入っていない番号最小の元）、lem-rn-step により $\operatorname{tp}^N(\bar d,d)=\operatorname{tp}^M(\bar c,a_m)$ となる $d$ をとって対を伸ばす。次に、$b_l$ をまだ $\bar d$ に入っていない番号最小の元として、lem-rn-step を $N,M$ の役割を入れ替えて使い、$\operatorname{tp}^M(\bar c,c)=\operatorname{tp}^N(\bar d,b_l)$ となる $c$ で対を伸ばす。これを交互に繰り返すと、$M$ のすべての元が左側に、$N$ のすべての元が右側に現れる。対応 $h$ を「左の組の第 $j$ 成分を右の組の第 $j$ 成分に移す」で定める。同じ型の組では $x_i=x_j$ の真偽が一致するので $h$ は矛盾なく定まる単射で、全射でもある。さらに、どの原子論理式の真偽も対応する組の間で一致するので、$h$ は定数・関数・関係を保ち、同型写像である（定数記号 $c$ の値 $c^M$ もある段で左側に入り、論理式 $x_j=c$ によりその像は $c^N$ になる）。よって $T$ の可算無限なモデルはすべて同型である。
1 ⇒ 3． 孤立していない $p\in S_n(T)$ があれば、省略型定理 の系「同型でない可算なモデル」により、$p$ を実現する可算無限なモデルと省略する可算無限なモデルがあって同型でない。これは 1 に反する。$\square$
3 ⇒ 1 の構成は、カテゴリー性 の定理「Cantor の定理」の証明と同じ形の往復である。Cantor の定理では「隙間に元を選ぶ」段を順序の稠密性で行ったが、ここでは型を孤立させる論理式の証人を選ぶことで行っている。1 ⇒ 3 だけが省略型定理を使い、そこで言語の可算性が要る。
自己同型群による言い換え
構造 $M$ の自己同型の全体 $\operatorname{Aut}(M)$ は $M^n$ に成分ごとに作用する。自己同型は論理式の真偽を保つので、同じ軌道に属する組は同じ型をもつ。
$M$ を $T$ の可算無限なモデルとする。$T$ が $\omega$-範疇的であることと、各 $n\ge1$ について $\operatorname{Aut}(M)$ の $M^n$ への作用の軌道が有限個であることは同値である。このとき、$M^n$ の 2 つの組が同じ軌道に属することと同じ型をもつことは同値であり、軌道は $S_n(T)$ の元と 1 対 1 に対応する。
$\omega$-範疇的なら． thm-rn-main によりすべての完全型は孤立していて、型(モデル理論) の命題「孤立した型はすべてのモデルで実現される」により $M$ で実現される。$\bar a,\bar b\in M^n$ が同じ型をもつとき、thm-rn-main の 3 ⇒ 1 の往復を $M$ と $M$ について、最初の対を $(\bar a,\bar b)$ にして行うと、$\bar a$ を $\bar b$ に移す $M$ の自己同型が得られる。よって軌道と型は一致し、軌道の全体は $S_n(T)$ と 1 対 1 に対応する。とくに軌道は有限個である。
軌道が有限個なら． $M^n$ の軌道を $O_1,\dots,O_k$ とすると、$M$ で実現される $n$-型は有限個 $q_1,\dots,q_l$（$l\le k$、相異なる）である。$i\neq j$ ごとに $\varphi_{ij}\in q_i\setminus q_j$ を選び、$\chi_i:=\bigwedge_{j\neq i}\varphi_{ij}$ とおく。$M$ の組 $\bar a$ が $q_j$ を実現すれば、$\chi_i$ を満たすのは $j=i$ のときだけである（$j\neq i$ なら $\lnot\varphi_{ij}\in q_j$）。よって $M\models\forall\bar x\,(\chi_1\lor\cdots\lor\chi_l)$ で、各 $\psi\in q_i$ について $M\models\forall\bar x\,(\chi_i\to\psi)$ である。$T$ は完全で $M\models T$ なので、これらの文は $T$ から導かれる。$p\in S_n(T)$ をとると $\chi_1\lor\cdots\lor\chi_l\in p$ なので、ある $\chi_i$ が $p$ に属し（すべて属さなければ否定がすべて $p$ に入り、その連言と $\chi_1\lor\cdots\lor\chi_l$ が同時に $p$ に属して矛盾）、型(モデル理論) の命題「型の基本性質」の 4 により $q_i\subset p$、したがって $p=q_i$ である。よって $S_n(T)$ は有限で、thm-rn-main により $T$ は $\omega$-範疇的である。$\square$
軌道が各 $n$ で有限個であるような置換群は オリゴモルフィック（oligomorphic）とよばれる。thm-rn-oligomorphic により、$\omega$-範疇的な理論の可算なモデルは、その自己同型群で「対称性が非常に大きい」構造として特徴づけられる。
例
等号だけの言語の無限集合の理論 $I_\infty$（完全な理論 の例「無限集合の理論」）は $\omega$-範疇的で、可算なモデル $\mathbb N$ の $\mathbb N^n$ の軌道は、組の成分のどれとどれが等しいかの指定（$\{1,\dots,n\}$ の分割）と 1 対 1 に対応する。端点のない稠密な線形順序の理論 $\mathrm{DLO}$ では $S_n(\mathrm{DLO})$ が有限であり（型(モデル理論) の例「稠密な線形順序の型」）、thm-rn-main から $\omega$-範疇性が再び従う。
$I_\infty$ では記号がないので、$\mathbb N$ の自己同型は全単射 $\mathbb N\to\mathbb N$ にほかならない。$\bar a,\bar b\in\mathbb N^n$ の等しさの指定が同じなら、$a_i\mapsto b_i$ は矛盾なく定まる単射で、$\mathbb N\setminus\{a_i\}$ から $\mathbb N\setminus\{b_i\}$ への全単射（どちらも可算無限）と合わせて全単射に延びる。逆に自己同型は等しさを保つ。分割は有限個なので軌道は有限個で、thm-rn-oligomorphic により $I_\infty$ は $\omega$-範疇的である。$\square$
グラフの言語 $\{E\}$ で、$E$ が対称で反射的でないことと、各 $m,m'\ge0$ について次の 拡張公理 $\varepsilon_{m,m'}$ からなる理論を $T_{\mathrm{RG}}$ とする：相異なる $u_1,\dots,u_m,v_1,\dots,v_{m'}$ に対し、どの $u_i,v_j$ とも異なり、すべての $u_i$ と辺で結ばれ、どの $v_j$ とも結ばれない頂点 $z$ がある。$T_{\mathrm{RG}}$ はモデルをもち、$\omega$-範疇的で完全である。したがって $S_n(T_{\mathrm{RG}})$ は有限で、たとえば $S_2(T_{\mathrm{RG}})$ は「$x_1=x_2$」「$x_1\neq x_2$ で辺がある」「$x_1\neq x_2$ で辺がない」の 3 点からなる。
要点：二進展開で具体的なモデルを作り、Cantor の定理と同じ往復で可算なモデルの同型を作る。
詳しい証明を開く
モデル． 頂点集合 $\mathbb N$ で、$i< j$ のとき $j$ の二進展開の $i$ 桁目が $1$ なら $i,j$ を辺で結ぶ。相異なる $u_1,\dots,u_m,v_1,\dots,v_{m'}$ が与えられたら、すべての $u_i,v_j$ より大きい $N$ をとり $z:=2^N+\sum_i2^{u_i}$ とおく。$z> N$ はどの $u_i,v_j$ よりも大きく、$z$ の $u_i$ 桁目は $1$、$v_j$ 桁目は $0$ なので、$z$ は拡張公理の条件を満たす。
$\omega$-範疇性． $G,H$ を可算なモデルとする（相異なる $k$ 個の頂点を $u_1,\dots,u_k$ として $\varepsilon_{k,0}$ を使うと、そのどれとも異なる頂点があるので無限である）。有限部分集合の間の、辺の有無を保つ単射（部分同型）$p$ と $a\in G$ について、$p$ の定義域を $U\sqcup V$（$U$ は $a$ と辺で結ばれる元、$V$ はそうでない元）に分ける。$H$ の拡張公理 $\varepsilon_{\lvert U\rvert,\lvert V\rvert}$ を $p(U)$ と $p(V)$ に使うと、$p(U)$ のすべてと結ばれ $p(V)$ のどれとも結ばれず、$p$ の値域にない $b$ がある。$p\cup\{(a,b)\}$ は部分同型である。カテゴリー性 の定理「Cantor の定理」の証明と同じく、これを交互に使って全単射に広げれば同型が得られる。
完全性と型． 有限のモデルはなく、$\aleph_0$-範疇的なので、Löwenheim–Skolemの定理 の定理「Łoś–Vaught の判定法」により完全である。$S_2$ の 3 つの型は、それぞれ論理式 $x_1=x_2$、$x_1\neq x_2\land E(x_1,x_2)$、$x_1\neq x_2\land\lnot E(x_1,x_2)$ を含み、可算なモデルの中で同じ論理式を含む組は（往復を $(\bar a,\bar b)$ から始めて得られる）自己同型で移り合うので、thm-rn-oligomorphic によりこの 3 つで尽きる。$\square$
拡張公理を満たす可算なグラフは Rado グラフともよばれる。
- 有理数体上の $\{0\}$ でないベクトル空間の理論 $T_{\mathbb Q}$（カテゴリー性 の定理「有理数体上のベクトル空間の理論の範疇性」の理論）では、$q\in\mathbb Q$ ごとの論理式 $x_1\neq0\land x_2=\lambda_q(x_1)$ が互いに両立せず、どれも充足可能なので、$S_2(T_{\mathbb Q})$ は無限である。
- 標数 $0$ の代数閉体の理論 $\mathrm{ACF}_0$ では、$m\in\mathbb N$ ごとの論理式 $x=1+\cdots+1$（$m$ 個の和）が互いに両立せず、$S_1(\mathrm{ACF}_0)$ は無限である。
- $\operatorname{Th}(\mathbb Z,<)$ では、$k\ge1$ ごとの論理式「$x_1< x_2$ で、間にちょうど $k-1$ 個の元がある」が互いに両立せず、$S_2$ は無限である。一方 $S_1$ は 1 点である。
1・2 の理論が完全であることは、カテゴリー性 の節「Łoś–Vaught の判定法との関係」と 完全な理論 の例「完全な理論と完全でない理論」による。互いに両立しない論理式は相異なる型に属するので、型は無限個ある。1：$x_1\neq0$ で $\lambda_q(x_1)=\lambda_r(x_1)$ なら $(q-r)x_1=0$ から $q=r$ である。2：標数 $0$ では $m\cdot1\neq m'\cdot1$（$m\neq m'$）である。3：$\operatorname{Th}(\mathbb Z,<)$ は構造の理論なので完全で、$\mathbb Z$ で 2 元の間の元の個数は一意に決まる。$S_1$ については、平行移動 $x\mapsto x+k$ が自己同型なので、各論理式 $\varphi(x)$ について文 $\forall x\,\forall y\,(\varphi(x)\leftrightarrow\varphi(y))$ が $\mathbb Z$ で真であり、$T$ に属する。$p\in S_1(T)$ を実現する元 $a$ と $\mathbb Z$ の元 $0$ について、$\varphi\in\operatorname{tp}(0)$ なら $\mathbb Z\models\forall x\,\varphi(x)$ なので $T\models\forall x\,\varphi(x)$、したがって $\varphi\in p$ である。よって $p=\operatorname{tp}(0)$ である。$\square$
反例：条件を外すと成り立たない
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-rn-main の「$T$ が完全」 | 言語 $\{P\}$ で、$I_\infty$ に文 $\forall x\,P(x)\lor\forall x\,\lnot P(x)$ を加えた理論 | 2 ⇒ 1 |
| thm-rn-main の 2 の「各 $n$ について」（$n=1$ だけにする） | $\operatorname{Th}(\mathbb Z,<)$ | 2 ⇒ 1 |
| thm-rn-oligomorphic の「$M$ が可算」 | 同値関係の理論 $T_E$ の、類の濃度が $\aleph_0,\aleph_1,\aleph_2,\dots$ のモデル | $\omega$-範疇的なら軌道が有限個であること |
1 行目：この理論 $T'$ の完全な拡張は、$\forall x\,P(x)$ を加えたものと $\forall x\,\lnot P(x)$ を加えたものの 2 つで、どちらでも $P(x)$ は $x=x$ か $x\neq x$ と同値になるので、型は等しさの指定で決まり（ex-rn-sets-dlo）、$S_n(T')$ は有限である。しかし $P$ が全体の可算なモデルと空の可算なモデルは同型でない。
2 行目：ex-rn-non-examples の 3 のとおり、$S_1$ は有限だが $S_2$ は無限なので、thm-rn-main により $\omega$-範疇的でない。
3 行目：$T_E$ は、$E$ が同値関係で、類が無限個あり、どの類も無限であることを表す文からなる理論とする。可算なモデルでは類は可算無限個で、どの類も可算無限なので、類どうしの全単射と各類の中の全単射を合わせて同型が作れる。有限のモデルはないので Łoś–Vaught の判定法により完全で、$\omega$-範疇的である。類 $C_k$ の濃度が $\aleph_k$（$k\in\mathbb N$）のモデル $M$ では、自己同型は類を類へ濃度を保って移すので各 $C_k$ を動かさず、異なる類の元は異なる軌道に属する。よって $M$ の軌道は無限個である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
