Ehrenfeucht–Mostowski模型

同義語:Ehrenfeucht-Mostowski模型Ehrenfeucht–MostowskiモデルEhrenfeucht–Mostowski model

概要

Ehrenfeucht–Mostowski模型(Ehrenfeucht–Mostowski model)とは、一階の理論のモデルのうち、全順序集合で添字づけられた識別不能列から Skolem 関数で生成されるもので、識別不能列とは論理式が添字の大小の順序以外に何も区別しない列をいう。無限のモデルをもつ理論は、任意の全順序集合で添字づけられた識別不能列を含むモデルをもつ(Ehrenfeucht–Mostowski、Ramsey の定理とコンパクト性定理による)。識別不能列から生成したモデルでは添字の順序の自己同型がモデルの自己同型に延び、濃度 $\kappa$ で $2^\kappa$ 個の自己同型をもつモデルや、可算言語のとき可算部分集合の上で可算個の型しか実現しないモデル(Morley)が得られる。

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

前提知識: 一階述語論理, コンパクト性定理(一階論理), Ramseyの定理, 初等部分モデル

Ehrenfeucht–Mostowski模型(Ehrenfeucht–Mostowski model)は、一階の理論のモデルのうち、任意に与えた全順序集合 $(I,<)$ で添字づけられた識別不能列(不可識別列ともいう)から Skolem 関数で生成されるものである。識別不能列 $(a_i)_{i\in I}$ とは、論理式が添字の大小の順序以外に何も区別しない列のことで、増加する添字の組 $i_1< \dots< i_n$ と $j_1< \dots< j_n$ について $\varphi(a_{i_1},\dots,a_{i_n})$ と $\varphi(a_{j_1},\dots,a_{j_n})$ の真偽がつねに一致する。
この記事の主定理(thm-em-existence)は Ehrenfeucht と Mostowski(1956 年、EM56)による。無限のモデルをもつ理論は、どんな全順序集合で添字づけられた識別不能列を含むモデルももつ。 証明は、有限の段階を無限集合の部分集合の塗り分けの定理(lem-em-ramsey)で作り、全体を コンパクト性定理(一階論理) でまとめる。Ehrenfeucht と Mostowski はこの考えを、多くの自己同型をもつモデルを作るために導入した(KM78 p. 131)。
識別不能列から Skolem 関数で生成したモデルでは、添字の順序の自己同型がモデルの自己同型に延びる(thm-em-functor)。この性質から、無限のモデルをもつ理論は濃度 $\kappa$ で $2^\kappa$ 個の自己同型をもつモデルをもつこと(cor-em-automorphisms)と、可算言語なら可算部分集合の上で可算個の型しか実現しないモデルをもつこと(thm-em-few-types)を証明する。後者は Morley が Morleyの範疇性定理 の証明に使った。最後に、0♯ の Silver の識別不能元との関係を述べる。

識別不能列

以下、$L$ は一階の言語、モデルや構造は $L$ 構造とする。全順序集合 $(I,<)$ の元の組 $(i_1,\dots,i_n)$ が $i_1< \dots< i_n$ を満たすとき増加する組といい、$\bar\imath$ と略す。列 $(a_i)_{i\in I}$ と組 $\bar\imath$ について $a_{\bar\imath}:=(a_{i_1},\dots,a_{i_n})$ と書く。

識別不能列と Ehrenfeucht–Mostowski 型

$M$ を構造、$(I,<)$ を全順序集合、$(a_i)_{i\in I}$ を $M$ の元の列とする。
(1) 列 $(a_i)_{i\in I}$ が $M$ の中で識別不能であるとは、各 $n$、各論理式 $\varphi(x_1,\dots,x_n)$、$I$ の増加する組 $\bar\imath,\bar\jmath$(長さ $n$)について
$$ M\models\varphi(a_{\bar\imath})\iff M\models\varphi(a_{\bar\jmath}) $$
が成り立つことをいう。$I$ が無限集合のとき、識別不能な列を識別不能列という。
(2) 列 $(a_i)_{i\in I}$ の Ehrenfeucht–Mostowski 型(EM 型)$\operatorname{EM}(a)$ を、$I$ のすべての増加する組 $\bar\imath$ で $M\models\varphi(a_{\bar\imath})$ となる論理式 $\varphi(x_1,\dots,x_n)$($n\ge1$)の全体とする。

