01 / 導讀
導讀
引用
Leary, C. C., & Kristiansen, L. (2015). A Friendly Introduction to Mathematical Logic (2nd ed.). Milne Library, SUNY Geneseo. 開放教材（CC BY-NC-SA）。
章節概要
全書共八章，另有一個簡短的附錄、部分練習的解答（約75頁）和參考文獻，總計約365頁。前面幾章中大多數小節以練習結尾，每章最後有一節"Summing Up, Looking Ahead"，說明論證接下來走向何處。第2版在Leary 2000年的第1版基礎上擴充，新增了一章可計算性理論以及練習解答。
第1章：結構與語言
建立一階邏輯的詞彙。先把一階語言定義為符號的集合，然後歸納地定義項和公式，並推廣歸納法，使其能證明關於項和公式的命題。數論語言（含0、後繼、加法、乘法、冪運算和序關係）成為貫穿全書的例子。隨後定義結構、變元指派和結構中的真，處理代入以及變元在量詞之下被捕獲的問題，最後講邏輯蘊涵和有效性。
第2章：演繹
從"什麼是證明"這一問題出發，定義形式演繹。給出邏輯公理（等詞公理和量詞公理）和推理規則（命題後承與量詞規則），證明可靠性定理和該系統的一些性質，包括等號是等價關係以及演繹定理的一種形式。最後講非邏輯公理，以向量空間和算術的一個較弱公理系統N為例。
第3章：完全性與緊緻性
用亨金的方法證明完全性定理：把一致的語句集擴張為極大一致集，並由項構造模型。緊緻性隨之而來，並被用來構造算術的非標準模型，說明沒有任何一階語句集能唯一刻畫自然數。本章以子結構、初等子結構以及向下和向上的呂文海姆–斯科倫定理結束。
第4章：從兩個角度看不完全性
解釋為什麼在完全性一章之後接著講不完全性，定義完全的公理集，並確立目標：找到一個無法被證明的真語句。章中引入由有界和無界量詞衡量的公式複雜度，給出以把演繹編碼為數為基礎的路線，預告另一條經過可計算函數的路線，並展示如何把數的有限序列編碼成一個數。本章以回顧公理系統N及其強度結束。此後讀者可以繼續讀第5、6章，也可以直接跳到第7章。
第5章：句法不完全性：準備工作
基於公式的路線的技術核心。引入可表示的集合與函數，把它們與計算機程式及等價的計算模型（遞迴函數、圖靈機、λ演算）作非形式的聯繫，然後建立哥德爾編碼的機制。逐步證明項、公式、公理和演繹的編碼都可以在N中表示，最終得到一個公式，它成立當且僅當某個數是某個公式的一個演繹的編碼。
第6章：不完全性定理
證明自指引理，並用它構造一個斷言自身不可證的語句。據Peter Smith的書評，本章接著給出第一不完全性定理的語義形式和句法形式、算術的不可判定性、塔斯基定理、羅瑟的改進，以及布洛斯基於貝里悖論的不完全性證明，並在假設可導性條件的前提下證明第二不完全性定理。
第7章：可計算性理論
第2版新增的一章，約70頁。從簡短的歷史一節出發，進入μ-遞迴函數、s-m-n定理和克林範式定理，隨後證明集合K不可計算。這被用來證明判定問題（Entscheidungsproblem）不可判定、給出不完全性的第二個證明以及希爾伯特第十問題（見Smith的書評）。
第8章與書末部分
第8章"Summing Up, Looking Ahead"把各條線索收攏，並指出進一步閱讀的方向。附錄"Just Enough Set Theory to Be Dangerous"之後是部分練習的解答和參考文獻。
核心概念
第1–2章：語言、結構、演繹
- 一階語言與結構：一邊是由符號和公式構成的句法，另一邊是解釋它們的數學模型。
- 邏輯蘊涵與有效性：一個公式從另一些公式推出，是指在滿足後者的每個結構和指派下它都為真。
- 演繹：公式的有限序列，每一項或是公理，或由前面的項按規則得出，是證明的形式化。
- 可靠性：能被演繹出來的，在所有模型中都為真。
第3章：完全性與緊緻性
- 完全性定理：從一個公理集邏輯地推出的，都可以從它演繹出來。
- 緊緻性定理：一個語句集有模型，當且僅當它的每個有限子集都有模型。
- 非標準模型：與自然數初等等價、但不與之同構的結構。
- 呂文海姆–斯科倫定理：存在其他基數的初等子結構和初等擴張。
第4–6章：不完全性
- 完全的公理集：能證明或否證其語言中每個語句的公理集。
- 可表示的集合或函數：被理論中的公式所定義，並且理論能證明其正確性的集合或函數。
- 哥德爾編碼：給符號、公式和演繹分配自然數，使關於證明的陳述變成關於數的陳述。
- 自指引理：對任一公式，都存在一個語句，斷言該公式對它自身成立。
- 第一、第二不完全性定理：算術不存在可判定、一致且完全的公理化，足夠強的公理系統也不能證明自身的一致性。
第7–8章：可計算性
- 可計算（μ-遞迴）函數：由基本函數經複合、原始遞迴和極小化構造出的函數。
- 範式定理：每個可計算函數都可以用一個固定的可計算謂詞和一次無界搜尋來寫出。
- 判定問題（Entscheidungsproblem）：判定一階邏輯有效性的問題，其答案是否定的。
評析
優點
- 親切、節奏適中的敘述。 Peter Smith在Logic Matters上的書評喜歡其輕鬆而有吸引力的語氣，認為講解的水平很適合入門課程，並稱其清晰度堪稱典範。作者用來提示記號陷阱和交代動機的"Chaff"旁註（例如把數字0與數0區分開來）是各章的一大特色。
- 通向同一目標的兩條路。 作者在第4章之後把通往不完全性定理的道路分成兩條：經過第5、6章的基於公式的路線，以及經過第7章的基於計算的路線。課程可以任選其一，讀者也可以看到兩種方法。
- 練習與解答。 前六章中大多數小節以練習結尾，第2版又增加了約75頁解答。開放教材倡議（Open Textbook Initiative）列出本書有許多練習的解答，Smith則說這使它更適合自學。
- 對可表示性的細緻演示。 Smith稱第5章直接寫出定義公式的處理，是現有的完整演示中最易於使用的之一，並指出第2版緩和了對角化引理證明給人的突兀感。
- 免費而緊湊。 正文以知識共享許可開放，作者的目標是在一個學期內講到不完全性定理。
局限
- 希爾伯特式系統。 演繹系統是規則很少的公理化系統。Smith提醒說，沒有見過一階邏輯形式系統的讀者起初可能覺得它很密集，習慣於樹形或自然演繹的學生也許希望有人解釋這一選擇。
- 第5章很費力。 作者自己也把這一章描述為密集而技術性的，是接連不斷的定義。需要為它預留時間。
- 範圍較窄。 本書涵蓋到呂文海姆–斯科倫定理為止的一階邏輯、不完全性定理和一部分可計算性；更深入的模型論和公理集合論不在其內，集合論只出現在一個簡短的附錄中。
- 預設已懂命題邏輯。 命題邏輯只在推理規則一章中作簡要複習，沒有學過的讀者需要先找別的資料。
- 第二不完全性定理依賴假設的條件。 據Smith所說，可導性條件是被假設而非被證明的。
在課程中的定位
在本站的邏輯與集合論書籍中，Leary和Kristiansen是面向哥德爾定理的數理邏輯第一門課的教材。它接在講證明寫作的書之後：Hammack的免費教材 Book of Proof 和Velleman的 How to Prove It 以非形式的方式講邏輯、集合和證明方法，這正是本書加以形式化的背景。Liebeck、Eccles和Allenby關於證明、集合與數系的較廣泛的書，則是更早階段的另一些選擇。
最接近的比較對象是Enderton的 A Mathematical Introduction to Logic，它嚴格地處理命題邏輯和一階邏輯、形式理論與模型論，並與可計算性相聯繫。Leary和Kristiansen則是目標更集中的免費選擇，直奔不完全性定理，在模型論上花的篇幅較少。無論讀哪一本，都為學習模型論、集合論或可計算性的專門教材做好了準備。
如何使用本書
本書寫給高年級本科生，序言介紹了通往不完全性的兩條路線；據Smith所說，對於不排斥抽象論證的哲學專業學生，它也是可讀的。本站列出的先修條件是有證明型數學的經驗。
建議的計畫如下：
- 核心： 第1–4章。第1–3章是一階邏輯直到完全性和緊緻性的自足入門；請慢慢讀第1、2章的定義，因為後面的證明依賴其確切形式。Smith指出，已經熟悉結構和演繹的讀者可以單獨閱讀第3章。
- 選擇通向不完全性的路線： 第4章之後，選第5、6章（公式與哥德爾編碼）或第7章（可計算性）。第二遍閱讀時再讀另一條。
- 可選： 第8章和附錄篇幅不長，主要起導向作用。
- 練習： 做那些要求給出明確演繹和結構的題目，並用解答核對。