數理邏輯 (2) 一階邏輯

上一篇: 命題邏輯

一階邏輯

命題邏輯雖結構簡單易於研究, 但應用範圍較窄, 例如含有量詞的古典三段論推理就沒法在其中得到表達. 一階邏輯在命題邏輯的基礎上引入謂詞和量詞, 讓我們可以對 “所有”, “存在” 這樣的詞語進行形式化分析.

在一階邏輯中, 變元僅僅指代個體, 量詞的控制範圍也僅限於個體, 這一點與討論 “(個體組成的)集合” 和 “(個體間的)關係” 的二階邏輯不同. 儘管二階邏輯的語言更豐富, 一階邏輯仍然在邏輯學中佔有主導地位. Lindström 定理表明: 一階邏輯是同時具有緊緻性和向下 Löwenheim-Skolem 性質的表達能力最強的邏輯系統.

語法

公式集

一階邏輯的形式語言 (謂詞演算) 包括如下符號:

• 個體變元: $x_1,x_2,\cdots$, 用於表示取值可變的個體對象;
• 個體常元: $c_1,c_2,\cdots$, 用於表示確定的個體對象;
• 運算符: $f^1_1,f^1_2,\cdots,f^2_1,\cdots$, 用 $f^n_i$ 表示一個 $n$ 元運算;
• 謂詞: $R^1_1,R^1_2,\cdots,R^2_1,\cdots$, 用 $R^n_i$ 表示個體對象集上的一個 $n$ 元關係;
• 命題聯結詞 $\neg,\to$;
• 全稱量詞 $\forall$;
• 左右括號, 逗號.

其中個體常元集和運算集都可為空集, 但謂詞集不能為空, 否則無法形成語句.

個體常元和個體變元分別對應於語言哲學中的專名 (proper name) 和變項 (variable), 前者有完全確定的指稱, 後者沒有指稱, 但在特定的域上可取不同的值. 一般地, 項 (terms) 對應於自然語言中所有指示個體的名詞性成分, 在形式語言中, 項包括個體常元, 個體變元以及在兩者上進行有限次運算所得的結果.

把項集記作 $T$, 則

• 個體變元 $x_i\in T$,
• 個體常元 $c_i\in T$,
• 若 $t_1,\cdots,t_n\in T$, 則 $f_i^n(t_1,\cdots,t_n)\in T$,
• 除此之外 $T$ 中沒有其他元素.

特別地, $T$ 中只含個體常元的項稱為閉項.

進而定義原子公式集:

$$Y=\bigcup_{i,n}\left(\lbrace R^n_i\rbrace\times T^n\right)$$

即

$$Y=\lbrace(R^n_i,t_1,\cdots,t_n):R^n_i\in R,t_1,\cdots,t_n\in T\rbrace$$

其中 $(R^n_i,t_1,\cdots,t_n)$ 一般寫作 $R^n_i(t_1,\cdots,t_n)$.

在謂詞演算中, 原子公式是用來表示命題的最小單位. 原子公式之於謂詞演算, 就如命題變元之於命題演算.

從原子公式出發, 謂詞演算公式的形成規則如下:

• 每個原子公式是公式,
• 若 $\varphi$, $\psi$ 是公式, 則 $\neg\varphi$, $\varphi\to\psi$, $\forall x\varphi$ 也是公式,
• 任一公式由前兩條規則使用有限次得到.

用 $K(Y)$ 表示所有謂詞演算公式構成的集. $T$ 是可數集, 故 $Y$ 是可數集, 從而 $K(Y)$ 也是可數集.

命題聯結詞 $\vee$, $\wedge$, $\leftrightarrow$ 的定義與命題演算相同:

$$\begin{align*} \varphi\vee\psi &:= \neg\varphi\to\psi \\ \varphi\wedge\psi &:= \neg(\varphi\to\neg\psi) \\ \varphi\leftrightarrow\psi &:= (\varphi\to q)\wedge(\psi\to\varphi) \end{align*}$$

存在量詞 $\exists$ 定義為全稱量詞 $\forall$ 的對偶:

$$\exists x\varphi:=\neg\forall x \neg\varphi$$

自由/約束出現

設公式 $\varphi\in K(Y)$, 若 $\varphi$ 的一部分形如 $\forall x\psi$, 則稱 $\forall x\psi$ 是 $\forall x$ (這一出現) 的轄域 (scope). 個體變元 $x$ 的一次出現若不在量詞轄域中, 則稱它自由出現, 否則叫做約束出現. 至少一次自由出現的變元稱為自由變元, 否則稱約束變元. 一個公式若不含自由變元, 就叫做閉式 (或語句).

用項 $t$ 去替換公式 $\varphi$ 中的自由出現的變元 $x$, 若在替換後的公式裡 $t$ 的變元都是自由的, 則稱 “$t$ 對 $\varphi$ 中 $x$ 是自由的”. 換言之, 如果用 $t$ 替換 $\varphi$ 中的自由變元 $x$, 結果 $t$ 中某一變元 $y$ 落入原公式 $\forall y$ 的轄域內, 那麼原本不受約束的部分就會受到約束, 這種情況下 $t$ 對 $\varphi$ 中 $x$ 就是不自由 (不可替換) 的.

顯然在如下兩種情況下, $t$ 對 $\varphi$ 中 $x$ 是自由的:

• $t$ 是閉項;
• $x$ 不在 $\varphi$ 中自由出現.

用 $\varphi^x_t$ 表示用項 $t$ 代換 $\varphi$ 中所有自由出現的 $x$.

謂詞演算

謂詞演算 $K$ 的定義方式與命題演算 $L$ 類似, 即在公式集 $K(Y)$ 上規定 “公理” 和 “證明”.

“公理” 定義為 $K(Y)$ 的具有如下形狀的公式:

