Vaughtの二基数定理(Vaught's two-cardinal theorem)とは、可算言語の一階の理論が、ある基数 $\kappa>\lambda\ge\aleph_0$ についてモデルの濃度が $\kappa$、1 項述語 $U$ の定める集合の濃度が $\lambda$ となるモデルをもてば、濃度の組が $(\aleph_1,\aleph_0)$ のモデルももつという定理である。これは、初等部分モデル $N\preccurlyeq M$ で $N\ne M$ かつ $U$ の部分が等しく無限なもの(Vaught 対)の存在と同値である。証明では、可算で均質な Vaught 対 $(M,N)$ で $M\cong N$ となるものを作り、同じ形の拡大を $\omega_1$ 回繰り返す。濃度の差を任意に広げる向きには移れない。
前提知識: 初等部分モデル, 型(モデル理論), Löwenheim–Skolemの定理
Vaught の二基数定理(Vaught's two-cardinal theorem)は、可算言語の一階の理論について、「モデル全体の濃度」と「1 項述語 $U$ が表す部分集合の濃度」の組 $(\lvert M\rvert,\lvert U^M\rvert)$ がどんな値をとりうるかを述べる定理である。ある $\kappa>\lambda\ge\aleph_0$ について $\lvert M\rvert=\kappa$、$\lvert U^M\rvert=\lambda$ となるモデルがあれば、$\lvert M\rvert=\aleph_1$、$\lvert U^M\rvert=\aleph_0$ となるモデルもある。2 つの濃度に差をつけられる理論では、その差を最も小さい無限の差 $(\aleph_1,\aleph_0)$ まで縮められる、という主張である。
同じ Vaught の名がつく Vaught予想(可算モデルの個数についての未解決の予想)や Vaughtの定理(可算モデルの個数)(可算モデルがちょうど 2 個にはならない)とは別の定理である。Löwenheim–Skolemの定理 がモデル全体の濃度だけを動かすのに対し、この定理は 2 つの濃度を同時に動かす。この記事では、Vaught 対という言い換え、可算な均質モデルの一意性、$\omega_1$ の長さの初等鎖による証明を与え、差を広げる向きには移れない例を示す。
以下、$L$ は可算な関係言語(関数記号と定数記号をもたない言語)で、1 項の関係記号 $U$ を含むとする。関数記号はそのグラフを表す関係記号に替えればよく、濃度や定義可能な集合は変わらないので、可算言語の一般の場合もここに含まれる。構造の台集合は空でないとし、$L$ 構造 $M$ と同じ文字で台集合も表す。$\bar a$ は有限個の元の組を表し、$\operatorname{tp}^M(\bar a)$ は 型(モデル理論) の定義「実現と省略」の型である。$N\preccurlyeq M$ は $N$ が $M$ の初等部分モデルであることを表す。
$\kappa,\lambda$ を基数とする。
Vaught 対では、$U$ の部分を一つも増やさずにモデル全体だけが真に大きくなっている。理論 $T$ について「$T$ が Vaught 対をもつ」とは、$M\models T$ となる Vaught 対 $(M,N)$ があることをいう(このとき $N\equiv M$ なので $N\models T$ でもある)。
$T$ を可算言語 $L$ の文の集合とする。次は同値である。
1 から 3 を導く部分は MV62 Theorem 6.2(p. 55)で、同論文は §5 以降、可算な添字集合の関係構造に話を限っている(p. 54)。序文(p. 37)はこの節を「2 つの基数についての Löwenheim–Skolem の定理」と呼んでいる。証明の方針(均質な可算モデルの組を作り、$\omega_1$ の長さの鎖を伸ばす)は同じ箇所の証明に従うが、均質性の定義は同論文と異なり、以下ではその定義に合わせて全部を証明する。
$L$ に新しい 1 項の関係記号 $P$ を足した言語を $L_P$ とし、$N\subseteq M$ の組を、$P$ を $N$ と解釈した $L_P$ 構造 $(M,N)$ と見る。$L$ の論理式 $\varphi$ の量化を $P$ に制限したもの($\exists x$ を $\exists x\,(P(x)\land\cdots)$ に替えたもの)を $\varphi^P$ と書く。$N$ が空でなければ、$\bar a\in N$ について $(M,N)\models\varphi^P(\bar a)$ と $N\models\varphi(\bar a)$ は同値である(論理式の構成についての帰納法)。
$T_V$ を、$T$ の文、$\exists x\,P(x)$、$\exists x\,\lnot P(x)$、$\forall x\,(U(x)\to P(x))$、$U$ が少なくとも $n$ 元を含むという文($n\ge1$)、および各 $L$ の論理式 $\varphi(\bar x)$ についての
$$
\forall\bar x\,\Bigl(\textstyle\bigwedge_iP(x_i)\to\bigl(\varphi^P(\bar x)\leftrightarrow\varphi(\bar x)\bigr)\Bigr)
$$
からなる $L_P$ の文の集合とする。最後の文の全体は $N\preccurlyeq M$ を表すので、$(M,N)\models T_V$ であることと、$(M,N)$ が $M\models T$ となる Vaught 対であることは同値である。$L_P$ も可算なので、Vaught 対の性質は $L_P$ の初等部分モデル・初等拡大・初等鎖の和に引き継がれる。とくに $(M,N)\preccurlyeq_{L_P}(M',N')$ なら、$\bar a\in N$ について $N\models\varphi(\bar a)\iff(M,N)\models\varphi^P(\bar a)\iff(M',N')\models\varphi^P(\bar a)\iff N'\models\varphi(\bar a)$ なので $N\preccurlyeq N'$ でもある。
$L$ 構造 $M$ が 均質 であるとは、$\operatorname{tp}^M(\bar a)=\operatorname{tp}^M(\bar b)$ となる同じ長さの組 $\bar a,\bar b$ と $c\in M$ について、$\operatorname{tp}^M(\bar ac)=\operatorname{tp}^M(\bar bd)$ となる $d\in M$ があることをいう。$M$ の組が実現する型の全体 $\{\operatorname{tp}^M(\bar a)\mid\bar a\text{ は }M\text{ の有限の組}\}$ を $\mathcal S(M)$ と書く(空の組も含め、その型は $M$ で真な文の全体とする)。
$N\preccurlyeq M$ なら、$N$ の組の型は $N$ で求めても $M$ で求めても同じなので $\mathcal S(N)\subseteq\mathcal S(M)$ である。
$M,M'$ を可算な均質モデルとし、$\mathcal S(M)=\mathcal S(M')$ とする。このとき $M\cong M'$ である。
$M=\{m_0,m_1,\dots\}$、$M'=\{m'_0,m'_1,\dots\}$ と番号をつける(有限なら途中で止める)。$\operatorname{tp}^M(\bar a)=\operatorname{tp}^{M'}(\bar b)$ となる同じ長さの組の対応 $\bar a\mapsto\bar b$ を「良い対応」と呼ぶ。空の組どうしは、$M,M'$ の理論が $\mathcal S$ の長さ $0$ の元として一致するので良い対応である。
前進. $\bar a\mapsto\bar b$ が良い対応で $c\in M$ とする。$\operatorname{tp}^M(\bar ac)\in\mathcal S(M)=\mathcal S(M')$ なので、$M'$ の組 $\bar b'd'$ で $\operatorname{tp}^{M'}(\bar b'd')=\operatorname{tp}^M(\bar ac)$ となるものがある。$\operatorname{tp}^{M'}(\bar b')=\operatorname{tp}^M(\bar a)=\operatorname{tp}^{M'}(\bar b)$ なので、$M'$ の均質性により $\operatorname{tp}^{M'}(\bar bd)=\operatorname{tp}^{M'}(\bar b'd')$ となる $d\in M'$ がある。よって $\bar ac\mapsto\bar bd$ は良い対応である。
後退. 役割を入れ替えて、$d\in M'$ について $\bar ac\mapsto\bar bd$ が良い対応になる $c\in M$ が、$M$ の均質性から同じように得られる。
第 $2k$ 段で前進により $m_k$ を、第 $2k+1$ 段で後退により $m'_k$ を加えて、良い対応を増大させる。全段の和 $f$ は $M$ から $M'$ への全単射である($x_1=x_2$ が型に入るかどうかで単射性も保たれる)。各関係記号 $R$ と $f$ の定義域の組について、原子論理式 $R(\bar x)$ が型に入るかどうかが一致するので、$f$ は同型である。$\square$
$(M_k)_{k<\delta}$($\delta$ は可算な極限順序数)を可算な均質モデルの初等鎖とし、すべての $k$ で $\mathcal S(M_k)=\mathcal S_0$ とする。和 $M_\delta$ は可算な均質モデルで、$\mathcal S(M_\delta)=\mathcal S_0$ である。
各 $M_k$ は $M_\delta$ の初等部分モデルである(初等部分モデル の定理「初等鎖の和」)。有限個の元は一つの $M_k$ に入るので、$M_\delta$ の組の型はある $M_k$ の組の型で $\mathcal S_0$ に属し、逆に $\mathcal S_0=\mathcal S(M_0)\subseteq\mathcal S(M_\delta)$ である。$\operatorname{tp}^{M_\delta}(\bar a)=\operatorname{tp}^{M_\delta}(\bar b)$、$c\in M_\delta$ なら、$\bar a,\bar b,c$ を含む $M_k$ で型は等しく、$M_k$ の均質性から $d\in M_k$ で $\operatorname{tp}^{M_k}(\bar ac)=\operatorname{tp}^{M_k}(\bar bd)$ となるものがあり、初等性によりこれは $M_\delta$ での型でもある。可算個の可算集合の和なので $M_\delta$ は可算である。$\square$
$T$ が Vaught 対をもてば、$M\models T$ となる Vaught 対 $(M,N)$ で、$M,N$ がともに可算かつ均質で $\mathcal S(M)=\mathcal S(N)$ となるものがある。とくに lem-v2c-unique により $M\cong N$ である。
出発点. $T_V$ はモデルをもつので、初等部分モデル の定理「下向き Löwenheim–Skolem の定理」を可算言語 $L_P$ で使って、可算な $(M_0,N_0)\models T_V$ がとれる。
1 段の拡大. $(M',N')\models T_V$ を可算とする。$L_P$ の論理式の集合 $\Sigma(\bar y)$(パラメータは $M'$ の元)が $(M',N')$ で有限充足可能なら、モデル理論 の命題「型の実現定理」により $\Sigma$ を実現する $L_P$ の初等拡大があり、下向き Löwenheim–Skolem の定理でその中から $M'$ と実現する組を含む可算な初等部分モデル $(M'',N'')$ がとれる。これは $T_V$ のモデルで、$(M',N')\preccurlyeq_{L_P}(M'',N'')$ である。次の 3 種類の $\Sigma$ はどれも有限充足可能である((b)(c) の $\varphi$ は $L$ の論理式を動く)。$\Sigma$ の有限部分集合の連言は、型が連言で閉じているので一つの論理式 $\varphi$ で代表させてよい。
(a) $p\in\mathcal S(M')$ について $\Sigma(\bar y)=p(\bar y)\cup\{P(y_i)\}_i$。$\varphi\in p$ なら $M'\models\exists\bar y\,\varphi$ で、$N'\preccurlyeq M'$ から $N'$ にも $\varphi$ を満たす組があり、その組は $M'$ でも $\varphi$ を満たす。
(b) $\bar a,\bar b\in M'$、$\operatorname{tp}^{M'}(\bar a)=\operatorname{tp}^{M'}(\bar b)$、$c\in M'$ について $\Sigma(y)=\{\varphi(\bar b,y)\mid M'\models\varphi(\bar a,c)\}$。$M'\models\varphi(\bar a,c)$ なら $\exists y\,\varphi(\bar x,y)$ は $\bar a$ の型、したがって $\bar b$ の型に入る。
(c) $\bar a,\bar b\in N'$、$\operatorname{tp}^{N'}(\bar a)=\operatorname{tp}^{N'}(\bar b)$、$c\in N'$ について $\Sigma(y)=\{\varphi(\bar b,y)\mid M'\models\varphi(\bar a,c)\}\cup\{P(y)\}$。(b) と同じ理由で $N'\models\exists y\,\varphi(\bar b,y)$ となり、$N'$ の証人は $N'\preccurlyeq M'$ により $M'$ でも $\varphi(\bar b,y)$ を満たす($N'$ の組の型は $N'$ と $M'$ で同じ)。
鎖. 可算な $L_P$ の初等鎖 $(M_k,N_k)_{k<\omega}$ を作る。各段 $k$ で、(a) の $p\in\mathcal S(M_k)$、(b) の $(\bar a,\bar b,c)$、(c) の $(\bar a,\bar b,c)$ の課題は合わせて可算個である(可算な構造の有限の組は可算個)。全段の課題に $\omega\times\omega$ の番号 $(k,j)$ をつけ、全単射 $\pi\colon\omega\times\omega\to\omega$ で $\pi(k,j)\ge k$ となるもの(例えば Cantor の対関数)を固定する。第 $l$ 段では $\pi(k,j)=l$ の課題を 1 段の拡大でこなして $(M_{l+1},N_{l+1})$ とする。課題 (b)(c) の型の等式は $M_k$ から $M_l$ へ、$N_k$ から $N_l$ へ初等性で引き継がれるので、課題はそのまま意味をもつ。
和. $M:=\bigcup_kM_k$、$N:=\bigcup_kN_k$ とおくと、$(M,N)$ は初等鎖の和として各段の $L_P$ の初等拡大で、$T_V$ のモデル、すなわち Vaught 対である。$M,N$ は可算である。$M_k\preccurlyeq M$ かつ $N_k\preccurlyeq N$ である。(b) の課題により $M$ は均質($M$ の $\bar a,\bar b,c$ はある $M_k$ に入り、そこで型が等しい)、(c) の課題により $N$ は均質である。$p\in\mathcal S(M)$ はある $\mathcal S(M_k)$ に属し、(a) の課題により $N$ で実現されるので $\mathcal S(M)\subseteq\mathcal S(N)$、逆の包含は $N\preccurlyeq M$ による。$\square$
1 ⇒ 2. $M\models T$ を $(\kappa,\lambda)$ 型、$\kappa>\lambda\ge\aleph_0$ とする。下向き Löwenheim–Skolem の定理により、$U^M\subseteq N\preccurlyeq M$、$\lvert N\rvert\le\lambda+\aleph_0=\lambda$ となる $N$ がある。$\lvert N\rvert<\kappa$ なので $N\ne M$、$U^N=U^M\cap N=U^M$ は無限で、$(M,N)$ は Vaught 対である。
3 ⇒ 1. $\kappa=\aleph_1$、$\lambda=\aleph_0$ とすればよい。
2 ⇒ 3. prop-v2c-homogeneous-pair の Vaught 対 $(M,N)$ をとり、$\mathcal S_0:=\mathcal S(M)$ とおく。$\alpha\le\omega_1$ について $L$ 構造 $M_\alpha$ を、次の 3 条件を満たすように作る。
証明の要は、可算な均質モデルが「実現する型」だけで決まること(lem-v2c-unique)である。これにより、組 $(M,N)$ の形の拡大 $N\to M$ を、極限の段を越えても同じ形のまま何度でも繰り返せる。可算な極限で均質性と型が保たれるので、鎖は $\omega_1$ まで伸びる。$\omega_1$ を越えると、極限の段のモデルが非可算になり lem-v2c-unique が使えなくなる。
$U$ を、$L$ の論理式 $\psi(x)$(パラメータなし)が定める集合に替えても同じ定理が成り立つ。新しい記号 $U$ と文 $\forall x\,(U(x)\leftrightarrow\psi(x))$ を足せば、モデルの濃度も $U$ の濃度も変わらないからである。
$L=\{U,R\}$($R$ は 2 項)とし、$\kappa\ge\lambda\ge\aleph_0$ について、台集合を $(\kappa\times\lambda)\sqcup\lambda$、$U$ を後ろの $\lambda$、$R$ を射影 $(\alpha,\beta)\mapsto\beta$ のグラフとする構造 $M_{\kappa,\lambda}$ を考える。$M_{\kappa,\lambda}$ は $(\kappa,\lambda)$ 型で、$\kappa>\lambda$ のとき $T:=\operatorname{Th}(M_{\kappa,\lambda})$ は thm-v2c-main の 1 を満たす。したがって $T$ は Vaught 対と $(\aleph_1,\aleph_0)$ 型のモデルをもつ。$U$ の各元の上の「ファイバー」をモデル全体より小さい $U$ を保ったまま太らせられることが、二基数のモデルがあることの典型的な形である。
$L=\{U,F\}$($F$ は 2 項)とし、$T$ を「$U$ は無限」「$F$ は $U$ の外から $U$ への全単射のグラフ」という文からなる理論とする。モデル $M$ では $\lvert M\rvert=\lvert U^M\rvert+\lvert U^M\rvert=\lvert U^M\rvert$ なので、$\kappa>\lambda\ge\aleph_0$ の $(\kappa,\lambda)$ 型のモデルはない。thm-v2c-main により Vaught 対もないが、これは直接にも分かる。$(M,N)$ を Vaught 対とし $m\in M\setminus N$ とすると、$U^M=U^N\subseteq N$ なので $m\notin U^M$、$F$ による像 $u\in U^M=U^N$ は $N$ に属する。$N\models\exists x\,F(x,u)$ の $N$ の証人 $x$ は、$N\preccurlyeq M$ により $M$ でも $F(x,u)$ を満たし、$F$ の単射性から $x=m$ となって $m\in N$ に反する。
Morleyの範疇性定理 の記事の強極小な理論で、$U$ が無限の集合を定めるなら、$U$ の補集合は有限で、$T$ が完全ならその元の個数 $n$ は全モデルで同じなので、$\lvert M\rvert=\lvert U^M\rvert+n$ となり、やはり二基数のモデルはない。
$L=\{U,E\}$($E$ は 2 項)とし、可算無限集合 $X$ と、その冪集合 $\mathcal P(X)$ の互いに交わらない写しの和を台集合、$U:=X$、$E(x,y):\iff x\in X,\ y\in\mathcal P(X),\ x\in y$ とする構造を $A$ とする。$A$ は文
$$
\forall y\,\forall y'\,\Bigl(\lnot U(y)\land\lnot U(y')\land\forall x\,\bigl(E(x,y)\leftrightarrow E(x,y')\bigr)\to y=y'\Bigr)
$$
を満たし、$(2^{\aleph_0},\aleph_0)$ 型である。$T:=\operatorname{Th}(A)$ のモデル $M$ では、$y\mapsto\{x\in U^M\mid M\models E(x,y)\}$ が $M\setminus U^M$ から $\mathcal P(U^M)$ への単射になるので $\lvert M\rvert\le\lvert U^M\rvert+2^{\lvert U^M\rvert}$ である。よって $T$ は $(\kappa,\aleph_0)$ 型($\kappa>2^{\aleph_0}$)のモデルをもたない。thm-v2c-main は差を $(\aleph_1,\aleph_0)$ へ縮めるだけで、任意の $(\kappa',\lambda')$ へ移せるわけではない。この例は MV62 p. 55 が R. Robinson のものとして挙げている。
thm-v2c-main の「1 ならば 3」の仮定を一つずつ外すと、結論「$(\aleph_1,\aleph_0)$ 型のモデルをもつ」が成り立たなくなる。
| 外した仮定 | 理論 $T$ | 成り立たなくなる結論 |
|---|---|---|
| 言語が可算 | $\{U\}$ と $\aleph_2$ 個の定数記号 $c_\alpha$ の言語で、$c_\alpha\ne c_\beta$($\alpha\ne\beta$)、$\lnot U(c_\alpha)$、$U$ が無限という文 | $(\aleph_2,\aleph_0)$ 型のモデルはあるが、モデルは $\aleph_2$ 個以上の元をもつので $(\aleph_1,\aleph_0)$ 型のモデルはない |
| $\lambda\ge\aleph_0$($U$ が無限) | $L=\{U\}$ で「$U$ はちょうど 1 元」「全体は無限」 | どの無限の $\kappa$ でも $(\kappa,1)$ 型のモデルはあるが、$U^M$ はつねに 1 元なので $(\aleph_1,\aleph_0)$ 型のモデルはない |
| $\kappa>\lambda$ | ex-v2c-bijection の理論 | $(\aleph_0,\aleph_0)$ 型のモデルはあるが、$\lvert M\rvert=\lvert U^M\rvert$ なので $(\aleph_1,\aleph_0)$ 型のモデルはない |
第 1 行で $(\aleph_2,\aleph_0)$ 型のモデルは、$\aleph_2$ 個の定数を $U$ の外の相異なる元とし、$U$ を可算無限にとれば得られる。第 2 行・第 3 行の理論のモデルは、定めた条件を満たす集合と写像を選べばよい。
$(\aleph_1,\aleph_0)$ を $(\kappa^+,\kappa)$ に替えた移行が成り立つかは、MV62 p. 56 が 1962 年の時点で分からないと述べた問題で、その後 Chang(1965 年)や Keisler(1966 年)らが研究した。一方、可算言語の $(\aleph_2,\aleph_1)$ 型の構造がどれも $(\aleph_1,\aleph_0)$ 型の初等部分構造をもつという命題は、Chang の予想と呼ばれる。KM78 p. 212 は、Chang らが調べたこの種の関係のうち、ZFC で否定できると知られていない最も低い段のものとして Chang の予想を挙げ、ラムジー基数の存在が無矛盾ならこの予想も無矛盾であるという Silver の定理を述べている。二基数定理が理論の「あるモデル」の存在を述べるのに対し、Chang の予想は「与えられたどの構造」にも初等部分構造があるという主張である点が違う。
二基数のモデルがないことは、理論の構造についての条件としても使われる。例えば、強極小で完全な理論では、$U$ が無限集合を定めるとき二基数のモデルがない(ex-v2c-bijection の後半)ので、thm-v2c-main により $U$ についての Vaught 対もない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する