Scott高さ

$\alpha$ に関する超限帰納法で、すべての $\mathcal N$ とすべての列について同時に示す。$\alpha=0$：$\varphi^0_{\bar a}[\bar b]$ は「$\bar a$ が満たす原子論理式を $\bar b$ も満たし、$\bar a$ が満たさない原子論理式を $\bar b$ も満たさない」ということであり、$\sim_0$ の定義そのものである。$\alpha=\beta+1$：$\mathcal N\models\varphi^{\beta+1}_{\bar a}[\bar b]$ は次の 3 つの連言である。
$$ \mathcal N\models\varphi^\beta_{\bar a}[\bar b],\qquad\forall c\in M\ \exists d\in N\ \mathcal N\models\varphi^\beta_{\bar ac}[\bar b,d],\qquad\forall d\in N\ \exists c\in M\ \mathcal N\models\varphi^\beta_{\bar ac}[\bar b,d]. $$
帰納法の仮定により、それぞれ $(\mathcal M,\bar a)\sim_\beta(\mathcal N,\bar b)$、（行き）、（帰り）と同値であり、合わせて $(\mathcal M,\bar a)\sim_{\beta+1}(\mathcal N,\bar b)$ と同値である。$\alpha$ が極限なら、両辺とも「すべての $\beta< \alpha$ について」の形なので、帰納法の仮定からよい。$\square$

$X$ を $M$ の同じ長さの列の組 $(\bar a,\bar b)$ 全体の集合とし、$E_\beta=\{(\bar a,\bar b)\in X\mid\bar a\sim_\beta\bar b\}$ とおく。lem-sr-basic の 1 により $E_\beta$ は $\beta$ について減少する。
2：$E_\alpha=E_{\alpha+1}$ とする。$\sim_{\alpha+2}$ は「$\sim_{\alpha+1}$ であり、行き先と帰り先を $\sim_{\alpha+1}$ でとれる」ことだが、$M$ の中では $\sim_{\alpha+1}$ と $\sim_\alpha$ が一致するので、これは「$\sim_\alpha$ であり、行き先と帰り先を $\sim_\alpha$ でとれる」こと、すなわち $\sim_{\alpha+1}$ と同じである。よって $E_{\alpha+2}=E_{\alpha+1}$。これをくり返し、極限の段では共通部分をとるので、超限帰納法ですべての $\beta\ge\alpha$ で $E_\beta=E_\alpha$。
1 と 3：Scott 高さが存在しないか、存在して $\gamma$ 以上であるとすると、すべての $\beta< \gamma$ で $E_{\beta+1}\subsetneq E_\beta$ である。$X$ を整列しておき、各 $\beta< \gamma$ に $E_\beta\setminus E_{\beta+1}$ の最小元 $x_\beta$ を対応させる。$\beta< \beta'$ なら $x_{\beta'}\in E_{\beta'}\subset E_{\beta+1}$、$x_\beta\notin E_{\beta+1}$ なので $x_\beta\ne x_{\beta'}$ であり、$\beta\mapsto x_\beta$ は $\gamma$ から $X$ への単射になる。$\gamma$ を $X$ の濃度より大きい基数にとれば矛盾するので 1 を得る。$\mathcal M$ が可算なら $X$ は可算なので、$\gamma=\omega_1$ として 3 を得る。$\square$

$\sim_\alpha$ は $\sim_0$ を含意するので組は部分同型であり、空列どうしは $\sim_\alpha$ の関係にあるので空でない。$\bar a\sim_\alpha\bar b$ なら高さの定義から $\bar a\sim_{\alpha+1}\bar b$ であり、$\sim_{\alpha+1}$ の（行き）（帰り）は $\sim_\alpha$ に入る組への延長を与える。
1：⇐ は lem-sr-basic の 4。⇒ は、この往復系に 無限論理 の補題「可算構造の往復」を使う。
2：自己同型で移り合う関係を $O$ とする。1 から $\sim_\alpha=O$ である。逆に $\gamma< \alpha$ なら、高さの最小性から $\bar a\sim_\gamma\bar b$ だが $\bar a\not\sim_{\gamma+1}\bar b$ となる組があり、lem-sr-basic の 4 から $O$ は $\sim_{\gamma+1}$ に含まれるので、この組は $O$ に入らない。よって $\sim_\gamma\ne O$。$\square$

$\alpha=\operatorname{sh}(\mathcal M)$ とし、thm-sr-define を使って $\sigma_{\mathcal M}$ を読み替える：$\mathcal N\models\sigma_{\mathcal M}$ は、$(\mathcal M,\emptyset)\sim_\alpha(\mathcal N,\emptyset)$ であり、かつ $M$ のすべての列 $\bar a$ と $N$ の同じ長さのすべての列 $\bar b$ で「$(\mathcal M,\bar a)\sim_\alpha(\mathcal N,\bar b)$ ならば $(\mathcal M,\bar a)\sim_{\alpha+1}(\mathcal N,\bar b)$」であることと同値である。
⇒：$F=\{(\bar a,\bar b)\mid(\mathcal M,\bar a)\sim_\alpha(\mathcal N,\bar b)\}$ とおく。$(\emptyset,\emptyset)\in F$ で、$F$ の元は部分同型であり、$F$ の元は $\sim_{\alpha+1}$ の関係にあるので、その（行き）（帰り）が $F$ の中への延長を与える。よって $F$ は往復系である。
⇐：$F$ を往復系とし、元 $(\bar a_0,\bar b_0)\in F$ を 1 つとる。lem-sr-basic の 4 と、3 を長さ $0$ の部分列に使うことで、すべての $\beta$ で $(\mathcal M,\emptyset)\sim_\beta(\mathcal N,\emptyset)$ を得る。次に $(\mathcal M,\bar a)\sim_\alpha(\mathcal N,\bar b)$ とする。$(\bar a_0,\bar b_0)$ から始めて（帰り）を $\bar b$ の長さだけくり返すと、$(\bar a_0\bar a',\bar b_0\bar b)\in F$ となる $M$ の列 $\bar a'$ がとれ、lem-sr-basic の 3・4 から $(\mathcal M,\bar a')\sim_\beta(\mathcal N,\bar b)$（すべての $\beta$）である。lem-sr-basic の 2 により $\bar a\sim_\alpha\bar a'$（$\mathcal M$ の中で）であり、高さの定義から $\bar a\sim_{\alpha+1}\bar a'$、これと $(\mathcal M,\bar a')\sim_{\alpha+1}(\mathcal N,\bar b)$ をつなげば $(\mathcal M,\bar a)\sim_{\alpha+1}(\mathcal N,\bar b)$ である。$\square$

thm-sr-height の 3 から $\alpha=\operatorname{sh}(\mathcal M)< \omega_1$ なので、$\varphi^\alpha_{\bar a},\varphi^{\alpha+1}_{\bar a}$ は $L_{\omega_1\omega}$ の論理式であり、$M$ の有限列は可算個なので $\sigma_{\mathcal M}$ は $L_{\omega_1\omega}$ の文である。同値は、thm-sr-canonical と、可算な構造の間の往復系から同型が得られること（無限論理 の補題「可算構造の往復」）、同型な構造の間には往復系があることによる。$\square$