• $\text{(K1)}$ $\varphi\to(\psi\to \varphi)$,
• $\text{(K2)}$ $(\varphi\to (\psi\to\gamma))\to((\varphi\to\psi)\to(\varphi\to\gamma))$,
• $\text{(K3)}$ $(\neg\varphi\to\neg\psi)\to(\psi\to\varphi)$,
• $\text{(K4)}$ $\forall x\varphi\to\varphi^x_t$, 其中 $t$ 對 $\varphi$ 中 $x$ 是自由的,
• $\text{(K5)}$ $\forall x(\varphi\to\psi)\to(\forall x\varphi\to\forall x\psi)$.
• $\text{(K6)}$ $\varphi\to\forall x\varphi$, 其中 $x$ 不在 $\varphi$ 中自由出現.

等詞 "$\approx$" 是一個特殊的二元謂詞, 用於表示 "相等" 的概念. 關於等詞有如下三條公理:

• $\text{(E1)}$ $t\approx t$,
• $\text{(E2)}$ $t_k\approx u\to f(t_1,\cdots,t_k,\cdots,t_n)\approx f(t_1,\cdots,u,\cdots,t_n)$,
• $\text{(E3)}$ $t_k\approx u\to (R(t_1,\cdots,t_k,\cdots,t_n)\to R(t_1,\cdots,u,\cdots,t_n))$.

易見 "$\approx$" 具有自反性, 對稱性和傳遞性, 表明等詞不一定解釋為字面意義的 "相等", 但它表示的一定是一個等價關係.

“證明” 的定義與命題演算相同.

如果我們把 $K(Y)$ 的公式視為命題演算中用命題變元表示的簡單命題, 那麼謂詞演算 $K$ 可以很自然地看成是命題演算的擴張.

命題演算中的內定理可以照搬到謂詞演算, 只需用公式 $\varphi_1,\cdots,\varphi_n\in K(Y)$ 代換原公式中的命題變元 $x_1,\cdots,x_n$ 即可. 即

$$\vdash_{L}\enspace p(x_1,\cdots,x_n)\enspace\Longrightarrow\enspace\vdash_{K}\enspace p(\varphi_1,\cdots,\varphi_n)$$

若 $p(x_1,x_2,\cdots,x_n)$ 是命題演算中的重言式, 則代換後的 $p(\varphi_1,\cdots,\varphi_n)$ 稱為一階意義的重言式. 這類重言式一定是 $K$ 的定理, 反之則不然.

---

謂詞演算的幾個常用的元定理:

• 概括定理: 若 $\Gamma\vdash\varphi$ 且 $x$ 不在 $\Gamma$ 的任何公式中自由出現, 則 $\Gamma\vdash\forall x\varphi$.
• 演繹定理: $\Gamma,\varphi\vdash\psi$ $\Longleftrightarrow$ $\Gamma\vdash\varphi\to\psi$.
• 反證律: 若 $\Gamma,\neg\varphi\vdash\psi$ 且 $\Gamma,\neg\varphi\vdash\neg\psi$, 則 $\Gamma\vdash\varphi$.
• 歸謬律: 若 $\Gamma,\varphi\vdash\psi$ 且 $\Gamma,\varphi\vdash\neg\psi$, 則 $\Gamma\vdash\neg\varphi$.

概括定理有如下推論:

• 推論1: 設 $\Gamma,\varphi\vdash\psi$, $x$ 不在 $\Gamma$ 和 $\psi$ 中自由出現, 則有 $\Gamma,\exists x\varphi\vdash\psi$.
• 推論2: 設 $\Gamma,\varphi\vdash\psi$, $x$ 不在 $\Gamma$ 中自由出現, 則 $\Gamma,\forall x\varphi\vdash\forall x\psi$. 特別地, 如果 $\vdash\varphi\to\psi$, 則 $\vdash\forall x\varphi\to\forall x\psi$.
• 推論3: 設 $\Gamma,\varphi\vdash\psi$, $x$ 不在 $\Gamma$ 中自由出現, 則 $\Gamma,\exists x\varphi\vdash\exists x\psi$. 特別地, 如果 $\vdash\varphi\to\psi$, 則 $\vdash\exists x\varphi\to\exists x\psi$.

---

常元概括定理: 設 $\Gamma\vdash\varphi$, $c$ 是不在 $\Gamma$ 中出現的常元, 則存在不在 $\varphi$ 中出現的變元 $y$ 使得 $\Gamma\vdash\varphi^c_y$.

定理 (約束變元替換): 令 $\varphi$ 為一公式, $t$ 為一個項, $x$ 為一個變元, 總可以找到一個公式 $\varphi'$, 它和 $\varphi$ 的差別僅在於約束變元, 使得:

