数学结构 (Structure)

同构 (Isomorphism)

数学结构的同构

下面讨论结构上的同构，给出两个数学结构同构的定义：

定义：数学结构的同构

给定两个数学结构 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) ，称两个结构同构，符号上记为 \(\mathfrak{A}\simeq \mathfrak{B}\) ，当且仅当存在双射 \(\eta: |\mathfrak{A}|\to |\mathfrak{B}|\) 满足：

1. 对于 \(p\in \mathrm{Rs}_L\) 且所有的 \(a_0,\cdots,a_{\nu_L(p)-1}\in |\mathfrak{A}|\) ，有 $$ p^\mathfrak{A}(a_0,\cdots,a_{\nu_L(p)-1})\iff p^\mathfrak{B} (\eta(a_0),\cdots,\eta(a_{\nu_L(p)-1})) $$
2. 对于每个 \(f\in \mathrm{Fs}_L\) 和所有的 \(a_0,\cdots,a_{\nu_L(p)-1}\in |\mathfrak{A}|\) ，有 $$ \eta \left(f^\mathfrak{A}(a_0,\cdots,a_{\nu_L(p)-1})\right) = f^\mathfrak{B} (\eta(a_0),\cdots,\eta(a_{\nu_L(p)-1})) $$
3. 对于每个 \(c\in \mathrm{Cs}_L\) ，\(\eta(c^\mathfrak{A}) = c^\mathfrak{B}\) .

这里和我们在群论当中同构的定义非常类似，如果 \(\mathfrak{A}\simeq \mathfrak{A}\) ，那么也称自同构.

例：证明同构

设 \(\mathfrak{A} = (\mathbb{R},<,+,0)\) ，\(\mathfrak{B} = (\mathbb{R}^{>0},<,\times ,1)\) ，证明二者同构.

要考虑构造双射，就必须要考虑一个双射 \(\eta\) 使得：

• \(r< s \iff \eta (r)< \eta(s)\) ；
• \(\eta (r+s) = \eta(r)\times \eta(s)\) ；
• \(\eta(0)=1\) .

第二个由数学分析的 Cauchy 方程可以得到 \(\eta(x) = a^x\) 成立. 检验发现这确实满足如上的三个条件. \(\square\)

初等等价

定义：初等等价

对于任意的 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) ，\(\mathfrak{A}\) 和 \(\mathfrak{B}\) 是初等等价的当且仅当对于所有的 \(L\)-语句 \(\varphi\) 有
$$ \underset{\mathfrak{A}}{\models}\varphi \iff \underset{\mathfrak{B}}{\models} \varphi $$
从符号上它可以表示为 \(\mathfrak{A}\equiv \mathfrak{B}\) .

其实从定义来说，初等等价看起来和同构比较类似，之后我们会进行讨论：初等等价比同构要强.

诱导指派、依从

定义：诱导指派、依从

对于任意的 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) ，以及函数 \(\eta: |\mathfrak{A}|\to |\mathfrak{B}|\) ，

1. 对于任意的 \(\mathfrak{A}\)-指派 \(\alpha\) ，诱导 \(\mathfrak{B}\)-指派 (induced assignment) 定义为：$$ \alpha^\eta (x) = \eta(\alpha(x)) $$
2. \(\eta\) 依从 (respect) 一个项 \(t\) 当且仅当对于每个 \(\mathfrak{A}\) 指派 \(\alpha\) 都有 $$ \eta(t^\mathfrak{A}[\alpha]) = t^\mathfrak{B}[\alpha^\eta]; $$
3. \(\eta\) 依从 一个公式 \(\varphi\) 当且仅当对于每个 \(\mathfrak{A}\) 指派 \(\alpha\) 都有 $$ \underset{\mathfrak{A}}{\models} \varphi[\alpha]\iff \underset{\mathfrak{B}}{\models} \varphi[\alpha^\eta]$$

翻译问题

这里面的 respect 的翻译“依从”是本人的翻译，我并不知道是否有相对正式的译名.

例

设 \(\mathfrak{A} = (\mathbb{R},<,+,0)\) ，\(\mathfrak{B} = (\mathbb{R}^{>0},<,\times ,1)\).

这个例子和之前的例子基本一致，但是这次我们要进行一个依从的说明.

设 \(t\) 为项 \(x*(y*c)\) ，并且 \(\alpha\) 为一个指派，使得 \(\alpha(x) = \pi, \alpha(y) = 7\) .

我们已经证明这两个结构是同构的，现在取对应的双射 \(\eta\) 有：

