数理逻辑

• 命题逻辑
  • 命题逻辑的语言
  • 真值指派
  • 命题逻辑的一个推演系统
  • 命题逻辑的可靠性定理与完全性定理
• 一阶逻辑和形式证明
  • 一阶逻辑的语言的定义
  • 一阶逻辑的一个公理系统
  • 推理和元定理
  • 一阶语言的结构
  • 可定义性
  • 同态和同构

命题逻辑

命题逻辑的语言

古典命题逻辑的语言包括：

• 可数多个命题符号：$A_0, A_1, A_2, \cdots$。
• 5个联词：否定符号$\neg$、合取符号$\wedge$、析取符号$\vee$、蕴含符号$\rightarrow$、双蕴含符号$\leftrightarrow$。
• 括号：左括号“(”和右括号“)”。

合式公式由如下规则自定义：

• 每个命题符号$A_i$都是合式公式；
• 如果$\alpha$和$\beta$都是合式公式，那么$(\neg\alpha)$、$(\alpha\wedge\beta)$、$(\alpha\vee\beta)$、$(\alpha\rightarrow\alpha)$、$(\alpha\leftrightarrow\beta)$也是合式公式；
• 别无其他。

称一个满足上述条件中的(2)的表达式集合是封闭的。合式公式全体是最小的包含所有命题符号的封闭的表达式集。

归纳原理：令$P(\alpha)$是一个关于合式公式的性质，设

• 对所有命题符号$A_i$，性质$P(A_i)$都成立；
• 对所有的合式公式$\alpha$和$\beta$，如果$P(\alpha)$和$P(\beta)$成立，那么$P((\neg\alpha))$、$P((\alpha\wedge\beta))$、$P((\alpha\vee\beta))$、$P((\alpha\rightarrow\alpha))$、$P((\alpha\leftrightarrow\beta))$也成立，

那么$P(\alpha)$对所有合式公式都成立。

真值指派

定义真假值${T,F}$。$S$是一个命题符号的集合，$S$上的一个真值指派$v$是从$S$到真假值的映射$v:S\rightarrow{T,F}$。令$\bar{S}$为只含有$S$中的命题符号的公式集。将真值指派$v$扩张到$\bar{S}$得到$\bar{v}:\bar{S}\rightarrow{T,F}$，满足：

• 对任意$A\in S$，$\bar{v}(A)=v(A)$；
• $\bar{v}((\neg\alpha))=\begin{cases}T, &\bar{v}(\alpha)=F\F,&\text{其他}\end{cases}$;
• $\bar{v}((\alpha\wedge\beta))=\begin{cases}T, &\bar{v}(\alpha)=T\text{并且}\bar{v}(\beta)=T\F,&\text{其他}\end{cases}$;
• $\bar{v}((\alpha\vee\beta))=\begin{cases}T, &\bar{v}(\alpha)=T\text{或者}\bar{v}(\beta)=T\F,&\text{其他}\end{cases}$;
• $\bar{v}((\alpha\rightarrow\beta))=\begin{cases}F, &\bar{v}(\alpha)=T\text{并且}\bar{v}(\beta)=F\T,&\text{其他}\end{cases}$;
• $\bar{v}((\alpha\leftrightarrow\beta))=\begin{cases}T,&\bar{v}(\alpha)=\bar{v}(\beta)\F,&\text{其他}\end{cases}$。

定理：对任意$S$上的真值指派$v$都有唯一的一个扩张$\bar{v}:\bar{S}\rightarrow{T,F}$满足上述条件。

称真值指派$v$满足一个公式$\varphi$，如果$\bar{v}(\varphi)=T$。

称公式集$\varSigma$重言蕴含公式$\tau$，记为$\varSigma\vDash\tau$，也称$\tau$是$\varSigma$的语义后承。即对所有满足$\Sigma$的真值指派$v$都满足$\tau$，即如果对所有的公式$\sigma\in\varSigma$有$\bar{v}(\sigma)=T$，则$\bar{v}(\tau)=T$。

