跳轉到

5.1 形式語言與語義#

本章導言#

Frege 發明量詞邏輯（1.3 節）後，半個世紀內它被精煉為一階邏輯（first-order logic）：變元只取「對象」為值（不取集合、謂詞），量詞只約束對象變元。1930 年前後，Tarski 的真值定義使「語義」成為數學對象，Gödel 的完備性定理（5.2 節）證明一階邏輯的語法與語義完全吻合。本節建立整個現代邏輯的基礎詞彙：語言、結構、賦值、真、可證，以及「語法—語義」的對偶——這一對偶是模型論、可計算性、證明論共同的操作台。

一階語言的語法#

一階語言 \(\mathcal{L}\) 由符號表決定：關係符號（如 \(\in, <\) ）、函數符號（如 \(+, \times\) ）、常元（如 \(0\) ）、邏輯符號（ \(\neg, \wedge, \vee, \to, \forall, \exists, =\) ）、變元 \(x, y, \dots\) 。項與公式由歸納定義生成；變元有自由／約束之分。例： \(\forall x (x + 0 = x)\) 是封閉公式（語句）， \(\forall x (x + y = y + x)\) 中 \(y\) 自由。

為何限制為一階？因為二階量詞（「對每個子集 \(P\) 」）使邏輯失去關鍵性質：完備性（5.2 節）、Löwenheim–Skolem、緊緻性（5.3 節）。二階算術能唯一刻畫 \(\mathbb{N}\) （範疇性）但沒有完備的證明系統。表達力與可操作性不可兩全——一階邏輯是這個 trade-off 的最佳點，這是二十世紀邏輯最重要的設計決策。

語義：結構與滿足#

\(\mathcal{L}\) -結構（模型） \(\mathfrak{A} = (A, \dots)\) ：非空域 \(A\) + 各符號的解釋。滿足關係 \(\mathfrak{A} \models \phi[a]\) （在賦值 \(a\) 下 \(\phi\) 為真）由 Tarski 遞迴定義：

\[ \mathfrak{A} \models \phi \wedge \psi \iff \mathfrak{A} \models \phi \text{ 且 } \mathfrak{A} \models \psi; $$ $$ \mathfrak{A} \models \exists x\, \phi(x) \iff \text{存在 } d \in A,\ \mathfrak{A} \models \phi[d]. \]

Tarski 1933 的貢獻是遞迴地定義「真」，證明它在後設語言中可定義，且（他同時證明的不可定義性定理）在對象語言中不可定義（3.1 節場景三）。語義於是成為嚴格的數學對象——模型論誕生。

語法：證明系統#

證明系統給出公理（邏輯公理模式）與推理規則（modus ponens、全稱概括）。記 \(\Gamma \vdash \phi\) （從 \(\Gamma\) 可推 \(\phi\) ）。關鍵性質：

  • 可靠性（soundness）： \(\Gamma \vdash \phi \Rightarrow \Gamma \models \phi\) 。語法不會撒謊。
  • 完備性（completeness）： \(\Gamma \models \phi \Rightarrow \Gamma \vdash \phi\) 。語法不會遺漏。（5.2 節。）

兩者合取：** \(\vdash\) 與 \(\models\) 等價**。這一對偶是整個邏輯學的槓桿：研究證明（語法）與研究模型（語義）可以互換。

一個具體例子#

例題 5.1.1：考慮一階語言 \(\mathcal{L} = \{+, \times, 0, 1\}\) 。寫出「 \(p(x)\) 是素數」的一階表達式；並解釋為何「 \(P\) 是素數集」不能用一階公式定義為整體謂詞，而「對每個 \(x\) ，若 \(x > 1\) 則存在 \(y, z\) 使 \(x = yz\) 或 \(p(x)\) 」可以。

解：素性的一階定義（以 \(\mathcal{L}_{PA}\) 表達）：

\[ \operatorname{Prime}(x) \equiv x > 1 \wedge \forall y\, \forall z\, (x = y \cdot z \to y = 1 \vee z = 1), \]

