Table of contents

結構

定義 2.1.1 結構 structure

結構是一個序列 $\mathfrak{A} = \langle A, R_1, ..., R_n, F_1, ...,F_m, \{ c_i|i\in I \} \rangle$，其中 $A$ 是非空集合、$R_1, ..., R_n$ 是 $A$ 上的關係、$F_1, ..., F_m$ 是 $A$ 上的函數、$c_i(i \in I)$ 是 $A$ 的常元。

定義 2.1.2 相似類型 similarity type

$\mathfrak{A} = \langle A, R_1, ..., R_n, F_1, ...,F_m, \{ c_i|i\in I \} \rangle$ 的相似類型是一個序列 $\langle r_1, ..., r_n; a_1, ..., a_m; \kappa \rangle$，其中 $R_i \subset A^{r_i}, F_j: A^{a_j} \rightarrow A, \kappa=| I |$。

相似類型的語言

以下，我們給定 $\langle r_1, ..., r_n; a_1, ..., a_m; \kappa \rangle$ 是一個相似類型，假定 $r_i \geq 0$ 且 $a_j > 0$。

以下是我們使用的符號：

• 述詞符號：$P_1, P_2, ..., P_n, =$。
• 函數符號：$f_1, f_2, ..., f_m$。
• 常元：$\bar{c_i} | i \in I$。
• 變元：$x_i | i \in \mathbb{N}$。
• 連接詞：$\land, \lor, \rightarrow, \neg, \leftrightarrow, \bot, \forall, \exists$。
• 輔助符號：$(,)$。

定義 2.2.1 詞項集

$TERM$（詞項集）是滿足下述性質的最小集合 $X$：

1. 常元 $Const$：$\bar{c_i}\in X(i\in I)$；
2. 變元 $Var$：$x_i \in X(i \in \mathbb{N})$；
3. 函數封閉性：若 $t_1, ..., t_{a_i} \in X$，則 $f_i(t_1, ..., t_{a_i}) \in X$。

定義 2.2.2 構句集

$FORM$（構句集）是滿足下述性質的最小集合 $X$：

1. $\bot \in X$；
2. 若 $r_i = 0$，則 $P_i \in X$（即 $P_i$ 是命題符號）；
3. 若 $t_1,...,t_{r_i} \in TERM$，則 $P_i(t_1,...,t_{r_i}) \in X$；
4. 若 $t_1, t_2 \in TERM$，則 $(t_1 = t_2) \in X$；
5. 若 $\phi,\psi \in X$，則 $(\phi \square \psi) \in X$；
6. 若 $\phi \in X$，則 $(\neg \phi) \in X$；
7. 若 $\phi \in X$，則 $\forall x_i \phi, \exists x_i \phi \in X$。

定理 2.2.3 歸納法與遞迴性

參考命題邏輯的定理 1.1.3與1.1.6，不難證明 $TERM$ 和 $FORM$ 都滿足一般與遞迴的歸納法原理。

詞項集的歸納法原理

令 $A(t)$ 為詞項的性質。若 $A(t)$ 對變數或常數 $t$ 成立，且若對所有函數 $f$ 都有 $A(t_1), A(t_2), . . . , A(t_n) \Rightarrow A(f (t_1, . . . , t_n))$，則 $A(t)$ 對所有 $t \in TERM$ 成立。

構句集的歸納法原理

令 $A(φ)$ 為構句的性質。若

1. 對原子句 $φ$，$A(φ)$ 成立，
2. $A(φ),A(ψ)⇒A(φ \land ψ)$，
3. $A(φ)⇒A(¬φ)$，
4. 對所有 $i$，$A(φ)⇒A((∀xi)φ),A((∃xi)φ)$，

則 $A(φ)$ 對所有 $φ∈FORM$ 成立。

詞項集的遞迴性

令 $H_0: Var \cup Const \rightarrow A$，$H_1: A^{a_i} \rightarrow A$，則存在唯一的函數 $H: TERM \rightarrow A$ 使得：

