Keisler–Shelahの同型定理

同義語:Keisler–Shelahの定理Keisler–Shelah isomorphism theoremKeisler–Shelah theoremKeisler–Shelah ultrapower theorem

概要

Keisler–Shelahの同型定理(Keisler–Shelah isomorphism theorem)とは、同じ言語の 2 つの構造が初等同値であることと、ある集合の上のある超フィルターについて両者の超冪が同型であることが同値である、という定理である。同型な超冪をもてば初等同値であることは Łoś の定理から従い、逆向きは Keisler が一般連続体仮説のもとで、Shelah が仮定なしに示した。連続体仮説のもとでは、可算言語で濃度が連続体以下の初等同値な構造の $\omega$ 上の非主超冪は、可算集合の上の型をすべて実現する濃度 $\aleph_1$ の飽和モデルとなり、同型である。帰結として、初等クラスは超積と超冪で特徴づけられる。

$$\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}} $$

前提知識: 超積, Łośの定理, 初等同値, 超フィルター, 型(モデル理論)

Keisler–Shelah の同型定理(Keisler–Shelah isomorphism theorem)は、同じ言語の 2 つの構造 $\mathcal M,\mathcal N$ が 初等同値 であることと、ある集合 $I$ の上のある超フィルター $D$ について超冪 $\mathcal M^I/D$ と $\mathcal N^I/D$ が同型であることが同値である、という定理である。初等同値は「同じ一階の文を満たす」という論理の言葉で定義される関係だが、この定理により、超冪と同型という構造だけの言葉で言い換えられる。H. J. Keisler が一般連続体仮説(GCH)を仮定して 1961 年に示し、S. Shelah が 1971 年に GCH なしで示した。
初等同値な構造の超冪が同型になることの一般の証明は、超フィルターを超限帰納法で組み立てる長いもので、この記事では主張と帰属にとどめる。逆向き(同型な超冪をもてば初等同値)は Łośの定理 からすぐに従うので証明する。さらに、連続体仮説 のもとで、可算言語の濃度が連続体以下の構造については、$\omega$ の上のどの非主超フィルターでも超冪が同型になること(thm-ks-ch)を完全に証明する。鍵は、$\omega$ を添字とする超積が可算集合の上の型をすべて実現すること(lem-ks-aleph1)である。最後に、主定理の帰結として、理論のモデルの全体として書けるクラスを超積で特徴づける。

主張

以下、$L$ は一階言語、構造の台集合は空でなく、基数の議論では選択公理を仮定する。$I$ 上の超フィルター $D$ による超冪 $\mathcal M^I/D$ と対角写像 $d\colon M\to M^I/D$ は 超積 の定義「超積と超冪」のとおりとする。

Keisler–Shelah の同型定理

$\mathcal M,\mathcal N$ を $L$ 構造とする。次は同値である。

  1. $\mathcal M\equiv\mathcal N$。
  2. ある集合 $I$ と $I$ 上のある超フィルター $D$ について、$\mathcal M^I/D\cong\mathcal N^I/D$。
    さらに、無限基数 $\lambda$ ごとに $\mu=\min\{\mu'\mid 2^{\mu'}>\lambda\}$ とおくと、$\lambda$ 上のある超フィルター $D$ で、濃度が $\mu$ 未満の初等同値な構造 $\mathcal M\equiv\mathcal N$(言語は共通)について必ず $\mathcal M^\lambda/D\cong\mathcal N^\lambda/D$ となるものがある。
出典と証明の所在

2 から 1 を導く部分は下の prf-ks-easy で証明する。1 から 2 を導く部分と後半は She71 の冒頭の Theorem の (1)(p. 224)で、この記事では証明しない。同論文の主定理の証明の冒頭(p. 230)は、濃度が $\mu$ 未満の構造の言語を、濃度 $\lambda$ の 1 つの言語の部分言語に取り替えてよいことを注意しており、後半の主張は言語の大きさに仮定を置かない。同論文の序文(p. 224)によれば、Keisler Kei61 は $2^\lambda=\lambda^+$ を仮定して、言語の濃度が $\lambda$ 以下で濃度が $\lambda$ 以下の初等同値な構造について、$\lambda$ 上の 1 つの超フィルターで超冪が同型になることを示した。Shelah の証明(同論文 pp. 230–232)は、超フィルターを $2^\lambda$ 段の超限帰納法で組み立て、各段で同型写像の定義域と値域を広げ、同時に超冪の飽和性を確保する。

