数理論理学・集合論の問題

$A$ の元の個数を $n(\ge 1)$ とし、$A=\{a_1,\dots ,a_n\}$（$a_i$ は互いに異なる）と番号を付ける。$L$ の部分集合 $L_0$ に対し、$\mathcal{A}{|}_{L_0}$, $\mathcal{B}{|}_{L_0}$ で $L_0$ への縮小を表す。

手順 1（$B$ も $n$ 元）. $L$ 文
$${\lambda }_n:\exists x_1\cdots \exists x_n(\underset{1\le i<j\le n}{\bigwedge }{x}_i\ne x_j\wedge \forall y\underset{i=1}{\overset{n}{\bigvee }}y=x_i)$$
は「ちょうど $n$ 元である」ことを表し、$\mathcal{A}\models {\lambda }_n$（$x_i$ に $a_i$ を割り当てればよい）。$\mathcal{A}\equiv \mathcal{B}$ より $\mathcal{B}\models {\lambda }_n$ なので、$B$ もちょうど $n$ 元である。

手順 2（有限部分言語では同型）. $L_0\subset L$ を有限部分集合とする。次の論理式の有限個の連言を ${\Delta }_{L_0}(x_1,\dots ,x_n)$ とおく。
- $1\le i<j\le n$ について $x_i\ne x_j$。
- $L_0$ の各 $k$ 項関係記号 $R$ と各 $(i_1,\dots ,i_k)\in \{1,\dots ,n{\}}^k$ について、$R^{\mathcal{A}}(a_{i_1},\dots ,a_{i_k})$ が成り立つなら $R(x_{i_1},\dots ,x_{i_k})$、成り立たないなら $\neg R(x_{i_1},\dots ,x_{i_k})$。
- $L_0$ の各 $k$ 項関数記号 $f$ と各 $(i_1,\dots ,i_k)$ について、$f^{\mathcal{A}}(a_{i_1},\dots ,a_{i_k})=a_j$ となる唯一の $j$ をとって $f(x_{i_1},\dots ,x_{i_k})=x_j$。
- $L_0$ の各定数記号 $c$ について、$c^{\mathcal{A}}=a_j$ となる唯一の $j$ をとって $c=x_j$。

$L_0$ も $\{1,\dots ,n{\}}^k$ も有限なので、これは有限の連言であり、$L$ の論理式である。$x_i$ に $a_i$ を割り当てると各連言肢は作り方から $\mathcal{A}$ で真なので、$\mathcal{A}\models \exists x_1\cdots \exists x_n{\Delta }_{L_0}$。$\mathcal{A}\equiv \mathcal{B}$ より $\mathcal{B}\models \exists x_1\cdots \exists x_n{\Delta }_{L_0}$ なので、$\mathcal{B}\models {\Delta }_{L_0}[b_1,\dots ,b_n]$ となる $b_1,\dots ,b_n\in B$ がある。

$\sigma (a_i)=b_i$ で $\sigma :A\to B$ を定める。$x_i\ne x_j$ の連言肢から $b_i$ は互いに異なるので $\sigma$ は単射で、手順 1 より $|B|=n$ だから全単射である。$L_0$ の $k$ 項関係記号 $R$ と任意の $(i_1,\dots ,i_k)$ について、$R^{\mathcal{A}}(a_{i_1},\dots )$ が成り立てば $R(x_{i_1},\dots )$ が連言肢なので $R^{\mathcal{B}}(b_{i_1},\dots )$ が成り立ち、成り立たなければ $\neg R(x_{i_1},\dots )$ が連言肢なので $R^{\mathcal{B}}(b_{i_1},\dots )$ は成り立たない。よって $R^{\mathcal{A}}(a_{i_1},\dots ,a_{i_k})⟺R^{\mathcal{B}}(\sigma a_{i_1},\dots ,\sigma a_{i_k})$。関数記号 $f$ については、$f^{\mathcal{A}}(a_{i_1},\dots )=a_j$ のとき連言肢 $f(x_{i_1},\dots )=x_j$ から $f^{\mathcal{B}}(b_{i_1},\dots )=b_j$、すなわち $\sigma (f^{\mathcal{A}}(a_{i_1},\dots ))=f^{\mathcal{B}}(\sigma a_{i_1},\dots )$。定数記号も連言肢 $c=x_j$ から $\sigma (c^{\mathcal{A}})=c^{\mathcal{B}}$。$A$ のすべての元は $a_1,\dots ,a_n$ のどれかなので、これで $\sigma$ は $\mathcal{A}{|}_{L_0}\cong \mathcal{B}{|}_{L_0}$ の同型写像である。

手順 3（記号ごとの条件への分解）. $\mathrm{Bij}$ を $A$ から $B$ への全単射全体とする。手順 1 より $|A|=|B|=n$ なので $\mathrm{Bij}$ は $n!$ 個の元からなる有限集合である。各記号 $s\in L$ に対して、$\sigma \in \mathrm{Bij}$ が「$s$ を保つ」とは、同型写像の定義の中で $s$ に関する条件が成り立つことをいう。同型写像の定義により、$\sigma \in \mathrm{Bij}$ が $\mathcal{A}\cong \mathcal{B}$ の同型写像であることは、$\sigma$ がすべての $s\in L$ を保つことと同値であり、また $\mathcal{A}{|}_{L_0}\cong \mathcal{B}{|}_{L_0}$ の同型写像であることは、$\sigma$ がすべての $s\in L_0$ を保つことと同値である。

手順 4（有限性による貼り合わせ）. 背理法で示す。$\mathcal{A}$ と $\mathcal{B}$ が同型でないと仮定する。すると、どの $\sigma \in \mathrm{Bij}$ も同型写像ではないので、手順 3 より各 $\sigma \in \mathrm{Bij}$ に対して $\sigma$ が保たない記号 $s_{\sigma }\in L$ が存在する。$\mathrm{Bij}$ は有限なので
$$L^{\ast }=\{s_{\sigma }:\sigma \in \mathrm{Bij}\}$$
は $L$ の有限部分集合である。手順 2 を $L_0=L^{\ast }$ に適用すると、$\mathcal{A}{|}_{L^{\ast }}\cong \mathcal{B}{|}_{L^{\ast }}$ の同型写像 $\tau \in \mathrm{Bij}$ が存在する。手順 3 より $\tau$ は $L^{\ast }$ のすべての記号を保つが、$s_{\tau }\in L^{\ast }$ は $\tau$ が保たない記号なので矛盾する。

したがって $\mathcal{A}$ と $\mathcal{B}$ は同型である。すなわち、台集合が有限な $L$ 構造に初等同値な $L$ 構造は、それと同型である。