1. 對於變元或常元 $t$，$H(t) = H_0(t)$；
2. 對於函數 $f_i$，$H(f_i(t_1, ..., t_{a_i})) = H_1(H(t_1), ..., H(t_{a_i}))$。

構句集的遞迴性

令 $H_{at}: ATOM \rightarrow A$，$H_\square : A^2\rightarrow A$，$H_{\neg}: A \rightarrow A$，$H_{\forall}: A \rightarrow A$，$H_{\exists}: A \rightarrow A$，則存在唯一的函數 $H: FORM \rightarrow A$ 使得：

1. 對於所有的原子式 $t$，$H(t) = H_{at}(t)$；
2. $H(t_1 \square t_2) = H_\square(H(t_1), H(t_2))$；
3. $H(\neg \phi) = H_{\neg}(H(\phi))$；
4. $H(\forall x_i \phi) = H_{\forall}(H(\phi))$；
5. $H(\exists x_i \phi) = H_{\exists}(H(\phi))$。

定義 2.2.4 自由變元

$TERM$:

1. $FV(\bar{c_i}) = \emptyset$；
2. $FV(x_i) = \{ x_i \}$；
3. $FV(f_i(t_1, ..., t_{a_i})) = FV(t_1) \cup ... \cup FV(t_{a_i})$。

$FORM$:

1. $FV(\bot) = \emptyset$；
2. 若 $P$ 是命題符號，則 $FV(P) = \emptyset$；
3. $FV(t_1 = t_2) = FV(t_1) \cup FV(t_2)$；
4. $FV(P_i(t_1, ..., t_{r_i})) = FV(t_1) \cup ... \cup FV(t_{r_i})$；
5. $FV(\phi \square \psi) = FV(\phi) \cup FV(\psi)$；
6. $FV(\neg \phi) = FV(\phi)$；
7. $FV(\forall x_i \phi) = FV(\phi) \setminus \{ x_i \}$；
8. $FV(\exists x_i \phi) = FV(\phi) \setminus \{ x_i \}$。

定義 2.2.5 封閉詞項和封閉構句

1. 若 $FV(t) = \emptyset$，則 $t$ 稱為封閉詞項。封閉詞項集合寫作 $TERM_c$。
2. 若 $FV(\phi) = \emptyset$，則 $\phi$ 稱為封閉構句或語句。語句集合寫作 $SENT$。
3. 無量詞的構句稱為開放構句。

定義 2.2.6 拘束變元

$TERM$:

1. $BV(\bar{c_i}) = \emptyset$；
2. $BV(x_i) = \emptyset$；
3. $BV(f_i(t_1, ..., t_{a_i})) = BV(t_1) \cup ... \cup BV(t_{a_i})$。

$FORM$:

1. $BV(\bot) = \emptyset$；
2. 若 $P$ 是命題符號，則 $BV(P) = \emptyset$；
3. $BV(t_1 = t_2) = BV(t_1) \cup BV(t_2)$；
4. $BV(P_i(t_1, ..., t_{r_i})) = BV(t_1) \cup ... \cup BV(t_{r_i})$；
5. $BV(\phi \square \psi) = BV(\phi) \cup BV(\psi)$；
6. $BV(\neg \phi) = BV(\phi)$；
7. $BV(\forall x_i \phi) = BV(\phi) \cup \{ x_i \}$；
8. $BV(\exists x_i \phi) = BV(\phi) \cup \{ x_i \}$。

定義 2.2.7 替代

$TERM$：

令 $s$ 和 $t$ 是兩個詞項，則 $s[t/x]$ 定義如下：

1. $c[t/x] = c$；
2. 若 $y$ 不是 $x$，則 $y[t/x] = y$；
3. 若 $y$ 即是 $x$，則 $y[t/x] = t$；
4. $(f(t_1, ..., t_{a_i}))[t/x] = f(t_1[t/x], ..., t_{a_i}[t/x])$。

$FORM$ 的詞項替代：

令 $\phi$ 是一個構句，$t$ 是一個詞項，則 $\phi[t/x]$ 定義如下：