対角写像で文を移す

2 を仮定する。Łośの定理 の系「対角写像は初等埋め込み」により $\mathcal M\equiv\mathcal M^I/D$、$\mathcal N\equiv\mathcal N^I/D$ である。同型写像は文の真偽を保つので $\mathcal M^I/D\equiv\mathcal N^I/D$ である。初等同値は同値関係なので $\mathcal M\equiv\mathcal N$ となる。$\square$

後半で $\lambda=2^{\aleph_0}$ とすると、$2^{\aleph_0}$ は $2^{\aleph_0}$ より大きくないので $\mu>\aleph_0$ である。したがって、濃度 $2^{\aleph_0}$ の集合の上の 1 つの超フィルター $D$ で、初等同値な可算構造の組をすべて同型な超冪に移すものがある。添字集合を $\omega$ にとれるかは、次の節で見るように集合論の仮定に関わる。

可算添字の超積の飽和性

$A\subset M$ について、$S^{\mathcal M}(A)$ は $A$ の元をパラメータとする 1 変数の論理式の集合で、$\mathcal M$ で有限充足可能かつ各論理式かその否定を含むもの(完全型)の全体とする(安定性理論 の定義「完全型」)。

$\aleph_1$-飽和

$\mathcal M$ が $\aleph_1$-飽和 であるとは、$M$ の可算部分集合 $A$ ごとに、$S^{\mathcal M}(A)$ のすべての型が $\mathcal M$ の元で実現されることをいう。$\lvert M\rvert=\aleph_1$ の構造が $\aleph_1$-飽和であることは、Morleyの範疇性定理 の定義「飽和モデル」の意味で飽和であることと同じである(濃度が $\aleph_1$ 未満の集合は可算だから)。

可算添字の超積は $\aleph_1$-飽和

$L$ を可算言語、$D$ を $\omega$ 上の非主超フィルター、$(\mathcal M_i)_{i<\omega}$ を $L$ 構造の列とする。このとき超積 $\prod_{i<\omega}\mathcal M_i/D$ は $\aleph_1$-飽和である。

段ごとに満たす論理式を増やす

$\mathcal P=\prod_{i<\omega}\mathcal M_i/D$ とおく。$D$ は非主なので有限集合を含まない(有限集合 $F\in D$ なら、$F$ の 1 点集合のどれかが $D$ に入り、$D$ は主超フィルターになる)。よって補集合が有限な集合はすべて $D$ に入り、とくに $\{i\mid i\ge n\}\in D$ である。
$A\subset P$ を可算集合、$p\in S^{\mathcal P}(A)$ とする。$A$ の各元 $a$ に代表元 $f_a\in\prod_iM_i$ を 1 つ選ぶ。$L$ と $A$ が可算なので $p$ は可算集合であり、$p=\{\varphi_n(x,\bar a_n)\mid n<\omega\}$ と(重複を許して)並べる。ここで $\bar a_n$ は $A$ の元の組で、$\bar a_n(i)$ はその代表元の第 $i$ 成分の組を表す。$\psi_n=\varphi_0\land\cdots\land\varphi_n$ とおく。
$p$ は $\mathcal P$ で有限充足可能なので $\mathcal P\models\exists x\,\psi_n(x,\bar a)$ であり、Łośの定理 により $Y_n=\{i\mid\mathcal M_i\models\exists x\,\psi_n(x,\bar a(i))\}\in D$ である。$X_n=Y_n\cap\{i\mid i\ge n\}$ とおくと $X_n\in D$ で、$\psi_{n+1}$ は $\psi_n$ を導くので $X_0\supseteq X_1\supseteq\cdots$ である。$i\in X_0$ なら $\{n\mid i\in X_n\}$ は $\{0,1,\dots,i\}$ に含まれる空でない集合なので最大元 $n(i)$ をもつ。$i\in X_0$ のとき $\mathcal M_i\models\psi_{n(i)}(g(i),\bar a(i))$ となる $g(i)\in M_i$ を選び、$i\notin X_0$ のときは $g(i)\in M_i$ を任意に選ぶ。
$n$ を固定する。$i\in X_n$ なら $n(i)\ge n$ なので、$\psi_{n(i)}$ が $\varphi_n$ を導くことから $\mathcal M_i\models\varphi_n(g(i),\bar a_n(i))$ である。よって $\{i\mid\mathcal M_i\models\varphi_n(g(i),\bar a_n(i))\}\supseteq X_n$ は $D$ に入り、Łośの定理 により $\mathcal P\models\varphi_n([g],\bar a_n)$ である。これがすべての $n$ で成り立つので、$[g]$ は $p$ を実現する。$\square$

