用户: 不萌/Löwenheim–Skolem 定理

Löwenheim–Skolem 定理说的是对于任何一个 一阶逻辑语言 ${\mathcal{L}}_{\mathcal{A}}$ , $\mathcal{N}=(N,J)$ 为它的一个无穷结构, 对于任何一个可数子集 $X\subset N$, 存在一个包含 $X$ 的可数同质缩小结构 $\mathcal{M}=(M,I)$. 即 $X\subset M$, $M$ 可数, 且 $\mathcal{M}$ 是 $\mathcal{N}$ 的初等子结构.

证明. 根据 Tarski–Vaught 判别法, 我们就是需要构造一个 $N$ 的含 $X$ 的子集 $M$, 满足与 $N$ 的任意可定义集合交非空.

在这里的证明用到选择公理.

首先, 依照良序原理, 我们可以给出 $N$ 的一个良序, 并且此后我们所说的所有集合的最小元都是在这个良序的意义下阐述.

第二步, 注意到一个重要的事实: 对于一个可数子集 $Y\subset N$, 以 $Y$ 为参数的所有可定义集合 $\mathrm{D}\mathrm{e}\mathrm{f}(\mathcal{N},Y)$ 是可数的. 根据可定义集的定义, 因为所有 $Y$ 的有限子集只有可数多个, 而所有表达式的全体亦是可数多个, 那么两个部分笛卡尔积也只有可数多个. 所以以 $Y$ 为参数可定义的集合只有可数多.

第三步, 我们对于 $X$ 的每一个可数子集 $Y$, 可以构建一个 $\mathrm{D}\mathrm{e}\mathrm{f}(\mathcal{N},Y)$ 的列表 $⟨A_i(Y)|i\in \mathbb{N}⟩$, 并且对于每个非空的 $A_i(Y)$, 都找到一个最小元素 $a_i(Y)$, 当 $A_i(Y)$ 为空集时, 就定义 $a_i(Y)$ 为 $N$ 的最小元素.

第四步, 递归地构造我们想要的集合 $\left\{M_k\right\}$: 令 $M_0=X$, $M_{k+1}=M_k\cup \left\{a_i(M_k)|i\in \mathbb{N}\right\}$. 最后, 令 $M={\bigcup }_{k\in \mathbb{N}}{M}_k$.

需要验证 $M$ 就是满足条件的集合:

•	$M$ 是可数集合, 因为 $M_k$ 为两个可数集合的并, 因此 $M_k$ 的可数, 从而 $M$ 是可数集合的可数并, 因此是可数的.
•	$X\subset M$, 因为构造中有 $X=M_0,M_k\subset M_{k+1}$ 故 $X\subset M$
•	$M$ 上可以定义 $\mathcal{N}$ 的子结构. 这部分就是比较平凡地验证定义: ∘ 对于常元符号 $c_i\in \mathcal{A}$, $\left\{J(c_i)\right\}$ 是免参数可定义的, 那么 $J(c_i)\in M_1\subset M$. 从而我们就定义 $I(c_i)=J(c_i)$. ∘ 对于 $n$ 元函数符号 $F_k\in \mathcal{A}$ $a_1,a_2,\dots ,a_n\in M$ 我们可以有 $J(F_k)(a_1,a_2,\dots ,a_n)\in M$. 这是因为 $x_0=F_k(x_1,x_2,\dots ,x_n)$ 这一表达式就给出了一个用参数 $a_1,a_2,\dots ,a_n$ 定义这一元素的表达式, 那么它在 $M$ 中. 那我们就定义 $I(F_k)=J(F_k){|}_{M^n}$. ∘ 对于 $n$ 元的函词符号 $P_j$, 自然地定义 $I(P_j)=J(P_j)\cap M^n$. 因此, 我们定义了子结构 $\mathcal{M}=(M,I)⪯(N,J)=\mathcal{N}$.
•	对于任意一个 $M$ 为参数定义的集合 $A\in \mathrm{D}\mathrm{e}\mathrm{f}(\mathcal{N},M)$, $A\cap M\ne \varnothing$. 这是根据参数的有限性, 总存在某个 $k$, 使得 $A\subset \mathrm{D}\mathrm{e}\mathrm{f}(\mathcal{N},M_k)$ 那么就有 $A\cap M_{k+1}\ne \varnothing$, 从而 $A\cap M\ne \varnothing$.

验证完毕.

$\square$