称一个公式$\tau$为重言式，记作$\vDash\tau$，如果$\varnothing\vDash\tau$。即重言式在所有真值指派下为真。

如果$\sigma\vDash\tau$且$\tau\vDash\sigma$，称$\sigma$和$\tau$重言等价。

命题逻辑的一个推演系统

证明是从假设到结论的一根逻辑链条，公理集是证明的起点，通过推理规则得到新的公式。

引入命题逻辑的一个推演系统$L$，它的公理集$\varLambda$为：

• $\alpha\rightarrow(\beta\rightarrow\alpha)$；
• $(\alpha\rightarrow(\beta\rightarrow\gamma))\rightarrow((\alpha\rightarrow\beta)\rightarrow(\alpha\rightarrow\gamma))$；
• $(\neg\beta\rightarrow\alpha)\rightarrow((\neg\beta\rightarrow\alpha)\rightarrow\beta)$。

系统$L$中只有一条推理规则——分离规则：从$\alpha$和$\alpha\rightarrow\beta$可以推出$\beta$。

从公式集$\varGamma$到公式$\varphi$的一个推演（证明）是一个有穷的公式序列$(\alpha_0, \alpha_1, \cdots, \alpha_n)$，满足$\alpha_n=\varphi$且对所有的$i\le n$有$\alpha_i$属于$\varGamma\cup\varLambda$或存在$j,k<i$，$\alpha_i$是从$\alpha_j$和$\alpha_k$中由分离规则得到的，即$\alpha_k=\alpha_j\rightarrow\alpha_i$。

如果存在$\varGamma$到$\varphi$的一个推演，称$\varphi$为$\varGamma$的一个内定理，记作$\varGamma\vdash\varphi$。

演绎定理：设$\varGamma$是一个公式集，$\alpha$和$\beta$为公式，则$\varGamma\cup{\alpha}\vdash\beta$当且仅当$\varGamma\vdash\alpha\rightarrow\beta$。

命题逻辑的可靠性定理与完全性定理

可靠性定理：设$\varSigma$是一个公式集，$\tau$是一个公式。如果$\varSigma\vdash\tau$则$\varSigma\vDash\tau$。特别地，如果$\vdash\tau$则$\vDash\tau$，即$L$中的每个内定理都是重言式。

完全性定理：如果$\varSigma\vDash\tau$，则$\varSigma\vdash\tau$。

称一个公式集$\varSigma$是不一致的（矛盾的），如果存在某个公式$\alpha$使得$\varSigma\vdash\alpha$且$\varSigma\vdash\neg\alpha$。称$\varSigma$是一致的如果它不是不一致的。

引理：$\varSigma$是不一致的当且仅当对所有的公式$\beta$，$\varSigma\vdash\beta$。

引理：$\varSigma\vdash\tau$当且仅当$\varSigma\cup{\neg\tau}$不一致。

称公式集$\varSigma$是可满足的，如果存在一个真值指派满足$\varSigma$中的所有公式。称$\varSigma$是不可满足的如果$\varSigma$不是可满足的。

引理：下列命题等价：

• 如果$\varSigma$一致，则$\varSigma$可满足；
• 如果$\varSigma\vDash\tau$，则$\varSigma\vdash\tau$。

称一个公式集$\varDelta$是极大一致的，如果$\varDelta$是一致的，并且对任何不在$\varDelta$中的公式$\alpha$，$\varDelta\cup{\alpha}$都是不一致的。

林登鲍姆引理：每一个一致的公式集$\varSigma$都可以扩张成一个极大一致集$\varDelta$。

引理：任何极大一致集$\varDelta$都是可满足的。事实上，定义真值指派$v(A)=T$当且仅当$A\in\varDelta$，则$v$满足$\varDelta$中的所有公式。

定理（完全性定理的弱形式）：如果$\vDash\tau$，则$\vdash\tau$。即每个重言式都是$L$的内定理。

紧致性定理：公式集$\varSigma$是可满足的当且仅当$\varSigma$的每一个有穷子集都是可满足的。