1. $\bot[t/x] = \bot$；
2. 若 $P$ 是命題符號，則 $P[t/x] = P$；
3. $(t_1 = t_2)[t/x] = t_1[t/x] = t_2[t/x]$；
4. $(P_i(t_1, ..., t_{r_i}))[t/x] = P_i(t_1[t/x], ..., t_{r_i}[t/x])$；
5. $(\phi \square \psi)[t/x] = \phi[t/x] \square \psi[t/x]$；
6. $(\neg \phi)[t/x] = \neg \phi[t/x]$；
7. 若 $y$ 不是 $x$，則 $(\forall y \phi)[t/x] = \forall y \phi[t/x]$；
8. 若 $y$ 即是 $x$，則 $(\forall y \phi)[t/x] = \forall y \phi$；
9. 若 $y$ 不是 $x$，則 $(\exists y \phi)[t/x] = \exists y \phi[t/x]$；
10. 若 $y$ 即是 $x$，則 $(\exists y \phi)[t/x] = \exists y \phi$。

$FORM$ 的構句替代：

令 $\phi$ 和 $\psi$ 是兩個構句，則 $\phi[\psi/ P]$ 定義如下：

1. 若 $\phi$ 即是 $P$，則 $\phi[\psi/ P] = \psi$；
2. 若 $\phi$ 不是 $P$，但 $\phi$ 是原子語句，則 $\phi[\psi/ P] = \phi$。
3. 若 $\phi = \phi_1 \square \phi_2$，則 $\phi[\psi/ P] = \phi_1[\psi/ P] \square \phi_2[\psi/ P]$；
4. 若 $\phi = \neg \phi_1$，則 $\phi[\psi/ P] = \neg \phi_1[\psi/ P]$；
5. 若 $\phi = \forall x_i \phi_1$，則 $\phi[\psi/ P] = \forall x_i \phi_1[\psi/ P]$；
6. 若 $\phi = \exists x_i \phi_1$，則 $\phi[\psi/ P] = \exists x_i \phi_1[\psi/ P]$。

定義 2.2.8 自由詞項

在 $\phi$ 中，$t$ 對 $x$ 是自由的，代表下述性質之一被滿足：

1. $\phi$ 是原子的，
2. $\phi = \phi_1 \square \phi_2$，且 $t$ 對 $x$ 在 $\phi_1$ 或 $\phi_2$ 中是自由的，
3. $\phi = \neg \phi_1$，且 $t$ 對 $x$ 在 $\phi_1$ 中是自由的，
4. $\phi = \exists y \psi$，且若 $x\in FV(\phi)$，則 $y \not\in FV(t)$ 而 $t$ 對 $x$ 在 $\psi$ 中是自由的。
5. $\phi = \forall y \psi$，且若 $x\in FV(\phi)$，則 $y \not\in FV(t)$ 而 $t$ 對 $x$ 在 $\psi$ 中是自由的。

定義 4 和 5 比較抽象，但直覺卻很單純：$t$ 對 $x$ 是自由的，意味著將 $x$ 以 $t$ 替代是安全的，表示，當 $t$ 取代 $x$ 出現在 $\phi$ 中時，$y$ 不該提供新的量限，自由的必須保持自由的、拘束的必須保持拘束的。理解了這點以後，引理 2.2.9 和 2.2.11 都是非常容易理解的。

引理 2.2.9

在 $\phi$ 中，$t$ 對 $x$ 是自由的，當且僅當 $\phi[t/x]$ 的變數 $t$ 未被量詞拘束。

定義 2.2.10 自由構句

在 $\sigma$ 中，$\phi$ 對 $P$ 是自由的，代表下述性質之一被滿足：