其中 \(y = 1\) 、 \(x > 1\) 皆有標準一階展開（ \(x > 1 \equiv \exists w\, (w \ne 0 \wedge x = w + 1)\) ）。

「 \(x\) 的所有素因子」這類有限概念可以一階表達；但「素數集」作為二階對象（自然數集的子集）不在一階語言的論域中——一階變元只能取自然數為值。然而算術編碼（Gödel 編碼，6.2 節）改變了遊戲：可以用自然數編碼集合（如素數集的特徵函數的碼），使「碼 \(e\) 編碼的集合含 \(x\) 」成為一階可表達的。一階語言的表達力限制，部分被編碼技巧繞開——這正是 Gödel 不完備性證明的第一步。

例題 5.1.2：證明緊緻性的特例用法：若對每個 \(n\) 存在圖使「含 \(n\) 個頂點的圈」不存在，則存在無窮圖使任何有限圈不存在。（提示：取語句集 \(\{\neg C_3, \neg C_4, \dots\} \cup \{\text{「至少 } n \text{ 個頂點」} : n \in \mathbb{N}\}\) ，用緊緻性。）——此例預告 5.3 節。

解：設 \(T\) 為上述語句集。 \(T\) 的每個有限子集 \(T_0\) 有模型：取一個足夠大的、無 \(T_0\) 所禁圈長的有限圖（如足夠大的完全二部圖，無奇圈；或大圈上取頂點）。由緊緻性， \(T\) 有模型 \(\mathfrak{G}\) ，其域無窮（「至少 \(n\) 個頂點」對所有 \(n\) ），且無任何有限圈。「有限可滿足則可滿足」直接從有限構造生產無窮對象——緊緻性的典型生產方式。 \(\blacksquare\)

語法—語義對偶的技術意義#

概念 語法面 語義面
一致性 無 \(\Gamma \vdash \bot\) 有模型 \(\mathfrak{A} \models \Gamma\)
完備性 每語句 \(\phi\) ： \(\vdash \phi\) 或 \(\vdash \neg\phi\) 唯一模型（至同構）
可定義性 公式 \(\phi(x)\) \(\phi\) 在 \(\mathfrak{A}\) 中的外延
對角線 語法編碼（6.2 節） 語義不動點

注意：完備性（本節）指「語法完備於語義」（Gödel 1930），完備性（6.1 節）指「理論能判定一切語句」——兩者不同！前者對一階邏輯成立，後者對含算術的理論不成立。這對「同名字不同義」的概念是學習邏輯的第一陷阱。

歷史啟示#

  • 一階邏輯是被「選中」的邏輯：它的地位不是先驗的，而是因為它擁有完備性、緊緻性等元性質——工具的選擇由工具的後設性質決定。
  • Tarski 真值定義使語義成為數學：之前「模型」「真」是哲學詞，之後是可研究對象。後設層的數學化是 Hilbert 綱領（3.3 節）方法論的邏輯版。
  • 表達力的 trade-off 決定學科版圖：一階（完備、緊緻）成為模型論基礎；二階（強表達、不完備）成為描述集合論與高階邏輯的領域。

與其他章節及領域的關聯#

  • 1.3 節：Frege 概念文字是語法層的祖先。
  • 3.3 節：形式系統的「語法—語義」兩層是 Hilbert 綱領架構的邏輯學實現。
  • 5.2 節：完備性定理使本節的對偶成為定理。
  • 5.3 節：緊緻性與非標準模型——對偶的生產性應用。
  • 6.1–6.2 節：不完備性是語法層對語義層的「背叛」：有真語句不可證。
  • 7.1 節：可計算性把「語法操作」變成機器——證明檢查是機械的。
  • 9.3、10.2 節：類型論以「證明即構造」重組語法—語義對偶。
  • 計算機科學：SQL 與關聯代數是一階查詢語言；SMT 求解器（Z3）自動判定一階片段；軟體驗證的 Hoare 邏輯是一階（擴充）邏輯的直接應用。