列が識別不能なら、各論理式 $\varphi(x_1,\dots,x_n)$ について $\varphi$ か $\neg\varphi$ のどちらかが $\operatorname{EM}(a)$ に入る($I$ が $n$ 個以上の元をもつとき)。識別不能列は「元の集合」ではなく「添字の順序つきの列」についての条件である。順序を入れ替えた組まで同じ真偽を要求するものは全識別不能(totally indiscernible)という。
識別不能列の元が 1 組でも一致すれば、論理式 $x_1=x_2$ により、すべての元が一致する。以下では、相異なる元からなる識別不能列を考える。

稠密な順序の増加列

$(\mathbb Q,<)$ で、$i< j$ なら $a_i< a_j$ となる列 $(a_i)_{i\in I}$ は識別不能である。実際、$a_{i_1}< \dots< a_{i_n}$ と $a_{j_1}< \dots< a_{j_n}$ について、区間ごとに 1 次式で $a_{i_k}\mapsto a_{j_k}$ とする順序の自己同型 $f\colon\mathbb Q\to\mathbb Q$ がある。自己同型は論理式の真偽を保つ(初等部分モデル の補題「自己同型は真偽を保つ」)ので、$\varphi(a_{\bar\imath})$ と $\varphi(a_{\bar\jmath})$ の真偽は等しい。$\operatorname{EM}(a)$ は $x_1< x_2$ を含み、$x_2< x_1$ を含まないので、この列は全識別不能ではない。

ベクトル空間の基底

体 $K$ 上の無限次元 ベクトル空間 $V$ を、加法と $K$ の各元によるスカラー倍を記号とする言語の構造とみる。基底 $(e_i)_{i\in I}$ は、任意の全順序で添字づけて全識別不能である。基底の元の置換は線形な自己同型に延び、自己同型は真偽を保つからである。

反例:整数の順序には無限の識別不能列がない

$(\mathbb Z,<)$ に、相異なる元からなる識別不能列 $(a_i)_{i\in I}$($I$ は無限)があったとする。論理式 $x_1< x_2$ の真偽は一定なので、列は増加か減少である。増加とし、$i< j< k$ をとる。$m:=a_j-a_i-1$ とし、「$x_1$ と $x_2$ の間にちょうど $m$ 個の元がある」を表す論理式を $\psi_m(x_1,x_2)$ とする。$\psi_m(a_i,a_j)$ が成り立つので、識別不能性から $\psi_m(a_i,a_k)$ も成り立ち、$a_k=a_j$ となって矛盾する。減少の場合も同じである。
一方、$\mathbb Z$ は無限なので、主定理(thm-em-existence)により $(\mathbb Z,<)$ と同じ文を満たす構造 $M$ の中には識別不能列がある。上の議論で使った「$x< y< z$ で $\psi_m(x,y)$ と $\psi_m(x,z)$ が成り立てば $y=z$」は $\mathbb Z$ で真な文なので $M$ でも真であり、$M$ の識別不能列の 2 元の間には、どの $m$ についても $m$ 個ちょうどの元があるのではない、すなわち無限個の元がある。主定理の結論のモデルは、元の構造そのものにはとれない。

主定理

主定理の組合せ論の部分は、無限集合の $n$ 元部分集合を有限個の色で塗ると、無限の単色の部分集合がとれることである。これは Ramsey理論 の定理「無限Ramseyの定理」である($n=2$ は Ramseyの定理 の定理「無限 Ramsey の定理」)。主定理の証明に使うので、証明もここに置く。集合 $X$ の $n$ 元部分集合の全体を $[X]^n$ と書く。

無限集合の $n$ 元部分集合の塗り分け

$n,r\ge1$ とし、$X\subseteq\mathbb N$ を無限集合、$c\colon[X]^n\to\{1,\dots,r\}$ を写像とする。このとき無限集合 $H\subseteq X$ で、$c$ が $[H]^n$ の上で一定であるものがある。

1 点を固定して次元を下げる