\[ \eta(t^\mathfrak{A}[\alpha]) = \eta(\pi+(7+0)) \]

根据其保持运算和关系，有

\[ \begin{aligned} \eta(\pi+(7+0)) &= \eta(\pi)\times (\eta(7)\times \eta(0)) \\ &= t^\mathfrak{B}[\alpha^\eta] \end{aligned} \]

这也就说明 \(\eta\) 依从于项 \(t\) . \(\square\)

同构和初等等价的关系

引理

对于任意的 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) 以及 \(\eta: \mathfrak{A}\simeq \mathfrak{B}\) ，\(\eta\) 依从所有 \(L\)-项和 \(L\)-公式.

证明很繁复，就是依次将项和公式里面的 关系、存在量词和逻辑连接词进行证明，参考一下教材引理 2.3.6 即可.

由于 Hinman 说：

The calculation for other atomic formulas is similar, and the induction steps for ¬ and ∨ are straightforward; we leave them to the reader.

我们还是证明一下当作练习吧. 用 \(\neg\) 当作例子即可.

首先基于原子公式的情形，设 \(\varphi,\psi\) 为原子公式，我们有：

\[ \begin{aligned} \underset{\mathfrak{A}}{\models} (\neg\varphi)[\alpha] &\iff \underset{\mathfrak{A}}{|\!\!\!\neq}\ \varphi[\alpha] \\ &\iff \underset{\mathfrak{B}}{|\!\!\!\neq}\ \varphi[\alpha^\eta] \\ &\iff \underset{\mathfrak{B}}{\models} (\neg\varphi)[\alpha^\eta] \end{aligned} \]

\(\square\)

最后，利用如上的引理对如下的重要定理进行证明：

定理：同构推出初等等价

对于任意的 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) ，如果 \(\mathfrak{A}\simeq \mathfrak{B}\) ，那么 \(\mathfrak{A}\equiv \mathfrak{B}\) .

设 \(\eta\) 为 \(\mathfrak{A}\) 到 \(\mathfrak{B}\) 的同构映射，那么根据引理，如果 \(\varphi\) 为语句，由于 \(\eta\) 必定依从 \(\varphi\) ，有：

\[ \begin{aligned} \underset{\mathfrak{A}}{\models} \varphi &\iff \text{任意指派 } \alpha, \underset{\mathfrak{A}}{\models} \varphi[\alpha] \\ &\iff \text{任意指派 } \alpha, \underset{\mathfrak{B}}{\models} \varphi[\alpha^\eta] \\ &\iff \underset{\mathfrak{B}}{\models} \varphi \end{aligned} \]

\(\square\)

\(L_=\) 中的同构

在 \(L_=\) 中，由于我们并没有非逻辑符号，此时我们仅仅只需要考虑全域 \(A\) ，故我们将 \(L_=\) 中以 \(A\) 为全域的结构写为 \((A)\)，此时它们的同构关系非常容易说明：

命题：\(L_=\) 中的同构

对于任意的两个 \(L_=\) 结构 \((A)\) 和 \((B)\) . 有
$$ (A)\simeq (B) \iff |A| = |B| $$

此时，对于初等等价关系 \((A)\equiv (B)\) ，如果我们考虑 \(\exists^{=n}\) ，根据命题，我们能推出 \((A)\simeq (B)\) . 那么教材上的 Corollary 2.3.9 实际上就是在阐述：

定理

对有限集 \(A\) 和 \(B\) ，如果 \((A)\equiv (B)\) ，那么 \((A)\simeq (B)\) . 更进一步，\(L_=\) 中初等等价和同构是等价的.

如果用符号语言来表述，令 \(\theta^{(A)} = \exists^{=n}\) ，就能说明

\[ (A)\simeq (B) \iff \underset{(B)}{\models} \theta^{(A)} \]

有限结构

定义：有限结构

一个 \(L\)-结构 \(\mathfrak{A}\) 是有限的（至多可数的、可数的）当且仅当其全域 \(A\) 是一个有限（至多可数、可数）集.

这个相对比较好理解，就不多说了.

在 \(L_=\) 中的同构当中，我们用

\[ (A)\simeq (B) \iff \underset{(B)}{\models} \theta^{(A)} \]

来表现出它们的同构关系，其中 \(\theta^{(A)}\) 是一个语句，我们能否将这样的性质进行推广？我们在这里看似依赖了 \(L_=\) 的性质，但是实际上我们依赖的是 \(A\) 和 \(B\) 的有限性. 因此我们能推广到所有的有限结构：

