認識論概要/數學基礎

數學可以被定義為對所有邏輯上可能的事物的科學，包括所有存在和所有可以在理論中研究的概念。對於一個數學存在來說，只要一個理論正確地確定了它的存在，就足以證明它的存在，而不需要它在有形的和可觀察的現實中存在。

一階邏輯提供了建立理論的手段，這些理論將有限數量的基本概念應用於一個域，這個域可以是有限的，也可以是無限的。為了用一階邏輯原理推理關於可以應用於指定域的個體的所有概念，只需要將概念（屬性和關係）視為新的個體，並給自己一個新的歸屬關係，該關係將屬性（關係）與它們所歸屬的個體（個體的n元組）相關聯。因此，我們可以建立二階邏輯和更高階邏輯。集合論是一種更簡單的方法，可以在一階邏輯框架內建立對所有邏輯上可能事物進行理論化的理論。由於這對初學者來說有點混亂，本章首先概述了一種更自然的方法來奠定數學基礎，從自然數理論開始。

自然數和皮亞諾公理

戴德金 (1888) 和皮亞諾 (1889) 給出了足夠證明其大部分定理的公理系統。皮亞諾算術可以被認為是最基本的數學理論。並且它足以證明大部分最重要的定理，甚至包括微積分中的定理，因為關於實數的定理可以轉化為關於自然數的定理。

在目前的形式化中，所有自然數都從0和一個單一的運算子s（後繼）開始命名

1=s0, 2=s1=ss0, 3=sss0, ...

皮亞諾公理:

0 是一個自然數。
一個自然數 n 總是有一個唯一的後繼 sn，它也是一個自然數。
兩個不同的自然數有不同的後繼。
0 不是任何自然數的後繼。

對於所有自然數 n 和 p

它們的和 n + p 存在且是唯一的，同樣對於它們的唯一乘積 n.p
0 + 0 = 0
n + sp = sn + p = s (n + p)
0.0 = 0
n.sp = n.p + n
sn.p = n.p + p

無窮歸納原理

任何包含 0 並且始終包含其每個元素的後繼的自然數集合都包含所有自然數。

為了進行算術，我們需要對自然數集合進行推理。因此，我們可以考慮用關於數字集合存在的公理來補充皮亞諾公理，但這並不是必需的。具有一個自由變數的算術公式足以命名數字集合。例如，由“存在 p 使得 n = 2.p”定義的公式 A(n) 命名了所有偶數的集合。用這樣的算術公式，我們可以定義許多自然數集合，這對於大多數理論目的來說已經足夠了，但不是全部。

皮亞諾算術既簡單又非常強大。透過對數字進行推理，我們可以對所有可以計數的存在集合進行推理。當我們研究一個邏輯上可能的世界時，其個體是如何被識別的並不重要。它們是被編號還是以其他方式表示，都不會改變所研究的邏輯上可能的世界。重要的是對個體賦予的概念（屬性和關係），而不是個體是如何被識別的。這就是為什麼皮亞諾算術非常強大。它提供了對許多邏輯上可能的世界進行推理的手段。

策梅洛集合論

集合論使得能夠對所有概念進行理論化，因為一個概念可以透過它的外延來表示，即對它為真的存在集合。偶數的概念可以由偶數的集合來表示。數字之間的大於關係可以用所有 (x, y) 數字對的集合來表示，其中 x 大於 y 。

為了建立集合論，最自然的方法是從不是集合的存在開始，例如自然數，或者其他存在，我們將其作為我們定義的集合的元素。

純粹的集合論只研究集合。該理論假設存在的任何存在始終是集合。這對初學者來說有點混亂。我們如何從頭開始建立集合？我們從空集 {} 開始，它不包含任何元素。然後，我們可以定義新的集合：{{}}, {{}, {{}}} ...

自然數可以用集合來表示。例如，我們可以將 0 識別為空集 {}，將 1 識別為 {0}，將 2 識別為 {0,1}，更一般地，將 n 識別為 {0 ... n-1}。所有其他數字都可以從自然數構建出來。

為了研究邏輯上可能的世界，個體是如何被識別的並不重要。它們可以用數字、數字系統或集合來表示。一個邏輯上可能的世界不是由其個體是如何被識別的來決定的，而是由它賦予它們的屬性和關係來決定的。這就是為什麼純粹的集合論能夠建立對所有邏輯上可能事物進行理論化的理論。

一個函式（一個運算子）f 可以用一個關係來表示：y=f(x)，或者 z=f(x,y) ...

一個關係可以用一對、三元組或 n 元組的集合來表示。

一對 (x,y) 可以用一個集合來表示，例如 {{x}, {x,y}}。一個三元組可以從對中表示：例如，(x,y,z) = ((x,y),z)。對於所有 n 元組也是如此。

由於純粹的集合論提供了表示所有個體、所有屬性、所有關係、所有函式的手段，因此它提供了對所有邏輯上可能事物進行推理的手段。

為了證明所有自然數的存在，只需要假設 0 是一個自然數，並且自然數的後繼總是自然數。為了證明集合的存在，我們以類似的方式進行，我們從空集 {} 開始，並證明從我們已經證明存在的集合構建的新集合的存在。

策梅洛公理 (1908)

外延公理： 兩個集合在它們具有相同元素時相等。
空集公理： 存在一個空集。
對公理： 如果兩個集合存在，那麼存在一個集合，它們是唯一的兩個元素。
和集公理： 如果一個集合存在，那麼其所有元素的元素的集合也存在。
無窮公理： 存在一個包含所有自然數的集合。
分離公理： 如果 E 是一個集合，並且 A(x) 是關於集合的定義明確的公式，那麼 E 中所有使 A(x) 為真的 x 的集合存在。
冪集公理： 如果一個集合存在，那麼它的所有部分或子集的集合也存在。
選擇公理：將在下面介紹。

第一個公理是集合的本質特徵。如果兩個存在體在它們具有完全相同的元素時是不同的，那麼它們就不是集合。

接下來的三個公理使得構造自然數成為可能。兩個集合的並集是它們對的和集。集合 *x* 的後繼是並集 *x U {x}*。然後我們定義：*0 = {}*，*1 = 0 U {0} = {0}*，*2 = 1 U {1} = {0,1}* ...

第五和第六公理證明了自然數集 *N* 的存在。這個集合包含所有自然數，並且被包含在包含所有自然數的所有集合中。因此，我們發現數學歸納原理是自然數集定義的結果。

由此，第七公理使得構建第一個無限集的層次結構成為可能：*N*，*N* 的所有子集的集合 *P(N)*，*P(P(N)) = P²(N)*，*P(P(P(N))) = P³(N)* ...

分離公理可以比作雕刻家的鑿子。我們透過給自己提供大型集合，就像大型大理石塊，然後用鑿子，也就是分離公理，來切割它們，從而構建集合。

為了用一階邏輯的方式表達這些公理，我們只需給自己兩個基本關係，屬於一個集合的關係，*是...的元素*，以及等於的關係 =，並假定所有個體的域是所有集合的域（或我們感興趣的所有集合）。