这里指出几个观察

1. $L$的可靠性证明是在$L$之外进行的
2. 命题逻辑的定理集是可判定的，存在一个算法来告诉我们$\alpha$是否是$L$的一个定理——列真值表来看是否是重言式。这种算法对一阶逻辑是不存在的。

一阶逻辑和形式证明

一阶逻辑的语言的定义

一阶逻辑的语言$L$包括：

• 括号：左括号“(”和右括号“)”；
• 命题连词：$\neg$和$\rightarrow$；
• （全称）量词符号：$\forall$；
• 变元：$v_1,v_2,\cdots$
• 常数符号若干；
• 函数符号若干；
• 谓词符号若干；
• 等词符号（可以没有）：$\approx$。

项是公式中的对象，自上而下地如下定义：

• 每个变元$v_i$是项；
• 每个常数符号是项；
• 如果$t_1,t_2,\cdots,t_n$是项，$f$是$n$元函数符号，则$ft_1t_2\cdots t_n$是项。

（合式）公式是项构成的表达式：

• 如果$t_1,t_2,\cdots,t_n$是项，$P$是$n$元谓词符号，则$Pt_1t_2\cdots t_n$是合式公式，这样的公式称为原子公式，特别地，$\approx t_1t_2$是原子公式
• 如果$\alpha$和$\beta$是合式公式，那么$(\neg\alpha)$、$(\alpha\rightarrow\beta)$是合式公式；
• 如果$\alpha$是合式公式，那么$(\forall v_i\alpha)$是合式公式。

在表达上：

• 引入符号$\vee$、$\wedge$、$\leftrightarrow$等
• 引入$\exists x\alpha$作为$(\neg\forall(\neg\alpha))$的缩写
• 对于二元谓词，可以把谓词写在项的中间，$u\approx t$表示$\approx ut$，$u\not\approx t$表示$\neg(\approx ut)$。

定义自由出现：

• 如果$\alpha$是原子公式，那么$x$在$\alpha$中自由出现当且仅当$x$在$\alpha$中作为项出现；
• 如果$\alpha$是$\neg\beta$，那么$x$在$\alpha$中自由出现当且仅当$x$在$\beta$中自由出现；
• 如果$\alpha$是$\alpha_1\rightarrow\alpha_2$，那么$x$在$\alpha$中自由出现当且仅当$x$在$\alpha_1$中自由出现或者$x$在$\alpha_2$中自由出现；
• 如果$\alpha$是$\forall v_i\beta$，那么$x$在$\alpha$中自由出现当且仅当$x$在$\beta$中自由出现且$x\ne v_i$。

如果变量出现但不是自由出现，则称为约束出现。如果公式$\alpha$中的变元都是约束出现，那么称$\alpha$是一个闭公式或语句。

公式中变元的替换，在公式$\alpha$中将变元$x$在其自由出现的地方用项$t$代替的公式，记作$\alpha^x_t$，递归定义如下：

• 如果$\alpha$是原子公式，那么$\alpha^x_t$是$\alpha$中所有$x$用$t$替代后得到的表达式；
• $(\neg\alpha)^x_t=(\neg\alpha^x_t)$；
• $(\alpha\rightarrow\beta)^x_t=(\alpha^x_t\rightarrow\beta^x_t)$；
• $(\forall y\alpha)^x_t=\begin{cases}\forall y\alpha,&x=y\\forall y(\alpha^x_t),&x\ne y\end{cases}$。

一阶逻辑的一个公理系统

一阶逻辑的推理系统和命题逻辑类似，推理规则依然只有分离规则，公理集$\varLambda$包含以下内容：

• 命题逻辑公理中(A1)、(A2)、(A3)的一阶公式；
• $\forall x\alpha\rightarrow\alpha^x_t$，其中项$t$可以在$\alpha$中替代$x$；
• $\forall x(\alpha\rightarrow\beta)\rightarrow(\forall x\alpha\rightarrow\forall x\beta)$；
• $\alpha\rightarrow\forall x\alpha$，其中$x$不在$\alpha$中自由出现。
• $x\approx x$
• $x\approx y\rightarrow(\alpha\rightarrow\alpha’)$，其中$\alpha$是原子公式，$\alpha’$是将$\alpha$中若干个$x$替换为$y$得到的公式。