定理：有限结构的等价与同构、刻画

对于任意的有限的一阶语言（即非逻辑符号有限） \(L\) 和有限结构 \(\mathfrak{A}\) ，

1. 对于任意的 \(L\)-结构 \(\mathfrak{B}\) ，如果 \(\mathfrak{A}\equiv \mathfrak{B}\) ，那么 \(\mathfrak{A}\simeq \mathfrak{B}\) ；
2. 事实上，存在一个单 \(L\)-语句 \(\theta^\mathfrak{A}\) ，它将 \(\mathfrak{A}\) 刻画 (characterizes) 到同构，意思是说对于任意的结构 \(\mathfrak{B}\) ， $$ \mathfrak{A}\simeq \mathfrak{B}\iff \underset{\mathfrak{B}}{\models} \theta^\mathfrak{A} $$

在后续的章节中再进行证明，此时只需了解即可. 教材上目前也仅仅是在有二元关系和一元函数的结构当中的弱化证明.

子结构

定义：子结构

对于任意的 \(L\)-结构 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) ，\(\mathfrak{A}\) 是 \(\mathfrak{B}\) 的一个子结构，符号表示为 \(\mathfrak{A}\subseteq \mathfrak{B}\) 当且仅当

1. \(|A|\) 是 \(|B|\) 的子集.
2. 对任意的 \(p\in \mathrm{Rs}_L\) ，\(p^\mathfrak{A} = p^\mathfrak{B}\cap |\mathfrak{A}|^{\nu_L(p)}\) ；
3. 对任意的 \(f\in \mathrm{Fs}_L\) ，\(f^\mathfrak{A} = f^\mathfrak{B}\upharpoonright |\mathfrak{A}|^{\nu_L(f)}\) ；
4. 对任意的 \(c\in \mathrm{Cs}_L\) ，\(c^\mathfrak{A} = c^\mathfrak{B}\) ；

符号说明

其中的 \(\upharpoonright\) 表示一个函数在一个集合上的限制. 例如 \(f \upharpoonright A\) 就是指将 \(f\) 的定义域限制到 \(A\) 上. 类似于我们在点集拓扑中看到的 \(f|_A\) .

简单来说就是保持关系，保持函数，保持常量. 看一个简单的例子：

• \((\omega,<_\omega)\) 是 \((\mathbb{Z},<_\mathbb{Z})\) 的子结构，但不是 \((\mathbb{Z},\leqslant_{\mathbb{Z}})\) 或者 \((\mathbb{Z},<_\mathbb{Z},0)\) 的子结构.

是子结构的部分就不多说，不是的部分也比较简单：前者关系出现了变化，后者常量出现了变化.

命题

对于任意 \(L\)-结构 \(\mathfrak{B}\) 以及 \(|\mathfrak{B}|\) 的任意非空子集 \(A\) ，\(A\) 能称为 \(\mathfrak{B}\) 的某个子结构 \(\mathfrak{A}\) 的全域当且仅当如下两条均成立：

1. 对于任意 \(f\in \mathrm{Fs}_L\) ，\(A\) 在 \(f^\mathfrak{B}\) 下封闭.
2. 对于任意常量 \(c\in \mathrm{Cs}_L\)，\(c^\mathfrak{B}\in A\).

其实翻译成人话就是：常量得在全域里面。函数值也不能跑出全域.

例题：子结构问题

下列哪些是 \((\mathbb{R},<,\cos,\pi)\) 的子结构？

• \(([-1,0],<,\cos,\pi)\)
• \(([-\pi,\pi],<,\cos,\pi)\)
• \(([0,2\pi],<,\cos,\pi)\)

首先，常量至少必须在全域当中，第一个自然不是子结构，同时，尽管函数 \(\cos\) 的定义域被限制，但是其值不能跑出全域当中，所以第三个有问题 （\(\cos \pi = -1\)），因此只有第二个是子结构. \(\square\)

生成的子结构

命题：生成的子结构

对于任意 \(L\)-结构 \(\mathfrak{B}\) 以及 \(|\mathfrak{B}|\) 的任意子集 \(X\) ，如果有 \(X\neq \varnothing\) 或 \(\mathrm{Cs}_L\neq \varnothing\) ，那么存在一个唯一的最小子结构 \(\left\langle X \right\rangle_\mathfrak{B} \subseteq \mathfrak{B}\) ，使得 \(X \subseteq |\left\langle X \right\rangle|_\mathfrak{B}\) ，这个最小子结构称为 \(X\) 生成的 \(\mathfrak{B}\) 的子结构，如果 \(X\) 和 \(L\) 都是可数的，那么 \(\left\langle X \right\rangle_\mathfrak{B}\) 也是.

