NKU 第五次作业

T1

考虑 $\mathfrak{Q} = (\mathbb{Q},+)$.

找到 $\mathfrak{Q}$ 中 $4$ 个可定义的 $\mathbb{Q}$ 的子集，并且给出定义他们的公式.
证明在 $\mathfrak{Q}$ 中没有其他可定义的 $\mathbb{Q}$ 的子集.

(1) 以下给出四个可定义的 $\mathbb{Q}$ 的子集：
➀ $\left\lbrace 0 \right\rbrace$ ，定义它的公式为 $x+x=x$ .

➁ 基于 ➀，可以定义常量 $0$ ，那么此时 $\mathbb{Q}\sim\left\lbrace 0 \right\rbrace$ 是可定义的，利用如下的公式：

\[ \neg(x = 0) \]

➂ $\varnothing$ 是可定义的，根据公式 $\neg(x=x)$ 即可.

➃ $\mathbb{Q}$ 是可定义的，利用如下公式：

\[ (x=0)\lor (\neg (x=0)) \]

(2) 设 $\mathbb{Q}$ 的某个可定义子集为 $A$ ，此时设存在 $p\neq 0$ 且 $p\in A$ ，由于 $A$ 可定义，则对于任意的自同构 $\eta$ 都有 $A = \eta(A)$ .

考虑自同构 $\eta_n : x\to nx,(n\neq 0 \text{ and } n\in \mathbb{Q})$ （利用有理数的分配律即可证明其为自同构），此时对于 $p\in A$ ，必有 $np\in A$ ，由于对于任意的有理数 $q\neq 0$ ，都可以找到有理数 $n = \dfrac{q}{p}$ 使得 $q\in A$ . 因此必为以下几种情形：

不包含元素，则 $A=\varnothing$.
仅包含 $0$ ，也就是 $A = \left\lbrace 0 \right\rbrace$ .
不包含 $0$ 但包含非 $0$ 元素，即 $A = \mathbb{Q}-\left\lbrace 0 \right\rbrace$ .
包含 $0$ 和非 $0$ 元素，即 $A = \mathbb{Q}$ .

即 (1) 中的 $4$ 个可定义子集. $\square$

T2

一个相容理论 $T$ 被称为模型完全 (model complete) 的，如果对于所有的 $T$ 的模型 $\mathfrak{A}$ 和 $\mathfrak{B}$ ，当 $\mathfrak{A} \subseteq \mathfrak{B}$ ，就有 $\mathfrak{A}\prec \mathfrak{B}$.

例如，无端点的稠密线序理论 $T_{\text{(DLO)}}$ 是模型完全的.

$T$ 的模型 $\mathfrak{M}$ 被称为 $T$ 的一个主模型 (prime model) ，当且仅当对于 $T$ 的每个模型 $\mathfrak{A}$ ，都存在一个 $\mathfrak{M}$ 到 $\mathfrak{A}$ 的一个嵌入.

证明：一个有主模型的模型完全理论是完全的.

翻译勘误

之前的问题翻译有问题，现在的才是正确的中文翻译.

设 $T$ 为一个有主模型的模型完全理论，其主模型为 $\mathfrak{M}$ ，根据完全理论的等价条件，考虑证明 $T$ 的任意两个模型都是初等等价的.

取任意的两个模型 $\mathfrak{A}$ 和 $\mathfrak{B}$ ，此时 $\mathfrak{M}$ 到 $\mathfrak{A}$ 和 $\mathfrak{B}$ 均有嵌入，此时存在 $\mathfrak{A}'\subseteq \mathfrak{A}$ 和 $\mathfrak{B}'\subseteq \mathfrak{B}$ ，使得

\[ \mathfrak{A}'\simeq \mathfrak{M} \simeq \mathfrak{B}' \]

因此 $\mathfrak{M}\equiv \mathfrak{A}'\equiv \mathfrak{B}'$ ，而由于 $T$ 是模型完全的，所以 $\mathfrak{A}' \prec \mathfrak{A}$ ，也就有 $\mathfrak{A}\equiv \mathfrak{M}$ ，同理 $\mathfrak{B}\equiv \mathfrak{M}$ . 因此对于 $T$ 的任意两个模型 $\mathfrak{A}$ 和 $\mathfrak{B}$ 都有

\[ \mathfrak{A} \equiv \mathfrak{B} \]

故 $T$ 是完全的. $\square$

T3

假定一个语言 $L$ 仅有一个非逻辑符号 $P$ ，$P$ 为一个二元关系符号. 令 $\mathfrak{A}$ 为一个全域为 $|\mathfrak{A}|=\mathbb{Z}$ 的结构，且 $(a,b)\in P^\mathfrak{A}$ 当且仅当 $|a-b|=1$ ，因此 $\mathfrak{A}$ 可以视为一个无穷图：
$$ \cdots \leftrightarrow \bullet \leftrightarrow \bullet \leftrightarrow \bullet \leftrightarrow \cdots $$
证明：存在一个初等等价的结构 $\mathfrak{B}$ ，且它不是连通的 (connected) .

连通 (connected)

连通的 意为对于 $|\mathfrak{B}|$ 中的任意两个数，它们之间都存在一个路径 (path)；而从 $a$ 到 $b$ 的（长为 $n$ 的）路径表示一个序列 $\left\langle p_0,p_1,\cdots,p_n \right\rangle$ ，其中 $p_0=a,p_n=b$ ，并且 $(p_i,p_{i+1})\in P^\mathfrak{B}$ 对任意 $i\in \left\lbrace 0,1,\cdots,n-1 \right\rbrace.$

提示：加入常量符号 $c$ 和 $d$ ，并写下语句说明 $c$ 和 $d$ 相距较远 (far apart) ，利用紧性.

引入常量符号 $c$ 和 $d$ ，记 $\varphi_n$ 为如下的语句

\[ \varphi_n = \neg\exists x_1\exists x_2\cdots \exists x_n\left(\bigwedge_{i=1}^{n-1} Px_ix_{i+1}\right) \]

其中 $x_1=c,x_n=d$ ，该语句即说明不存在一个 $n$ 长的路径连通 $c$ 和 $d$ . 令 $\Gamma = T\cup \left\lbrace \varphi_n : n \in \omega \right\rbrace$ . 其中 $\mathrm{Th}(\mathfrak{A})$ ，考虑其有限子集：

\[ \Gamma_{n_0} = T'\cup \left\lbrace \varphi_{n}: n \leqslant n_0\right\rbrace \]

其中 $T'$ 为 $T$ 的有限子集，且对于任意的 $\Gamma$ 的有限子集 $\Gamma'$，都存在 $n_0$ 使得 $\Gamma' \subseteq \Gamma_{n_0}$ ，此时 $\Gamma_{n_0}$ 也为有限语句集，由于 $c$ 和 $d$ 之间足够远，因此任意 $n_0$ ， $\Gamma_{n_0}$ 有模型.

这说明 $\Gamma$ 的所有有限子集都有模型，即 $\Gamma$ 有限相容，那么根据 ACCT ，$\Gamma$ 也是有模型的，但是对于 $\Gamma$ ，若连通图为其模型，则 $c,d$ 连通，其路径长度必然有限，这就和 $\Gamma$ 中的 $\left\lbrace \varphi_n:n\in \omega \right\rbrace$ 矛盾，因此 $\Gamma$ 存在非连通图为其模型. 该非连通图 $\mathfrak{B}$ 即为题中所需模型. $\square$

NKU 第五次作业

评论