如果一阶公式$\alpha$是原子公式（一个谓词公式）或全称公式（形如$\forall\beta$），则称为素公式。对任何一阶公式$\varphi$，将所有素子公式替换为命题符号（把一阶的新增内容替换成命题符号），就得到一个命题逻辑中的公式$\varphi’$。如果$\varphi’$是命题逻辑中的公理或重言式，那么$\varphi$就是形如公理或者一阶意义下的重言式。

定理（一阶意义的完全性定理）：如果$\varphi$是一个一阶意义下的重言式，则$\vdash\varphi$，即$\varphi$是一阶逻辑的一个内定理。

第二组公理称为替换公理，项$t$可以在$\alpha$中替代$x$，是指替换前自由出现的变元不能因替换而变得受约束。精确定义如下：

• 如果$\alpha$是原子公式，那么$t$总可以在$\alpha$中替代$x$；
• 如果$\alpha$是$\neg\beta$，那么$t$可以在$\alpha$中替代$x$当且仅当$t$可以在$\beta$中替代$x$；
• 如果$\alpha$是$\alpha_1\rightarrow\alpha_2$，那么$t$可以在$\alpha$中替代$x$当且仅当$t$可以在$\alpha_1$中替代$x$且$t$可以在$\alpha_2$中替代$x$；
• 如果$\alpha$是$\forall y\beta$，那么$t$可以在$\alpha$中替代$x$当且仅当$x$不在$\alpha$中自由出现；或$y$不在$t$中出现并且$t$在$\beta$中可以替换$x$。

第三组和第四组公理可以证明概括定理，即如果没有使用$x$的任何假设就证明了$\alpha(x)$，那么这个假设对任意$x$都成立，即：

概括定理：如果$\varGamma\vdash\varphi$，并且$x$不在$\varGamma$的任何公式中自由出现，那么$\varGamma\vdash\forall x\varphi$。

推理和元定理

引理（重言规则）：如果$\varGamma\vdash\alpha_1,\varGamma\vdash\alpha_2,\cdots,\varGamma\vdash\alpha_n$，并且$\alpha_1\rightarrow\alpha_2\rightarrow\cdots\rightarrow\alpha_n\rightarrow\beta$是一阶意义下的重言式，那么$\varGamma\vdash\beta$。

定理（演绎定理）：$\varGamma\cup{\gamma}\vdash\varphi$当且仅当$\varGamma\vdash(\gamma\rightarrow\varphi)$。

推论（逆否命题）：$\varGamma\cup{\varphi}\vdash\neg\psi$当且仅当$\varGamma\cup{\psi}\vdash\neg\varphi$。

推论（反证法）：如果$\varGamma\cup{\varphi}$不一致，那么$\varGamma\vdash\neg\varphi$。

证明的技巧：

若要从$\varGamma$证明$\psi\rightarrow\theta$，根据演绎定理，只需证明$\varGamma\cup{\psi}\vdash\theta$。

若要从$\varGamma$证明$\forall x\psi$，如果$x$不在$\varGamma$的任何公式中自由出现，根据概括定理，只需证明$\varGamma\vdash\psi$。后面我们会证明，即使$x$在$\varGamma$中自由出现，仍可以找到一个变元$y$使得$\varGamma\vdash\forall y\psi^x_y$且$\forall y\psi^x_y\vdash\forall x\psi$。

若要从$\varGamma$证明$\neg(\psi\rightarrow\theta)$，只需证明$\varGamma\vdash\psi$和$\varGamma\vdash\neg\theta$。

若要从$\varGamma$证明$\neg\neg\psi$，只需证明$\varGamma\vdash\psi$。

