α-同构

在模型论里, $\mathbf{\alpha }$-同构衡量的是两个模型间最多能有多少部分同构. 一般来说,$$\mathcal{M}\cong \mathcal{N}\Rightarrow \mathcal{M}{\cong }_{\infty }\mathcal{N}\Rightarrow \mathcal{M}{\cong }_{\alpha }\mathcal{N}\Rightarrow \mathcal{M}{\cong }_{\omega }\mathcal{N}\Rightarrow \mathcal{M}\equiv \mathcal{N}.$$而往返法指的是用 $\alpha$-同构来证明模型之间的等价/同构的方法.

1定义

在如下定义里, $A$ 和 $B$ 都是有限集.

定义 1.1 ($0$-同构). 设一阶语言 $\mathcal{L}$ 的两个模型 $\mathcal{M}$ 与 $\mathcal{N}$ 以及 $f:\mathcal{M}\supset A\to B\subset \mathcal{N}$ 满足 $⟨A⟩{\cong }_{\mathcal{L}}⟨B⟩$, 则称 $A$ 和 $B$ 是 $0$-同构的, 也就是说, 它们满足相同的不含量词的公式, 记作 $A{\cong }_{0}B$. 如果 ${\varnothing }_{\mathcal{M}}{\cong }_0{\varnothing }_{\mathcal{N}}$, 则称模型 $\mathcal{M}$ 与 $\mathcal{N}$ 是 $0$-同构的, 记作 $\mathcal{M}{\cong }_0\mathcal{N}$.

然后递归地定义:

定义 1.2 ($\alpha$-同构). 设 $\alpha$ 为序数. 如果存在 $A\subset \mathcal{M}$ 与 $B\subset \mathcal{N}$ 的一个 $\alpha$-同构, 满足:

•	对任意 $x\in \mathcal{M}$, 存在 $y\in \mathcal{N}$, $A\cup \{x\}{\cong }_{\alpha }B\cup \{y\}$.
•	对任意 $y\in \mathcal{N}$, 存在 $x\in \mathcal{M}$, $B\cup \{y\}{\cong }_{\alpha }A\cup \{x\}$.

且上述的 $\alpha$-同构与 $A$, $B$ 之间的 $\alpha$-同构相容, 则称 $A$ 与 $B$ 是 ($\mathbf{\alpha }+1$)-同构的, 记作 $A{\cong }_{\alpha +1}B$.

对于极限序数 $\alpha$, $A{\cong }_{\alpha }B$ 定义成对于任何 $\beta <\alpha$, $A{\cong }_{\beta }B$.

如果 ${\varnothing }_{\mathcal{M}}{\cong }_{\alpha }{\varnothing }_{\mathcal{N}}$, 则称模型 $\mathcal{M}$ 与 $\mathcal{N}$ 是 $\mathbf{\alpha }$-同构的, 记作 $\mathcal{M}{\cong }_{\alpha }\mathcal{N}$.

定义 1.3 ($\infty$-同构). 如果存在一族 $\mathcal{M}$ 的子集与 $\mathcal{N}$ 的子集之间的 $0$-同构 $\Sigma$, 使得 $({\varnothing }_{\mathcal{M}}{\cong }_0{\varnothing }_{\mathcal{N}})\in \Sigma$, 且满足如下的往返条件:

(往)	对任意 $(\mathcal{M}\supset A{\cong }_{0}B\subset \mathcal{N})\in \Sigma$, 任意 $x\in \mathcal{M}$, 存在 $y\in \mathcal{N}$ 使得 $A\cup \{x\}{\cong }_{0}B\cup \{y\}$. 且所有的这些 $0$-同构的扩张都在 $\Sigma$ 中.
(返)	对任意 $(\mathcal{M}\supset A{\cong }_{0}B\subset \mathcal{N})\in \Sigma$, 任意 $y\in \mathcal{N}$, 存在 $x\in \mathcal{M}$ 使得 $B\cup \{y\}{\cong }_{0}A\cup \{x\}$. 且所有的这些 $0$-同构的扩张都在 $\Sigma$ 中.

则称 $\mathcal{M}$ 与 $\mathcal{N}$ 是 $\infty$-同构的, 记为 $\mathcal{M}{\cong }_{\infty }\mathcal{N}$.

注 1.4. 容易看出, $\mathcal{M}$ 与 $\mathcal{N}$ 是 $\infty$-同构的, 等价于对足够大的 $\alpha$, $\mathcal{M}$ 与 $\mathcal{N}$ 是 $\mathbf{\alpha }$-同构的.

2性质