1. $\sigma$ 是原子的，
2. $\sigma = \sigma_1 \square \sigma_2$，且 $\phi$ 對 $P$ 在 $\sigma_1$ 或 $\sigma_2$ 中是自由的，
3. $\sigma = \neg \sigma_1$，且 $\phi$ 對 $P$ 在 $\sigma_1$ 中是自由的，
4. $\sigma = \exists y \psi$，且若 $P$ 在 $\sigma$ 中出現，則 $y \not\in FV(\phi)$ 而 $\phi$ 對 $P$ 在 $\psi$ 中是自由的。
5. $\sigma = \forall y \psi$，且若 $P$ 在 $\sigma$ 中出現，則 $y \not\in FV(\phi)$ 而 $\phi$ 對 $P$ 在 $\psi$ 中是自由的。

引理 2.2.11

在 $\sigma$ 中，$\phi$ 對 $P$ 是自由的，當且僅當 $\phi$ 的自由變元並未在 $\sigma[\phi/P]$ 中被量詞拘束。

定義 2.2.12 擴充語言

$\mathfrak{A}$ 的擴充語言 $L(\mathfrak{A})$ 由語言 $L$、$\mathfrak{A}$ 的類型加上 $|\mathfrak{A}|$ 中的常元所構成。我們將 $|\mathfrak{A}|$ 中的 $a$ 標註為 $\bar{a}$，作為語言中的常元符號。

此處的 $|\mathfrak{A}|$ 表示為 $\mathfrak{A}$ 中的所有元素命名。

語義學

考慮 $\mathfrak{A} =\langle A, R_1, ..., R_n, F_1, ...,F_m, \{ c_i|i\in I \} \rangle$，以及給定的相似類型 $\langle r_1, ..., r_n; a_1, ..., a_m; \kappa \rangle$。

相應的擴充語言的述詞符號是 $\bar{R_1}, ..., \bar{R_n}, \bar{F_1}, ..., \bar{F_m}, \bar{c_i}$。並且，對於所有的 $a\in \mathfrak{A}$，我們有 $\bar{a}$ 的常元符號。

定義 2.3.13 封閉詞項與構句的詮釋

$TERM_c$：

$L(\mathfrak{A})$ 在 $\mathfrak{A}$ 的封閉詞項的詮釋是一個函數 $(.)^{\mathfrak{A}}: TERM_c \rightarrow |\mathfrak{A}|$ 滿足（使用 Scott brackets 標記）：

1. $\llbracket \bar{c_i} \rrbracket_{\mathfrak{A}} = c_i$；
2. $\llbracket \bar{a} \rrbracket_{\mathfrak{A}} = a$；
3. $\llbracket F_i(t_1, ..., t_{a_i}) \rrbracket_{\mathfrak{A}} = \bar{F_i}(\llbracket t_1 \rrbracket_{\mathfrak{A}}, ..., \llbracket t_{a_i} \rrbracket_{\mathfrak{A}})$。

$SENT$：

$L(\mathfrak{A})$ 在 $\mathfrak{A}$ 的語句的詮釋是一個函數 $(.)^{\mathfrak{A}}: SENT \rightarrow \{ 0, 1 \}$ 滿足：