連続体仮説のもとでの同型

連続体仮説のもとでの可算添字の同型

連続体仮説 $2^{\aleph_0}=\aleph_1$ を仮定する。$L$ を可算言語、$\mathcal M,\mathcal N$ を $\mathcal M\equiv\mathcal N$ かつ $\lvert M\rvert,\lvert N\rvert\le2^{\aleph_0}$ を満たす $L$ 構造、$D$ を $\omega$ 上の非主超フィルターとする。このとき $\mathcal M^\omega/D\cong\mathcal N^\omega/D$ である。

濃度 $\aleph_1$ の飽和モデルに帰着する

$\mathcal M$ が有限の場合:初等同値 の定理「有限構造は初等同値なら同型」により同型 $h\colon\mathcal M\to\mathcal N$ がある。$[f]\mapsto[h\circ f]$ は代表元によらず($f\sim_Df'$ なら $h\circ f\sim_Dh\circ f'$)、関係・関数・定数の解釈を成分ごとに保つ全単射なので、$\mathcal M^\omega/D\cong\mathcal N^\omega/D$ である。
$\mathcal M$ が無限の場合:$n$ 個以上の元があることを述べる文は $\mathcal M$ で真なので $\mathcal N$ でも真であり、$\mathcal N$ も無限である。超積 の命題「可算添字の非主超冪の濃度」により $\lvert M^\omega/D\rvert=\lvert N^\omega/D\rvert=2^{\aleph_0}$ で、仮定よりこれは $\aleph_1$ に等しい。lem-ks-aleph1 により両者は $\aleph_1$-飽和であり、def-ks-aleph1 で注意したとおり飽和である。また Łośの定理 の系「対角写像は初等埋め込み」により
$$ \operatorname{Th}(\mathcal M^\omega/D)=\operatorname{Th}(\mathcal M)=\operatorname{Th}(\mathcal N)=\operatorname{Th}(\mathcal N^\omega/D) $$
であり、これは完全な理論である。同じ濃度の飽和モデルは同型である(Morleyの範疇性定理 の定理「飽和モデルの一意性」)から、$\mathcal M^\omega/D\cong\mathcal N^\omega/D$ となる。$\square$

thm-ks-ch では超フィルターを選ぶ必要がなく、$\omega$ 上のどの非主超フィルターでもよい。連続体仮説を外すと、この証明のうち超冪の濃度が $\aleph_1$ になる段が使えず、$\aleph_1$-飽和からは同型が導けなくなる。添字集合を濃度 $2^{\aleph_0}$ の集合にとれば集合論の仮定なしに同型な超冪が得られることは、thm-ks-main の後半($\lambda=2^{\aleph_0}$ の場合)が述べている。

帰結:初等クラスの特徴づけ

$L$ 構造のクラス $\mathcal K$ が同型で閉じているとする。$\mathcal K$ の元の族の超積がつねに $\mathcal K$ に入るとき $\mathcal K$ は 超積で閉じている といい、$\mathcal M\in\mathcal K$ の超冪がつねに $\mathcal K$ に入るとき 超冪で閉じている という。$L$ の文の集合 $T$ のモデルの全体 $\operatorname{Mod}(T)$ として書けるクラスを 初等クラス という。

初等クラスの判定法

同型で閉じた $L$ 構造のクラス $\mathcal K$ について、次が成り立つ。

  1. $\mathcal K$ が初等クラスであることは、$\mathcal K$ が超積で閉じていて、補クラス($\mathcal K$ に属さない $L$ 構造の全体)が超冪で閉じていることと同値である。
  2. $\mathcal K=\operatorname{Mod}(\{\sigma\})$ となる 1 つの文 $\sigma$ があることは、$\mathcal K$ と補クラスがともに超積で閉じていることと同値である。
文の有限集合ごとにモデルを選んで超積をとる