若要从$\varGamma$证明$\neg\forall x\psi$。尝试找到项$t$，它在$\psi$中可以替换$x$，然后证明$\varGamma\vdash\neg\psi^x_t$。不过这并不总是成立，因为前者推不出后者。如果做不出，之后可以尝试换位、归谬法等。

一阶逻辑是不可判定的，不存在一个算法对于任何可证的$\varphi$都提供一个证明。

定理（常数概括定理）：假设$\varGamma\vdash\varphi$，而$c$是一个不在$\varphi$中出现的常数符号，则存在不在$\varphi$中出现的变元$y$，使得$\varGamma\vdash\varphi^c_y$。进一步，存在一个从$\varGamma$到$\varGamma\forall y\varphi^c_y$的证明。

引理（循环替换引理）：如果变元$y$完全不在公式$\varphi$中出现，则变元$x$可以在公式$\varphi^x_y$中替换$y$并且$(\varphi^x_y)^y_x=\varphi$。

定理（约束变元替换定理）：设$\varphi$是一个公式，$x$是一个变元，$t$是一个项，总可以找到一个公式$\varphi’$，它和$\varphi$的区别仅在于约束变元，使得使得$\varphi\vdash\varphi’$且$\varphi’\vdash\varphi$，$t$可以在$\varphi’$中替换$x$。

最后是几个和等词有关的内定理

$\forall x,x\approx x$ $\forall x,y(x\approx y\rightarrow(y\approx x))$ $\forall x,y,z(x\approx y\rightarrow y\approx z\rightarrow x\approx z)$

此外，等词还和所有的谓词和函数相容

$\forall x_1\cdots\forall x_n\forall y_1\cdots\forall y_n(x_1\approx x_2\rightarrow\cdots\rightarrow x_n\approx x_n\rightarrow Px_1\cdots x_n\rightarrow Py_1\cdots y_n)$

$\forall x_1\cdots\forall x_n\forall y_1\cdots\forall y_n(x_1\approx x_2\rightarrow\cdots\rightarrow x_n\approx x_n\rightarrow fx_1\cdots x_n\approx fy_1\cdots y_n)$

一阶语言的结构

前述所有一阶逻辑都不包含任何语义，现在我们为语言中的每一个符号赋予意义，这个过程是通过挑选一个外部结构来完成的，这个过程同时规定量词的范围，并指定谓词、函数和常数符号的意义。

一个一阶语言的结构$\mathfrak{A}$是一个定义域为语言中的符号的函数，并且满足下列条件：

• $\mathfrak{A}$给量词符号指定一个非空集$

  \mathfrak{A}

  $，称为$\mathfrak{A}$的论域。

• 对每个$n$元谓词符号$P$，$\mathfrak{A}$指定一个$n$元关系$P^\mathfrak{A}\subseteq

  \mathfrak{A}

  ^n$。

• 对每个常数符号$c$，$\mathfrak{A}$指定$

  \mathfrak{A}

  $中的一个元素$c^\mathfrak{A}$。

• 对每个$n$元函数符号$f$，$\mathfrak{A}$指定一个函数$f^\mathfrak{A}:

  \mathfrak{A}

  ^n\rightarrow

  \mathfrak{A}

  $。

一个赋值$s$是一个从所有自由变元$V$到$

\mathfrak{A}

$的函数，即$s:V\rightarrow

\mathfrak{A}

$。固定一个语言$L$，令$\varphi$是$L$中的一个公式，$\mathfrak{A}$是一个$L$的结构，$s$是一个赋值，下面定义$(\mathfrak{A},s)\models\varphi$，即$\mathfrak{A}$满足$\varphi$在$s$下的赋值，为将$\varphi$按$\mathfrak{A}$翻译并将自由变元$x$赋值为$s(x)$，得到元语言的一个数学陈述，并通过数学知识得到这个陈述成立。精确而言：