1. $\llbracket \bot \rrbracket_{\mathfrak{A}} = 0$；
2. $\llbracket \bar{R} \rrbracket_{\mathfrak{A}} = R$（$0$ 或 $1$）；
3. $\llbracket \bar{R}_i(t_1, ..., t_{r_i}) \rrbracket_{\mathfrak{A}} = 1$ 當且僅當 $\llbracket t_1 \rrbracket_{\mathfrak{A}}, ..., \llbracket t_{r_i} \rrbracket_{\mathfrak{A}} \in R_i$；
4. $\llbracket t_1 = t_2 \rrbracket_{\mathfrak{A}} = 1$ 當且僅當 $\llbracket t_1 \rrbracket_{\mathfrak{A}} = \llbracket t_2 \rrbracket_{\mathfrak{A}}$；
5. $\llbracket \phi \land \psi \rrbracket_{\mathfrak{A}} = \min(\llbracket \phi \rrbracket_{\mathfrak{A}}, \llbracket \psi \rrbracket_{\mathfrak{A}})$；
6. $\llbracket \phi \lor \psi \rrbracket_{\mathfrak{A}} = \max(\llbracket \phi \rrbracket_{\mathfrak{A}}, \llbracket \psi \rrbracket_{\mathfrak{A}})$；
7. $\llbracket \phi \rightarrow \psi \rrbracket_{\mathfrak{A}} = \max(1, 1 - \llbracket \phi \rrbracket_{\mathfrak{A}} + \llbracket \psi \rrbracket_{\mathfrak{A}})$；
8. $\llbracket \phi \leftrightarrow \psi \rrbracket_{\mathfrak{A}} = 1 - |\llbracket \phi \rrbracket_{\mathfrak{A}} - \llbracket \psi \rrbracket_{\mathfrak{A}}|$；
9. $\llbracket \neg \phi \rrbracket_{\mathfrak{A}} = 1 - \llbracket \phi \rrbracket_{\mathfrak{A}}$；
10. $\llbracket \forall x_i \phi \rrbracket_{\mathfrak{A}} = \min_{a \in |\mathfrak{A}|} \llbracket \phi[a/x_i] \rrbracket_{\mathfrak{A}}$；
11. $\llbracket \exists x_i \phi \rrbracket_{\mathfrak{A}} = \max_{a \in |\mathfrak{A}|} \llbracket \phi[a/x_i] \rrbracket_{\mathfrak{A}}$。

定義 2.3.14 $\models$

$\mathfrak{A}\models \phi$ 當且僅當 $\llbracket \phi \rrbracket_{\mathfrak{A}} = 1$。

定義 2.3.15 宇封閉句 universal closure

令 $FV(\phi)={z_1, ..., z_n}$，則 $Cl(\phi):= \forall z_1...z_k \phi$ 是 $\phi$ 的宇封閉句。

透過宇封閉句，我們可以將詮釋從封閉構句擴展到所有構句，由於對於所有的封閉構句 $\psi$，$Cl(\psi) = \psi$，因此這個定義是合法的：

定義 2.3.16

$\mathfrak{A}\models \phi$ 當且僅當 $\mathfrak{A}\models Cl(\phi)$。

定義 2.3.17

1. $\models \phi$ 當且僅當 $\mathfrak{A}\models \phi$ 對所有的 $\mathfrak{A}$ 成立。
2. $\mathfrak{A}\models \Sigma$ 當且僅當 $\mathfrak{A}\models \phi$ 對所有的 $\phi \in \Sigma$ 成立。
3. $\Gamma \models \phi$ 當且僅當若 $\mathfrak{A}\models \Gamma$，則 $\mathfrak{A}\models \phi$。

引理 2.3.18 構句的邏輯意涵

對於語句 $\phi$ 和 $\psi$，下列等價性成立：

1. $\mathfrak{A}\models \phi \land \psi$ 當且僅當 $\mathfrak{A}\models \phi$ 且 $\mathfrak{A}\models \psi$；
2. $\mathfrak{A}\models \phi \lor \psi$ 當且僅當 $\mathfrak{A}\models \phi$ 或 $\mathfrak{A}\models \psi$；
3. $\mathfrak{A}\models \neg \phi$ 當且僅當 $\mathfrak{A}\not\models \phi$；
4. $\mathfrak{A}\models \phi \rightarrow \psi$ 當且僅當 $\mathfrak{A}\models \phi$ 蘊含 $\mathfrak{A}\models \psi$；
5. $\mathfrak{A}\models \phi \leftrightarrow \psi$ 當且僅當 $\mathfrak{A}\models \phi$ 等價於 $\mathfrak{A}\models \psi$；
6. $\mathfrak{A}\models \forall x_i \phi$ 當且僅當 $\mathfrak{A}\models \phi[\bar{a}/x_i]$ 對所有的 $a \in |\mathfrak{A}|$；
7. $\mathfrak{A}\models \exists x_i \phi$ 當且僅當 $\mathfrak{A}\models \phi[\bar{a}/x_i]$ 對某個 $a \in |\mathfrak{A}|$。

述詞邏輯的簡單性質

