用户: 不萌/数理逻辑/子结构

1一阶结构的同构与同样

同构

在线性代数和抽象代数中, 我们有过线性空间同构和群同构的概念. 现在, 我们将这个概念推广到一般的一阶结构上面.

定义 1.1 (同构映射与同构). 一个一阶语言 ${\mathcal{L}}_{\mathcal{A}}$ 中, 两个结构 $\mathcal{M}=(M,I)$ 与 $\mathcal{N}=(N,J)$ 这两个结构被称为是同构的, 如果存在一个双射 $e:M\to N$, 满足:

•	两个结构对于常元的解释相对应, 即对于常元 $c\in \mathcal{A}$, 有 $e(I(c))=J(c)$;
•	两个结构对于函数符号的解释相对应, 即对于 $n$ 元函数符号 $F\in \mathcal{A}$, 对于任意的 $(a_0,a_1,a_2,\dots ,a_n)\in M^{n+1}$, $$a_0=I(F)(a_1,a_2,\dots ,a_n)\iff e(a_0)=J(F)(e(a_1),e(a_2),\dots ,e(a_n));$$
•	两个结构对于谓词的解释要求一致, 即对于任意的 $n$ 元谓词符号 $P$, 对于 $M^n$ 的任意一个点 $(a_1,a_2,\dots ,a_n)$, $$(a_1,a_2,\dots ,a_n)\in I(P)\iff (e(a_1),e(a_2),\dots ,e(a_n))\in J(P)$$

如果满足以上条件, 我们就称 $e$ 为 $\mathcal{M}$ 与 $\mathcal{N}$ 之间的同构映射, 并称 $\mathcal{M}$ 与 $\mathcal{N}$ 同构, 记作 $\mathcal{M}\cong \mathcal{N}$. 如果 $M=N$, 那么就称 $e$ 是一个自同构.

我们希望研究同构的结构的一阶语言性质, 于是我们有了以下定理:

定理 1.2 (同质定理). 设 $e:\mathcal{M}\to \mathcal{N}$ 是 $\mathcal{L}$-结构 $(M,I)$ 和 $(N,J)$ 间的一个同构映射, 那么对于 $(M,I)$ 上的赋值映射 $\nu$, 对于 $e$ 和 $\nu$ 的合成映射 $e\circ \nu$, 是 $(N,J)$ 上的一个赋值映射. 对于任意一个 $\mathcal{L}$ 的表达式 $\varphi$, 都有$$((M,I,\nu )\models \varphi )\iff ((N,J,e\circ \nu )\models \varphi ).$$

证明. 先说明同构映射的结论对于所有项都成立, 这一部分采用归纳法, 首先对常元符号与变元符号都成立, 然后对于项的建立过程进行归纳, 说明对于一个函数也成立.

然后再对于表达式来进行验证, 即对于等值式, 谓词式, 否定式, 全域式分别讨论. 这里对于全域式的情况进行证明, 其他情况比较容易 (这个情况也不困难).$♣$

现在假设 $\varphi$ 是 $(\forall x_i\phi )$. 假设 $(M,I,\nu )\models (\forall x_i\phi )$, 根据定义就是说, 对于任何一个 $(M,I)$ 赋值 $\mu$, 如果有 $\mu {\equiv }_{\varphi }\nu$, 就有 $(M,I,\mu )\models \phi$.

那么类似地, 我们要证明的就是对于任何一个 $(N,J)$ 赋值 ${\mu }^{\ast }$, 如果有 ${\mu }^{\ast }{\equiv }_{\varphi }e\circ \nu$, 就有 $(N,J,{\mu }^{\ast })\models \phi$.

那么因为 $e$ 是一个同构, 我们令 $\mu =e^{-1}\circ {\mu }^{\ast }$, 就有 $\mu {\equiv }_{\varphi }\nu$, 从而 $(M,I,\mu )\models \phi$, 根据归纳假设就有 $(N,J,{\mu }^{\ast })\models \phi$ 于是证毕.

当 $(M,I,\nu )/\models (\forall x_i\phi )$ 时, 直接取一个反例 $\mu$, 将 $e\circ \mu$ 赋值到 $(N,J)$ 上, 就根据归纳假设得到一个反例.

$\square$

应用替换定理 (??), 可以得到以下的推论:

推论 1.3.

1.

设 $♠$