对于给定的 \(X \subseteq |\mathfrak{B}|\) ，我们令 \(A\) 为 \(|\mathfrak{B}|\) 的满足如下条件的最小子集：

\[ X \cup \left\lbrace c^\mathfrak{B}: c\in \mathrm{Cs}_L \right\rbrace\subseteq A \]

并且 \(A\) 要在 \(f^\mathfrak{B} \ (f\in \mathrm{Fs}_L)\) 函数的意义下封闭，此时 \(A \neq \varnothing\) 是显然成立的，此时令 \(|\left\langle X \right\rangle_\mathfrak{B}| = A\) 即可. 生成的子结构就是 \(X\cup \left\lbrace c^\mathfrak{B}: c\in \mathrm{Cs}_L \right\rbrace\) 在 \(\left\lbrace f^\mathfrak{B}: f\in \mathrm{Fs}_L \right\rbrace\) 下的归纳闭包. \(\square\)

例题：生成的子结构

求集合 \(\left\lbrace 30,42 \right\rbrace\) 生成的群 \((\mathbb{Z},+,-,0)\) 的子结构.

利用加减法可以算出由 \(30,42\) 可以算出所有的 \(6\) 的倍数，生成的子结构为：

\[ (\left\lbrace 6n:n\in \mathbb{Z} \right\rbrace,+,-,0) \]

\(\square\)

无量词公式 (Quantifier-free formulas)

定义：布尔组合、无量词公式

对于任意公式集 \(\Gamma\) ，其布尔组合 (Boolean Combinations) \(\mathrm{Bool}(\Gamma)\) 表示包含 \(\Gamma\cup \left\lbrace \mathrm{T} \right\rbrace\) 的最小集合. 特别的，定义无量词公式集为
$$ \mathrm{QF} := \mathrm{Bool}(\mathrm{AtFm}_L) $$

这里给几个例子：
- 无常量的语言 \(L\) .
无常量的语言 \(L\) 中，\(\mathrm{T}\) 必须包含量词，这就出现 \(\mathrm{QF}\) 中包含有量词的语句的情形，非常离谱. 但是这是定义，我们还是得接受，原文是这么写的：

The special sentence T must actually contain a quantifier, so QF is not completely free of quantifiers. This will never cause any problems.

不会引起任何问题（迫真）.

引理

对于任意的结构 \(\mathfrak{A}\subseteq \mathfrak{B}\) ，任意的项 \(t\) 和任意的 \(\mathfrak{A}\) 指派 \(\alpha\) ，\(t^\mathfrak{A}[\alpha] = t^\mathfrak{B}[\alpha]\).

利用项归纳，细节参考书本. \(\square\)

命题：子结构的等价条件

对于任意的 \(L\)-结构 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) ，\(\mathfrak{A}\) 为 \(\mathfrak{B}\) 的子结构当且仅当如下两个条件同时成立：

1. \(|\mathfrak{A}| \subseteq |\mathfrak{B}|\) .
2. 对于任意的无量词 \(L\)-公式 \(\varphi\) 和任意 \(\mathfrak{A}\) 指派 \(\alpha\) 都有： $$ \underset{\mathfrak{A}}{\models} \varphi[\alpha] \iff \underset{\mathfrak{B}}{\models} \varphi[\alpha] $$

要做的就是定义里面的逐项验证. 在此不逐一验证.

需要注意的就是最后一个等价关系：
- 初等等价的情况下，它不需要无量词的条件；
- 子结构的等价条件里，它需要的只是无量词等价的条件.

逻辑全称、逻辑存在

定义：逻辑全称、逻辑存在

1. 一个公式是全称 (universal) 的（或者存在 (existential) 的），当且仅当对于一些无量词公式 \(\theta\) 和变量 \(y_0,\cdots,y_{n-1}\) ，\(\psi\) 为 \(\forall y_0 \cdots \forall y_{n-1} \theta (\exists y_0\cdots \exists y_{n-1}\theta)\) .
2. 一个公式是逻辑全称 (logically universal) 的或者逻辑存在 (logically existential) 的当且仅当对于一些全称的或者存在的公式 \(\psi\) ，有 \(\models \varphi\leftrightarrow \psi\) .

向上一致/向下一致 (upward/downward persistent)

定义：向上一致/向下一致