1 の前向き:$\mathcal K=\operatorname{Mod}(T)$ とする。Łośの定理 の系「文の真偽と理論のモデル」により、$T$ のモデルの超積は $T$ のモデルである。$\mathcal M\notin\mathcal K$ なら $\mathcal M\models\lnot\sigma$ となる $\sigma\in T$ があり、超冪 $\mathcal M^I/D$ も $\lnot\sigma$ を満たすので $\mathcal K$ に属さない。
1 の後ろ向き:$T$ を、$\mathcal K$ のすべての元で真な文の全体とする。$\mathcal K\subseteq\operatorname{Mod}(T)$ は明らかなので、$\mathcal M\models T$ から $\mathcal M\in\mathcal K$ を導く。$\Sigma=\operatorname{Th}(\mathcal M)$ とし、$I$ を $\Sigma$ の有限部分集合の全体とする。$\Delta\in I$ について、$\bigwedge\Delta$ を満たす $\mathcal K_\Delta\in\mathcal K$ がある(なければ $\lnot\bigwedge\Delta\in T$ となり、$\mathcal M\models T$ と $\mathcal M\models\bigwedge\Delta$ に反する)。$\sigma\in\Sigma$ について $\hat\sigma=\{\Delta\in I\mid\sigma\in\Delta\}$ とおくと、$\hat\sigma_1\cap\cdots\cap\hat\sigma_k\ni\{\sigma_1,\dots,\sigma_k\}$ なので $\{\hat\sigma\}_\sigma$ は有限交叉性をもち、これらを含む $I$ 上の超フィルター $E$ がある(超フィルター)。$\mathcal N=\prod_\Delta\mathcal K_\Delta/E$ とおくと、$\sigma\in\Sigma$ について $\{\Delta\mid\mathcal K_\Delta\models\sigma\}\supseteq\hat\sigma\in E$ なので $\mathcal N\models\sigma$ である。$\Sigma$ は完全な理論なので $\mathcal N\equiv\mathcal M$ であり、仮定より $\mathcal N\in\mathcal K$ である。thm-ks-main により $\mathcal M^J/F\cong\mathcal N^J/F$ となる $J$ と $F$ がある。$\mathcal N^J/F$ は $\mathcal K$ の元の超積なので $\mathcal K$ に属し、同型で閉じていることから $\mathcal M^J/F\in\mathcal K$ である。$\mathcal M\notin\mathcal K$ なら補クラスが超冪で閉じていることに反するので、$\mathcal M\in\mathcal K$ である。
2 の前向き:$\operatorname{Mod}(\{\sigma\})$ も $\operatorname{Mod}(\{\lnot\sigma\})$ も、Łośの定理 の系「文の真偽と理論のモデル」により超積で閉じている。
2 の後ろ向き:補クラスは超冪でも閉じているので、1 により $\mathcal K=\operatorname{Mod}(T)$ となる $T$ がある。$T$ のある有限部分集合 $T_0$ について $\operatorname{Mod}(T_0)=\operatorname{Mod}(T)$ となることを示せば、$\sigma=\bigwedge T_0$ でよい。そうでないとすると、$T$ の有限部分集合 $\Delta$ ごとに $\mathcal M_\Delta\models\Delta$、$\mathcal M_\Delta\notin\mathcal K$ となる構造がある。上と同じく $\hat\sigma=\{\Delta\mid\sigma\in\Delta\}$($\sigma\in T$)を含む超フィルター $E$ をとると、$\prod_\Delta\mathcal M_\Delta/E$ は $T$ のすべての文を満たして $\mathcal K$ に属するが、補クラスの元の超積なので補クラスに属する。これは矛盾である。$\square$

1 の後ろ向きの証明と、それを使う 2 の後ろ向きの証明は、thm-ks-main の 1 から 2 への向き(この記事では証明していない部分)に依存する。前向きの 2 つは Łośの定理 だけで閉じている。

例

構造のない無限集合

記号をもたない言語(等号だけ)では、無限集合どうしはつねに初等同値である(初等同値 の例「無限集合」)。$M,N$ を濃度 $2^{\aleph_0}$ 以下の無限集合、$D$ を $\omega$ 上の非主超フィルターとすると、超積 の命題「可算添字の非主超冪の濃度」により $M^\omega/D$ と $N^\omega/D$ はどちらも濃度 $2^{\aleph_0}$ であり、この言語では全単射がそのまま同型である。したがってこの場合は、連続体仮説を仮定しなくても thm-ks-ch の結論が成り立つ。たとえば $\mathbb N$ と $\mathbb R$ は同型でないが、$\omega$ 上の非主超冪は同型である。

有理数と実数の順序