命题 2.1. 有如下蕴含关系: $$\mathcal{M}\cong \mathcal{N}\Rightarrow \mathcal{M}{\cong }_{\infty }\mathcal{N}\Rightarrow \mathcal{M}{\cong }_{\alpha }\mathcal{N}\Rightarrow \mathcal{M}{\cong }_{\omega }\mathcal{N}\Rightarrow \mathcal{M}\equiv \mathcal{N}.$$其中 $\mathcal{M}\cong \mathcal{N}$, $\mathcal{M}\equiv \mathcal{N}$ 分别代表模型的同构与等价.

证明. 前四个显然. 下证最后一个. $\mathcal{M}{\cong }_{\omega }\mathcal{N}$ 意味着任意 $n$, $\mathcal{M}{\cong }_n\mathcal{N}$, 即 ${\varnothing }_{\mathcal{M}}{\cong }_n{\varnothing }_{\mathcal{N}}$. 下归纳证明任意 $n$, 如果 $A{\cong }_{n}B$ 则其 $n$ 阶型相同, 即 ${\mathrm{tp}}_n(A)={\mathrm{tp}}_n(B)$.

•

$n=0$. 即它们满足相同的不含量词, 参数在 $A$, $B$ 中的公式, 这由 $A{\cong }_{0}B$ 推出.

•

假设 $n$ 时成立. 任意 $\phi \in {\mathrm{tp}}_{n+1}(A)$ 可以等价于写成 $\exists x\chi (x,a)$, $\chi \in {\mathrm{tp}}_n(A)$. $\mathcal{M}\models \exists x\chi (x)$ 给出了 $a^{\prime }\in \mathcal{M}$, $\mathcal{M}\models \chi (a^{\prime },a)$. 由 $A{\cong }_{n+1}B$, 知存在 $b^{\prime }\in \mathcal{N}$ 使 $A\cup \{a^{\prime }\}{\cong }_{n}B\cup \{b^{\prime }\}$, 从而 ${\mathrm{tp}}_n(A\cup \{a^{\prime }\})={\mathrm{tp}}_n(B\cup \{b^{\prime }\})$. 故 $\mathcal{N}\models \chi (b^{\prime },b)$, 从而 $\phi \in {\mathrm{tp}}_{n+1}(B)$. 反之亦然.

因此 ${\varnothing }_{\mathcal{M}}{\cong }_n{\varnothing }_{\mathcal{N}}$ 意味着 ${\mathrm{tp}}_n({\varnothing }_{\mathcal{M}})={\mathrm{tp}}_n({\varnothing }_{\mathcal{N}})$, 但是$$\mathrm{Th}(\mathcal{M})=\bigcup _n{\mathrm{tp}}_n({\varnothing }_{\mathcal{M}}),$$所以 $\mathrm{Th}(\mathcal{M})=\mathrm{Th}(\mathcal{N})$, 即 $\mathcal{M}\equiv \mathcal{N}$.

$\square$

命题 2.2. 如果 $\mathcal{M}$ 与 $\mathcal{N}$ 都是可数模型, 那么$$\mathcal{M}{\cong }_{\infty }\mathcal{N}\Rightarrow \mathcal{M}\cong \mathcal{N}.$$

证明. 设 $\mathcal{M}=\{a_n\}$, $\mathcal{N}=\{b_n\}$. 由 $({\varnothing }_{\mathcal{M}}{\cong }_0{\varnothing }_{\mathcal{N}})\in \Sigma$ 知存在 $b_{f(1)}$ 使得 $(a_1{\cong }_0{b}_{f(1)})\in \Sigma$, 进而存在 $a_{g(1)}$ 使得 $(\{a_1,a_{g(1)}\}{\cong }_0\{b_1,b_{f(1)}\})\in \Sigma$. 再依次添加 $a_2$, $b_2$, $\cdots$ (如果已经在像集里就不用添加), 即可穷尽 $\mathcal{M}$ 与 $\mathcal{N}$, 即存在整个 $\mathcal{M}$ 到整个 $\mathcal{N}$ 上的 $0$-同构, 故 $\mathcal{M}\cong \mathcal{N}$.

$\square$

3例子

无界稠密全序理论

Cantor 最先证明如下结果:

定理 3.1 (Cantor). 所有可数无界稠密全序集都同构于 $(\mathbb{Q},<)$.

以 $\alpha$-同构的观点看, 这个定理是因为:

命题 3.2. 理论 $\mathsf{DLO}$ 的任两个模型都是 $\infty$-同构的, 因为所有的 $0$-同构 $A{\cong }_{0}B$ 都是 $1$-同构.

再由命题 (2.2) 得到它们同构.

Ehrenfeucht–Fraïssé 博弈

主条目: Ehrenfeucht–Fraïssé 博弈