• $\varphi\vdash\varphi'$ 且 $\varphi'\vdash\varphi$, (稱 $\varphi$ 和 $\varphi'$ 可證等價)
• $t$ 對 $\varphi'$ 中的 $x$ 是自由 (可替換) 的.

用項 $t$ 替換 $\varphi$ 中的自由變元 $x$, 如果 $t$ 中某一變元 $y$ 落入原公式 $\forall y$ 的轄域內, 那麼任取不在 $t$ 和 $\varphi$ 中出現的變元 $z$, 預先把 $\varphi$ 中的約束變元 $y$ 替換為 $z$ 即可.

這種對約束變元的替換叫做易字, 稱 $\forall y\varphi^x_y$ 為 $\forall x\varphi$ 的易字式.

前束範式指形如 $Q_1 x_1\cdots Q_n x_n\thinspace\varphi$ 的公式, 其中 $Q_i$ 為 $\forall$ 或 $\exists$, $\varphi$ 是不含量詞的公式. 每一個公式都有與之等價的前束範式, 求出該前束範式的方法是反覆使用如下可證等價規則: (用 $Q^{\ast}$ 表示 $Q$ 的對偶)

• $\vdash\neg Qx\varphi\leftrightarrow Q^{\ast}x\neg\varphi$,
• $\vdash(\varphi\to Qx\psi)\leftrightarrow Qx(\varphi\to\psi)$, 假定 $x$ 不在 $\varphi$ 中自由出現,
• $\vdash(Qx\varphi\to\psi)\leftrightarrow Q^{\ast}x(\varphi\to\psi)$, 假定 $x$ 不在 $\psi$ 中自由出現,
• $\vdash Qx\varphi\leftrightarrow Qy\varphi^x_y$, 假定 $y$ 不在 $\varphi$ 中出現.

設 $n>0$, 若前束範式是由全稱量詞開始, 從左至右改變 $n-1$ 次詞性, 則叫做 $\Pi_n$ 型前束範式; 若由存在量詞開始, 從左至右改變 $n-1$ 次詞性, 則叫做 $\Sigma_n$ 型前束範式.

語義

模型與解釋

要討論謂詞演算的語義, 我們必須解釋系統中每一個符號的意義, 即挑選一個外部的數學 “結構” 來符合這種語言的陳述, 使其中的謂詞, 函數和項有所指稱. 這點與命題邏輯有很大差別, 因為命題邏輯中的簡單命題只帶有抽象的真值, 一般不會具體地用來描述某個數學結構.

謂詞演算的一個模型是一個有序對 $\mathfrak{A}=\langle A,I\rangle$, 其中 $A$ 是一個非空集 (稱為 $\mathfrak{A}$ 的論域), $I$ 是一個解釋函數, 滿足:

1. 對 $K$ 的每個個體常元 $c$, $I(c)$ (記作 $c^{\mathfrak{A}}$) 是 $A$ 的元素,
2. 對 $K$ 的每個 $n$ 元運算符 $f$, $I(f)$ (記作 $f^{\mathfrak{A}}$) 是 $A$ 上的 $n$ 元運算.
3. 對 $K$ 的每個 $n$ 元謂詞 $R$, $I(R)$ (記作 $R^{\mathfrak{A}}$) 是 $A$ 上的 $n$ 元關係.

論域是帶有特定內部結構的集合, 其結構與謂詞演算的語法結構具有一定對應性, 但集合內部的性質不一定都能被一階語言 “捕捉”.

---

要討論 $K$ 中公式的真假, 除了給定模型, 還需確定個體變元的取值.

設 $\mathfrak{A}$ 為 $K$ 的一個模型, 定義 $\mathfrak{A}$ 上的一個變元賦值為個體變元到論域 $A$ 的映射 $s:X\to A$. 隨後遞歸地把 $s$ 擴張到項集 $T$ 上, 得到項解釋 $\overline{s}:T\to A$ 滿足:

• $\overline{s}(x)=s(x)$,
• $\overline{s}(c)=c^{\mathfrak{A}}$,
• $\overline{s}(f(t_1,\cdots,t_n))=f^{\mathfrak{A}}\left(\overline{s}(t_1),\cdots,\overline{s}(t_n)\right)$. (保運算性)

設 $s$ 為模型 $\mathfrak{A}$ 上的一個變元賦值, 給定 $a\in A$, 若變元賦值 $s'$ 滿足:

1. $s'(x)=a$,
2. $y\not=x$ $\Longrightarrow$ $s'(y)=s(y)$,

則稱 $s'$ 為 $s$ 的 $x$-變通, 記作 $s^x_a$. 項變通的概念將用於對含量詞公式的解釋.

公式的賦值函數

設 $\mathfrak{A}$ 是給定的模型, $\varphi$ 是 $K$ 中任一公式, 歸納定義真值 $|\varphi|$ 如下:

對任一變元賦值 $s$,

1. 當 $\varphi$ 為原子公式 $R(t_1,\cdots,t_n)$ 時, 令
$$|\varphi|(s)=\begin{cases} 1,&\text{if}\enspace\left(\overline{s}(t_1),\cdots,\overline{s}(t_n)\right)\in R^\mathfrak{A},\\ 0,&\text{if}\enspace\left(\overline{s}(t_1),\cdots,\overline{s}(t_n)\right)\notin R^\mathfrak{A}; \end{cases}$$
2. 當 $\varphi=\neg\psi$ 或 $\varphi=\psi\to\gamma$ 時, 分別令 (真值函數 $\neg$ 和 $\to$ 的定義見命題邏輯)
$$\begin{align*} |\neg\psi|(s)&=\neg|\psi|(s), \\ |\psi\to\gamma|(s)&=|\psi|(s)\to|\gamma|(s); \end{align*}$$
3. 當 $\varphi=\forall x\psi$ 時, 若 $s$ 的任一 $x$-變通 $s'$ 都使 $|\varphi|(s')=1$, 則 $|\forall x\psi|(s)=1$; 如若不然, 則 $|\forall x\psi|(s)=0$.

若 $|\varphi|(s)=1$, 我們寫 $(\mathfrak{A},s)\vDash\varphi$, 表示該公式在特定模型的特定賦值下為真, 讀作 $\mathfrak{A}$ 和 $s$ 滿足 $\varphi$.

這裡定義的語義是一階真值理論的核心, 一般稱為基本語義定義 (basic semantic definition, BSD), 最早由 Tarski 提出, 故又稱為 Tarski 真理定義. (有意思的是, Tarski 還證明了 “真之不可定義性”, 這兩個成果中 “定義” 一詞的含義是不同的. )

語義後承和有效式

合同引理: 設 $\varphi$ 為任意公式, $s$ 和 $s'$ 分別為模型 $\mathfrak{A}=\langle A,I\rangle$ 和 $\mathfrak{A}'=\langle A,I'\rangle$ 上的兩個賦值, 使得 $\varphi$ 中出現的常元符號, 函數符號和關係符號對應相等, 且 $\varphi$ 中所有自由出現的變元取值均相同, 則 $(\mathfrak{A},s)\vDash\varphi$ $\Longleftrightarrow$ $(\mathfrak{A}',s')\vDash\varphi$.

設 $\Gamma$ 為一公式集, $\varphi$ 為一公式, 若任何一對滿足 $\Gamma$ 的 $(\mathfrak{A},s)$ 都滿足 $\varphi$, 則稱 $\varphi$ 為 $\Gamma$ 的語義後承, 記作 $\Gamma\vDash\varphi$. 特別地, 如果 $\emptyset\vDash\varphi$, 就稱 $\varphi$ 是有效式, 記作 $\vDash\varphi$; 若 $\neg\varphi$ 不是有效式, 則稱 $\varphi$ 是可滿足公式.

