Tarski–Vaught 判别法

Tarski–Vaught 判别法是判定一个结构是否是另一个结构的初等子结构的充要条件. 它在用于构造一个大结构的初等子结构时的有用方法.

1定理

定理 1.1. 对于结构 $\mathcal{N}=(N,J)$ 与其子结构 $\mathcal{M}=(M,I)$, 有以下等价:

(1)	$\mathcal{M}$ 是 $\mathcal{N}$ 的初等子结构;
(2)	$\mathcal{N}$ 中以 $M$ 中元素为参数的非空可定义的子集都与 $M$ 交非空. 即对于每一个 $\mathcal{N}$ 的一阶语句 $\phi (x,y_1,\dots ,y_n)$, 当 $(a_1,\dots ,a_n)\in M^n$ 时, 若 $\mathcal{N}\models \exists x\phi (x,a_1,\dots ,a_n)$ 成立, 就存在 $b\in M$, $\mathcal{N}\models \phi (b,a_1,\dots ,a_n)$.

证明. $(1)\Rightarrow (2)$ 考虑一阶语句 $\phi (x,y_1,\cdots ,y_n)$ 在参数为 $(b_1,\dots ,b_n)$ 的情况下所定义的集合非空, 但与 $M$ 交为空, 那么式子 $(\forall x(\neg \phi )(x,b_1,\dots ,b_n))$ 在 $\mathcal{M}$ 中成立, 但在 $\mathcal{N}$ 中不成立. 这与初等子结构的定义相违背.

$(2)\Rightarrow (1)$ 对于表达式采用归纳法, 反证法证明, 假设它是初等子结构.

对于任何一个 $\mathcal{M}$ 的赋值映射 $\nu$, 有 $((\mathcal{M},\nu )\models \phi )\iff ((\mathcal{N},\nu )\models \phi )$. 归纳基础为对于所有常元与变元成立.

对于所有的 $\phi$ 是等值式, 谓词式, 否定式, 蕴涵式时, 应用归纳假设可直接说明其成立. 下考虑全域式的情况, 假设 $\phi =(\forall x_i\psi )$.

当 $(N,\nu )\models \phi$ 时, 根据定义, 对于每一个在 $\phi$ 的自由变元上取值与 $\nu$ 相同的 $\mathcal{M}$ 上赋值 $\mu$, 有 $(N,\mu )\models \psi$, 根据归纳假设就是 $(M,\mu )\models \psi$, 根据归纳法成立.

当 $(M,\mu )/\models \phi$ 时, 根据定义与归纳假设, 可以找到一个 $\phi M$-赋值映射 $\mu$, 满足$$\mu {\equiv }_{\phi }\nu 且(\mathcal{N},\mu )/\models \psi$$设 $y,x_{k_1},x_{k_2},\dots ,x_{k_m}$ 是所有的 $\phi$ 的自由变元, ($y$ 受囿的情况平凡, 且证明是无异的).

考虑表达式 $(\neg \psi (x_i,y,x_{k_1},\dots ,x_{k_n}))$. 在 $a=\nu (y),b_1=\nu (x_{k_1}),\dots ,b_m=\nu (x_{k_m})$ 为参数下, 该表达式 $\neg \psi$ 所定义的集合非空 (根据假设 $(\mathcal{N},\mu )/\models \psi$). 所以根据初等子结构定义, 它与 $M$ 的交也非空.

这也就是说, 存在一个 $b\in M$ 使得 $\neg \psi (b,a,b_1,\dots ,b_n)$ 成立. 于是我们得到了一个赋值与 $\nu$ 在 $\phi$ 的自由变元上都取相等的值, 在 $x_i$ 取值在 $M$ 中但是仍旧不能得到 $\psi$. 因此 $(\mathcal{M},\nu )/\models \phi$.

$\square$

2应用

•	用来判定 $(\mathbb{Q},<)$ 是 $(\mathbb{R},<)$ 的一个初等子结构. 这是因为通过考虑其上的序自同构可以证明, 所有的可定义集都是有限个端点为有理数的区间的并.
•	可用以证明 Löwenheim–Skolem 定理.

3相关概念

•	初等子结构
•	可定义集

术语翻译

Tarski–Vaught 判别法 • 英文 Tarski–Vaught test, criterion