$n$ についての帰納法による。$n=1$ は無限集合の 鳩の巣原理 である。$n$ で成り立つとし、$c\colon[X]^{n+1}\to\{1,\dots,r\}$ とする。
無限集合 $A_0:=X$ から始めて、数 $x_1< x_2< \cdots$、色 $\chi_1,\chi_2,\dots$、無限集合 $A_0\supseteq A_1\supseteq\cdots$ を順に定める。$A_{k-1}$ が定まったら $x_k:=\min A_{k-1}$ とし、$[A_{k-1}\setminus\{x_k\}]^n$ を $s\mapsto c(\{x_k\}\cup s)$ で塗る。帰納法の仮定により、無限集合 $A_k\subseteq A_{k-1}\setminus\{x_k\}$ と色 $\chi_k$ で、$s\in[A_k]^n$ ならつねに $c(\{x_k\}\cup s)=\chi_k$ となるものがある。
$A_k$ の元は $x_k$ より大きいので $x_k< x_{k+1}$ である。$k< l$ なら $x_l\in A_{l-1}\subseteq A_k$ だから、$k< l_1< \dots< l_n$ について $c(\{x_k,x_{l_1},\dots,x_{l_n}\})=\chi_k$ である。つまり $\{x_k\mid k\ge1\}$ の $n+1$ 元部分集合の色は、最小の元の番号だけで決まる。鳩の巣原理により、ある色 $\chi$ について $K:=\{k\mid\chi_k=\chi\}$ は無限集合で、$H:=\{x_k\mid k\in K\}$ の $n+1$ 元部分集合の色はすべて $\chi$ である。$\square$

Ehrenfeucht–Mostowski の定理

$A$ を無限の構造、$(b_k)_{k\in\mathbb N}$ を $A$ の相異なる元の列、$(I,<)$ を任意の全順序集合とする。このとき、$A$ と 初等同値 な構造 $M$ と、$M$ の相異なる元からなる識別不能な列 $(a_i)_{i\in I}$ で、$\operatorname{EM}(b)\subseteq\operatorname{EM}(a)$ となるものがある。
とくに、理論 $T$ が無限のモデルをもてば、$T$ のモデルで、$I$ で添字づけられた識別不能列を含むものがある。

有限個の論理式ごとに塗り分け、コンパクト性でまとめる

$L$ に新しい定数記号 $c_i$($i\in I$)を加えた言語を $L(C)$ とし、増加する組 $\bar\imath$ について $c_{\bar\imath}:=(c_{i_1},\dots,c_{i_n})$ と書く。$L(C)$ の文の集合 $\Sigma$ を、次の文全体とする。

  • (S1) $A$ で真な $L$ の文の全体 $\operatorname{Th}(A)$。
  • (S2) $c_i\ne c_j$($i\ne j$)。
  • (S3) $\varphi(c_{\bar\imath})$($\varphi\in\operatorname{EM}(b)$、$\bar\imath$ は増加する組)。
  • (S4) $\varphi(c_{\bar\imath})\leftrightarrow\varphi(c_{\bar\jmath})$($\varphi$ は $L$ の論理式、$\bar\imath,\bar\jmath$ は同じ長さの増加する組)。
    $\Sigma$ のモデル $M'$ があれば、その $L$ への簡約 $M$ と $a_i:=c_i^{M'}$ が求めるものである。(S1) から $M$ は $A$ と同じ文を満たし、(S2) から元は相異なり、(S4) から列は識別不能、(S3) から $\operatorname{EM}(b)\subseteq\operatorname{EM}(a)$ である。コンパクト性定理(一階論理) により、$\Sigma$ の有限部分集合 $\Sigma_0$ がどれもモデルをもつことを示せばよい。
    $\Sigma_0$ に現れる (S4) の論理式を $\varphi_1,\dots,\varphi_m$、その変数の個数を $n_1,\dots,n_m$ とし、$N:=\max(1,n_1,\dots,n_m)$ とおく。$\Sigma_0$ に現れる定数記号の添字の集合 $I_0$ は有限で、その元を $i_1< \dots< i_p$ とする。
    $[\mathbb N]^N$ の元 $s=\{k_1< \dots< k_N\}$ を、$m$ 個の真偽の組
    $$ c(s):=\bigl(\text{$A\models\varphi_l(b_{k_1},\dots,b_{k_{n_l}})$ か否か}\bigr)_{l=1,\dots,m} $$
    で $2^m$ 色に塗る。lem-em-ramsey により、$c$ が $[H]^N$ の上で一定な無限集合 $H\subseteq\mathbb N$ がある。
    このとき、各 $l$ と、$H$ の増加する組 $k_1< \dots< k_{n_l}$、$k'_1< \dots< k'_{n_l}$ について、$\varphi_l(b_{k_1},\dots,b_{k_{n_l}})$ と $\varphi_l(b_{k'_1},\dots,b_{k'_{n_l}})$ の真偽は等しい。実際、$H$ は無限なので、両方の組より大きい $H$ の元を $N-n_l$ 個加えて $N$ 元集合 $s,s'$ を作ると、$c(s)=c(s')$ の第 $l$ 成分が 2 つの真偽である。
    $H$ の元 $h_1< \dots< h_p$ を選び、$A$ の中で $c_{i_t}$ を $b_{h_t}$ と解釈する($\Sigma_0$ に現れない定数記号は使わない)。$\Sigma_0$ の文が成り立つことを確かめる。(S1) は $A$ で真である。(S2) は $b_k$ が相異なり $h_t$ が相異なることから従う。(S3) の $\varphi\in\operatorname{EM}(b)$ は $b$ のすべての増加する組で成り立つ。(S4) では、$I_0$ の増加する組は写像 $i_t\mapsto h_t$ で $H$ の増加する組に移るので、前段により両辺の真偽が等しい。よって $\Sigma_0$ はモデルをもつ。
    最後の主張は、$T$ の無限のモデル $A$ と、その相異なる元の列 $(b_k)$ に適用すればよい。$M$ は $A$ と同じ文を満たすので $T$ のモデルである。$\square$

