認識論概要/數學基礎

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

一階邏輯提供了一種方法，可以建立有限數量的基本概念應用於一個域（有限或無限）的個體的理論。為了用一階邏輯的原理推理關於所有可以應用於特定域個體的概念，只需要將概念（屬性和關係）視為新的個體，併為自己提供一個新的歸屬關係，該關係將屬性（關係）與它們所歸屬的個體（個體的 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) 是關於集合的明確定義的公式，則所有滿足 A(x) 為真的 E 中的 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，當且僅當對於所有 z（z 是 x 的元素當且僅當 z 是 y 的元素）時，x = 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 ，無法從策梅洛公理中證明。它可以透過一個新的公理，即由弗蘭克爾（1922）提出的替換公理來證明，該公理更強大，可以證明大型無限集合的存在。但即使有了這個新公理，仍然有一些集合是理論無法定義的。

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

對分離公理的解釋存在一個難題。什麼是明確定義的公式？根據弗蘭克爾的說法，任何從基本謂詞 是...的元素 和 等於 以及邏輯連線詞構成的公式都是明確定義的公式。分離公理始終可以應用於它們。但策梅洛並不相信這種方法，因為這些所謂的合理公式可能包含關於所有集合的斷言，就好像所有集合的宇宙具有客觀存在一樣。但我們不知道這樣的宇宙是什麼。因此，我們並不總是知道如何理解用於在 ZFC 中定義集合的公式的含義。這個理論導致證明了非明確定義集合的存在。然而，非明確定義的集合不是集合，它不存在。所以 ZFC 是假的。

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

選擇公理

證明一個集合存在的最直接方法是定義它，這相當於從已經定義的集合構建它。空集足以開始構建我們定義的所有集合。但我們也可以給出存在的間接證據。我們證明一個集合存在並具有某些屬性，而沒有明確地定義它，沒有構建它，沒有確切地說出我們指的是哪個集合。

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

選擇公理： 如果 E 是一個非空且不相交集合的集合，則存在一個集合，它包含每個 E 元素的一個元素，且僅包含一個。

羅素悖論

我們本來可以考慮一個比策梅洛分離公理更簡單的公理

弗雷格公理： 如果 A(x) 是一個合理的公式，則所有滿足 A(x) 的 x 的集合存在。

這個公理是由弗雷格（1879）提出的，用來奠定所有數學的基礎，但羅素（1901 年，1903 年出版）意識到它會導致矛盾。 x 不是 x 的元素 是一個合理的公式。通常，集合不是自身的元素，但也可能存在例外，例如所有集合的集合。 所有滿足 x 不是 x 的元素的 x 的集合 ，所有不是自身元素的集合，如果我們採用弗雷格公理，就存在。它是自身的元素嗎？從它的定義可以看出，它是一個元素，當且僅當它不是自身元素時。這是荒謬的，所以這個集合不可能存在，所以弗雷格公理是假的。

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

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

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 中的所有 x、y 和 z，一個集合 E 是全序的