定理 2.4.19 量詞拘束構句的等價性

1. $\models \neg \forall x \neg \phi \leftrightarrow \exists x \phi$；
2. $\models \neg \exists x \neg \phi \leftrightarrow \forall x \phi$。

定理 2.4.20 量詞的結構規則

1. $\models \forall x \forall y \phi \leftrightarrow \forall y \forall x \phi$；
2. $\models \exists x \exists y \phi \leftrightarrow \exists y \exists x \phi$；
3. $\models \forall x \phi \leftrightarrow \phi$，當 $x \not\in FV(\phi)$；
4. $\models \exists x \phi \leftrightarrow \phi$，當 $x \not\in FV(\phi)$。

定理 2.4.21 量詞的分配規則

1. $\models \forall x (\phi \land \psi) \leftrightarrow (\forall x \phi \land \forall x \psi)$；
2. $\models \exists x (\phi \lor \psi) \leftrightarrow (\exists x \phi \lor \exists x \psi)$；
3. $\models \forall x (\phi \lor \psi) \leftrightarrow (\forall x \phi \lor \psi)$，當 $x \not\in FV(\psi)$；
4. $\models \exists x (\phi \land \psi) \leftrightarrow (\exists x \phi \land \psi)$，當 $x \not\in FV(\psi)$。

引理 2.4.22 替代的交換律

1. $x\not\in FV(r)$ 和 $y$ 是相異變數，則 $(t[s/x])[r/y]=(t[r/y])[s[r/y]/x]$；
2. $x\not\in FV(s)$ 和 $y$ 是相異變數，且 $t$ 和 $s$ 對於 $x$ 和 $y$ 在 $\phi$ 是自由的，則 $(\phi[t/x])[s/y]=(\phi[s/y])[t[s/y]/x]$；
3. $\psi$ 對於 $P$ 在 $\phi$ 是自由的，並且 $t$ 對於 $x$ 在 $\phi$ 和 $\psi$ 中是自由的，則 $(\phi[\psi/P])[t/x]=(\phi[t/x])[\psi[t/x]/P]$；
4. $\phi$ 和 $\psi$ 對於 $P_1$、$P_2$ 在 $\sigma$ 是自由的，$\psi$ 對於 $P_2$ 在 $\phi$ 中是自由的，並且 $P_1$ 在 $\psi$ 中沒有出現，則 $(\sigma[\phi/P_1])[\psi/P_2]=(\sigma[\psi/P_2])[\phi[\psi/P_2]/P_1]$。

推論 2.4.23

1. $z\not\in FV(t)$，則 $t[\bar{a}/x] = (t[z/x])[\bar{a}/z]$；
2. $z\not\in FV(\phi)$ 且 $z$ 對於 $x$ 在 $\phi$ 中是自由的，則 $\phi[\bar{a}/x] = (\phi[z/x])[\bar{a}/z]$。

定理 2.4.24 拘束變數的變換

若 $x$ 和 $y$ 對於 $z$ 在 $\phi$ 中是自由的，且 $x, y \not\in FV(\phi)$，則 $\models\exists x \phi [x/z] \leftrightarrow \exists y \phi [y/z]$ 且 $\models\forall x \phi [x/z] \leftrightarrow \forall y \phi [y/z]$。

推論 2.4.25

所有構句都等價一個沒有變元同時是自由又拘束的構句。

定理 2.4.26 替代定理

1. $\models t_1 = t_2 \rightarrow s[t_1/x] = s[t_2/x]$；
2. $\models t_1 = t_2 \rightarrow (\phi[t_1/x] \leftrightarrow \phi[t_2/x])$；
3. $\models(\phi \leftrightarrow \psi) \rightarrow (\sigma[\phi/P] \leftrightarrow \sigma[\psi/P])$。

推論 2.4.27

1. $\llbracket s[t/x] \rrbracket = \llbracket s [\bar{ \llbracket t \rrbracket } / x] \rrbracket$；
2. $\llbracket \phi[t/x] \rrbracket = \llbracket \phi [\bar{ \llbracket t \rrbracket } / x] \rrbracket$。