$K$ 中的 (一階) 重言式都是有效式. 特別地, $\text{(K1)}$, $\text{(K2)}$, $\text{(K3)}$ 三種模式的公理都是有效式.

如果 $\varphi\vDash\psi$ 且 $\psi\vDash\varphi$, 則稱 $\varphi$ 和 $\psi$ 語義等價. 顯然有 $\varphi\vDash\psi$ $\Longleftrightarrow$ $\vDash\varphi\to\psi$, 故 $\varphi$ 和 $\psi$ 語義等價當且僅當 $\vDash\varphi\leftrightarrow\psi$.

閉式中沒有自由出現的變元, 由合同引理知, 模型 $\mathfrak{A}$ 一旦確定, 閉式的真值就與特定賦值無關. 故任一閉式 $\varphi$ 在 $\mathfrak{A}$ 中恆真或恆假二者必居其一.

設 $\Gamma$ 為一公式集, 若存在一模型 $\mathfrak{A}$, 對於 $\mathfrak{A}$ 上的任意賦值 $s$ 和任意公式 $\varphi\in\Gamma$ 都有 $(\mathfrak{A},s)\vDash\varphi$, 則稱 $\mathfrak{A}$ 滿足 $\Gamma$, 或 $\mathfrak{A}$ 是 $\Gamma$ 的一個模型, 記作 $\mathfrak{A}\vDash\Gamma$. 特別地, 當 $\Gamma=\lbrace\varphi\rbrace$ 時, 我們簡寫為 $\mathfrak{A}\vDash\varphi$, 並稱 $\mathfrak{A}$ 是 $\varphi$ 的模型. 若 $\varphi$ 是閉式, 則 $\mathfrak{A}\vDash\varphi$ 或 $\mathfrak{A}\nvDash\varphi$ 二者必居其一.

容易看出, $\mathfrak{A}\vDash\varphi$ $\Longleftrightarrow$ $\mathfrak{A}\vDash\forall x\varphi$. 設 $x_1,\cdots,x_n$ 是 $\varphi$ 中所有自由出現的變元, 我們稱 $\forall x_1\cdots\forall x_n\thinspace\varphi$ 為 $\varphi$ 的全稱閉式. 設 $\varphi$ 的全稱閉式為 $\varphi'$, 則 $\mathfrak{A}\vDash\varphi$ $\Longleftrightarrow$ $\mathfrak{A}\vDash\varphi'$.

關於語義後承有如下兩條命題:

• 若 $\Gamma\vDash\varphi$ 且變元 $x$ 不在 $\Gamma$ 中自由出現, 則 $\Gamma\vDash\forall x\varphi$. 特別地, 若 $\vDash\varphi$, 則 $\vDash\forall x\varphi$.
• 若 $\Gamma,\varphi\vDash\psi$ 且 $x$ 不在 $\Gamma$ 和 $\varphi$ 中自由出現, 則 $\Gamma,\exists x\varphi\vDash\psi$.

易見這兩條命題與語法推演中的概括定理的相似性.

理論與模型

稱形式語言中對語義後承封閉的閉公式集為一個理論. 如果一個理論 $\Sigma$ 是可滿足的, 就必存在模型 $\mathfrak{A}$ 使得 $\mathfrak{A}\vDash\Sigma$. 把滿足 $\Sigma$ 的模型稱為 $\Sigma$ 的模型.

給定一個語言, 對於一個理論 $\Sigma$, 用 $\text{Mod }\Sigma$ 來表示由 $\Sigma$ 的模型組成的類, 稱結構類 $\mathcal{K}$ 為一個初等類 ($\text{EC}$), 如果存在閉式 $\tau$ 使得 $\mathcal{K}=\text{Mod }\tau$. 稱 $\mathcal{K}$ 為一個廣義初等類 ($\text{EC}_{\Delta}$), 如果存在閉公式集 $\Sigma$ 使得 $\mathcal{K}=\text{Mod }\Sigma$.

取語言 $\mathcal{L}=\lbrace\approx,P\rbrace$, 令 $\tau$ 為如下3個閉式的合取: $$\begin{align*} \forall x\forall y\forall z &(xPy\to yPz\to xPz) \\ \forall x\forall y &(xPy\vee x\approx y\vee yPx) \\ \forall x\forall y &(xPy\to\neg yPx) \end{align*}$$ 則初等類 $\mathcal{K}=\text{Mod }\tau$ 為所有嚴格線序集構成的類.

同構模型

給定一個語言 $L$, 設 $\mathfrak{A}=\langle A,I\rangle$ 和 $\mathfrak{B}=\langle B,J\rangle$ 是兩個模型. 從 $A$ 到 $B$ 的函數 $f$ 是 $\mathfrak{A}$ 到 $\mathfrak{B}$ 的同構映射當且僅當 $f$ 是雙射, 且滿足:

• 對 $L$ 的任意 $n$ 元謂詞 $R$ 及任意 $a_1,\cdots,a_n\in A$,

$$R^{\mathfrak{A}}(a_1,\cdots,a_n)\Longleftrightarrow R^{\mathfrak{B}}\left(f(a_1),\cdots,f(a_n)\right)$$

• 對 $L$ 的任意 $n$ 元函數符 $g$ 及任意 $a_1,\cdots,a_n\in A$,

$$f(g^{\mathfrak{A}}(a_1,\cdots,a_n)) = g^{\mathfrak{B}}\left(f(a_1),\cdots,f(a_n)\right)$$

• 對 $L$ 的個體常元 $c$, $f(c^{\mathfrak{A}})=c^{\mathfrak{B}}$.

$\mathfrak{A}$ 和 $\mathfrak{B}$ 同構記作 $\mathfrak{A}\cong\mathfrak{B}$, 顯然 $\cong$ 是個等價關係.