$b$ がはじめから識別不能列で $I$ が無限なら、thm-em-existence の $a$ は $b$ と同じ EM 型をもつ。$\varphi\notin\operatorname{EM}(b)$ なら $\neg\varphi\in\operatorname{EM}(b)\subseteq\operatorname{EM}(a)$ だからである。つまり、識別不能列はその EM 型を保ったまま、任意の全順序で添字づけ直せる(Sim14 p. 11)。たとえば $\omega$ で添字づけた識別不能列から、$\mathbb Q$ や $\mathbb R$、非可算の順序数で添字づけた識別不能列が得られる。
Morley の論文では、主定理から $\operatorname{EM}(b)\subseteq\operatorname{EM}(a)$ を除いた形が Mor65 Theorem 3.2(pp. 525–526)として、同じ方針(Ramsey の定理とコンパクト性)で証明されている。Mor65 の証明は、背理法で書いたうえで、変数の個数が揃わない場合を最大の個数に揃えて扱う点も同じである。

Skolem 関数と Ehrenfeucht–Mostowski 模型

識別不能列を含むモデルは、識別不能列から作られているとは限らない。モデルの元をすべて識別不能列から作るために、Skolem 関数を言語に組み込む。

Skolem 関数を組み込んだ理論

$L$ の理論 $T$ が Skolem 関数を組み込んでいるとは、$L$ の各論理式 $\varphi(y,x_1,\dots,x_n)$ に対して $n$ 変数の関数記号($n=0$ なら定数記号)$f_\varphi\in L$ があり、
$$ T\models\forall x_1\cdots\forall x_n\bigl(\exists y\,\varphi(y,\bar x)\to\varphi(f_\varphi(\bar x),\bar x)\bigr) $$
となることをいう。この文を $\varphi$ の Skolem 公理という。

Skolem 化

選択公理 を仮定する。$L$ の理論 $T$ に対し、言語 $L^*\supseteq L$ と $L^*$ の理論 $T^*\supseteq T$ で、$T^*$ は Skolem 関数を組み込み、$\lvert L^*\rvert\le\lvert L\rvert+\aleph_0$ で、$T$ のどのモデルも $T^*$ のモデルに拡張できるものがある。

関数記号を $\omega$ 回つけ足す

要点:関数記号と Skolem 公理を $\omega$ 回つけ足し、各段で証人を選択公理で選んでモデルを拡張する。

詳しい証明を開く

$L_0:=L$、$T_0:=T$ とする。$L_k$ が定まったら、$L_k$ の各論理式 $\varphi(y,\bar x)$ に新しい関数記号 $f_\varphi$ を加えた言語を $L_{k+1}$ とし、$T_{k+1}$ を $T_k$ にそれらの Skolem 公理を加えたものとする。$L^*:=\bigcup_kL_k$、$T^*:=\bigcup_kT_k$ とおく。$L^*$ の論理式はある $L_k$ の論理式なので、その Skolem 公理は $T_{k+1}\subseteq T^*$ に入る。$L_k$ の論理式は $\lvert L_k\rvert+\aleph_0$ 個なので、帰納的に $\lvert L_k\rvert\le\lvert L\rvert+\aleph_0$ である。

$T_k$ のモデル $M$ は、各 $f_\varphi$ を「$M\models\exists y\,\varphi(y,\bar a)$ なら証人の 1 つを、そうでなければ $M$ の任意の元を $\bar a$ に対応させる関数」と解釈して $T_{k+1}$ のモデルに拡張できる(証人の選び方に選択公理を使う)。これを $k=0,1,\dots$ と続ければ $T^*$ のモデルになる。$\square$

