無限論理

ex-inf-natural-numbers の $\theta_{\mathbb N}$ を使う。

1. 新しい定数記号 $c$ を加え、$T=\{\theta_{\mathbb N}\}\cup\{c\ne S^n0\mid n\ge0\}$ とする。有限部分集合に現れる $c\ne S^n0$ は有限個なので、それらの $n$ のどれとも異なる $m$ をとり、標準モデルで $c$ を $m$ と解釈すればモデルになる。$T$ のモデル $\mathcal M$ があれば、$\theta_{\mathbb N}$ の最後の連言肢から $c^{\mathcal M}=(S^n0)^{\mathcal M}$ となる $n$ があり、$c\ne S^n0$ に反する。
2. $\theta_{\mathbb N}$ は無限モデル $\mathbb N$ をもち、そのモデルはすべて $\mathbb N$ に同型なので可算である。$\square$

1 ⇒ 2． 後半の主張を、すべての $(\bar a,\bar b)\in F$ について同時に、$\varphi$ の組み立てに関する帰納法で示す。原子論理式では部分同型の定義そのものである。$\lnot$ と $\bigwedge\Phi$・$\bigvee\Phi$ は、同じ $(\bar a,\bar b)$ に帰納法の仮定を使えばよい（$\Phi$ が無限でも、各元に仮定を使うだけである）。$\forall$ は $\lnot\exists\lnot$ と同じ真偽をもち、有限個の変数の量化 $\exists y_1\cdots y_k$ は（行き）・（帰り）を $k$ 回続けて使えば 1 変数の場合と同じに扱えるので、$\varphi=\exists y\,\psi(\bar x,y)$ の場合を示す。$\mathcal M\models\varphi[\bar a]$ なら $\mathcal M\models\psi[\bar a,c]$ となる $c$ があり、（行き）により $(\bar ac,\bar bd)\in F$ となる $d$ があるので、帰納法の仮定から $\mathcal N\models\psi[\bar b,d]$、つまり $\mathcal N\models\varphi[\bar b]$。逆向きは（帰り）を使う。$F$ は空でないので、$(\bar a,\bar b)\in F$ を 1 つとり、文（$\bar x$ を使わない論理式）に後半の主張を当てはめれば 2 を得る。
2 ⇒ 1． $F$ を、自由変数が $\bar x$ の中にある $L_{\infty\omega}$ のすべての論理式 $\varphi(\bar x)$ について $\mathcal M\models\varphi[\bar a]\iff\mathcal N\models\varphi[\bar b]$ となる組 $(\bar a,\bar b)$ の全体とする。原子論理式も含むので、$F$ の元は部分同型であり、2 から空列の組 $(\emptyset,\emptyset)$ は $F$ に属する。（行き）を示す。$(\bar a,\bar b)\in F$、$c\in M$ とする。$(\bar ac,\bar bd)\notin F$ となる各 $d\in N$ について、$\mathcal M\models\chi_d[\bar a,c]$ かつ $\mathcal N\not\models\chi_d[\bar b,d]$ となる論理式 $\chi_d(\bar x,y)$ を 1 つ選ぶ（真偽が逆なら否定をとる）。$\psi=\bigwedge_d\chi_d$ は自由変数が $\bar x,y$ の中にある $L_{\infty\omega}$ の論理式（添字の集合は $N$ の部分集合）で、$\mathcal M\models\psi[\bar a,c]$ である。よって $\mathcal M\models\exists y\,\psi[\bar a]$、$(\bar a,\bar b)\in F$ から $\mathcal N\models\exists y\,\psi[\bar b]$ となり、$\mathcal N\models\psi[\bar b,d]$ となる $d$ がある。この $d$ について $(\bar ac,\bar bd)\notin F$ なら $\chi_d$ が $\psi$ の連言肢で $\mathcal N\not\models\chi_d[\bar b,d]$ となり矛盾するので、$(\bar ac,\bar bd)\in F$ である。（帰り）は $\mathcal M$ と $\mathcal N$ の役割を入れ替えて同様に示せる。$\square$

$M=\{m_0,m_1,\dots\}$、$N=\{n_0,n_1,\dots\}$ と並べる（有限なら同じ元を繰り返す）。$(\bar a_0,\bar b_0)=(\bar a,\bar b)$ から始め、$(\bar a_{2k+1},\bar b_{2k+1})$ は（行き）で $m_k$ を、$(\bar a_{2k+2},\bar b_{2k+2})$ は（帰り）で $n_k$ を加えた $F$ の元とする。$\bar a_k$ の $i$ 番目の元を $\bar b_k$ の $i$ 番目に送る対応を $k$ について合わせたものを $\sigma$ とする。部分同型は等号の原子論理式を保つので、$\sigma$ は well-defined な単射であり、作り方から全射で、定義域は $M$ 全体である。原子論理式は有限個の元しか含まないので、ある段階の部分同型の条件から $\sigma$ が保つことが分かる。よって $\sigma$ は同型である。$\square$