一个公式 \(\varphi\) 是向上一致 (upward persistent) 的当且仅当对任意的结构 \(\mathfrak{A}\subseteq \mathfrak{B}\) 和任意的 \(\mathfrak{A}\) 指派 \(\alpha\) ，
$$ \underset{\mathfrak{A}}{\models} \varphi[\alpha] \Rightarrow \underset{\mathfrak{B}}{\models} \varphi[\alpha] $$
反向即为向下一致 (downward persistent) ：
$$ \underset{\mathfrak{A}}{\models} \varphi[\alpha] \Leftarrow \underset{\mathfrak{B}}{\models} \varphi[\alpha] $$

翻译问题

这里面还是我个人的翻译，如果有更好的翻译请指出.

命题：逻辑全称和向上一致的关系

1. 如果 \(\varphi\) 是逻辑存在的，那么 \(\varphi\) 是向上一致的.
2. 如果 \(\varphi\) 是逻辑全称的，那么 \(\varphi\) 是向下一致的.

证明：仅考虑最简单的情形：\(\models \varphi\leftrightarrow \exists x \theta\) ，其中 \(\theta\) 为无量词公式.

\[ \begin{aligned} \underset{\mathfrak{A}}{\models} \varphi[\alpha] &\iff \underset{\mathfrak{A}}{\models} \exists x \theta [\alpha] \\ &\iff \text{for some }a\in A, \underset{\mathfrak{A}}{\models}\theta[\alpha_{x\to a}] \\ &\iff \text{for some }a\in A, \underset{\mathfrak{B}}{\models}\theta[\alpha_{x\to a}] \\ &\Longrightarrow \text{for some }a\in B, \underset{\mathfrak{B}}{\models}\theta[\alpha_{x\to a}] \\ &\iff \underset{\mathfrak{B}}{\models} \varphi[\alpha]. \end{aligned} \]

\(\square\)

同态和嵌入

同态与嵌入的定义

定义：同态和嵌入

对于任意的结构 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) 以及任意的函数 \(\eta: |\mathfrak{A}|\to |\mathfrak{B}|\) ，

1. \(\eta\) 是 \(\mathfrak{A}\) 到 \(\mathfrak{B}\) 的 同态 (homomorphism)（符号上记为 \(\eta:\mathfrak{A}\to \mathfrak{B}\)） 当且仅当 \(\eta\) 在同构的基础上去掉单射或满射的条件.
2. \(\eta\) 是 \(\mathfrak{A}\) 到 \(\mathfrak{B}\) 的嵌入 (embedding) （符号上记为 \(\mathfrak{A}\hookrightarrow_0 \mathfrak{B}\)）当且仅当 \(\eta\) 是一个单同态（即同构去掉满射条件）. 同时称 \(\mathfrak{A}\) 是可嵌入 (embeddable) 到 \(\mathfrak{B}\) 的，如果存在一个嵌入映射：\(\mathfrak{A}\hookrightarrow_0 \mathfrak{B}\).

推论

对于任意结构 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) 以及任意同态 \(\eta :\mathfrak{A}\to \mathfrak{B}\) ，

1. \(\eta\) 依从 (respect) 每个项以及每个不包含 \(=\) 的无量词公式.
2. 如果 \(\eta\) 是一个嵌入，那么 \(\eta\) 依从每个无量词公式；
3. 如果 \(\eta\) 是满射，那么 \(\eta\) 依从每个不包含 \(=\) 的公式.

证明见计算机集合论与逻辑第四次作业. \(\square\)

嵌入的等价条件

定理：嵌入的等价条件

对于任意的结构 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) ，以及任意的函数 \(\eta: |\mathfrak{A}|\to \mathfrak{B}\) ，下列结论等价：

1. \(\eta\) 是一个嵌入；
2. \(\eta\) 依从于所有的无量词公式；
3. 存在（唯一的）子结构 \(\mathfrak{A}'\subseteq \mathfrak{B}\) ，\(\eta: \mathfrak{A}\simeq \mathfrak{A}'\).

这个定理就是之前嵌入相关性质的一个总结.

初等子结构与初等扩张

定义：初等子结构、初等扩张

对于所有的 \(L\)-结构 \(\mathfrak{A}\) 和 \(\mathfrak{B}\)，称 \(\mathfrak{A}\) 是 \(\mathfrak{B}\) 的初等子结构或者 \(\mathfrak{B}\) 是 \(\mathfrak{A}\) 的初等扩张 （符号上记为 \(\mathfrak{A}\prec \mathfrak{B}\)），如果如下两条成立：