$T^*$ は $T$ の 保存拡大 でもある($L$ の文については $T$ と同じ帰結をもつ)が、以下で使うのはモデルの拡張だけである。

Skolem 包

$T^*$ を Skolem 関数を組み込んだ $L^*$ の理論、$M\models T^*$、$X\subseteq M$ を空でない部分集合とする。$L^*$ の項 $t(x_1,\dots,x_n)$ と $X$ の元 $\bar x$ による値 $t^M(\bar x)$ の全体を $\operatorname{H}(X)$ と書き、$X$ の Skolem 包という。$\operatorname{H}(X)$ は $M$ の初等部分モデルの台であり、$\lvert\operatorname{H}(X)\rvert\le\lvert X\rvert+\lvert L^*\rvert+\aleph_0$ である。

$\operatorname{H}(X)$ は $X$ を含み、項の合成で関数記号と定数記号の値について閉じているので、部分構造の台である。$M\models\exists y\,\varphi(y,\bar c)$($\bar c\in\operatorname{H}(X)$)なら、Skolem 公理により $f_\varphi(\bar c)\in\operatorname{H}(X)$ が証人である。よって Tarski–Vaughtの判定法 により $\operatorname{H}(X)\preccurlyeq M$ である。項は $\lvert L^*\rvert+\aleph_0$ 個、$X$ の有限列は $\lvert X\rvert+\aleph_0$ 個なので、濃度の評価が従う。$\square$

Ehrenfeucht–Mostowski 模型

$T^*$ を Skolem 関数を組み込んだ $L^*$ の理論、$M\models T^*$、$(a_i)_{i\in I}$ を $M$ の($L^*$ についての)識別不能列とする。Skolem 包 $N:=\operatorname{H}(\{a_i\mid i\in I\})$ を、$(a_i)_{i\in I}$ から生成される Ehrenfeucht–Mostowski 模型という。$L\subseteq L^*$ への簡約 $N\restriction L$ もそう呼ぶ。

lem-em-hull により $N\preccurlyeq M$ なので、$(a_i)$ は $N$ の中でも識別不能で EM 型は変わらない。$N$ の各元は、項 $t$ と増加する組 $\bar\imath$ により $t^N(a_{\bar\imath})$ と書ける(変数を並べ替えて項を取り替えればよい)。

順序の埋め込みはモデルの初等埋め込みに延びる

def-em-model の状況で、$I$ は無限集合、$a_i$ は相異なるとする。順序を保つ単射 $f\colon I\to I$ ごとに、$\hat f(a_i)=a_{f(i)}$($i\in I$)を満たす $L^*$ の初等埋め込み $\hat f\colon N\to N$ がただ一つある。さらに次が成り立つ。
(1) $\widehat{g\circ f}=\hat g\circ\hat f$、$\widehat{\mathrm{id}}=\mathrm{id}$。
(2) $f$ が順序の自己同型なら $\hat f$ は $N$ の自己同型であり、$f\mapsto\hat f$ は順序の自己同型群 $\operatorname{Aut}(I,<)$ から $\operatorname{Aut}(N\restriction L)$ への単射な群準同型である。

項で書いた元を添字ごと動かす

定義:$b=t^N(a_{\bar\imath})$($\bar\imath$ は増加する組)に対し $\hat f(b):=t^N(a_{f(\bar\imath)})$ とおく。$f$ は順序を保つので $f(\bar\imath)$ も増加する組である。
矛盾なく定まること:$t^N(a_{\bar\imath})=s^N(a_{\bar\jmath})$ とする。$\bar\imath$ と $\bar\jmath$ に現れる添字を合わせて小さい順に並べた組を $\bar k$ とすると、この等式は、論理式 $\theta(\bar x)$「$t(\bar\imath$ の位置の変数$)=s(\bar\jmath$ の位置の変数$)$」が $a_{\bar k}$ で成り立つことである。$f(\bar k)$ は増加する組で、$f(\bar\imath)$ と $f(\bar\jmath)$ は $f(\bar k)$ の同じ位置に現れるので、識別不能性により $t^N(a_{f(\bar\imath)})=s^N(a_{f(\bar\jmath)})$ である。
初等的であること:$N\models\varphi(b_1,\dots,b_m)$、$b_r=t_r^N(a_{\bar\imath_r})$ とする。同じく添字を合わせた増加する組 $\bar k$ をとると、これは $a_{\bar k}$ についての 1 つの論理式の真偽であり、識別不能性から $a_{f(\bar k)}$ でも同じ真偽をとる。すなわち $N\models\varphi(\hat f(b_1),\dots,\hat f(b_m))$ である。初等的な写像は($x=y$ の真偽を保つので)単射で、関数記号の値を保つ。
一意性:$L^*$ の埋め込みは項の値を保つので、$\hat f(t^N(a_{\bar\imath}))=t^N(\hat f(a_{\bar\imath}))=t^N(a_{f(\bar\imath)})$ とならざるをえない。
(1) は定義から明らかである。(2) $f$ が全射なら、$t^N(a_{\bar\imath})=\hat f(t^N(a_{f^{-1}(\bar\imath)}))$ なので $\hat f$ も全射で、自己同型である。$L^*$ の自己同型は $L$ の自己同型でもある。(1) から準同型で、$f(i)\ne i$ なら $\hat f(a_i)=a_{f(i)}\ne a_i$ なので単射である。$\square$