• 将赋值$s$扩展到项，令$T$是所有表示项的集合，定义$\bar s:T\rightarrow

  \mathfrak{A}

  $：

  • 对每个变元符号$x$，$\bar s(x)=s(x)$；
  • 对每个常数符号$c$，$\bar s(c)=c^\mathfrak{A}$；
  • 对每个函数符号$f$和项$t_1,\cdots,t_n$，$\bar s(ft_1\cdots t_n)=f^\mathfrak{A}(\bar s(t_1),\cdots,\bar s(t_n))$。
• 对原子公式
  • $(\mathfrak{A},s)\vDash\approx t_1t_2$当且仅当$\bar s(t_1)=\bar s(t_2)$；
  • 对每个$n$元谓词符号$P$，$(\mathfrak{A},s)\vDash Pt_1\cdots t_n$当且仅当$(\bar s(t_1),\cdots,\bar s(t_n))\in P^\mathfrak{A}$。
• 对其他公式
  • $(\mathfrak{A},s)\vDash\neg\varphi$当且仅当$(\mathfrak{A},s)\nvDash\varphi$；
  • $(\mathfrak{A},s)\vDash\varphi\rightarrow\psi$当且仅当或者$(\mathfrak{A},s)\nvDash\varphi$或者$(\mathfrak{A},s)\vDash\psi$；

  • $(\mathfrak{A},s)\vDash\forall x\varphi$当且仅当对$

    \mathfrak{A}

    $中的每个元素$d$，$(\mathfrak{A},s^x_d)\vDash\varphi$，其中$s^x_d$是$s$将$x$替换为$d$的赋值，定义为：$s^x_d(x)=d$，$s^x_d(y)=s(y)$当$y\neq x$。

说明：

$(\mathfrak{A},s)\vDash\forall x\varphi$的含义是$\varphi(d)$都成立，然而这个记号没有含义，因为$d$不在语言中。为此只能采用赋值的方法。有的书会把它简记为$\varphi[d]$

如上的定义，是将对象语言中一阶语言的真假用元语言中的数学知识来判定（即$\mathfrak{A}\vDash\varphi$）。譬如$\varphi:\forall(x\cdot x\not\approx 1+1)$，就$\varphi$本身而言只是一个字符串，为它选定结构后，才能在有理数域$\mathbb{Q}$中判定为真，在实数域$\mathbb{R}$中判定为假。自然语言中，“雪是白的”一句为真，当且仅当物理世界中雪是白的。

设$\varGamma$是一个公式集，$\varphi$是一个公式，称$\varGamma$语义蕴含$\varphi$，记为$\varGamma\models\varphi$，当且仅当对每个结构$\mathfrak{A}$和每个赋值$s$，如果$\mathfrak{A}$和$s$满足$\varGamma$的所有成员，那么$\mathfrak{A}$和$s$也满足$\varphi$。

称两个公式$\varphi$和$\psi$语义等价，当且仅当$\varphi\models\psi$且$\psi\models\varphi$。

称一个公式$\varphi$普遍有效，当且仅当$\varnothing\vDash\varphi$，也记作$\vDash\varphi$。普遍有效的公式在一阶逻辑中的地位和重言式在命题逻辑中的地位类似。

定理：假定$s_1$和$s_2$是$V$到$

\mathfrak{A}

$的两个赋值函数，并且它们在公式$\varphi$中所有自由出现的变元上取值相同，那么$(\mathfrak{A},s_1)\vDash\varphi$当且仅当$(\mathfrak{A},s_2)\vDash\varphi$。

推论：对任何闭语句$\sigma$，赋值函数不影响其真假，即对所有赋值函数$s:V\rightarrow

\mathfrak{A}

$，$(\mathfrak{A},s)\vDash\sigma$，或者对所有赋值函数$s:V\rightarrow

\mathfrak{A}

$，$(\mathfrak{A},s)\nvDash\sigma$。如果前者满足，就称$\sigma$在$

\mathfrak{A}

$中真，记作$\mathfrak{A}\vDash\sigma$，也说$\mathfrak{A}$满足$\sigma$或$\mathfrak{A}$是$\sigma$的一个模型。

可定义性