• 如果 (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 的第一個元素的集合，並且當它包含 y 中所有嚴格在 z 之前的元素時，它總是包含 y 中的元素 z，則 x 包含 y 的所有元素。

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

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

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

集合是如何定義良好的？

除了空集之外，純集合論中的所有集合都是從先前定義的集合中定義的。當且僅當集合始終透過尊重以下三個條件來定義時，集合是定義良好的

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

我們可以考慮一個更嚴格的條件來代替第二個條件：一個新定義的集合的元素必須是先前定義的集合。但這個條件可能會禁止定義無限集合的冪集，因為它是不可數的。由於一個定義良好的集合的冪集本身是定義良好的，所以必須接受一個定義良好的集合可以有作為其元素的集合，這些集合以前沒有被定義。

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

在弗蘭克爾的公式化（ZFC）中，分離公理不尊重第三個條件，因為無界量詞的使用意味著屬於一個新定義的集合的原子真值由屬於所有集合的所有原子真值來確定，而不僅僅是屬於先前定義的集合的原子真值。為了尊重第三個條件，在集合定義中使用的所有量詞都必須受到先前定義的集合的限制。

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

Zermelo 理論中的可定義集合是什麼？

我們可以從一個初始數字零和一個數字建構函式——“後繼”——來定義所有自然數。類似地，我們可以用 Zermelo 的理論從初始集合和集合建構函式來定義所有可定義的集合。初始集合是空集和所有自然數的集合。基本建構函式是“二元組”、“和集”、“冪集”以及可以用分離公理定義的無限數量的建構函式，前提是量詞在集合定義中是受限的。建構函式是所有基本建構函式的有限組合。Zermelo 理論中可定義的集合是所有透過對空集和自然數集應用這些建構函式之一得到的集合。

替換公理

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

當一個關係總是將同一個元素與單個元素關聯時，它就是函式關係：對於所有 x、y 和 z，如果 Rxy 且 Rxz，那麼 y=z

對 Fraenkel 公理的解釋提出了一個難題：何時函式關係是定義良好的？

在 ZFC 理論中，Fraenkel 允許使用不受限的量詞定義函式關係，因此是定義不好的函式關係。因此，在 Fraenkel 的版本中，替換公理是錯誤的。要正確應用 Fraenkel 公理，需要一個定義良好的函式關係理論。

定義良好集合理論

Zermelo 的理論是一個定義良好集合理論，前提是在用分離公理構造集合的定義中施加了受限量詞規則。但是，如果我們想發展無限集合理論，它是不夠的。ZFC 強大得多，但它允許定義不好的構造。

我們可以定義一個比 Zermelo 理論強大得多的理論，它只允許使用基本建構函式及其有限組合來進行定義良好的構造。

第一類建構函式從已經構造的集合中構造集合。Zermelo 理論的基本建構函式（“二元組”、“和集”、“冪集”以及可以用分離公理定義的所有建構函式，前提是在集合定義中所有量詞都是受限的）是第一類建構函式。第一類建構函式的有限組合也是第一類建構函式。我們引入兩個新的基本建構函式：“像集”和“透過有限迭代獲得的集合”，我們將其縮寫為“無限集”。它們是第二類建構函式。它們從第一類建構函式中構造第一類建構函式。

如果f是一個具有一個引數的第一類建構函式，那麼“f的像集”是一個第一類建構函式，它對於任何集合x構造所有 y 的集合，使得存在 z 屬於 x，使得 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

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

為了奠定一個定義良好集合理論，我們保留了 Zermelo 的所有公理，除了無限公理，並且我們添加了兩個公理模式：替換公理和一個廣義的無限公理。

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

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

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

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

一致性證明

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

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

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

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

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

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

Peano 公理的真理

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

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

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

Zermelo 公理的模型

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

設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 不是集合的一部分。因此，無限二叉樹的所有路徑集是所有自然數集的集合的表示。現在，我們可以透過觀察無限二叉樹在視野中的展開來想象它。我們可以一眼看到它所有的路徑，它們是不可數的。

一條直線上有不可數多個點，即使它長度有限。因為我們可以看到直線和表面，所以我們可以看到不可數的東西。

為了使策梅洛公理的一致性證明為假，我們必須錯誤地認為不可數集合，即在不知不覺中，關於不可數的推理會導致我們陷入荒謬。但為什麼害怕我們可能被自己的理性愚弄？似乎我們在對一個集合的所有子集進行推理時沒有犯錯誤，即使它是一個無限集。

為了使策梅洛公理的一致性證明形式化，只需要在策梅洛公理中新增對無限公理的擴充套件：存在一個包含 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 ，任何理論都無法證明它。事實上，當我們在一個理論 T 中找到一個無法證明的真理 V 時，通常很容易定義一個理論 T+ ，在 T 中新增一個新公理，從而允許證明 V 。

希爾伯特（1930 年）的原理，“我們必須知道，我們將知道”，即使在哥德爾之後仍然成立。沒有任何東西可以證明存在我們永遠不會知道的數學真理。

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

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

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

我們首先以一種消除技術困難並允許我們專注於論證核心的一種方式來證明哥德爾的第一個不完備性定理，即一個關於自身不可證明性的真命題。哥德爾證明了，這個命題在允許表達它的理論 T 是真的的情況下是正確的。但是這個“不可證明”命題的真實性證明不能在 T 中形式化。這個命題從 T 的公理無法證明，但它不是絕對不可證明的，因為哥德爾已經證明了它的真實性。為了形式化這個證明，需要一個證明 T 的公理是真實的理論。但是塔斯基證明了一個理論永遠不能為自己定義一個真理謂詞。這就是為什麼“不可證明”命題的證明不能在 T 中形式化的原因。

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

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

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

這裡提出的證明是不尋常的。哥德爾論證的是一個算術理論。它表明公式可以用數字表示，邏輯推論之間的關係可以用數字之間的關係表示。他證明的全部技術難度來自這裡：表明公式之間的邏輯關係可以透過表示這些公式的數字之間的數字關係來確定。透過不針對數字理論，而是針對公式理論進行推理，消除了這種困難。

沒有什麼禁止做一個允許針對它自己的公式進行推理的理論。這種方式不像哥德爾的那麼令人信服，因為它沒有證明數論是不完整的，而只是證明它自己公式的一個奇怪理論是不完整的。人們甚至可能認為，證明的核心是那個悖論性的命題，它僅僅來自理論的奇怪性，並擔心存在一些不一致性，因此該理論不是一個好的數學理論。這種恐懼是毫無根據的。如果我們做對了，很容易建立一個真實的，因此是一致的數學理論，它陳述了關於它自己公式的真理。這是證明數學不完備性的最簡單、最快的方法。但這不足以證明數論的不完備性。

以下證明與哥德爾的證明相同，只有一點不同，即一個人針對公式理論進行推理，因此公式沒有用數字表示。

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

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

一旦定義了它的公理列表， T 就可以定義謂詞在 T 中可證明，因為要可證明，就足以是公理的有限合取的邏輯推論。

T 然後允許定義以下謂詞

Gödel (f) 按定義等於 f 是一個具有一個自由變數的公式，並且存在 g 使得 g 在 T 中不可證明，並且 g 是透過用 f 替換其所有自由變量出現來從 f 中獲得的。

Gödel (f) 是一個具有一個自由變數 f 的公式，因為變數 g 被存在量詞繫結。

然後我們可以證明 Gödel (Gödel (f)) 是一個真命題，但在T中不可證。

Gödel (Gödel (f)) 根據定義意味著 Gödel (f) 是一個帶有自由變數的公式，並且 Gödel (Gödel (f)) 在 T 中不可證 。

如果 Gödel (Gödel (f)) 在 T 中可證，那麼它將是假的，因為它本身表示它在 T 中不可證。現在假設 T 的所有公理都是真的。因此， T 的所有定理，即在 T 中可證的命題，也是真的。因此， Gödel (Gödel (f)) 不能是 T 的定理，因此它是真的，因為這正是它所表達的。因此，我們在 T 中找到了一個真命題且不可證的命題。

為了將這個證明移植到數論，只需證明謂詞 在數論中可證 和 g 是透過將 x 代入其所有自由變數的出現而從帶有自由變數的公式 f 中得到的 可以用表示公式的數字之間的算術關係來表示。

技術說明：為了正確地構建理論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 獲得的 來定義帶有自由變數的公式 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 中可證。這個點在 Gödel 證明中有時被認為是困難的。但對於理論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₀是皮亞諾算術或策梅洛理論，或者我們選擇作為我們數學知識基礎的其他理論。我們事先知道這些理論允許我們證明真理，因為沒有它們，我們就不會有數學知識，而且我們似乎很清楚我們有一些數學知識。如果我們非常悲觀，我們可能會擔心我們的形式理論包含會導致矛盾的措辭錯誤，而我們並不知道。但毫無疑問，這些理論經常揭示真理，除非我們放棄數學知識。當我們證明形式理論是真實和相容的時，我們證實了我們已經直覺上相信的東西。並且證明了我們自身的推理能力足以對推理進行正確的推理。所以這不是惡性迴圈。這是理效能理解自身的良性迴圈。

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

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

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

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

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

不可判定集合和問題

遞迴可列舉集合總是可數的。由於它們的元素都可以命名，一旦我們確定了一個命名系統，我們就可以始終在所有命名存在的集合中定義它們的補集。

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

一個問題在它的所有解的集合是不可判定時是不可判定的。

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

說一個問題不可判定，並不意味著我們無法解決它，也不意味著它有我們永遠找不到的解，它只意味著沒有明確定義的理論可以帶來該問題的所有解。我們定義的理論只能部分解決不可判定問題，永遠無法完全解決。對於不可判定問題，我們永遠無法完成，這是永恆的苦役。但我們仍然可以尋找和找到解決方案，沒有解決方案是先驗不可觸及的。只要我們足夠有創造力，就可以發明一個使我們能夠找到它的理論。

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

通用機器和理論

一臺可程式設計計算機是一臺通用機器，因為它能夠執行任何可能的程式。如果程式是一勞永逸地寫入只讀儲存器 (ROM)，則該計算機只是一臺特定機器。

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

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

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

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

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

這個悖論的解釋有點微妙。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 年獨立使用不同的方法證明。

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

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

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

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