勒文海姆-斯科伦定理(向下)

我们把 $N$ 构造为 $M$ 的一列可数递增子集的并,使用塔斯基–沃特判别法:子集 $N \subseteq M$(作为子结构)是初等的,当且仅当对每个 $\mathcal{L}$-公式 $\psi(x, \bar{y})$ 与 $N$ 中每个元组 $\bar{a}$,若存在某个 $b \in M$ 使 $\mathcal{M} \models \psi(b, \bar{a})$,则已经存在这样的见证 $b \in N$。

由于 $\mathcal{L}$ 可数,公式 $\psi(x,\bar y)$ 只有可数多个。从任意可数无穷的 $X_0 \subseteq M$ 出发(因 $M$ 无限故可行)。给定可数的 $X_n$,对每个公式 $\psi(x,\bar y)$ 与 $X_n$ 中的每个元组 $\bar a$(仍只有可数多对,因为 $X_n$ 可数且 $\mathcal{L}$ 可数),若 $\exists b \in M\, \mathcal{M} \models \psi(b,\bar a)$,则(用选择公理)选取一个这样的见证 $b$ 并加入以构成 $X_{n+1}$;这只增加了可数多个新元素,故 $X_{n+1}$ 仍是可数的。

设 $N = \bigcup_{n<\omega} X_n$;可数个可数集之并,故 $N$ 可数(且无限,因 $X_0 \subseteq N$)。我们对 $N$ 验证塔斯基–沃特判别法:给定 $\psi(x,\bar y)$ 与 $N$ 中的 $\bar a$,因 $\bar a$ 是有限元组,它整个落在某个 $X_n$ 中(该链是递增的);若存在见证 $b \in M$ 使 $\psi(b, \bar a)$ 成立,则由 $X_{n+1}$ 的构造,某个见证已被选取并放入 $X_{n+1} \subseteq N$。

由塔斯基–沃特判别法,$N$(带有诱导的 $\mathcal{L}$-结构 $\mathcal{N}$)满足 $\mathcal{N} \preceq \mathcal{M}$。初等子结构与母结构满足完全相同的语句,故 $\mathcal{N}$ 是见证该定理的可数无穷模型。