稱 $L$ 上的兩個模型 $\mathfrak{A}$ 和 $\mathfrak{B}$ 是初等等價的, 記作 $\mathfrak{A}\equiv\mathfrak{B}$, 如果 $\mathfrak{A}\vDash\varphi$ $\Longleftrightarrow$ $\mathfrak{B}\vDash\varphi$. 若 $\mathfrak{A}$ 和 $\mathfrak{B}$ 同構, 則顯然 $\mathfrak{A}$ 和 $\mathfrak{B}$ 是初等等價的, 反之不然. 進而若 $\mathfrak{A}$ 和 $\mathfrak{B}$ 同構, 則對每個理論 $\Sigma$ 有 $\mathfrak{A}\vDash\Sigma$ $\Longleftrightarrow$ $\mathfrak{B}\vDash\Sigma$.

---

一般地, 任何理論只要有模型, 就必然有與之同構的另一模型, 同構的兩個模型在我們的語言下無法區別 (或者說, 同構的兩個結構就是同一結構). 所以在討論不同模型時, 我們一般只關心同構意義下的 “不同”.

能否在一個理論中添加足夠多的公式, 使其模型在同構意義下是唯一的? 這個問題取決於使用我們的語言能在多大程度上對一個結構做出精細刻畫, 在本質上即是語言表達力的問題.

固定一個語言和其上的一個模型 $\mathfrak{A}$, 我們把 $\lbrace\varphi:\mathfrak{A}\vDash\varphi\rbrace$ 記作 $\text{Th }\mathfrak{A}$, 稱為 $\mathfrak{A}$ 的完全理論. 上面的問題於是轉化為: $\text{Th }\mathfrak{A}$ 是否有與 $\mathfrak{A}$ 不同構的模型?

令 $\mathfrak{N}=\langle\mathbb{N},I\rangle$ 為標準算術模型, 設二元謂詞 $R$ 在 $\mathfrak{N}$ 中解釋為 $<$. 下文將用緊緻性定理證明一階理論 $\text{Th }\mathfrak{N}$ 存在不同構於 $\mathfrak{N}$ 的非標準模型 $\mathfrak{A}$. 用 $\prec$ 表示 $R^{\mathfrak{A}}$, 則 $\mathfrak{A}$ 與標準模型的不同之處在於 $\mathfrak{A}$ 的 $\prec$-無窮升鏈之後有無窮大元素, 其形象為: $a_0\prec a_1\prec a_2\prec\cdots\prec b$. 一階語言中不存在公式集可排除這種情況, 因為假如存在這樣的公式集 $\Gamma$, 就有 $\mathfrak{N}\vDash\Gamma$, 故 $\Gamma\subseteq\text{Th }\mathfrak{N}$, 從而對非標準模型 $\mathfrak{A}$ 也有 $\mathfrak{A}\vDash\Gamma$, 矛盾. 這表明, $\mathfrak{N}$ 與 $\mathfrak{A}$ 的差別是一階語言不能表達的.

可定義性

固定一個語言 $L$ 和 $L$ 上的一個模型 $\mathfrak{A}$, 假定 $x_1,\cdots,x_n$ 是公式 $\varphi\in L$ 中所有自由出現的變元, $a_1,\cdots,a_n\in\mathfrak{A}$, 我們用 $\mathfrak{A}\vDash\varphi\left[a_1,\cdots,a_n\right]$ 表示: 存在項解釋 $s$ 使得 $s(x_i)=a_i$ 且 $(\mathfrak{A},s)\vDash\varphi$.

進而, 我們稱 $n$ 元關係

$$\left\{(a_1,\cdots,a_n):\mathfrak{A}\vDash\varphi\left[a_1,\cdots,a_n\right]\right\}$$

是公式 $\varphi$ 在 $\mathfrak{A}$ 中定義的關係. 若 $\mathfrak{A}$ 中的 $n$ 元關係 $R$ 可被某公式 $\varphi$ 定義, 則稱 $R$ 是可定義的. 可定義的一元關係稱為可定義集. 易見, 同構映射保持可定義性.

模型 $\mathfrak{A}$ 上的一個自同構就是 $\mathfrak{A}$ 到 $\mathfrak{A}$ 自身的一個同構. 設 $f:\mathfrak{A}\to \mathfrak{A}$ 是一個自同構, $R$ 是 $\mathfrak{A}$ 上的一個可定義的 $n$ 元關係, 則對任意 $a_1,\cdots,a_n\in A$ 都有

$$(a_1,\cdots,a_n)\in R\Longleftrightarrow(f(a_1),\cdots,f(a_n))\in R$$

這個結果經常被用來證明某些關係的不可定義性.

例如, 考慮由全體實數和其上的自然序組成的結構 $\langle\mathbb{R},<\rangle$. 設 $f:\mathbb{R}\to\mathbb{R}$ 為 $f(x)=\sqrt[3]{x}$, 則 $f$ 是該結構的一個自同構. 據此可證明自然數集 $\mathbb{N}$ 在該結構上是不可定義的: 假設公式 $\varphi$ 在該結構上定義了一元關係 $N$, 那麼對自然數 $n>1$, 若 $n\in N$ 則必有 $f(n)=\sqrt[3]{n}\in N$, 因此 $N\not=\mathbb{N}$.

再比如, 加法函數的圖像 $\lbrace(m,n,p):p=m+n\rbrace$ 在結構 $\langle\mathbb{N},\cdot\rangle$ 中不可定義. 我們只需令 $f:\mathbb{N}\to\mathbb{N}$: $$f(x)=\begin{cases} 2^b \cdot 3^a ,&\text{if}\enspace x=2^a \cdot 3^b\\ x,&\text{if}\enspace 2\nmid x,\thinspace 3\nmid x \end{cases}$$ 由唯一分解定理知 $f$ 是一個雙射, 故 $f$ 定義了 $\mathbb{N}$ 上的一個自同構. 如果有一個公式 $\varphi$ 定義了關係 $R=\left\{(m,n,p):p=m+n\right\}$, 則由 $(1,2,3)\in R$ 可以推出 $(f(1),f(2),f(3))=(1,3,2)\in R$, 矛盾.

可靠性和完備性

可靠性