この定理は Mor65 Theorem 3.5・3.6(p. 527)にあたる。順序の埋め込み $f\colon I\to J$ についても同様に、$I$ と $J$ の識別不能列が同じ EM 型をもてば、$\hat f\colon\operatorname{H}(a_I)\to\operatorname{H}(a_J)$ が初等埋め込みとして定まる。EM 型を固定すれば、Ehrenfeucht–Mostowski 模型は全順序集合 $J$ から同型を除いて一意に決まり($\hat f$ を全単射な $f$ に当てればよい)、$J\mapsto\operatorname{H}(a_J)$ は全順序集合と順序の埋め込みの圏から、モデルと初等埋め込みの圏への関手になる。

応用

自己同型の多いモデル

$T$ を無限のモデルをもつ $L$ の理論、$\kappa\ge\lvert L\rvert+\aleph_0$ を基数とする。このとき $T$ のモデル $N$ で、$\lvert N\rvert=\kappa$ かつ $\lvert\operatorname{Aut}(N)\rvert=2^\kappa$ となるものがある。

$\kappa$ 個の $\mathbb Q$ を並べる

要点:Skolem 化した理論で $J=\kappa\times\mathbb Q$ で添字づけた識別不能列の Skolem 包をとり、各 $\mathbb Q$ の成分を独立にずらす $2^\kappa$ 個の順序の自己同型を thm-em-functor で延ばす。

詳しい証明を開く

lem-em-skolemization の $T^*$ をとる。$T$ の無限のモデルを $T^*$ のモデルに拡張し、thm-em-existence を $L^*$ について使うと、$T^*$ のモデル $M$ と、$J:=\kappa\times\mathbb Q$(辞書式順序。$\kappa$ は順序数とみる)で添字づけた相異なる元の識別不能列 $(a_j)_{j\in J}$ がある。$N:=\operatorname{H}(\{a_j\})\restriction L$ とおく。

$a_j$ は相異なるので $\lvert N\rvert\ge\lvert J\rvert=\kappa$、lem-em-hull により $\lvert N\rvert\le\kappa+\lvert L^*\rvert+\aleph_0=\kappa$ である。各 $\alpha< \kappa$ について $(\mathbb Q,<)$ の自己同型 $g_\alpha\in\{\mathrm{id},\,x\mapsto x+1\}$ を選ぶと、$(\alpha,q)\mapsto(\alpha,g_\alpha(q))$ は $J$ の順序の自己同型で、選び方 $2^\kappa$ 通りはどれも異なる。thm-em-functor (2) により $\lvert\operatorname{Aut}(N)\rvert\ge2^\kappa$ で、自己同型は $N$ から $N$ への写像なので $\lvert\operatorname{Aut}(N)\rvert\le\kappa^\kappa=2^\kappa$ である。$\square$

添字の順序を整列順序にとると、逆にモデルの「型の少なさ」が得られる。部分集合 $A\subseteq N$ の上の型(型(モデル理論))について、元 $b\in N$ の $A$ 上の型を $\operatorname{tp}(b/A)$ と書く。

可算部分集合の上で可算個の型しか実現しないモデル

$L$ を可算言語、$T$ を無限のモデルをもつ $L$ の理論、$\kappa$ を無限基数とする。このとき $T$ のモデル $N$ で、$\lvert N\rvert=\kappa$ であり、$N$ の各可算部分集合 $A$ について $\{\operatorname{tp}(b/A)\mid b\in N\}$ が可算集合であるものがある。

整列順序に有限集合を差し込む仕方は可算通り