1. \(|\mathfrak{A}| \subseteq |\mathfrak{B}|\) .
2. 对于任意的公式 \(\varphi\) 和 \(\mathfrak{A}\) 指派 \(\alpha\) ： $$ \underset{\mathfrak{A}}{\models} \varphi[\alpha]\iff \underset{\mathfrak{B}}{\models} \varphi[\alpha] $$

需要注意的是 初等等价+子结构 要弱于初等子结构.

初等等价的条件是初等子结构第二个条件的弱化版（初等等价仅要求无量词公式）. 而子结构根据定义也是比较显然的，所以有

命题：初等等价+子结构弱于初等子结构

如果 \(\mathfrak{A}\prec \mathfrak{B}\) ，那么 \(\mathfrak{A}\subseteq \mathfrak{B}\) 且 \(\mathfrak{A}\equiv \mathfrak{B}\).

反过来不成立，可以给出如下的反例：

反例

\(\mathfrak{A} = (\omega \sim \left\lbrace 0 \right\rbrace, \leqslant)\) 且 \(\mathfrak{B} = (\omega,\leqslant)\) .

\(\mathfrak{A} \subseteq \mathfrak{B}\) 和 \(\mathfrak{A}\equiv \mathfrak{B}\) 是显然的（后者由同构推出），然而，\(\mathfrak{A}\prec \mathfrak{B}\) 是不成立的，因为

\[ \underset{\mathfrak{A}}{\models} \forall y (x \leqslant y)[1] \]

也就是说 \(1\) 是 \(\mathfrak{A}\) 中最小元素，但是

\[ \underset{\mathfrak{B}}{|\!\!\!\neq} \forall y (x \leqslant y) [1] \]

因此 \(\mathfrak{A}\) 不为 \(\mathfrak{B}\) 的初等子结构. \(\square\)

例题：证明初等子结构

设 \(\mathfrak{A} = (\mathbb{R}^+,<)\) 和 \(\mathfrak{B} = (\mathbb{R},<)\)，证明：\(\mathfrak{A}\prec \mathfrak{B}\) .

要证：

\[ \underset{\mathfrak{A}}{\models} \varphi[\alpha]\iff \underset{\mathfrak{B}}{\models} \varphi[\alpha] \]

设 \(\varphi\) 的自由变量为 \(x_0,\cdots,x_{k-1}\) ，\(\alpha(x_i) = a_i (i=0,1,\cdots,k-1)\) ，只需证明：

\[ \underset{\mathfrak{A}}{\models} \varphi[a_0,\cdots,a_{k-1}]\iff \underset{\mathfrak{B}}{\models} \varphi[a_0,\cdots,a_{k-1}] \]

构造同构 \(y:\mathbb{R}^+\to \mathbb{R}\) 使得 \(y(a_i)=a_i\) 即可. \(\square\)

Tarski 判别法和可数下行 Löwenhiem-Skolem 定理 (\(\mathrm{CLS}\downarrow\))

Tarski （塔斯基）判别法

定理：Tarski 判别法

如果 \(\mathfrak{A}\subseteq \mathfrak{B}\) 且对于每个 \(L\)-公式 \(\psi\) 和每个 \(\mathfrak{A}\) 指派 \(\alpha\) 和变元 \(x\) ，
$$ \underset{\mathfrak{B}}{\models} (\exists x \psi)[\alpha] \iff \text{存在一些 }a\in |\mathfrak{A}|, \underset{\mathfrak{B}}{\models} \psi[\alpha_{x\to a}]$$
那么 \(\mathfrak{A}\prec \mathfrak{B}\) .

要证明 \(\mathfrak{A}\prec \mathfrak{B}\) ，就需要证明对于任意的 \(\mathfrak{A}\) 指派 \(\alpha\) 和任意的公式 \(\varphi\) ，都有

\[ \underset{\mathfrak{A}}{\models} \varphi[\alpha]\iff \underset{\mathfrak{B}}{\models} \varphi[\alpha] \]

考虑利用公式归纳法，根据子结构的等价条件，\(\varphi\) 为原子公式的时候已经不需证明，当有 \(\neg\) 和 \(\lor\) 时，利用子结构的等价条件的证明即可.

对 \(\varphi = \exists x \psi\) 的情形，那么

\[ \begin{aligned} \underset{\mathfrak{A}}{\models} \varphi [\alpha] &\iff \text{for some } a\in |\mathfrak{A}| , \underset{\mathfrak{A}}{\models}\psi[\alpha_{x\to a}] \\ &\iff \text{for some } a\in |\mathfrak{A}| , \underset{\mathfrak{B}}{\models}\psi[\alpha_{x\to a}] \\ &\iff \underset{\mathfrak{B}}{\models} \varphi[\alpha]. \end{aligned} \]