可靠性定理: $\Gamma\vdash\varphi\Longrightarrow\Gamma\vDash\varphi$.

證明類似命題邏輯, 驗證 $\text{(K1)}$ ~ $\text{(K5)}$ 型公理的有效性, 然後歸納法.

推論: $K$ 是一致的, 即對任意公式 $\varphi$, $\vdash\varphi$ 和 $\vdash\neg\varphi$ 不同時成立.

證明: 如若不然, 則由可靠性定理就會有 $\vDash\varphi$ 和 $\vDash\neg\varphi$ 同時成立, 而這是不可能的. $\square$

類似地可以證明: 若公式集 $\Gamma$ 可滿足, 則 $\Gamma$ 必是一致的.

完全性

完全性定理: $\Gamma\vDash\varphi\Longrightarrow\Gamma\vdash\varphi$, 即 $K$ 的有效式一定是 $K$ 的定理.

完全性定理有如下等價形式:

• 每個一致的公式集都是可滿足的.

下面先證明這個等價形式, 然後再從中推出完全性定理. (這裡只考慮可數語言)

---

先給出三個定義:

• 公式集 $\Gamma$ 稱為極大一致的, 當且僅當 $\Gamma$ 是一致的, 且對任意公式 $\varphi$, $\varphi\in\Gamma$ 或 $\neg\varphi\in\Gamma$. 顯然, 極大一致集對演繹封閉, 即 $\Gamma\vdash\varphi$ $\Longleftrightarrow$ $\varphi\in\Gamma$.
• 設 $\neg\forall x\varphi\in\Gamma$, $\neg\forall x\varphi$ 在 $\Gamma$ 中有見證當且僅當存在項 $t$ 使得 $\neg\varphi^x_t\in\Gamma$. $\Gamma$ 是見證健全集當且僅當每個 $\neg\forall x\varphi\in\Gamma$ 在 $\Gamma$ 中都有見證.
• 公式集 $\Gamma$ 稱為 Henkin 集, 當且僅當 $\Gamma$ 是見證健全的極大一致集. 若 $\Gamma$ 是 Henkin 集, 則對任何全稱公式 $\forall x\varphi$, $\forall x\varphi\in\Gamma$ $\Longleftrightarrow$ 對每個項 $t$ 都有 $\varphi^x_t\in\Gamma$.

首先作擴大的謂詞演算 $K^{+}$: 向 $K$ 中添加可數個新常元 $d_0,d_1,d_2,\cdots$, 其他不變, 則 $K^{+}\supsetneq K$, 且 $K^{+}$ 仍是可數語言. $K^{+}$ 的項集記作 $T^{+}$.

設 $\Gamma$ 為一致的 $K$ 公式集, 並令 $\forall x_0\varphi_0,\forall x_1\varphi_1,\cdots$ 為所有形如 $\forall x\varphi$ 的 $K^{+}$ 公式. 由於 $\Gamma\subset K$, 所以新常元 $d_0,d_1,\cdots$ 都不在 $\Gamma$ 中出現. 定義一個新常元的序列 $c_0,c_1,\cdots$, 其中 $c_k$ 為按照 $d_0,d_1,\cdots$ 排在最前面的滿足如下條件的常元:

• $c_k$ 不在 $\forall x_0\varphi_0,\cdots,\forall x_k\varphi_k$ 中出現,
• $c_k\notin\lbrace c_0,\cdots,c_{k-1}\rbrace$.

記公式 $\gamma_k=\varphi^{x_k}_{c_k}\to\forall x_k\varphi_k$, 令 $K^{+}$ 公式集 $\Gamma'=\Gamma\cup\lbrace\gamma_0,\gamma_1,\cdots\rbrace$. 若 $\Gamma'$ 不一致, 則存在最小的 $m$ 使得 $\Gamma_m=\Gamma\cup\lbrace\gamma_0,\cdots,\gamma_m\rbrace$ 是不一致的, 所以 $\Gamma_{m-1}$ 與 $\gamma_m$ 不一致, 即 $\Gamma_{m-1}$ 與 $\neg\varphi^{x_k}_{c_k}$ 一致但與 $\neg\forall x_k\varphi_k$ 一致, 與常元概括定理矛盾. 故 $\Gamma'$ 是一致公式集.

把 $K^{+}$ 的公式排成不重複的一列: $\varphi_0,\varphi_1,\cdots$, 按如下方式遞歸定義公式集序列:

• $\Gamma_0=\Gamma'$,
• $\Gamma_{k+1}=\Gamma_k\cup\lbrace\varphi_k\rbrace$, 若 $\Gamma_k$ 與 $\varphi_k$ 一致,
• $\Gamma_{k+1}=\Gamma_k\cup\lbrace\neg\varphi_k\rbrace$, 若 $\Gamma_k$ 與 $\varphi_k$ 不一致.

令 $\Gamma^{+}=\bigcup_{k\ge0}\Gamma_k$, 顯然 $\Gamma^{+}$ 是 $K^{+}$ 的極大一致集.

由 $\Gamma'$ 的定義知, 對 $K^{+}$ 的所有全稱公式 $\forall x\varphi$, 必有相應的公式 $\varphi^x_c\to\forall x\varphi\in\Gamma^{+}$ (稱為 Henkin 公式, 本質上是通過引入常元來消去量詞), 從而如果 $\neg\forall x\varphi\in\Gamma^{+}$ 就有 $\neg\varphi^x_c\in\Gamma^{+}$. 即 $\neg\forall x\varphi$ 在 $\Gamma^{+}$ 有見證. 所以 $\Gamma^{+}$ 是 Henkin 集.

---

對於不含等詞的謂詞演算, 我們的準備工作已經完成, 可以直接在 $K^{+}$ 的項集 $T^{+}$ 上定義模型 $\mathfrak{A}$:

• $c^{\mathfrak{A}}=c$, $f^{\mathfrak{A}}=f$,
• $(t_1,\cdots,t_n)\in R^{\mathfrak{A}}$ $\Longleftrightarrow$ $R(t_1,\cdots,t_n)\in\Gamma^{+}$.