**外延公理**: *對於所有 x 和所有 y，x = y 當且僅當對於所有 z（z 是 x 的元素當且僅當 z 是 y 的元素）*
**空集公理**: *存在 x 使得對於所有 y，y 不是 x 的元素*
**對公理**: *對於所有 x 和所有 y 存在 z 使得對於所有 w（w 是 z 的元素當且僅當 (w = x 或 w = y)）*
**和集公理**: *對於所有 x 存在 y 使得對於所有 z（z 是 y 的元素當且僅當 (存在 w 使得 (w 是 x 的元素並且 z 是 w 的元素)）*

為了表達無窮公理，我們首先定義集合之間的後繼關係：*y 是 x 的後繼當且僅當 y = xU {x}*

y = xU {x} 當且僅當對於所有 z（z 是 y 的元素當且僅當 (z 是 x 的元素或 z = x)）

對於任何集合 x，x 的後繼的存在性由對公理和和公理保證。

**無窮公理**: *存在 x 使得 ({} 是 x 的元素並且對於所有 y，如果 y 是 x 的元素那麼 yU {y} 是 x 的元素)*
**分離公理**: *對於任何定義良好的公式 A(x) 和所有 y 存在 z 使得對於所有 w（w 是 z 的元素當且僅當 (A(w) 並且 w 是 y 的元素)）*

為了表達冪集公理，我們首先定義集合之間的包含關係：*x 包含於 y，或者 x 是 y 的一部分，或者 y 的子集，當且僅當 x 的任何元素也是 y 的元素。*

x 包含於 y 當且僅當對於所有 z，如果 z 是 x 的元素那麼 z 是 y 的元素

**冪集公理**: *對於所有 x 存在 y 使得對於所有 z（z 是 y 的元素當且僅當 z 包含於 x）*

這些公理並不能定義所有集合。特別是，集合 *{N, P(N), P(P(N)) ...}* 的存在，它包含所有 *Pⁿ(N)* 對於所有自然數 *n*，無法從 Zermelo 公理證明。它可以用一個新的公理，由 Fraenkel (1922) 提出的替換公理來證明，這個公理更強大，可以用來證明大型無限集合的存在。但即使有了這個新的公理，仍然有一些集合是該理論無法定義的。

對於普通數學，甚至對於非常高階的數學，Zermelo 理論足以構建我們想要構建的所有集合，並證明我們想要證明的所有內容。特別是，實數、從實數構造的空間、在其中定義的函式、這些函式的空間、函式的函式，以及因此微積分的所有物件，都可以透過限制自己到無限集層次結構的前幾級來構造。Zermelo 理論不允許構造的較大無限集使用得少得多。

分離公理的解釋帶來一個困難。什麼是定義良好的公式？根據 Fraenkel，任何從基本謂詞 *是...的元素* 和 *等於*，以及邏輯連線詞形成的良好格式的公式，都是定義良好的公式。分離公理總是可以應用於它們。但 Zermelo 並不認可這種方法，因為這些所謂的明智公式可能包含對所有集合的斷言，就好像所有集合的宇宙具有客觀存在一樣。但我們不知道這樣的宇宙是什麼。因此，我們並不總是知道對用於在 ZFC 中定義集合的公式賦予什麼意義。這個理論導致證明了存在非良好定義的集合。然而，非良好定義的集合不是集合，它不存在。所以 ZFC 是假的。

要糾正 Fraenkel 的錯誤，只需要求分離公理應用於定義良好的公式，它們只包含有界量詞，也就是說它們不包含關於所有集合的陳述，而只包含關於已經定義集合的所有元素的陳述。有了這些限制，並且沒有替換公理，我們擁有了當前數學所需的足夠力量。

選擇公理

證明一個集合存在的最直接方法是定義它，這相當於從已經定義的集合中構造它。空集足以開始構建我們定義的所有集合。但我們也可以間接地證明存在。我們證明一個集合存在並具有一定的性質，而沒有明確地定義它，沒有構造它，沒有準確地說我們談論的是哪個集合。

存在性的間接證明使我們能夠證明，為了證明一個集合的存在，人們總是可以進行有限次數的任意選擇。更準確地說，如果有一份非空且不相交集合的有限列表，那麼可以證明，存在至少一個集合，它包含每個列表集合中的一個且只有一個元素。我們沒有構建這個新的集合，我們沒有選擇它的元素，我們只是證明了它存在。有限集合的邏輯原理和構造公理足以證明它的存在。但如果非空且不相交集合的列表是無限的，那麼這些原理和公理就不能證明存在一個集合，它包含每個列表集合中的一個且只有一個元素。選擇公理明確地說明了這樣的集合存在（Zermelo 1904）

**選擇公理**: *如果 E 是一個非空且不相交集合的集合，那麼存在一個集合，它包含 E 的每個元素中的一個且只有一個元素。*

羅素悖論

除了 Zermelo 的分離公理，我們本可以想到一個更簡單的公理

**弗雷格公理**: *如果 A(x) 是一個明智的公式，那麼所有使得 A(x) 為真的 x 的集合存在。*

這個公理是由弗雷格 (1879) 提出的，用來奠定所有數學的基礎，但羅素 (1901，出版於 1903) 意識到它導致了矛盾。*x 不是 x 的元素* 是一個明智的公式。一般來說，集合不是自身的元素，但可能存在例外，比如所有集合的集合。*所有使得 x 不是 x 的元素的 x 的集合*，所有不是自身元素的集合的集合，如果我們採用弗雷格公理，則存在。它是否為自身的元素？從它的定義可以得出，它是一個元素當且僅當它不是自身的元素。這是荒謬的，所以這個集合不能存在，所以弗雷格公理是假的。

Zermelo 理論使得定義非常大的集合成為可能，但仍然不能定義所有集合的集合。否則，分離公理將使得定義所有不是自身元素的集合的集合成為可能，並且該理論將是矛盾的。我們將在後面展示它確實是正確的，因此是自洽的。因此，它不允許構建會導致矛盾的悖論集合。

一般來說，集合論不允許我們定義它允許定義的所有集合的集合。否則，這個集合將是自身的元素，並且有了分離公理，該理論將是矛盾的，因為在該理論中定義的所有不是自身元素的集合的集合將在該理論中是可定義的。如果該理論是定義良好的，那麼在該理論中定義的所有集合的集合也是定義良好的，但它在該理論中是不可定義的。這是數學基礎不完備性的原因之一。

在 Zermelo 理論中定義的所有集合的集合在 Zermelo 理論中是不可定義的，但它在一個更強大的理論中是可定義的。例如，替換公理提供了定義它的方法。

不可數無限

當我們能夠用自然數 0, 1, 2, 3, 4... 對集合中的所有元素進行編號時，該集合就是可數的。可數集合可以是有限的或無限的。所有自然數的集合是無限的且可數的。康托爾 (1874) 證明存在更大的無限集合。特別是，自然數集合的集合不可數。

這是透過歸謬法證明的。假設自然數集合的集合是可數的。這意味著它們都可以用一個數字來標識。然後讓我們定義集合 C ，該集合包含不在其編號的集合中的數字，並讓 n 為 C 的編號。但如果 n 不在 C 中，那麼根據 C 的定義，它就在 C 中。因此它必須在 C 中。但這樣一來，根據 C 的定義，它就不在 C 中了。n 在 C 中當且僅當它不在 C 中。這是個矛盾。因此集合 C 不可能存在。因此，自然數集合的集合不可數。

由一個理論定義和命名的存在物的集合總是可數的，因為我們使用有限的字母表來定義和命名。總能對從有限字母表中形成的單詞進行編號。只需按長度排序，然後按字母順序排列相同長度的單詞即可。單詞的編號就是其序列號。

不可數性是數學基礎不完備性的原因之一。一個理論只能定義可數的集合，因此它永遠無法定義不可數集合中的所有元素，它永遠無法提供完全填充不可數集合的手段。

當從一個集合到另一個集合存在雙射時，這兩個集合具有相同的基數。這意味著我們可以用另一個集合的元素識別一個集合中的所有元素。從 E 到 F 的雙射是一個函式，該函式的定義域是 E，並且每個 F 元素都有唯一的先行元素。因此，具有相同基數的兩個有限集合必然具有相同數量的元素。基數的概念將元素數量的概念推廣到無限集合。兩個集合，無論是有限的還是無限的，只有當且僅當它們具有相同數量的元素時，它們才具有相同的基數。根據這個定義，康托爾創立了無窮數理論。

當一個集合與自然數集合具有相同的基數時，該集合是可數無限的。

康托爾證明了一個集合不能與其所有部分的集合具有相同的基數。他得出結論，存在許多無窮數，而不僅僅是自然數的數目。

良序集和無窮歸納法

良序集的概念使我們能夠指定一個過程的概念，在這個過程中，每一步都在前一步完成之後確定。當這樣的過程是有限的時，它的每一步都可以用從 1 到 n 的自然數進行編號。當一個過程是無限的時，它的每一步都可以用良序集中的一個元素來標識。

一個集合 E 是全序的，當且僅當存在一個關係 <，使得對於 E 中的所有 x，y 和 z，

如果 (x<y 且 y<z) 那麼 x<z
如果 x<y 那麼不成立 y<x
x<y 或 y<x 或 x=y

為了使一個逐步過程能夠確定，剩餘步驟中的第一個步驟必須始終確定。因此，我們要求步驟的順序，以便後續步驟的集合始終具有第一個元素（或最小元素）。這導致對 E 上的順序關係強加以下屬性

如果 E 的任何部分的嚴格上界的集合不為空，則該集合具有第一個元素。

(x 是 y 的嚴格上界當且僅當 x 嚴格大於（或在）y 的所有元素。）

可以證明，如果 E 是一個全序集，則這個嚴格上界屬性等價於以下屬性

E 的任何非空部分都具有第一個元素。

一個集合是良序的，當且僅當（它是全序的，並且它的每個非空部分都具有第一個元素）。

自然數集是其自然順序關係最小的良序無限集。更大的良序集可以簡單地透過在無限步驟序列之後新增步驟來定義。

無窮歸納原理可以推廣到所有良序集

如果 x 是一個包含良序集 y 的第一個元素的集合，並且當 x 包含 y 中所有嚴格在 z 之前的元素時，x 始終包含 y 中的元素 z，那麼 x 包含 y 中的所有元素。

這是透過歸謬法證明的：如果 y 中所有不在 x 中的元素的集合不為空，則該集合具有第一個元素。這個第一個元素的存在與關於 x 的一個或多個條件相矛盾。因此，y 中所有不在 x 中的元素的集合為空。

兩個良序集 E 和 F 代表相同的序數，當且僅當它們是同構的。這意味著存在從 E 到 F 的雙射 f，使得 x<y 當且僅當 f(x)<f(y)。

與基數一樣，序數也可以被認為是數字，可以是有限的也可以是無限的。但是序數的算術比基數的算術更精細，因為兩個良序無限集可以具有相同的基數，但代表非常不同的序數。

集合是如何定義良好的？

除了空集之外，純集合論中的所有集合都是從先前定義的集合中定義的。當集合總是透過遵守以下三個條件來定義時，它們就是定義良好的

對於一個新定義的集合，我們必須能夠給出集合的良序列表，可以是有限的也可以是無限的，使得列表中的每個集合都是從先前定義的集合中定義的。列表中的第一個專案始終為空集。列表中的最後一個專案是新定義的集合。
新定義集合的元素必須始終是先前定義的集合或先前定義集合的一部分。
屬於新定義集合的原子真理必須由集合的定義以及屬於先前定義集合及其部分的原子真理決定。

我們可以考慮一個更嚴格的條件來代替第二個條件：新定義集合的元素必須是先前定義的集合。但這個條件可能會禁止定義無限集合的全部部分集合，因為它不可數。由於一個定義良好的集合的全部部分集合本身就是定義良好的，因此必須承認，一個定義良好的集合的元素可以是尚未先前定義的集合。

弗雷格的公理不符合第二個條件，因為新定義集合的元素不一定是先前定義的集合或此類集合的一部分。

在弗蘭克爾的公式 (ZFC) 中，分離公理不符合第三個條件，因為使用無界量詞意味著屬於新定義集合的原子真理是由屬於所有集合的所有原子真理決定的，而不僅僅是由屬於先前定義集合的原子真理決定的。為了滿足第三個條件，用於定義集合的所有量詞必須受先前定義的集合約束。

策梅洛提出的所有集合構造公理都符合這三個條件，前提是在使用分離公理構造的集合的定義中，量詞是有限制的。

在策梅洛的理論中，可定義的集合是什麼？

我們可以從一個初始數字零和一個數字建構函式 the successor of 中定義所有自然數。同樣，我們可以從初始集合和集合建構函式中定義策梅洛理論中的所有可定義集合。初始集合是空集和所有自然數的集合。基本建構函式是 the pair of、the sum-set of、the set of parts of 以及所有可以用分離公理定義的無限數量的建構函式，前提是量詞在集合的定義中是有限制的。建構函式是基本建構函式的所有有限組合。策梅洛理論中的可定義集合是所有透過將這些建構函式之一應用於空集和所有自然數的集合而獲得的集合。

置換公理

如果 R 是集合之間定義良好的函式關係，並且 E 是一個集合，那麼我們可以將 E 中的所有元素替換為它們的函式影像，從而得到一個集合。更準確地說，存在一個集合，其中包含所有滿足存在 E 中的 x 使得 Rxy 的 y，並且只有這些 y。

一個關係是函式關係，當且僅當它始終將單個元素與同一個元素關聯起來：對於所有 x，y 和 z，如果 Rxy 且 Rxz，那麼 y=z

弗蘭克爾公理的解釋提出一個難題：何時函式關係是定義良好的？

在 ZFC 理論中，弗蘭克爾允許使用無界量詞定義的函式關係，因此是定義不當的函式關係。在弗蘭克爾的版本中，置換公理因此是錯誤的。為了正確應用弗蘭克爾的公理，我們需要一個定義良好的函式關係理論。

一個定義良好的集合理論

策梅洛理論是一個關於定義良好的集合的理論，前提是在用分離公理構造集合的定義中強制使用有界量詞規則。但是，如果我們想發展無限集理論，這就不夠。ZFC 更加強大，但它允許定義不明確的構造。

我們可以定義一個比策梅洛理論更強大的理論，該理論只允許使用基本建構函式及其有限組合進行定義良好的構造。

第一類建構函式使用已經構造的集合構造新的集合。策梅洛理論的基本建構函式（對，和集，冪集以及所有可以用分離公理定義的建構函式，前提是所有量詞在集合定義中是有界的）是第一類建構函式。第一類建構函式的有限組合也是第一類建構函式。我們引入兩個新的基本建構函式：映象集和透過有限次迭代獲得的集合，我們將其簡稱為無限集。它們是第二類建構函式。它們用第一類建構函式構造第一類建構函式。

如果f是一個帶有一個引數的第一類建構函式，那麼f 的映象集是一個第一類建構函式，對於任何集合x，它構造所有滿足以下條件的 y 的集合：存在 x 中的 z 使得 y=f(z)。f 對 x 的無限集是包含以下元素的集合：x, f(x), f(f(x)), f(f(f(x))) ... 對於f 的所有有限次迭代。

一個建構函式f總是可以用一個關係來定義：f(x)=y 或 f(x,y)=z 或 ...

我們將證明本理論中的所有第一類建構函式都可以用純集合理論中的關係來定義。

{x,y}=z 由以下定義：對於所有 w，w 是 z 的元素當且僅當 (w=x 或 w=y)

y 是 x 的和集 由以下定義：對於所有 z，z 是 y 的元素當且僅當存在 w 使得 (w 是 x 的元素，並且 z 是 w 的元素)。

y 是 x 的冪集 由以下定義：對於所有 z，z 是 y 的元素當且僅當 z 包含在 x 中

令 A(w, y₁ ... y_n) 是一個自由變數為 w, y₁ ... y_n 的語句。我們假設 A(w, y₁ ... y_n) 中的量詞總是受 y₁ ... y_n 之一的限制。分離公理斷言：對於所有 y₁ ... y_n 和所有 x，存在 z 使得對於所有 w，w 是 z 的元素當且僅當 (w 是 x 的元素，並且 A(w, y₁ ... y_n))。這相當於斷言存在一個帶 n+1 個引數的建構函式f。f(x, y₁ ... y_n)=z 由以下定義：對於所有 w，w 是 z 的元素當且僅當 (w 是 x 的元素，並且 A(w, y₁ ... y_n))。因此，所有用分離公理定義的建構函式都可以用純集合理論中的關係來定義。

在理論中可以定義的建構函式組成的建構函式也可以在該理論中定義。例如 g(f(x))=y 可以用以下定義：存在 z 使得 f(x)=z 且 g(z)=y

令f 是一個帶有一個引數的第一類建構函式，R 是定義它的關係：Rxy 當且僅當 f(x)=y

y 是 f 對 x 的映象集 由以下定義：對於所有 z (z 是 y 的元素當且僅當存在 w 使得 (w 是 x 的元素，並且 Rwz))

x 對 R (或對f) 封閉由以下定義：對於所有 y 和所有 z，如果 y 是 x 的元素，並且 Ryz，那麼 z 是 x 的元素

y 是 f 對 x 的無限集 由以下定義：x 是 y 的元素，並且 y 對 R 關閉，並且對於所有 z，如果 (x 是 z 的元素，並且 z 對 R 關閉)，那麼 y 包含在 z 中

我們得出結論，本理論中的所有第一類建構函式都可以用純集合理論中的關係來定義。

為了建立一個定義良好的集合理論，我們保留了策梅洛的所有公理，除了無窮公理，並添加了兩個公理模式：替換公理和廣義無窮公理。

替換公理：如果 R 是一個定義帶有一個引數的第一類建構函式的關係，那麼對於所有 x，存在 y 使得對於所有 z (z 是 y 的元素當且僅當存在 w 使得 (w 是 x 的元素，並且 Rwz))
廣義無窮公理：如果 R 是一個定義帶有一個引數的第一類建構函式的關係，那麼對於所有 x，存在 y 使得 (x 是 y 的元素，並且 y 對 R 關閉，並且對於所有 z，如果 (x 是 z 的元素，並且 z 對 R 關閉)，那麼 y 包含在 z 中)

所有第一類建構函式都是透過基本建構函式的有限組合得到的：對，和集，冪集，無限集，映象集以及所有用分離公理定義的建構函式，前提是所有量詞在集合定義中是有界的。

該理論中所有可定義集合的集合是透過將所有第一類建構函式應用於空集得到的。

我們可以用一個更強大的無窮公理來豐富這個理論，該公理允許對任何序數進行無限歸納。

一致性證明

當一個理論永遠不允許同時證明一個公式及其否定時，它是一致的、非矛盾的或連貫的，否則它是矛盾的、不一致的、荒謬的、不連貫的。

當然，我們希望一個數學理論是一致的。一個不一致的理論不能區分真假。

為了證明一個理論是一致的，最直接的方法就是簡單地證明它是真的，也就是說，證明它的所有定理都是真的。一個真實的理論不可能是不一致的，因為如果一個公式是真，那麼它的否定就是假，因此不是真的。

為了證明一個理論的所有定理都是真的，只需證明它的所有公理都是真的，因為真公式的邏輯結果總是真的。

一個公式的數學真值總是從一個模型中定義的，一個作為思維存在而存在的理論實體。在數學上是真實的，就是在一個數學模型中是真實的。

為了證明一個理論是一致的，只需要證明它的公理對於一個理論模型是正確的。

皮亞諾公理的真實性

一個理論的模型是透過定義一組原子真值來定義的。一個公式是原子的，當它不包含邏輯連線詞時。皮亞諾算術的原子公式是數值表示式之間的等式，以及斷言它們是自然數的公式。一個數值表示式是由0、s、+ 和 . 組成的。

例如，ss0 + ss0 = ssss0 (2 + 2 = 4) 是一個原子公式，它是真的。同樣，s0 + (ss0.ss00) 是一個自然數 也是真的。

所有真實的數值等式的集合可以用多種方式構建。這有點費力，因為我們必須給自己足夠的規則來生成所有這些基本真理，而不遺漏任何一個，但這並不難，因為它是非常基本的。任何計算機都可以輕鬆地區分真等式和其他等式。顯然，這個原子真值集合是存在的。由於一個真實的理論必然是一致的，因此皮亞諾公理的一致性同時得到了證明。

策梅洛公理的模型

我們可以透過將集合的宇宙取為如下定義的集合M來定義策梅洛公理的模型

令S(x) = x U P(x) 是x 和其所有部分的集合的並集。M 是N 與S(N)、S(S(N)) ... 的並集，也就是說，對於任何自然數n，所有Sⁿ(N) 的並集。

讓我們證明所有公理對於這個集合的宇宙M 都是正確的。

從M 的定義中，我們可以立即得出空集公理和無窮公理是正確的。

由於Sⁿ(N) 包含在Sⁿ⁺¹(N) 中，如果n <p，那麼Sⁿ(N) 包含在S^p(N) 中。

令x 和y 是M 中的兩個元素。因此，我們必須有n 和p，使得x 是Sⁿ(N) 的元素，而y 是S^p(N) 的元素。如果n <= p，那麼x 和y 都在S^p(N) 中，因此它們的對在S^p+1(N) 中。如果n>=p，那麼{x,y} 在Sⁿ⁺¹(N) 中。因此，對公理在M 中是正確的。

讓我們用歸納法證明S^p(N) 的元素的元素也是S^p(N) 的元素。該語句對於N = S⁰(N) 是正確的，因為任何自然數n = {0 ... n-1}。由於P(x) 的元素的元素都在x 中，因此如果該語句對於Sⁿ(N) 是正確的，那麼該語句對於Sⁿ⁺¹ (N) 也正確，因此該語句對於任何自然數n 都是正確的。

因此，Sⁿ(N) 的元素的和包含在Sⁿ(N) 中，因此是Sⁿ⁺¹(N) 的元素。因此，和公理在M 中是正確的。

由此可見，Sⁿ(N) 中一個元素的所有子集都包含在Sⁿ(N) 中，因此它們都是Sⁿ⁺¹(N) 的元素。所以，Sⁿ(N) 中一個元素的所有子集組成的集合包含在Sⁿ⁺¹(N) 中，因此是Sⁿ⁺²(N) 的一個元素。因此，冪集公理在M 中成立。

由於M 中所有元素的子集都是M 的元素，因此分離公理在M 中必然成立。

如果E 是一個非空且不相交的集合的集合，並且它屬於Sⁿ(N)，那麼從E 的每個元素中選擇一個元素的集合包含在Sⁿ(N) 中，因為E 的元素的元素都在Sⁿ(N) 中，因此它是Sⁿ⁺¹(N) 的一個元素，因此屬於M。所以選擇公理在M 中成立。

從集合M 的公理的成立情況，我們可以得出結論：策梅洛理論是一致的。然而，這種一致性證明與之前算術一致性的證明之間存在差異。我們沒有顯式構建原子真命題的集合。我們沒有命名模型的所有元素，也沒有說明如何為所有這些元素生成真原子公式的集合。我們無法做到這一點，因為集合M 是不可數的。

是否需要得出結論，這種一致性證明毫無價值？不。但這引發了一個疑問。我們能確定我們構建的集合存在嗎？談論甚至無法列出所有元素的集合，是否冒著荒謬的風險？

我們知道不可數集存在，因為我們可以想到它們。沒有什麼可以阻止我們思考所有自然數集的集合。我們甚至可以在想象中看到它。

無限二叉樹是由一個根節點構建的，根節點分為兩個分支，一個在左邊，另一個在右邊，這兩個分支又分別分為兩個分支，以此類推，無限地進行。從根節點開始並且永不停止的路徑定義了一個自然數集。如果在第n 步中路徑選擇了左邊的分支，那麼n 是該集合的一部分，但如果路徑選擇了右邊的分支，則不是。因此，無限二叉樹的所有路徑的集合是所有自然數集的集合的一種表示。現在我們可以透過觀察無限二叉樹在視野中展開來想象它。我們可以一目瞭然地看到它所有的路徑，並且它們是不可數的。

即使是一條有限長度的直線，它上面也有不可數個點。就像我們可以看到直線和曲面一樣，我們也可以看到不可數。

為了使策梅洛公理的相容性證明為假，必須是我們對不可數集的理解是錯誤的，也就是說，在我們不知情的情況下，對不可數的推理導致了荒謬。但為什麼害怕我們會被自己的推理所愚弄呢？當我們推理一個集合的所有子集時，似乎我們並沒有犯任何錯誤，即使它是一個無限集。

為了使策梅洛公理的一致性證明形式化，只需要在策梅洛公理中新增一個對無限公理的擴充套件：存在一個包含N且當包含x時總是包含x U P(x)的集合。這樣我們就得到了一個更強大的理論，可以證明之前理論的一致性。如果我們想證明這個新理論的一致性，只需要給自己一個新的無限公理。存在一個包含M且當包含x時總是包含x U P(x)的集合。因此，我們可以定義一系列越來越強大的理論，使得一個理論的一致性總是可以由下一個理論證明。

集合論沒有終極模型。

當我們定義一個集合的集合，使得所有公理在無界量詞被解釋為該集合的集合的界限量詞時為真時，我們就定義了集合論的一個模型。集合的集合在該理論中扮演著所有被研究集合的宇宙的角色。集合論的一個自然模型是取該理論中所有可定義集合的並集（M 是策梅洛理論的一個這樣的自然模型）。但這個模型不能是終極模型，因為它不可能定義終極真理。當我們陳述一個關於所有集合的定理時，它的真理超出了關於該理論中所有可定義集合的並集的真理。我們希望它即使對於該理論中不可定義的集合也是真的，因為我們希望它對所有集合都真正成立，只要它們被很好地定義。

要有一個終極模型，必須能夠很好地定義所有良好定義的集合的集合，但這是不可能的，因為它將是它自己的元素。

我們可以考慮為集合論定義一個終極模型 $V$ ，如下所示

$V_{0}=\varnothing$ ，其中 $\varnothing$ 是空集 {}。

$V_{\alpha }=\bigcup _{\beta <\alpha }{\mathcal {P}}(V_{\beta })$ 對於每個序數 α，其中 ${\mathcal {P}}(X)\!$ 是 $X$ 的所有子集的集合。

類 $V$ 然後被定義為所有 $V_{\alpha }$ 的並集，對於所有序數 α

$V=\bigcup _{\alpha }V_{\alpha }$

但這個類別並沒有被很好地確定。為了確定它，所有序數的類別必須事先被很好地確定。但是，序數本質上是一個良序集。我們不能從所有序數的類別來定義所有集合的類別，因為第二個是從第一個定義的。

對於數論或其他特定數學實體，公理的真值總是透過參考模型來確立。我們有一個模型作為公理真值的標準。對於集合論，我們無法擁有最終模型，但我們仍然有真值標準。我們證明存在的集合必須要麼是定義明確的，要麼它們的存在必須源於定義明確的集合。在沒有最終模型的情況下，良好定義的要求充當了真值的標準。

基礎的不完備性

庫爾特·哥德爾於 1931 年證明，我們無法明確地給出所有數學原理的完整列表。更準確地說，一個明確的原理列表永遠不足以證明所有數學真理，即使我們將自己限制在關於自然數的真理。這是哥德爾第一個不完備性定理。原理的不完備性是必要的。它不是來自我們的缺乏想像力或工作。數學家能夠給出非常強大的公理列表，這些公理通常足以證明人們想要證明的所有真理。但是這些列表是不完備的，因為它們不足以證明所有數學真理。它們可以透過新的、更強大的公理來豐富，但它們永遠無法被最終完成。總會有一些數學真理是它們無法證明的。

這個不完備性定理有時被誤解為證據，表明存在我們永遠無法知道的真理，存在我們永遠無法回答的明智問題，存在我們永遠無法找到的解決方案。這種解釋是邏輯上的錯誤。哥德爾證明，對於任何由明確的公理列表定義的連貫理論 *T*，至少有一個真理 *V* 是 *T* 無法證明的。但這並不證明存在一個真理 *V* 是任何理論都無法證明的。實際上，當我們發現一個真理 *V* 在一個理論 *T* 中無法證明時，通常很容易定義一個理論 *T+*，將一個新的公理新增到 *T* 中，從而允許證明 *V*。

希爾伯特（1930 年）的原則「我們必須知道，我們將知道」，即使在哥德爾之後仍然成立。沒有任何東西可以說存在我們永遠無法知道的數學真理。

我們第一次聽到哥德爾的不完備性定理時，通常會非常驚訝，因為我們習慣於將數學真理和可證明性等同起來。當我們知道如何證明一個定理時，我們就知道它是真的。但當我們理解一個明確的公理列表不足以證明所有數學實體的存在時，這種驚訝很容易消失，即使我們將自己限制在最基本的東西，如自然數和自然數的集合。

康託爾的定理，*自然數集不可數*，可以被認為是關於原理不完備性的第一個定理，因為它表明一個理論永遠無法明確地定義所有自然數集。更一般地，只要集合是不可數的，一個理論就永遠無法明確地定義所有元素。

一個理論無法證明它所陳述的所有真命題，因為它永遠無法定義足夠的集合來給出這些證明。例如，無限歸納原理應用於自然數集。如果集合在理論中沒有被定義，我們就不能使用它們來定義用於歸納推理的公式。我們可以得出結論，數學不完備性是不可數性的結果，因為一個理論永遠無法定義不可數的集合，因此總有一些集合是它無法定義的。

我們首先以消除技術難度的方式證明哥德爾第一個不完備性定理，並讓我們專注於論證的核心，一個關於自身不可證明的真命題。哥德爾證明，這個命題在允許公式化的理論 *T* 為真的假設下是真的。但這個關於「不可證明」命題真值的證明無法在 *T* 中形式化。這個命題從 *T* 的公理中是不可證明的，但它不是絕對不可證明的，因為哥德爾已經證明瞭它的真值。為了形式化這個證明，需要一個證明 *T* 的公理為真的理論。但塔斯基已經證明，一個理論永遠無法為自身定義一個真值謂詞。這就是為什麼關於「不可證明」命題的證明無法在 *T* 中形式化的原因。

康託爾關於自然數集不可數性的定理、哥德爾關於可證明性不完備性的定理、塔斯基關於真值不可定義性的定理以及丘奇和圖靈關於不可判定性的定理，都是同一數學不完備性的體現。

我們將最後證明，數學原理的不完備性並不令人感到驚訝，因為如果我們知道如何找到所有不可判定問題的解決方案，我們就會擁有一種全知，我們就會知道如何找到所有問題的所有解決方案。

哥德爾第一個不完備性定理

這裡提出的證明是非傳統的。哥德爾在算術理論上進行論證。它表明公式可以用數字表示，邏輯推理關係可以用數字之間的關係來表示。他證明的所有技術難點都來自這裡：證明公式之間的邏輯關係可以用表示這些公式的數字之間的數值關係來確定。透過在不是數論而是公式論的理論上進行推理，消除了這種難度。

沒有任何東西禁止建立一個允許在自身公式上進行推理的理論。這種方式不如哥德爾的證明那麼令人信服，因為它並沒有證明數論是不完備的，而只是證明瞭關於自身公式的奇怪理論是不完備的。人們甚至可能相信，證明核心中的悖論命題僅來自理論的怪異，並擔心存在一些不一致，因此該理論不是一個好的數學理論。這種擔憂是沒有根據的。如果我們做對了，很容易建立一個關於自身公式陳述真理的真實且因此一致的數學理論。這是證明數學不完備性的最簡單和最快的方式。但這還不足以證明數論的不完備性。

以下證明與哥德爾的證明相同，只不過一點不同，那就是在公式論上進行推理，因此公式不是用數字表示的。

*T* 是一個將自身公式視為個體或物件的理論。它包含二元謂詞 *是……的邏輯結果*，並在其公理中承認邏輯原理。任何有限的前提列表都可以被識別為一個單一的公式，即它們的合取。

它還具有其他謂詞和公理，允許人們推理關於公式是如何構造的。特別是，它必須能夠定義一個謂詞 *是一個具有單個自由變數的公式*。具有自由變數的公式既不是真也不是假。我們必須為它們的變數 *f*、*x*、*y* ... 賦值，然後才能決定它們的真值。例如，*f 是一個公式* 是一個具有自由變數 *f* 的公式。*T* 理論 *T* 還必須能夠定義一個由 *g 是從一個具有自由變數的公式 f 中獲得的，透過用 x 替換其變數的所有出現* 定義的三元謂詞。假設所有公理都已正確選擇，因此它們是真實的，並且足以證明最基本的正式真理。

一旦定義了公理列表，*T* 就允許定義一個謂詞 *在 T 中是可證明的*，因為要成為可證明的，就足以是有限個公理的合取的邏輯結果。

*T* 然後允許定義以下謂詞

*哥德爾 (f)* 按定義等於 *f 是一個具有自由變數的公式，並且存在 g 使得 g 在 T 中不可證明，並且 g 是透過將 f 替換為其自由變數的所有出現從 f 中獲得的*。

*哥德爾 (f)* 是一個具有單個自由變數 *f* 的公式，因為變數 *g* 由存在量詞繫結。

然後我們可以證明，*哥德爾 (哥德爾 (f))* 是一個真命題，但在 *T* 中不可證明。

*哥德爾 (哥德爾 (f))* 按定義表示 *哥德爾 (f) 是一個具有自由變數的公式，並且哥德爾 (哥德爾 (f)) 在 T 中不可證明*。

如果 *哥德爾 (哥德爾 (f))* 在 T 中是可證明的，那麼它將是假的，因為它關於自身聲稱它在 *T* 中不可證明。現在我們假設 *T* 的所有公理都是真的。因此，*T* 的所有定理，即在 *T* 中可證明的命題，也都是真的。因此，*哥德爾 (哥德爾 (f))* 不能是 *T* 的定理，因此它是真的，因為這就是它所說的。因此，我們在 *T* 中找到了一個真命題和一個不可證明的命題。

為了將這個證明轉換為數論，只需證明謂詞 *在數論中是可證明的* 和 *g 是從一個具有自由變數的公式 f 中獲得的，透過用 x 替換其變數的所有出現* 可以用表示公式的數字之間的算術關係來表示。

技術說明：為了正確地構建理論T，必須注意公式變數的使用。f是公式變數，但本身並不是T的良構公式。因此，例如對於任何公式f，f，也不是T的良構公式。良構公式必須始終包含應用於常量或變數的常量謂詞。此外，當公式A(f)應用於另一個公式B(f)時，即形成A(B(f))，變數f在B(f)中是自由的，但在A(B(f))中不是，因為B(f)在那裡是一個常量。

不可數性和不完備性

哥德爾定理的證明類似於康托爾定理的證明，因為具有自由變數的公式可以被視為所有對其為真的存在物的名稱。哥德爾證明定義了所有無法證明屬於它們所編號的公式命名的集合的數字集合。

從數字集合的不可數性得出哥德爾不完備性結果並非先驗的。哥德爾真實的不可證語句只處理數字，而不是數字集合。人們可能希望算術能證明所有隻與數字相關的真理，它不需要證明所有數字集合的存在。但這種希望是徒勞的。

為了證明算術真理，我們使用數學歸納原理，它可以表述如下

如果一個數字集合包含零，並且它始終包含其每個元素的後繼，那麼它包含所有自然數。

沒有明確處理數字集合的數論將此原理應用於具有自由變數的公式。這些用來表示數字集合。

一個明確的理論永遠無法證明所有關於數字的真理並不奇怪，因為總是有它無法定義的數字集合，這些集合可能需要證明關於數字的某些真理。關於數字的真實語句是不可證的，當該理論沒有定義證明它所需的數字集合時。以下將表明，對於哥德爾的真實不可證語句，缺失的集合是算術真理的數字集合。

塔斯基關於真理不可定義性的定理

我們可以透過簡單地說出我們必須說的話來說出真理，但我們也可以透過冗餘地堅持並說出我們所說的是真理來表達。我們使用真理謂詞，可以將其歸因於或不歸因於我們所說的一切。塔斯基 (1933) 證明，如果一個數學理論是真實的，那麼這樣的真理謂詞就不可能存在。

讓我們從上面討論的關於其自身公式的理論 T 開始推理。

如果T包含真理謂詞它是真的，那麼公式它是真的，當且僅當f對於T的所有公式f都是真的。根據真理的定義，雪是白色的，當且僅當雪是白色的。正是憑藉這一原理，塔斯基奠定了數學真理理論（塔斯基 1933），我們現在將其理解為模型理論。

讓我們透過歸謬法來證明，如果一個理論T是真實的，那麼真理謂詞不可能存在於它之中。

假設對於T的所有公式，在T中定義了一個謂詞是真實的。

讓我們透過f是具有自由變數的公式，並且存在一個公式g，使得g不為真，並且g是透過將f的所有自由變量出現的f替換為f而從f獲得的，來定義具有自由變數的公式Tarski(f)。

Tarski(Tarski(f)根據定義意味著Tarski(Tarski(f))不為真。Tarski(Tarski(f))當且僅當不為真時才為真，這是一個謬論，因此如果謂詞是真實的是真實的，它就不可能存在於理論T中。

要將此證明轉換為數論，只需對謂詞是真公式的數字進行推理。一個數論永遠不允許定義這樣一個謂詞，如果它是真實的。

塔斯基既是能夠定義數學真理的理論家，也是證明它在所有數學理論中都不可定義的人。

塔斯基定理提供了哥德爾第一個不完備性定理的另一個間接證明：如果一個理論能夠定義自身可證性的謂詞，並且它的所有定理都是真的，那麼必須至少存在一個真且不可證的語句，否則可證性謂詞將是真理謂詞。

如何證明不可證的？

讓我們回到定義了可證性謂詞在T中可證和T中的一個真且不可證語句的理論T。透過展示這個“不可證”的語句，我們證明了它是真的。證明很簡單，但它基於理論T本身是真實的假設。但理論T不允許定義自身真理的謂詞，如果它是真實的，只允許定義可證性的謂詞。因此，我們無法用理論T的方法形式化“不可證”語句的非形式化證明。這就是為什麼這個可證語句在T中是不可證的。但是塔斯基對數學真理的定義允許我們用一個真理謂詞定義一個理論T+，該謂詞僅限於T：是T的真公式。然後可以在T+中形式化T中真且不可證語句的非形式化證明。因此，T中的不可證語句是T+中證明的定理。但當然T+不是一個完備的理論，因為我們可以在T+中找到一個新的真且不可證的語句，該語句需要一個真理謂詞來證明，該謂詞僅限於T+。

要在T+中形式化非形式化證明，必須在T+中證明T的所有定理都是真的。它是透過數學歸納法證明的。如果一個公式集合包含T的所有公理及其元素的所有直接邏輯結果，那麼根據T的定理集的定義，它包含T的所有定理。因此，要證明T的所有定理都是真的，只需證明T的所有公理都是真的，以及真公式的直接邏輯結果同樣也是真的就足夠了。但要形式化這個非形式化證明，需要在T+中有一個針對T公式的真理謂詞。

要將此證明轉換為數論，只需對謂詞是該理論的真公式的數字進行推理。人們總是可以為算術理論新增新的公理，以便這個真理謂詞（限於初始理論）是可定義的。因此，可以在富集的理論中證明初始理論中真實且不可證的語句。只需形式化非形式化證明即可。

哥德爾第二不完備性定理

哥德爾已經證明，一個一致的理論永遠無法證明自身的一致性。哥德爾的第二個不完備性定理經常被誤解。人們認為，對一致性的證明非常困難，或者難以獲得，或者永遠無法得到理性的證明，因為它會陷入惡性迴圈。但有一個更直接的解釋。一致性證明有時很容易找到，並且是不可反駁的，沒有任何邏輯錯誤，並且沒有任何疑問能夠持續存在，但它們不能在證明了一致性的理論中形式化，因為它們需要該理論的真理謂詞。塔斯基關於真理謂詞不可定義性的定理解釋了哥德爾的第二個不完備性定理。

哥德爾第二不完備性定理：一個真實的理論不能證明自身的一致性。

讓我們對理論T及其真語句進行推理，該語句在T中是不可證的，Gödel(Gödel(f))。

讓我們透過歸謬法來證明T不能證明自身的一致性。如果可以的話，它可以證明Gödel(Gödel(f))並且不是Gödel(Gödel(f))在T中是不可證的。

但根據Gödel(f)的定義，它可以證明如果不是Gödel(Gödel(f))那麼 (Gödel(Gödel(f)) 在T中是可證的)。因此它可以證明如果不是Gödel(Gödel(f))那麼 (不是Gödel(Gödel(f)) 在T中是不可證的)。但不是Gödel(Gödel(f))意味著Gödel(Gödel(f))根據Gödel(f)的定義在T中是可證的。因此T可以證明如果不是Gödel(Gödel(f))那麼 ((Gödel(Gödel(f)) 在T中是可證的) 在T中是不可證的)。

此外，T 可以證明對於每個公式 f，如果 f 在 T 中可證，則斷言 f 在 T 中可證的公式在 T 中可證。這一點有時被認為是哥德爾證明中的難點。但對於理論 T 來說，這幾乎是顯而易見的，因為對一個定理的證明同時證明了該定理是可證的。由於 T 可以證明 如果非 Gödel(Gödel(f))，那麼 (Gödel(Gödel(f)) 在 T 中可證)，它也可以證明 如果非 Gödel(Gödel(f))，那麼 ((Gödel(Gödel(f)) 在 T 中可證) 在 T 中可證)。

由於 T 可以從非 Gödel(Gödel(f)) 中得出矛盾的結論，它可以透過歸謬法證明Gödel (Gödel(f))。但Gödel(Gödel(f)) 自己說它在T 中不可證。所以T 不會是真的。

因此，T 如果為真，則不能證明自身的相容性。

這種推理可以透過對公式進行編號而移植到數論。

一致性證明是否陷入惡性迴圈？

展示模型的一致性證明是在一個比T₀ 強的理論 T₊ 中形式化的，T₀ 是它證明了一致性的理論，因為它們定義了 T₀ 的真值集，而這個集合在 T₀ 中無法定義。如果一個理論是荒謬的，那麼透過新增公理獲得的任何理論也是荒謬的。一個荒謬的理論可以證明任何東西，一個肯定和它的反面，包括荒謬並非荒謬。因此，我們證明一個理論一致性的方法不能讓我們區分一致理論和不一致理論，因為一個比不一致理論“更強”的理論可以證明它是相容的。這就是為什麼人們有時認為這種證明什麼也沒證明，但這是一種錯誤。

我們不會對任何我們一無所知的 T₀ 理論進行推理。 T₀ 是皮亞諾算術或策梅洛理論，或其他我們用來奠定數學知識的理論。我們事先知道這些理論允許我們證明真理，因為沒有它們，我們就不會擁有數學知識，而且似乎很明顯我們有一些數學知識。如果我們非常悲觀，我們可能會擔心我們的形式理論包含會導致矛盾的措辭錯誤，而我們並不知道。但毫無疑問，這些理論經常揭示真相，除非我們放棄數學知識。當我們證明形式理論是真實和一致時，我們證實了我們已經直觀相信的東西。而且我們證明了我們推理的自然能力足以讓我們正確地推理推理。所以這不是一個惡性迴圈。它是理性的良性迴圈，理解自身。

理論、軟體和遞迴可列舉集

數學理論和軟體、計算機程式之間存在著非常密切的對應關係。當我們明確定義一個理論時，我們總是可以編寫一個程式來證明它的所有定理。它只需按順序列印所有公理和它之前列印過的公式的所有直接邏輯推論即可。這種尋找證明的方法只具有理論上的意義。在實踐中，計算機將在找到值得寫入的定理之前列印大量的毫無意義的公式。即使是最強大的計算機，通常也需要等待過長的時間才能找到有趣猜想的證明或反證。

我們可以給出幾個遞迴可列舉集的定義，它們都是等價的。從許多其他條件中選擇的以下條件，這三個條件都定義了集合E 的遞迴可列舉性

屬於E 的所有原子真值都是一個明確理論的可證語句、定理。
存在一個軟體，當我們呈現E 的元素的名稱時，它總是回答“是”，當我們呈現不在E 中的實體的名稱時，它不回答或回答“否”。
存在有限數量的初始表示式和有限數量的生成規則（Smullyan 1961），足以生成屬於E 的所有原子真值。

一個明確理論的定理集始終是一個遞迴可列舉集。如果我們向一個證明查詢器軟體呈現一個定理，它將始終能夠識別它是一個定理，因為它會檢查所有可能的證明，無論它們有多長。如果我們呈現一個非定理，它不會回答，因為它會永遠尋找一個不存在的證明。

不可判定集和問題

遞迴可列舉集總是可數的。由於它們的所有元素都可以被命名，我們總是可以在所有命名實體的集合中定義它們的補集，只要我們固定了一個命名系統。

當一個集合及其補集都是遞迴可列舉時，這個集合是可判定的，否則它是不可判定的。

當一個問題的所有解的集合不可判定時，該問題是不可判定的。

一個不可判定集的例子是皮亞諾算術中的所有真值集。哥德爾的第一不完備性定理證明了這個真值集不是遞迴可列舉的，因此不可判定。如果它是遞迴可列舉的，那麼人們可以找到一個足夠的公理完整列表來證明所有算術真值，但哥德爾證明了這樣的列表不存在。

說一個問題不可判定並不意味著我們無法解決它，也不意味著它有我們永遠找不到的解，它只意味著沒有明確定義的理論可以給出該問題的所有解。我們定義的理論只能部分解決一個不可判定問題，永遠無法完全解決。對於不可判定問題，我們永遠不會結束，它是一個永遠確定的苦役。但我們仍然可以尋找和找到解決方案，而且沒有任何解決方案是先驗不可獲得的。只要有足夠的創造力，我們就可以發明一種理論，使我們能夠找到它。

數學原理的不完備性源於不可判定集的存在。如果所有真值集都是遞迴可列舉的，那麼我們可以給出足夠的公理列表來找到它們。但不可判定性表明真值集並不總是遞迴可列舉的。

通用機器和理論

一臺可程式設計計算機是一臺通用機器，因為它能夠執行任何可想象的程式。如果程式是一次性寫入只讀儲存器 (ROM)，那麼計算機只是一臺特定機器。

一臺通用機器可以做其他機器（通用或特定）所能做的一切。只需給出程式即可。因此，所有通用機器在本質上都是等價的。它們都能做完全相同的事情。

在實踐中，計算機的計算能力和儲存空間有限。但計算能力只是一個速度問題，儲存空間原則上可以無限擴充套件。想象一下，一臺安裝在能夠在一個可以隨時擴充套件的資料庫中移動的機器人的計算機。

一個通用理論是一個可以證明所有其他理論可以證明的理論。例如，邏輯可以被形式化為一個通用理論。只需給出足夠的公理，以便所有形式為 C 是 P 的邏輯結果 的真公式對於所有格式良好的公式C 和P 都是可證的。由於任何理論的任何定理總是從公理的有限合取中證明出來的，因此這種邏輯的形式化是一個通用理論。

哥德爾透過證明公式之間的邏輯關係可以透過表示公式的數字之間的算術關係來表示，證明了算術也是一個通用理論，即使它侷限於一階皮亞諾算術。

通用理論的存在構成悖論。與任何明確的理論一樣，一個通用理論U 不能證明所有真理。它們不能證明的這些真理原則上可以在一個更豐富的理論 U+ 中證明，該理論有更多公理。但由於初始理論U 是通用的，它可以證明 U+ 可以證明的所有內容，這似乎與 U+ 比 U 更豐富的假設相矛盾。特別是，一階算術的一致性證明可以在一階算術中形式化，因為它可以在一個明確的理論中形式化，並且一階算術是一個通用理論。但哥德爾的第二不完備性定理似乎禁止了這種可能性。

這個悖論的解釋有點微妙。U+ 理論可以在U 中形式化，但U “不知道”U+ 是U 的一個豐富，也就是說U 可以證明U+ 的所有定理都是U+ 的定理，但它不能證明U+ 的定理對它本身有效。因此，它可以形式化自身一致性的證明，而沒有明確地說出來，沒有斷言它是關於自身的一致性。

停機問題的不可判定性

停機問題：給定一個計算機程式和一個初始記憶體狀態，計算機將停止並提供答案，還是會無限執行而不會給出答案？

假設計算機在儲存空間上沒有限制，並且在計算時不受外部因素的影響。

圖靈證明了停機問題是不可判定的（1936 年）。

停止的機器的（程式、初始狀態）對的集合是可列舉的，因為計算機可以模擬所有其他機器。如果它被提供了一個程式和一個初始狀態，它只需要在初始狀態上執行程式並等待它停止。如果它停止了，計算機就會響應它停止了。如果它沒有停止，計算機就不會停止並且不會響應。

另一方面，不停止的機器的（程式、初始狀態）對的集合不是可列舉的。這可以透過歸謬法證明。如果它是可列舉的，那麼就會有一個程式 P，使得對於任何對（程式 p，初始狀態 i），當它為真時，機器停止並響應 p 從 i 開始不停止。一個程式可以被寫入記憶體，因此也是一個可能的初始狀態。從 P 開始，我們可以編寫一個程式 P'，使得對於任何程式 p，當它為真時，機器停止並響應 p 從初始狀態 p 開始不停止。我們可以將 P' 作為執行 P' 的機器的記憶體初始狀態。這臺機器會停止嗎？根據構造，當且僅當它不停止時，它才會停止。這是一個荒謬。因此 P' 不可能存在，因此 P 也不可能存在。因此，不停止的機器的（程式、初始狀態）對的集合不是可列舉的。因此停機問題是不可判定的。

所有邏輯定律集合的不確定性

邏輯定律的集合是一個通用理論，因為一個公式是某個理論的定理當且僅當斷言它來自其公理的有限合取是一個邏輯定律。因此，通過了解所有邏輯定律，我們就知道所有理論的所有定理。

當一個理論用有限數量的公理定義時，一個公式不是定理當且僅當斷言它來自公理的合取不是一個邏輯定律。

基本理論（皮亞諾算術，策梅洛理論 ...）通常用公理模式定義。例如，分離公理是一個模式，它允許以無窮數量的公式形成無限數量的公理。當它在謂詞邏輯中表述時，數學歸納原理也是如此。但是這些具有無限數量公理的理論總是等價於具有有限數量公理的理論。透過以哥德爾和伯奈斯的方式引入類，它們類似於集合，但太大而不能真正被視為集合，策梅洛理論只有有限數量的公理。

即使理論有無限數量的公理，人們也總是要求存在有限數量的原則或規則足以機械地產生所有公理，否則該理論就不是明確的。這就是為什麼明確的理論總是等價於具有有限數量公理的理論。

如果邏輯定律的集合是可判定的，那麼所有可列舉的集合都是可判定的。屬於可列舉集合 E 的所有真值都是具有有限數量公理的理論的定理。因此，E 的補集是所有 x 的集合，使得 如果公理成立，那麼 x 屬於 E 不是一個邏輯定律。如果邏輯定律的集合是可判定的，那麼該集合將是可列舉的，因此 E 將是可判定的。

停機問題不可判定性的證明表明，至少存在一個不可判定的可列舉集合。因此，邏輯定律的集合不是可判定的。

第一個不完備性定理的證明可以直接證明邏輯定律集合的不可判定性。如果邏輯定律的集合是可判定的，那麼理論 T 可以有足夠的公理來證明所有形式為 f 不是 g 的邏輯結果 的真公式。因此，它可以證明所有形式為 f 在 T 中不可證 的真公式。由於 Gödel(Gödel(f)) 在 T 中不可證，因此 T 可以證明它。但 Gödel(Gödel(f)) 說它本身在 T 中不可證。然後 T 可以證明 Gödel(Gödel(f)) 在 T 中不可證，這是荒謬的。因此邏輯定律的集合是不可判定的。

邏輯定律集合或 Entscheidungsproblem（希爾伯特 1928 年）的不可判定性是由丘奇和圖靈在 1936 年獨立地用不同的方法證明的。

普遍性是不可判定性的原因

我們知道如何證明其不可判定性的問題總是完備問題，因為如果我們有一種方法可以找到它們的所有解，那麼我們也會有一種方法來解決所有問題。從這個角度來看，數學原理的不完備性最終並不那麼令人驚訝。我們不必將其視為無能的表現，因為它是由思維的普遍性造成的。我們可以思考所有問題，所有理論。我們可以陳述適用於所有可想而知和可思考的事物的普遍定律。但是我們沒有足夠的方法或原則來解決所有問題。我們的方法，即使是最強大的方法，也不能解決所有問題。我們只是生物。知道如何找到一個不可判定問題的全部解將是一種全知，因為人們將同時知道如何找到所有問題的全部解。

一個有限的原則列表足以生成所有邏輯定律。這就是哥德爾關於邏輯完備性的定理。因此，邏輯定律的集合是可列舉的。但由於邏輯定律的集合是不可判定的，因此不是邏輯定律的公式的集合不是可列舉的。邏輯定律在所有可能的世界中都是真的。邏輯定律的否定是謬誤，在所有可能的世界中都是假的。既不是邏輯定律也不是邏輯定律的否定的公式在某些世界中為真，在其他世界中為假，它描述了可能的世界，可以想象的世界。描述一個可能世界的任何有限公理系統都使得其合取的否定不是一個邏輯定律。既不是邏輯定律也不是謬誤的公式的集合是所有公理和有限公理系統的集合，它們至少關於一個可以想象的世界。說它不是可列舉的意味著我們不能給出一個有限的原則列表，足以產生所有這些公理系統。想象力超越了所有框架。無論一個人給自己什麼有限的原則列表，總有它不允許研究的可能世界。因此，數學的不完備性是想象力的普遍性和力量的結果。

下一章：相對論原理的真值>>>