因此结论成立. \(\square\)

可数下行 Löwenhiem-Skolem 定理 (\(\mathrm{CLS}\downarrow\))

（这个部分较难，日后再补证明）

定理：\(\mathrm{CLS}\downarrow\)

对于任意可数语言 \(L\) ，任意的 \(L\) 结构 \(\mathfrak{B}\) 和任意 \(|\mathfrak{B}|\) 的可数子集 \(X\) ，存在可数的 \(L\) 结构 \(\mathfrak{A}\) 使得 \(X\subseteq |\mathfrak{A}|\) 且 \(\mathfrak{A}\prec \mathfrak{B}\) .

推论：\(\mathrm{CLS}\downarrow\) 的推论

设 \(L\) 是至多可数语言，\(\Gamma\) 为 \(L\)-语句集，若 \(\Gamma\) 有模型，则 \(\Gamma\) 有至多可数模型（即 \(\Gamma\) 有模型 \(\mathfrak{A}\) ，使得 \(|\mathfrak{A}|\) 为至多可数集）.

例

\(\mathfrak{R} = (\mathbb{R},<,+,\times,0,1)\)

根据 \(\mathrm{CLS}\downarrow\) ，可以知道存在一个可数的初等子结构

\[ \mathfrak{A} = (A,<,+,\times ,0,1) \]

由于 \(\mathfrak{A}\) 保持了加法逆元，四则运算和 \(n\) 次根号运算封闭，可以知道 \(A\) 包含了所有的实代数数.

---

现在我们将这个例子进一步推进，数学分析中的确界原理保证了 \(\mathbb{R}\) 中的每个有界子集都有上确界，而根据 Dedekind 分割对实数的一个确立，我们知道：包含了所有有理数且满足确界原理的线序集一定是不可数的.

但是 \(\mathfrak{A}\) 是可数的，这就说明 \(\mathfrak{A}\) 中不会有能表达出确界原理的语句. 另一方面，\(A\) 的一些有界子集的确有上确界，有哪些是有的？这就引出接下来可定义关系的定义.

可定义关系与可定义函数

可定义关系、函数及其例子

定义：可定义关系、函数

对任意的语言 \(L\) ，任意的 \(L\)-结构 \(\mathfrak{A}\) 以及任意的含有自由变量 \(x_0,x_1,\cdots,x_{m-1}\) 的 \(L\)-公式 \(\varphi\) ，对于 \(A\) 上的 \(m\) 元关系：
$$ \varphi^\mathfrak{A} := \left\lbrace (a_0,\cdots,a_{m-1})\in A^m : \underset{\mathfrak{A}}{\models} \varphi[a_0,\cdots,a_{m-1}] \right\rbrace $$
它被称为 \(\mathfrak{A}\) 上由 \(\varphi\) 定义的关系. 设 \(R \subseteq A^k\) ，若存在 \(\varphi\) 使得 \(R = \varphi^\mathfrak{A}\) ，则称 \(R\) 在 \(\mathfrak{A}\) 中是可定义关系.

更广泛地，如果 \(\varphi\) 在 \(x_0,\cdots,x_{m-1}\) 且 \(y_0,\cdots,y_{n-1}\) 中有自由变量，那么我们称

\[ \varphi^\mathfrak{A}_{b_0,\cdots,b_{n-1}} := \left\lbrace (a_0,\cdots,a_{m-1})\in A^m : \underset{\mathfrak{A}}{\models} \varphi[a_0,\cdots,a_{m-1},b_0,\cdots,b_{n-1}] \right\rbrace \]

在可定义关系的基础上，\(m\) 元函数 \(F: A^m \to A\) 在 \(\mathfrak{A}\) 上是可定义的，如果它的图像 (graph) ：
$$ \left\lbrace a_0,\cdots,a_{m-1},c: F(a_0,\cdots,a_{m-1}) = c \right\rbrace $$
也是可定义的.

\(A\) 中的一个元素是可定义的当且仅当 \(\left\lbrace a \right\rbrace\) 是可定义的.

这个定义比较长，我们需要来梳理一下.

首先，关系是否可定义实际上和集合是否可定义是一个问题，因为通常一个关系就能确定一个集合. 这个在之后的例子当中有详细的说明.