然而, 如果系統中含有等詞, 那就必須考慮如下情況: 設 $\varphi=\neg(x\approx d)$, 我們在添加公式時加入了 $\neg(c\approx d)\to\forall x\neg(x\approx d)$ 且 $c$ 和 $d$ 是兩個不同的常元, 那麼 $\neg\forall x\varphi$ 的見證將是 $c\approx d\in\Gamma^{+}$, 但在模型中卻沒有 $c=d$. 一般而言我們要求等詞解釋為字面意義的 “相等”, 這樣就出現了問題, 解決方法一般是考慮等價類.

對任意 Henkin 集 $\Gamma^{+}$, 定義 $K^{+}$ 項集上的等價關係 $\simeq_{\Gamma}$: $t\simeq_{\Gamma}t$ $\Longleftrightarrow$ $s\approx t\in\Gamma^{+}$. 考慮商集 $A_{\Gamma}={T^{+}}/{\simeq_{\Gamma}}=\left\lbrace [t]:t\in T^{+}\right\rbrace$, 定義模型 $\mathfrak{A}_{\Gamma}=\langle A_{\Gamma},I_{\Gamma}\rangle$ 如下:

• 對每個個體常元 $c$, $c^{\mathfrak{A}_{\Gamma}}=[c]$,
• $f^{\mathfrak{A}_{\Gamma}}\left([t_1],\cdots,[t_n]\right)=[f(t_1,\cdots,t_n)]$,
• $\left([t_1],\cdots,[t_n]\right)\in R^{\mathfrak{A}_{\Gamma}}$ $\Longleftrightarrow$ $R(t_1,\cdots,t_n)\in\Gamma^{+}$.

定義 $\mathfrak{A}_{\Gamma}$ 上的賦值函數 $s_{\Gamma}(x)=[x]$, 則對任意項 $t$, $\overline{s_{\Gamma}}(t)=[t]$.

容易驗證, $\varphi\in\Gamma^{+}$ $\Longleftrightarrow$ $(\mathfrak{A}_{\Gamma},s_{\Gamma})\vDash\varphi$, 從而 $(\mathfrak{A}_{\Gamma},s_{\Gamma})\vDash\Gamma^{+}$.

此處處理全稱公式時用到了見證健全集的性質: $\forall x\varphi\in\Gamma$ $\Longleftrightarrow$ 對每個項 $t$ 都有 $\varphi^x_t\in\Gamma$.

把 $(\mathfrak{A}_{\Gamma},s_{\Gamma})$ 限制在擴張前的語言 $K$ 上, 就得到所需的模型, 由此可知, 每個一致公式集都可滿足. $\square$

---

由這個等價形式, 我們立即能證明 $K$ 的完全性: $\Gamma\vDash p\Longrightarrow\Gamma\vdash p$.

證明: 反設 $\Gamma\nvdash\varphi$, 則 $\Gamma\cup\lbrace\neg\varphi\rbrace$ 是一致的, 所以公式集 $\Gamma\cup\lbrace\neg\varphi\rbrace$ 可滿足, 從而 $\Gamma\nvDash\varphi$, 與假設矛盾. $\square$

$K$ 的可靠性和完全性統稱為 $K$ 的 Gödel 完備性定理: $\Gamma\vDash\varphi\Longleftrightarrow\Gamma\vdash\varphi$. 該定理指出了 $K$ 的語義和語法的一致性.

緊緻性定理

類似命題演算, 在謂詞演算中也有如下緊緻性定理:

1. 若 $\Gamma$ 的所有有窮子集 $\Delta$ 都可滿足, 則 $\Gamma$ 可滿足.
2. 若 $\Gamma\vDash\varphi$, 則存在 $\Gamma$ 的某個有窮子集 $\Delta$ 使得 $\Delta\vDash\varphi$.

證明:

1. 設 $\Gamma$ 的所有有窮子集都可滿足, 則 $\Gamma$ 的所有有窮子集都是一致的, 從而 $\Gamma$ 也是一致的, $\Gamma$ 可滿足.
2. 反設對 $\Gamma$ 的任何有窮子集 $\Delta$ 都有 $\Delta\nvDash\varphi$, 即 $\Delta\cup\lbrace\neg\varphi\rbrace$ 都可滿足, 則由(1)知 $\Gamma\cup\lbrace\neg\varphi\rbrace$ 可滿足, 從而 $\Gamma\nvDash\varphi$. $\square$

下面是緊緻性定理的一些應用.

---

命題: 設 $\Sigma$ 是任何理論, 如果 $\Sigma$ 有任意大有窮模型, 那麼 $\Sigma$ 有無窮模型.

證明: 在 $\Sigma$ 的語言 $L$ 中添加新常元 $c_0,c_1,\cdots$ 得到語言 $L'$. 令 $\Theta=\Sigma\cup\Pi$, 其中 $\Pi=\lbrace c_i\not\approx c_j:i\not=j\rbrace$. 由於 $\Sigma$ 有任意大有窮模型, 所以對任意 $n>0$, $\Sigma\cup\Delta_n$ 都是可滿足的, 其中 $\Delta_n=\lbrace c_i\not\approx c_j:i,j\le n,i\not=j\rbrace$, 故由緊緻性定理, $\Theta$ 可滿足. 從而 $\Theta$ 有 $L'$-模型 $\mathfrak{A}$, 由於 $\mathfrak{A}\vDash\Pi$, 顯然 $\mathfrak{A}$ 是無窮模型. 把 $\mathfrak{A}$ 限制在 $L$ 中可得 $\Sigma$ 的無窮模型. $\square$

推論: 固定一個帶等詞的一階語言 $L$, $L$ 上所有有窮結構構成的類不是廣義初等類 (無窮結構不能被閉公式集排除); $L$ 上所有無窮結構構成的類不是初等類 (單個閉式不能排除有窮結構, 但可以用一個無窮閉公式集做到).

---

令 $\mathfrak{N}=\langle\mathbb{N},I\rangle$ 為自然數標準模型, $I$ 將語言 $L$ 中的非邏輯符號解釋為自然數集上的性質和關係 (其中包括小於關係) 等.