要点:$\kappa$ で添字づけた Ehrenfeucht–Mostowski 模型では、元 $t(a_{\bar\jmath})$ の可算集合の上の型が項 $t$ と、添字の組 $\bar\jmath$ の可算集合 $J_0$ に対する位置で決まり、整列順序 $J_0$ への差し込み方は可算通りしかない。

詳しい証明を開く

prf-em-automorphisms と同じく、$L^*$(可算)と $T^*$、順序数 $\kappa$ で添字づけた相異なる元の識別不能列 $(a_j)_{j< \kappa}$ をとり、$N^*:=\operatorname{H}(\{a_j\})$、$N:=N^*\restriction L$ とおく。$\lvert N\rvert=\kappa$ である。

$A\subseteq N$ を可算集合とする。$A$ の各元は有限個の $a_j$ の項の値なので、可算集合 $J_0\subseteq\kappa$ で $A\subseteq\operatorname{H}(\{a_j\mid j\in J_0\})$ となるものがある。

増加する組 $\bar\jmath=(j_1,\dots,j_n)$ の「$J_0$ に対する位置」を、各 $r$ について、$j_r\in J_0$ ならその値 $j_r$、$j_r\notin J_0$ なら $\{k\in J_0\mid k>j_r\}$ の最小元 $m$ に印を付けた $m^-$(集合が空なら記号 $\infty$)を並べたものとする。$J_0$ は整列されているので最小元は存在し、位置のとりうる値は $(J_0\cup\{m^-\mid m\in J_0\}\cup\{\infty\})^n$ の元で、可算個である。

主張:$b=t^{N^*}(a_{\bar\jmath})$、$b'=t^{N^*}(a_{\bar\jmath'})$ で、$\bar\jmath$ と $\bar\jmath'$ の $J_0$ に対する位置が等しければ、$\operatorname{tp}(b/A)=\operatorname{tp}(b'/A)$ である。

実際、位置が等しいと、$j_r\in J_0$ と $j'_r\in J_0$ は同値で、そのとき $j_r=j'_r$ である。よって、$J_0$ の上で恒等写像、$j_r\mapsto j'_r$ となる写像 $\sigma\colon J_0\cup\{j_1,\dots,j_n\}\to J_0\cup\{j'_1,\dots,j'_n\}$ は順序を保つ全単射である($j_r\notin J_0$ のとき、$k\in J_0$ と $j_r$ の大小は、$k$ が上の最小元以上か否かで決まり、$j'_r$ でも同じである)。$L$ の論理式 $\varphi(y,\bar z)$ と $A$ の元 $\bar c=\bar s^{N^*}(a_{\bar k})$($\bar k\subseteq J_0$)について、$N\models\varphi(b,\bar c)$ は、$\bar\jmath$ と $\bar k$ の添字を合わせた増加する組での 1 つの論理式の真偽である。$\sigma$ はこの組を、同じ位置関係を保って $\bar\jmath'$ と $\bar k$ を合わせた増加する組に移すので、識別不能性から $N\models\varphi(b',\bar c)$ と同値である。

$N$ の元は項 $t$ と増加する組 $\bar\jmath$ で $t^{N^*}(a_{\bar\jmath})$ と書け、項は可算個、位置も可算個なので、主張により $N$ が実現する $A$ 上の型は可算個である。$\square$

これは Mor65 Theorem 3.7(p. 527、証明 p. 528)である。Morley はこれを使い、可算言語の理論がある非可算基数で範疇的なら、可算集合の上の型が可算個しかないこと($\omega$-安定性)を導いた(Mor65 Theorem 3.8, p. 528。Morleyの範疇性定理)。証明で添字を整列順序にとることは欠かせない(ex-em-counter の 2)。

$0^\sharp$ との関係

集合論では、識別不能列から生成されるモデルが構成可能宇宙 $L$ の構造を記述する。0♯ の記事の定理「Silver の識別不能元」は、$0^\sharp$ が存在するとき(これは可測基数などの大きな基数の仮定から従い、ZFC では証明できない)、順序数のクラス $I$ があって、各非可算基数 $\lambda$ について $I\cap\lambda$ が $L_\lambda$ の識別不能集合(順序数の大小で添字づけた識別不能列で、全識別不能ではない)で、定義可能な項によって $L_\lambda$ を生成することを述べる。$L$ では論理式で定義できる整列順序 $<_L$ の最小の証人を与える定義可能な項が Skolem 関数の役を果たすので、$L_\lambda$ は識別不能集合 $I\cap\lambda$ から Ehrenfeucht–Mostowski 模型と同じ仕方で生成されている。$0^\sharp$ はその EM 型(0♯ の記事でいう特性)の Gödel 数の集合である。Silver の識別不能元を一つずつずらす写像が $L$ から $L$ への初等埋め込みに延びること(同記事の定理「Kunen の特徴づけ」の 1 ⇒ 2)は、thm-em-functor と同じ形の議論である。EM 型に整礎性などの条件を課した「EM 青写真」による定式化は KM78 7.1–7.20(pp. 132–138)にある。