其次，函数是否可定义就是看它的定义域和值域的并是否为一个可定义集合.

最后，元素是否可定义看的是它的单例 (singleton) 是否可定义.

此外，对于可定义的问题，最终还是需要落在含有自由变量的语句 \(\varphi\) 上.

\(<\) 是可定义关系

\(\mathfrak{A} = (\omega,+,0)\) 中，\(<\) 为可定义关系.

需要证明一个关系是可定义关系，就需要利用仅有的条件来造语句表示，"\(x<y\)" 可以用如下的语句表示：

\[ \varphi: \exists z (\neg (z = 0) \land y = x+z) \]

可定义区间

\((3,\infty)\) 区间在 \((\mathbb{R},<)\) 上可定义.

这里涉及到我们刚才说明的集合可定义问题，现在我们发现这个区间中有常量，因此需要参数 \(3\) ，事实上这个集合就可以表示为：

\[ \left\lbrace a\in \mathbb{R}: \underset{(\mathbb{R,<})}{\models} (y<x)[a,3] \right\rbrace \]

其中，中括号的两个位置分别是对应 \(x,y\) 的指派. 这个集合实际上对应了一个一元关系，这个关系可以简单理解为：“在 \((3,\infty)\) 这个区间中”. 定义这个区间的语句就是 \(y<x\) .

有了这个概念，下面这个问题也就不难了：

例题

证明素数集在一阶算数语言 \(L_\Omega\) 下的 \((\Omega,\times,\dot{\mathrm{S}},0)\) 结构当中是可定义的.

考虑如下两个公式的合取：

• \(x\) 既不为 \(0\) 也不为 \(1\) ：\(\neg (x=0)\land \neg(x=\dot{\mathrm{S}}0)\) .
• 以及

\[ \forall y\forall z [y\times z = x \to (y=x)\lor (z=x)] \]

二阶逻辑

我们回顾刚才的有关确界原理的例子，我们考虑任意一个以 \(x\) 和 \(y_0,\cdots,y_{n-1}\) 为自由变量的公式 \(\varphi\) ，令 \(\varphi_{\mathrm{ub}}\) 为如下的公式：

\[ \forall z (x <z \to \neg \varphi_x (z)). \]

（我知道你可能不记得 \(\varphi_x\) 的含义了，它就是语句的代换，此时 \(z\) 是项）
这个公式的含义就是

同构意义下的可定义

命题：同构意义下的可定义

对于任意的 \(L\) 结构 \(\mathfrak{A}\) 和 \(\mathfrak{B}\) ，如果存在 \(\eta:\mathfrak{A}\simeq \mathfrak{B}\) ，那么对于任意以 \(x_0,\cdots,x_{m-1}\) 为自由变量的公式 \(\varphi\) ，有
$$ \varphi^\mathfrak{B} := \left\lbrace (\eta(a_0),\cdots,\eta(a_m)): (a_0,\cdots,a_{m-1})\in \varphi^\mathfrak{A} \right\rbrace. $$

特别地，如果 \(\eta\) 是 \(\mathfrak{A}\) 的一个自同构，那么 \(\varphi^\mathfrak{A} = \eta(\varphi^\mathfrak{A})\) ，此时称 \(\eta\) 保持 (preserve) 了 \(\varphi^\mathfrak{A}\) ，因此我们有

定理

所有的自同构都能保持无需参数的可定义关系.

这个定理说明了：如果存在一个自同构无法保持某个关系 \(p\) ，那么 \(p\) 就不是一个无需参数的可定义关系. 可以参考下面的例子.

不可定义关系

不含参公式无法定义的关系

\((\omega,\times,1)\) 无法使用不含参公式进行定义.

使用如下的自同构：

\[ \eta: 2^m \times 3^n \times p \mapsto 2^n \times 3^m \times p \]

其中 \(p\) 不为 \(2,3\) 倍数，而对 \(0\) 和 \(1\) 都是不变的.
为了方便理解，可以参考如下的表格：

\[ \begin{array}{ccccc} k & 0 & 1 & 2 & 3 \\ \eta(k) & 0 &1 & 3 & 2 \end{array} \]

这也就是说 \(\eta\) 作为自同构无法保持 \(<\) 关系，因此无法定义. \(\square\)

初等嵌入

定义：初等嵌入

一个函数 \(\eta:|\mathfrak{A}|\to |\mathfrak{B}|\) 如果依从所有的公式，那么它就被称为初等嵌入. 符号上记为 \(\eta: \mathfrak{A} \hookrightarrow \mathfrak{B}\) .

评论