命題: $\text{Th }\mathfrak{N}$ 有與 $\mathfrak{N}$ 不同構的模型.

證明: 在 $L$ 中添加新常元 $d,c_0,c_1,\cdots$ 得到語言 $L'$. 令 $\Sigma=\text{Th }\mathfrak{N}\cup\Pi$, 其中 $\Pi=\lbrace Rc_i c_j:i<j\rbrace\cup\lbrace Rc_i d:0\le i\rbrace$, $R$ 在 $\mathfrak{N}$ 中解釋為 $<$. 對於 $\text{Th }\mathfrak{N}\cup\Delta_n$, 其中 $\Delta_n=\lbrace Rc_i c_j:i<j\le n\rbrace\cup\lbrace Rc_i d:0\le i\le n\rbrace$, 考慮 $\mathfrak{N}_n=\langle\mathbb{N},I_n\rangle$ 為如下模型: 對 $L$ 的每個非邏輯符號 $X$, 令 $X^{\mathfrak{N}_n}=X^{\mathfrak{N}}$, 對常元 $c_k$, 令 $c_k^{\mathfrak{N}_n}=k$, 對常元 $d$, 令 $d^{\mathfrak{N}}=n+1$, 則 $\mathfrak{N}_n$ 限制在 $L$ 上即為 $\mathfrak{N}$, 故 $\mathfrak{N}_n\vDash\text{Th }\mathfrak{N}$ 且顯然有 $\mathfrak{N}_n\vDash\Delta_n$, 所以 $\text{Th }\mathfrak{N}\cup\Delta_n$ 可滿足, 從而 $\Sigma$ 有模型 $\mathfrak{A}$. 設 $R^{\mathfrak{A}}$ 為 $\mathfrak{A}$ 上的二元關係 $\prec$, $c_k^{\mathfrak{A}}=a_k$, $d^{\mathfrak{A}}=b$, 則有 $a_0\prec a_1\prec a_2\prec\cdots\prec b$, 把 $\mathfrak{A}$ 限制在 $L$ 上即為要求的非標準模型.

下面證明 $\mathfrak{A}$ 與 $\mathfrak{N}$ 不同構. 反設存在同構映射 $f:A\to\mathbb{N}$ ($A$, $\mathbb{N}$ 分別為兩模型的論域), 並設 $f(b)=n$. 我們有 $a_0\prec a_1\prec a_2\prec\cdots$, 故 $f(a_0)<f(a_1)<\cdots$, 從而 $f(a_{k+1})>k$. 考慮 $f(a_{n+1})$, 我們有 $f(a_{n+1})>n=f(b)$, 但 $a_{n+1}\prec b$, 矛盾. 所以 $\mathfrak{A}$ 與 $\mathfrak{N}$ 不同構. $\square$

一個實際例子是, 如果我們把 Gödel 句子的否定作為公理放進形式算術系統, 這樣得到的理論 (它也是一致的) 就只有非標準模型.

---

一階 Peano 算術包含如下歸納公理:

$\varphi(0)\to\forall x(\varphi(x)\to\varphi(x'))\to\forall x\varphi(x)$, 其中 $x'$ 表示 $x$ 的後繼.

這實質上是一條公理模式, 取不同的 $\varphi$ 可產生無窮多條公理. 由於一階語言不能量化謂詞, 所以必須使用無窮多條公理來逼近數學歸納原理, 但與本義的歸納原理仍有差距, 這正是出現非標準模型的原因.

在二階語言中, Peano 算術的公理如下:

• $\forall x(x'\not\approx0)$,
• $\forall x\forall y(x'\approx y'\to x\approx y)$,
• $\forall P(P(0)\to\forall x(P(x)\to P(x'))\to\forall x P(x))$.

二階 Peano 公理的模型在同構意義下唯一.

應用

使用一階邏輯的語言, 我們很容易把日常語言或數學中的一些存在性和概括性命題翻譯成公式. 通過引入等詞 “$\approx$”, 我們還能進一步限定對象的具體數量.

採用等詞, “至少有 $n$ 個對象” 就可表示為:

$$\exists x_1\cdots\exists x_n\left(\bigwedge_{1\leq k<n}\left(\bigwedge_{k<i\leq n}x_k\not\approx x_i\right)\right)$$

“至多有 $n$ 個對象” 等價於 “任何 $n+1$ 個對象必有重合”:

$$\forall x_1\cdots\forall x_{n+1}\left(\bigvee_{1\leq k<n}\left(\bigvee_{k<i\leq n}x_k\approx x_i\right)\right)$$

“恰好有 $n$ 個對象” 則是把上述兩式結合:

$$\exists x_1\cdots\exists x_n\left[\left(\bigwedge_{1\leq k<n}\left(\bigwedge_{k<i\leq n}x_k\not\approx x_i\right)\right)\wedge\forall x_{n+1}\left(\bigvee_{1\leq k\leq n}x_k\approx x_{n+1}\right)\right]$$

設 $\varphi$ 和 $\psi$ 是一元謂詞, “至少 $n$ 個 $\varphi$ 是 $\psi$” 可表示為:

$$\exists x_1\cdots\exists x_n\left[\left(\bigwedge_{1\leq k<n}\left(\bigwedge_{k<i\leq n}x_k\not\approx x_i\right)\right)\wedge\left(\bigwedge_{1\leq k\leq n}(\varphi(x_k)\wedge\psi(x_k))\right)\right]$$

“至多 $n$ 個 $\varphi$ 是 $\psi$” 可表示為:

$$\forall x_1\cdots\forall x_{n+1}\left(\bigwedge_{1\leq k\leq n+1}(\varphi(x_k)\wedge\psi(x_k))\to\bigvee_{1\leq k<n}\left(\bigvee_{k<i\leq n+1}x_k\approx x_i\right)\right)$$

“恰好 $n$ 個 $\varphi$ 是 $\psi$” 結合兩式即可.

由此關於有限個對象的陳述就可以得到形式化.

---

下一篇: 形式算術和遞歸函數