设$\varSigma$是闭语句集，$\text{Mod}\varSigma$是$\varSigma$的所有模型构成的类。单个闭语句$\tau$的模型的类记作$\text{Mod}\tau$。称（同一个一阶语言上）的结构类$\mathcal{K}$为一个初等类，如果存在闭语句$\tau$使得$\mathcal{K}$是$\text{Mod}\tau$。称$\mathcal{K}$是一个广义初等类，如果存在闭语句集$\varSigma$使得$\mathcal{K}$是$\text{Mod}\varSigma$。有穷个闭语句可以通过合取变为一个闭语句，因此若$\varSigma$是有穷的闭语句集，则$\mathcal{K}=\text{Mod}\varSigma$是一个初等类。

称$k$元关系 \(\{(a_1,\cdots,a_k):\mathfrak{A}\vDash\varphi[a_1,\cdots,a_k]\}\)

为公式$\varphi$在$\mathfrak{A}$中定义的关系。这里$\mathfrak{A}\vDash\varphi[a_1,\cdots,a_k]$是指存在某个赋值$s$使得$(\mathfrak{A},s)\vDash\varphi$，并且$s(v_i)=a_i(1\le i\le k)$。称一个$

\mathfrak{A}

$上的$k$元关系为可定义的，如果存在某个公式$\varphi$在$\mathfrak{A}$中定义它。

同态和同构

令$\mathfrak{A}$和$\mathfrak{B}$是某语言的两个结构。称一个函数$h:|\mathfrak{A}|\rightarrow|\mathfrak{B}|$是$\mathfrak{A}$到$\mathfrak{B}$的一个同态，它满足：

• 对每个（不是等词）的$n$元谓词符号$P$，和每组$

  \mathfrak{A}

  $中的元素$a_1,\cdots,a_n$，都有$(a_1,\cdots,a_n)\in P^\mathfrak{A}\Leftrightarrow(h(a_1),\cdots,h(a_n))\in P^\mathfrak{B}$；

• 对每个$n$元函数符号$f$，和每组$

  \mathfrak{A}

  $中的元素$a_1,\cdots,a_n$，都有$h(f^\mathfrak{A}(a_1,\cdots,a_n))=f^\mathfrak{B}(h(a_1),\cdots,h(a_n))$；

• 对每个常数符号$c$，有$h(c^\mathfrak{A})=c^\mathfrak{B}$。

进一步，如果$h$是一个双射，则称它是一个同构。同时称$\mathfrak{A}$和$\mathfrak{B}$是同构，记作$\mathfrak{A}\cong\mathfrak{B}$。自身上的同构是自同构。

同态定理：设$h$是从$\mathfrak{A}$到$\mathfrak{B}$的同态，$s:V\rightarrow|\mathfrak{A}|$。则：

• 对任意项$t$，有$h(\bar s(t))=\overline{h\circ s}(t)$；
• 对任何不含量词且不含等词的公式$\alpha$，有$(\mathfrak{A},s)\vDash\alpha$当且仅当$(\mathfrak{B},\overline{h\circ s})\vDash\alpha$；如果$h$是单射，则$\alpha$可以包含等词；如果$h$是满射，则$\alpha$可以包含量词。

推论：任何自同构都保持可定义的关系。即设$h$是结构$\mathfrak{A}$上的自同构，$R$是$\mathfrak{A}$上的$n$元关系，则对任意$a_1,\cdots,a_n\in|\mathfrak{A}|$，都有 \((a_1,\cdots,a_n)\in R\Leftrightarrow(h(a_1),\cdots,h(a_n))\in R\)

固定某个语言$L$和其上的两个结构$\mathfrak{A}$和$\mathfrak{B}$，称$\mathfrak{A}$和$\mathfrak{B}$是初等等价的，记作$\mathfrak{A}\equiv\mathfrak{B}$，如果对$L$中的每个闭语句$\sigma$都有$\mathfrak{A}\vDash\sigma$当且仅当$\mathfrak{B}\vDash\sigma$。

同构的模型都是初等等价的，但是反之并不成立，只能说明语言不足描述出区别。