Scottの同型定理

長さ $n$ の列 $\bar b$ で、$\bar a$ と $\bar b$ が $L_{\omega_1\omega}$ の論理式を同じようには満たさないものごとに、$\mathcal M\models\chi_{\bar b}[\bar a]$、$\mathcal M\not\models\chi_{\bar b}[\bar b]$ となる論理式 $\chi_{\bar b}(\bar x)$ を 1 つ選ぶ（真偽が逆なら否定をとる）。$\varphi_{\bar a}$ を、これらの $\chi_{\bar b}$ すべてと、1 の原子論理式・原子論理式の否定すべての連言とする。$M$ の有限列は可算個であり、$L$ が可算なので変数が $\bar x$ の中にある原子論理式も可算個である。よって $\varphi_{\bar a}$ は $L_{\omega_1\omega}$ の論理式で、1 を満たす。
2 を示す。$\mathcal M\models\varphi_{\bar a}[\bar b]$ なら、$\bar b$ は選んだ $\chi_{\bar b'}$ をすべて満たすので、$\chi_{\bar b}$ が選ばれていてはいけない（選ばれていれば $\bar b$ で偽になる）。つまり $\bar a$ と $\bar b$ は $L_{\omega_1\omega}$ の論理式を同じように満たし、Karpの定理(無限論理) の系「可算な構造の同型の判定」の後半により、$\bar a$ を $\bar b$ に送る自己同型がある。逆に $\bar b=\sigma(\bar a)$ なら、組 $(\bar c,\sigma(\bar c))$ の全体は往復系なので、同記事の定理「往復系は論理式の真偽を保つ」により $\bar b$ は $\bar a$ と同じ論理式を満たし、$\mathcal M\models\varphi_{\bar a}[\bar a]$ から $\mathcal M\models\varphi_{\bar a}[\bar b]$ である。最後の主張は 2 から明らかである。$\square$

lem-sit-orbit の $\varphi_{\bar a}$ を使い、$M$ の各列 $\bar a$（長さ $n$）について
$$ \theta_{\bar a}=\forall\bar x\Bigl[\varphi_{\bar a}(\bar x)\to\Bigl(\bigwedge_{c\in M}\exists y\,\varphi_{\bar ac}(\bar x,y)\ \land\ \forall y\bigvee_{c\in M}\varphi_{\bar ac}(\bar x,y)\Bigr)\Bigr] $$
とおき、$\theta=\varphi_\emptyset\land\bigwedge_{\bar a}\theta_{\bar a}$ とする（$\varphi_\emptyset$ は空列の論理式で、文である）。$M$ とその有限列は可算個なので、$\theta$ は $L_{\omega_1\omega}$ の文である。
$\mathcal M\models\theta$． $\varphi_\emptyset$ は空列で真である。$\mathcal M\models\varphi_{\bar a}[\bar b]$ とすると、lem-sit-orbit の 2 により $\sigma(\bar a)=\bar b$ となる自己同型 $\sigma$ がある。各 $c\in M$ について $\mathcal M\models\varphi_{\bar ac}[\bar ac]$ を $\sigma$ で移すと $\mathcal M\models\varphi_{\bar ac}[\bar b\,\sigma(c)]$ なので、$y=\sigma(c)$ が存在の証拠になる。また、$e\in M$ について $c=\sigma^{-1}(e)$ とおけば同じく $\mathcal M\models\varphi_{\bar ac}[\bar be]$ なので、選言が真になる。よって $\mathcal M\models\theta_{\bar a}$ である。（自己同型が論理式の真偽を保つことは、prf-sit-orbit と同じく往復系から分かる。）
1 の ⇒． $\mathcal N\models\theta$ とし、$F=\{(\bar a,\bar b)\mid\mathcal N\models\varphi_{\bar a}[\bar b]\}$ とおく（$\bar a$ は $M$ の列、$\bar b$ は $N$ の同じ長さの列）。$\mathcal N\models\varphi_\emptyset$ なので $(\emptyset,\emptyset)\in F$。lem-sit-orbit の 1 により $\varphi_{\bar a}$ は $\bar a$ の原子論理式とその否定を含むので、$F$ の元は部分同型である。$(\bar a,\bar b)\in F$ とすると、$\mathcal N\models\theta_{\bar a}$ と $\mathcal N\models\varphi_{\bar a}[\bar b]$ から、各 $c\in M$ について $\mathcal N\models\varphi_{\bar ac}[\bar bd]$ となる $d\in N$ があり（行き）、各 $d\in N$ について $\mathcal N\models\varphi_{\bar ac}[\bar bd]$ となる $c\in M$ がある（帰り）。よって $F$ は往復系である。ここで $\mathcal N$ の濃度は使っていない。
1 の ⇐． $\mathcal N$ が $\mathcal M$ と部分同型的なら、Karpの定理(無限論理) の定理「Karp の定理」により $\mathcal M\equiv_{\infty\omega}\mathcal N$ である。$\theta$ は $L_{\infty\omega}$ の文で $\mathcal M\models\theta$ なので、$\mathcal N\models\theta$。
2． $\mathcal N$ が可算なら、1 と、可算な構造の間の往復系から同型が得られること（同記事の補題「Cantor の往復論法」）、同型な構造は部分同型的であることから従う。$\square$

$\theta$ を thm-sit-main の文とし、$\theta'$ と $\theta$ が同じモデルをもつことを示せばよい。$\mathcal N\models\theta'\land\lnot\theta$ となる $\mathcal N$ があったとする。$\mathcal N$ が非可算なら、thm-sit-lst を $\mu=\aleph_0$ として $L_{\omega_1\omega}$ の文 $\theta'\land\lnot\theta$ に使い、$\mathcal N$ を可算なモデルに取り替える。可算な $\mathcal N$ は $\theta'$ を満たすので $\mathcal N\cong\mathcal M$ であり、$\mathcal M\models\theta$ から $\mathcal N\models\theta$ となって矛盾する。$\theta\land\lnot\theta'$ のモデルがないことも、$\theta$ と $\theta'$ の役割を入れ替えて同じに示せる（$\mathcal M\models\theta'$ は Scott 文の定義で $\mathcal N=\mathcal M$ とすれば分かる）。$\square$

$\mathcal N\models\theta_\omega$ とし、$x\in N$ について $f(x)$ を $x$ より小さい元の個数とする。$x< y$ なら $x$ より小さい元と $x$ 自身は $y$ より小さいので $f(x)< f(y)$ であり、全順序なので $f$ は順序を保つ単射である。値域が $\omega$ 全体であることを示す。

• $f(w)=0$ となる $w$ がある：$x\in N$ をとり、$x$ 以下の元の有限集合の最小元を $w$ とする。$w$ より小さい元があればそれも $x$ より小さく、$w$ の最小性に反する。
• $f(x)=n$ なら $f(z)=n+1$ となる $z$ がある：最大元がないので $y> x$ をとり、$x< z\le y$ となる元の有限集合（$y$ を含む）の最小元を $z$ とする。$w< z$ なら、$w\le x$ であるか、$x< w< z\le y$ で $z$ の最小性に反するかのどちらかなので、$z$ より小さい元は $x$ より小さい元と $x$ 自身である。よって $f(z)=n+1$。
  帰納法により $f$ は全射で、$\mathcal N\cong(\omega,<)$ である。$\square$