例と反例

反例の確かめ

下の表の 4 つの反例を確かめる。

確かめを開く

1. 無限のモデルをもたない理論:「元はちょうど 2 個」という文からなる理論のモデルには、無限集合で添字づけた相異なる元の列がない。仮定「無限のモデルをもつ」を外すと、thm-em-existence の結論が成り立たない。

2. 整列でない添字:$T$ を稠密な線形順序(端点なし)の理論とし、$J=\mathbb R$ で添字づけた識別不能列から Ehrenfeucht–Mostowski 模型 $N$ を作る。$x_1< x_2$ か $x_2< x_1$ が EM 型に入り、前者とすると、$A:=\{a_q\mid q\in\mathbb Q\}$ の上で $a_r$($r\in\mathbb R$)の型は $\{q\mid a_q< a_r\}=\{q\mid q< r\}$ により相異なる。$N$ は可算集合 $A$ の上で $2^{\aleph_0}$ 個の型を実現し、thm-em-few-types の結論の性質をもたない(後者の場合も同じ)。稠密な線形順序の理論も定理の仮定を満たし、結論のモデルは別にあるので、これは証明の構成で添字を整列順序にとることが欠かせない例である。

3. 非可算言語:実数ごとの定数記号 $c_r$ をもつ言語で $\operatorname{Th}(\mathbb R,<,r)_{r\in\mathbb R}$ を考えると、どのモデルも空集合の上で型 $\{x=c_r\}$ を $2^{\aleph_0}$ 個実現する。言語が可算という仮定を外すと、thm-em-few-types の結論が成り立たない。

4. Skolem 関数なし:稠密な線形順序の理論で $L=\{<\}$ のまま、$(\mathbb Q,<)$ の増加列 $a_n=n$($n\in\omega$)をとると、$\{a_n\}$ が生成する部分構造は $\{a_n\}$ 自身で、順序型 $\omega$ をもち最小元があるので稠密な線形順序の理論のモデルでない。Skolem 関数を組み込む仮定を外すと、生成されたものがモデルであるという def-em-model の前提(lem-em-hull の結論)が成り立たない。

外した仮定例成り立たなくなる結論
理論が無限のモデルをもつ「元はちょうど 2 個」の理論thm-em-existence:識別不能列を含むモデルの存在
$M$ を $A$ と別の構造にとってよい($M=A$ を求める)$A=(\mathbb Z,<)$(ex-em-integers)thm-em-existence:識別不能列を含むモデルの存在
証明の構成で添字を整列順序にとる$\mathbb R$ で添字づけた稠密な順序の模型(この模型では性質が成り立たない)thm-em-few-types:可算集合上の型が可算個
言語は可算実数の定数をもつ $\operatorname{Th}(\mathbb R,<,r)_r$thm-em-few-types:可算集合上の型が可算個
Skolem 関数の組み込み$\{<\}$ だけの稠密な順序と $a_n=n$lem-em-hull:生成された部分構造がモデル

関連項目

参考文献

[1]
Michael Morley, Categoricity in power, Transactions of the American Mathematical Society, 1965, §3:Theorem 3.1(Ramsey)p. 525、Theorem 3.2(識別不能列を含むモデルの存在)pp. 525–526、Theorem 3.3(Skolem 関数)p. 526、Theorem 3.4–3.6(順序の自己同型の延長)p. 527、Theorem 3.7 p. 527(証明 p. 528)、Theorem 3.8 p. 528
[3]
Akihiro Kanamori, Menachem Magidor, The evolution of large cardinal axioms in set theory, Higher Set Theory, Lecture Notes in Mathematics 669, Springer, pp. 99–275, 1978, §7(pp. 131–141):p. 131(Ehrenfeucht–Mostowski による識別不能性の導入と基本定理)、EM 青写真 7.1–7.20(pp. 132–138)
[4]
Andrzej Ehrenfeucht, Andrzej Mostowski, Models of axiomatic theories admitting automorphisms, Fundamenta Mathematicae 43, pp. 50–68, 1956

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