⇒ は明らかである。⇐：thm-inf-karp の 2 ⇒ 1 の証明で $L_{\infty\omega}$ を $L_{\omega_1\omega}$ に替えて同じ $F$ を作る。そこで使った連言は $N$ の元を添字とするので可算であり、証明はそのまま通る。$(\emptyset,\emptyset)\in F$ に lem-inf-countable-bf を使えばよい。後半は、$\mathcal N=\mathcal M$ として組 $(\bar a,\bar a')$ を含む同じ $F$ に lem-inf-countable-bf を使う。$\square$

論理式 $\varphi_{\bar a}$ の構成． $M$ の各有限列 $\bar a$（長さ $n$、空列も含む）について、同じ長さの列 $\bar b$ で、$\bar a$ と $\bar b$ が $L_{\omega_1\omega}$ の論理式を同じように満たさないものごとに、$\bar a$ では真で $\bar b$ では偽になる論理式 $\chi_{\bar a,\bar b}(\bar x)$ を 1 つ選ぶ。$\varphi_{\bar a}(\bar x)$ を、これらすべての $\chi_{\bar a,\bar b}$ と、$\bar a$ が満たす原子論理式・原子論理式の否定（変数は $\bar x$ の中）すべての連言とする。$M$ の有限列は可算個、$L$ が可算なので原子論理式も可算個であり、$\varphi_{\bar a}$ は $L_{\omega_1\omega}$ の論理式である。作り方から、$M$ の列 $\bar b$ について
$$ \mathcal M\models\varphi_{\bar a}[\bar b]\iff\bar a,\bar b\ \text{は}\ L_{\omega_1\omega}\ \text{の論理式を同じように満たす}\iff\bar a\ \text{を}\ \bar b\ \text{に送る}\ \mathcal M\ \text{の自己同型がある} $$
が成り立つ。この同値を $(*)$ とよぶ。最初の ⇒ は $\chi_{\bar a,\bar b}$ が $\bar b$ で偽になること、⇐ は $\bar a$ が $\varphi_{\bar a}$ を満たすことから、2 つ目の同値は cor-inf-countable-iso の後半（⇒）と、自己同型が論理式の真偽を保つこと（⇐）から分かる。
Scott 文． 各 $\bar a$ について
$$ \theta_{\bar a}=\forall\bar x\Bigl[\varphi_{\bar a}(\bar x)\to\Bigl(\forall y\bigvee_{c\in M}\varphi_{\bar ac}(\bar x,y)\ \land\ \bigwedge_{c\in M}\exists y\,\varphi_{\bar ac}(\bar x,y)\Bigr)\Bigr] $$
とおき、$\theta=\varphi_{\emptyset}\land\bigwedge_{\bar a}\theta_{\bar a}$ とする。可算個の連言・選言しか使っていないので $\theta$ は $L_{\omega_1\omega}$ の文である。
$\mathcal M\models\theta$． $\varphi_\emptyset$ は $\mathcal M$ で真である。$\mathcal M\models\varphi_{\bar a}[\bar b]$ とすると、$(*)$ から $\sigma(\bar a)=\bar b$ となる自己同型 $\sigma$ がある。$e\in M$ について $c=\sigma^{-1}(e)$ とおくと $\mathcal M\models\varphi_{\bar ac}[\bar a,c]$ なので、$\sigma$ で移して $\mathcal M\models\varphi_{\bar ac}[\bar b,e]$。また各 $c$ について $y=\sigma(c)$ が $\varphi_{\bar ac}(\bar b,y)$ を満たす。よって $\mathcal M\models\theta_{\bar a}$。$\theta$ は同型で保たれるので、$\mathcal M$ に同型な構造はすべて $\theta$ を満たす。
可算な $\mathcal N\models\theta$ なら $\mathcal N\cong\mathcal M$． $F=\{(\bar a,\bar b)\mid\mathcal N\models\varphi_{\bar a}[\bar b]\}$ とおく。$\mathcal N\models\varphi_\emptyset$ なので $(\emptyset,\emptyset)\in F$。$\varphi_{\bar a}$ は $\bar a$ の満たす原子論理式とその否定を含むので、$F$ の元は部分同型である。$(\bar a,\bar b)\in F$ とすると $\mathcal N\models\theta_{\bar a}$ から、各 $c\in M$ について $\mathcal N\models\varphi_{\bar ac}[\bar b,d]$ となる $d$ があり（行き）、各 $d\in N$ について $\mathcal N\models\varphi_{\bar ac}[\bar b,d]$ となる $c$ がある（帰り）。よって $F$ は往復系で、lem-inf-countable-bf により $\mathcal N\cong\mathcal M$。$\square$