定義 2.4.28 前束標準句 prenex normal form

一個構句 $\phi$ 是前束標準式，當且僅當 $\phi = Q_1 x_1 ... Q_n x_n \psi$，其中 $Q_i$ 是量詞，$\{ Q_i \}$ 可以是 $\emptyset$，$\psi$ 是開放構句，且 $x_1, ..., x_n$ 是互異的變數。

定理 2.4.29 前束標準句的存在

對於每一個構句 $\phi$，存在一個等價的前束標準句。

定義 2.4.30 一元述詞與量詞作用域 unary predicate and scope of quantifier

若 $P$ 是一個一元述詞符號，則 $(\forall x \in P)\phi =_\text{df} \forall x (P(x) \rightarrow \phi)$，$(\exists x \in P)\phi =_\text{df} \exists x (P(x) \land \phi)$。

定義 2.4.31 子構句

$Sub^+$ 和 $Sub^-$ 定義如下：

1. $Sub^+(\phi) = \{ \phi \}$，
2. $Sub^-(\phi) = \emptyset$，對於 $\phi$ 是原子句。
3. $Sub^+(\phi_1 \square \phi_2) = Sub^+(\phi_1) \cup Sub^+(\phi_2) \cup \{ \phi_1 \square \phi_2 \}$，
4. $Sub^-(\phi_1 \square \phi_2) = Sub^-(\phi_1) \cup Sub^-(\phi_2)$，對於 $\square \in \{ \land, \lor \}$。
5. $Sub^+(\phi_1 \rightarrow \phi_2) = Sub^+(\phi_1) \cup Sub^-(\phi_2) \cup \{ \phi_1 \rightarrow \phi_2 \}$，
6. $Sub^-(\phi_1 \rightarrow \phi_2) = Sub^+(\phi_1) \cup Sub^-(\phi_2)$。
7. $Sub^+(Qx.\phi) = Sub^+(\phi) \cup \{ Qx.\phi \}$，
8. $Sub^-(Qx.\phi) = Sub^-(\phi)$，對於 $Q \in \{ \forall, \exists \}$。

若 $\phi \in Sub^+(\psi)$，我們說 $\phi$ 在 $\psi$ 中正面出現（occurs positively），若 $\psi \in Sub^+(\phi)$，我們說 $\phi$ 在 $\psi$ 中負面出現（occurs negatively）。

Van Dalen 在這裡的定義缺了 $\neg \phi$，我覺得這是滿奇怪的。按照正面出現和負面出現的意義，應該如此定義：

1. $Sub^+(¬\phi) = Sub^-(\phi) \cup {¬\phi}$，
2. $Sub^-(¬\phi) = Sub^+(\phi)$。

定理 2.4.32 出現與語義值

令 $\phi$ 在 $\psi$ 中未負面出現、在 $\sigma$ 中未正面出現，則：

1. $\llbracket \phi_1 \rrbracket \leq \llbracket \phi_2 \rrbracket \Rightarrow \llbracket \sigma[\phi_1 / \phi ] \rrbracket \leq \llbracket \sigma[\phi_2 / \phi ] \rrbracket$，
2. $\llbracket \psi_1 \rrbracket \leq \llbracket \psi_2 \rrbracket \Rightarrow \llbracket \sigma[\psi_1 / \psi ] \rrbracket \geq \llbracket \sigma[\psi_2 / \psi ] \rrbracket$，
3. $\mathfrak{A}\models (\phi_1 \rightarrow \phi_2) \rightarrow (\sigma[\phi_1 / \phi] \rightarrow \sigma[\phi_2 / \phi])$，
4. $\mathfrak{A}\models (\psi_1 \rightarrow \psi_2) \rightarrow (\sigma[\psi_2 / \phi] \rightarrow \sigma[\psi_1 / \phi])$。

同一性

定義 2.5.1 同一性公理

$=$ 是同一性的符號，它並非一般的二元述詞，因為它需要滿足以下公理與公理格式：