練習#

  1. 將「每個非零實數有逆」寫成一階公式（語言 \(\{+, \times, 0, 1\}\) ），並寫出其否定。
  2. 證明： \(\mathfrak{A} \models \exists x\, (\phi(x) \vee \psi(x)) \iff \mathfrak{A} \models \exists x\, \phi(x) \vee \exists x\, \psi(x)\) 。
  3. 說明為何「對每個子集 \(S \subseteq \mathbb{N}\) ，……」不能在一階算術中直接表達，但可以用編碼表達什麼樣的替代命題。
  4. 檢驗例題 5.1.2 的論證：寫出「無長 \(k\) 圈」的一階表達式，並確認語句集的每個有限子集有有限圖模型。
  5. 思考題：一階邏輯犧牲範疇性（Peano 公理一階版有多個非同構模型，見 5.3 節）換取完備性。若你重視「唯一刻畫 \(\mathbb{N}\) 」，你會付什麼代價？

進階研讀：三個深化場景#

場景一：Tarski 的不可定義性定理。1933： \((\mathbb{N}, \dots)\) 中的「真」不可在算術自身內定義（否則可造 liar 語句）。語義必須住在更高的層——這是羅素悖論（3.1 節）的語義版餘波，也是 6.1 節 Gödel 編碼「用語法代替語義」的直接動機。

場景二：Lindström 定理（1969）。一階邏輯是唯一同時滿足緊緻性與 Löwenheim–Skolem 向下性質的「正則」邏輯。一階邏輯不只是被選中，而是被刻畫——元性質的組合唯一確定它。這是邏輯學中最美的刻畫定理之一。

場景三：描述複雜性（Immerman–Vardi）。計算機科學的 P = 多項式時間等價於某種固定點邏輯（在有窮結構上）——邏輯的表達力刻畫計算的複雜度。一階邏輯對應 AC⁰、傳遞閉包邏輯對應 NL。語法—語義對偶在計算複雜性中成為分類工具。

名詞速查表#

  • 一階語言：量詞只約束對象變元的形式語言。
  • 結構（模型）：域 + 符號解釋。
  • **滿足 \(\models\) **：Tarski 遞迴定義的真關係。
  • 可靠性 / 完備性： \(\vdash \subseteq\, \models\) / \(\models \subseteq\, \vdash\) 。
  • 範疇性：所有模型互相同構（一階理論只在無窮域上無範疇性）。
  • Lindström 定理：一階邏輯的元性質唯一性刻畫。

年表速查#

  • 1879：Frege 概念文字。
  • 1910–13：Principia 的形式系統。
  • 1928：Hilbert–Ackermann 提出完備性問題。
  • 1930：Gödel 完備性定理。
  • 1933：Tarski 真值定義與不可定義性。
  • 1936：Turing 機（7.1 節），證明檢查的機械化。
  • 1969：Lindström 刻畫定理。
  • 1974：Fagin 定理（NP = 存在二階邏輯），描述複雜性開端。

深化問答三則#

問：為什麼「一階」不是「最自然的」邏輯？ 答：人類直覺的數學語言是二階以上的（「所有子集」「所有函數」）。一階是工程妥協：為了完備性、可判定片段、緊緻性。它的成功證明了一個原則：形式系統的價值在後設性質，不在表達力的最大化——這與程式語言設計（表達力 vs 可分析性）完全同構。

問：Tarski 定義「真」是循環的嗎？ 答：不是，因為它跨層：對象語言 \(\mathcal{L}\) 的「真」由後設語言 \(\mathcal{M}\) （更豐富，含 \(\mathcal{L}\) 的語法）定義。循環只在「同一層」發生（不可定義性定理禁止之）。分層是邏輯學對自我指涉問題的一般解法——從 Russell 類型論（3.1 節）到 Tarski 到 Grothendieck 宇宙（10.1 節），同一招式不斷重現。

問：完備性定理與「數學可被機械證明」是什麼關係？ 答：完備性說一階邏輯真理可被系統地證明（存在證明當且僅當語義有效），且證明可機械檢查。但它不說可機械找到證明（半可判定：會停機當有證明，但不會停機當無證明，見 7.3 節）。「存在系統」與「存在有效搜索」之間的差，就是可計算性理論的舞台。

（本節完）