$(\mathbb Q,<)$ と $(\mathbb R,<)$ は端点のない稠密な全順序なので初等同値である(初等同値 の例「端点のない稠密な全順序」)。濃度が違うので同型ではない。$D$ を $\omega$ 上の非主超フィルターとすると、超冪 $\mathbb Q^\omega/D$ と $\mathbb R^\omega/D$ はどちらも濃度 $2^{\aleph_0}$ の端点のない稠密な全順序で、lem-ks-aleph1 によりどちらも $\aleph_1$-飽和である。連続体仮説のもとでは thm-ks-ch により両者は同型になる。thm-ks-main の後半からは、集合論の仮定なしに、$\lambda=2^{2^{\aleph_0}}$ の上のある超フィルター $D'$ で $\mathbb Q^\lambda/D'\cong\mathbb R^\lambda/D'$ となるものがあることが分かる($\mathbb R$ の濃度は $\mu$ 未満でなければならないが、この $\lambda$ では $2^{2^{\aleph_0}}$ は $\lambda$ より大きくないので $\mu>2^{\aleph_0}$ となる)。

反例:仮定を外すと成り立たないこと

thm-ks-ch の仮定を 1 つずつ外す。どの行でも連続体仮説と可算言語の仮定は残している。

外した仮定例成り立たなくなる結論
$\mathcal M\equiv\mathcal N$$\mathcal M=(\mathbb Z,<)$、$\mathcal N=(\mathbb Q,<)$、$D$ は $\omega$ 上の非主超フィルター$\mathcal M^\omega/D\cong\mathcal N^\omega/D$
$D$ は非主$\mathcal M=(\mathbb Q,<)$、$\mathcal N=(\mathbb R,<)$、$D$ は $0$ で生成される主超フィルター$\mathcal M^\omega/D\cong\mathcal N^\omega/D$
$\lvert N\rvert\le2^{\aleph_0}$$\mathcal M=(\mathbb Q,<)$、$\mathcal N$ は濃度 $2^{2^{\aleph_0}}$ の端点のない稠密な全順序、$D$ は $\omega$ 上の非主超フィルター$\mathcal M^\omega/D\cong\mathcal N^\omega/D$
反例の確かめ

要点:1 行目は 2 つの超冪が別の文を満たすこと、2 行目は超冪がもとの構造と同型になること、3 行目は濃度が違うことによる。

詳しい確かめを開く

1 行目:文 $\sigma=\forall x\,\exists y\,(x< y\land\lnot\exists z\,(x< z\land z< y))$(どの元にも直後の元がある)は $(\mathbb Z,<)$ で真、$(\mathbb Q,<)$ で偽である。Łośの定理 の系「対角写像は初等埋め込み」により $\mathbb Z^\omega/D\models\sigma$、$\mathbb Q^\omega/D\models\lnot\sigma$ であり、同型写像は文の真偽を保つので 2 つの超冪は同型でない。ほかの仮定(可算言語、濃度が $2^{\aleph_0}$ 以下、$D$ が非主)は満たされている。

2 行目:$(\mathbb Q,<)\equiv(\mathbb R,<)$ で、濃度はどちらも $2^{\aleph_0}$ 以下である。超積 の命題「主超フィルターの超積」により $\mathbb Q^\omega/D\cong\mathbb Q$、$\mathbb R^\omega/D\cong\mathbb R$ であり、可算集合と非可算集合の間に全単射はないので、2 つの超冪は同型でない。

3 行目:$(\mathbb Q,<)$ は無限のモデルをもつ理論 $\mathrm{DLO}$ のモデルなので、Löwenheim–Skolemの定理 により濃度 $2^{2^{\aleph_0}}$ のモデル $\mathcal N$ があり、初等同値 の例「端点のない稠密な全順序」により $\mathcal N\equiv(\mathbb Q,<)$ である。対角写像は単射なので $\lvert N^\omega/D\rvert\ge2^{2^{\aleph_0}}>2^{\aleph_0}=\lvert\mathbb Q^\omega/D\rvert$(超積 の命題「可算添字の非主超冪の濃度」)であり、2 つの超冪は同型でない。

関連項目

参考文献

[1]
Saharon Shelah, Every two elementarily equivalent models have isomorphic ultrapowers, Israel Journal of Mathematics, 1971, 冒頭の Theorem (1)–(3) と Keisler の結果の紹介 p. 224、主定理の証明(言語の取り替えと、超フィルターを超限帰納法で組み立てる構成)pp. 230–232
[2]
H. Jerome Keisler, Ultraproducts and elementary classes, Indagationes Mathematicae 23(Koninklijke Nederlandse Akademie van Wetenschappen Proceedings Series A 64), pp. 477–495, 1961

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