• (I$_1$) $\forall x (x=x)$（反身性），
• (T$_2$) $\forall x y (x=y \rightarrow y=x)$（對稱性），
• (T$_3$) $\forall x y z (x=y \land y=z \rightarrow x=z)$（傳遞性），
• (T$_4$-1) $\forall x_1 ... x_n y_1 ... y_n (\bigwedge_{i \leq n} x_i=y_i \rightarrow t(x_1, ..., x_n)=t(y_1, ..., y_n))$，
• (T$_4$-2) $\forall x_1 ... x_n y_1 ... y_n (\bigwedge_{i \leq n} x_i=y_i \rightarrow (\phi(x_1, ..., x_n) \rightarrow \phi(y_1, ..., y_n)))$（全等性 congruence）。

定義 2.5.2 同一性的推導規則

• (RI$_1$) $x = x \in X$。
• (RI$_2$) 若 $D / x = y \in X$，則 $D / x = y \over y = x$ $\in X$。
• (RI$_3$) 若 $D / x = y, y = z \in X$，則 $D / x = y, y = z \over x = z$ $\in X$。
• (RI$_4$-1) 若 $D / x_1 = y_1, ..., x_n = y_n \in X$，則 $D / x_1 = y_1, ..., x_n = y_n \over t(x_1, ..., x_n) = t(y_1, ..., y_n)$ $\in X$。
• (RI$_4$-2) 若 $D / x_1 = y_1, ..., x_n = y_n \in X$，則 $D / x_1 = y_1, ..., x_n = y_n, \phi(x_1, ..., x_n) \over \phi(y_1, ..., y_n)$ $\in X$，其中 $y_1, ..., y_n$ 對於 $x_1, ..., x_n$ 在 $\phi$ 中是自由的。

引理 2.5.3 公理的可推導性

$\vdash$ I$_1$, I$_2$, I$_3$, I$_4$。

引理 2.5.4 RI$_4$ 的可推導性

令 $L$ 的型是 $\langle r_1, ..., r_n; a_1, ..., a_m; \kappa \rangle$。若給定以下規則：

1. 若 $D / x_1 = y_1, ..., x_{r_i} = y_{r_i}, P_i(x_1, ..., x_{r_i}) \in X$，則 $D / x_1 = y_1, ..., x_{r_i} = y_{r_i}, P_1(x_1, ..., x_{r_i}) \over P_i(y_1, ..., y_{r_i})$ $\in X$，對於所有 $i \leq n$，
2. 若 $D / x_1 = y_1, ..., x_{a_j} = y_{a_j} \in X$，則 $D / x_1 = y_1, ..., x_{a_j} = y_{a_j} \over f_j(x_1, ..., x_{a_j}) = f_j(y_1, ..., y_{a_j})$ $\in X$，對於所有 $j \leq m$。

那麼 RI$_4$ 是可推導的。

自然演繹法

定義 2.6.1 擴充的演繹集合

從 1.4.1 的自然演繹法開始擴充，加入兩個推導規則：

• (2-$\forall I$) 若 $D / \phi(x) \in X$，且 $x$ 在 $\phi(x)$ 所依賴的假設中不自由出現，則 $D / \phi(x) \over \forall x \phi(x)$ $\in X$。
• (2-$\forall E$) 若 $D / \forall x \phi(x) \in X$，則 $D /\forall x \phi(x) \over \phi(t)$ $\in X$，其中 $t$ 對於 $x$ 在 $\phi$ 中是自由的。

定義 2.6.2 形式二

• (2-$\forall I$)’ $\Gamma \vdash \phi(x) \Rightarrow \Gamma \vdash \forall \phi(x)$，如果對於所有 $\psi \in \Gamma$，$x \not\in FV(\psi)$。
• (2-$\forall E$)’ $\Gamma \vdash \forall \phi(x) \Rightarrow \Gamma \vdash \phi(t)$，如果 $t$ 對於 $x$ 在 $\phi$ 中是自由的。