數學證明與數學/邏輯/公理和等式原理

我們現在已經涵蓋了大部分被稱為一階邏輯的內容，或者至少我們已經涵蓋了本書其餘部分需要的內容。還存在二階和更高階邏輯，我們只簡要介紹一下。二階邏輯涉及以一階謂詞為引數的謂詞，而不是論域的物體。例如，關係 $P(x,y)$ 如果

對所有 $x$，$P(x,x).$

謂詞

$P$ 是一個自反關係

然後是一個二階謂詞。在這個方向上必須小心，以避免謂詞被應用於自身，否則可能會出現前面討論的“說謊者悖論”之類的自指語句，導致矛盾，整個系統可能會崩潰。我們將在後面看到更多關於這一點的資訊。

雖然我們有時會在二階謂詞的形式下進行定義，但這些應該被認為是語言上的捷徑，可以用它們的定義來替換。

公理系統

在沒有引入公理的情況下，我們已經儘可能地走了，但我們需要它們來前進，所以現在是詳細談談它們的時候了。

到目前為止，僅使用推理規則，我們只證明了重言式，換句話說，這些語句並沒有真正表達任何有意義的內容。它們可以作為練習，但在表達關於宇宙的任何有趣內容方面，它們並不是有用的。早在歐幾里得之前就意識到，為了避免迴圈論證，必須做出一些初始假設，正如你可能稱之為邏輯上的自舉。

這個過程是這樣的

1. 列出關於論域的假設。這些假設被稱為公理。
2. 使用邏輯來證明新的、有希望的有趣陳述。這些陳述被稱為定理。

這個公理列表有時被稱為公理系統。公理從哪裡來是一個有趣的問題。它們可能來自哲學、經驗，或者透過抽象其他系統的屬性而來。

公理系統的有用性質

為了有用，公理最好具有以下性質

• 一致性（存在一些不是定理的陳述）：這是必須具備的特性，否則該系統無法區分定理和非定理，因此毫無用處。另一種說法是語句 $False$ 不是一個定理，換句話說，不可能從公理中推匯出矛盾。

• 完備性（每個命題都有證明或反證）：這是必備的功能，因為能夠判斷給定命題的真假是可取的。換句話說，不應該存在無法解決的猜想，即既不可能證明也不可能找到反例。請注意，這與說命題 $P$ 是定理或不是定理不同，因為我們可能知道 $P$ 是真還是假，而不知道它是哪個。 （不過，這有點爭議；請參閱非標準邏輯部分。）另請注意，有很多猜想，其中一些很著名，我們目前還沒有找到 $P$ 的證明或非 $P$ 的證明。但這僅僅意味著尚未找到證明，並不意味著證明是不可能的。

• 獨立性（公理之間不能互相證明）：這既出於審美原因，也出於實際原因。從審美角度來看，如果系統沒有多餘的、不需要的公理，系統會更乾淨、更優雅。在實用方面，假設您有一個系統，您試圖用公理對其進行建模。您首先需要做的是驗證公理是否確實在您的系統中成立。不必要的公理增加了此工作量，而沒有額外的好處。

旁註：為了證明公理獨立於其他公理，人們需要找到一個所有公理都成立但給定公理不成立的數學系統。這表明給定公理不能從其他公理中證明出來，因為如果能證明出來，它就會在給定系統中成立。

• 無爭議性（關於應包含哪些公理，存在普遍共識）：如果這一點不成立，則理論的結論可能會受到爭議。

• 效力（公理應該易於描述，但能推匯出大量豐富的數學結果）：這最終決定了理論的實用性。有時，同一組公理可以用來對不同的系統進行建模，而您從理論中學習到的知識可以應用於兩者。

給定一個公理系統，能夠以某種方式證明它是一致的和完備的，這會令人欣慰。不幸的是，這在 1930 年代被庫爾特·哥德爾證明是不可能的，至少對於任何可用於數學的系統而言都是如此。

使用公理

我們現在可以引入另一個推理規則

如果 $P$ 是一個公理，那麼推匯出 $P.$

換句話說，您可以在證明中使用任何公理，無需其他理由，只需它是一個公理即可。

等式公理

我們的第一個公理與等式有關。雖然從技術上講，這仍然屬於邏輯的範疇，但我們現在已經足夠接近，可以從地平線上看到數學了。

請注意，我們永遠不會真正定義短語 $x$ 等於 $y$，因為這樣做不可能不迴圈。我們可以列出一些公理，這些公理告訴我們相等的物件如何表現，從某種意義上說，這等同於定義。我們還可以對 $x$ 等於 $y$ 的含義給出非正式的描述，這旨在作為直觀的指南，並有助於使公理看起來合理，但這沒有邏輯上的意義，不能在證明中使用。我們假設您已經對 $x$ 等於 $y$ 的含義有直觀的瞭解，因此在這種情況下我們將跳過這一部分。

公理 E0： 在論域的宇宙中定義了一個關係 “=”，寫作 $x=y$，讀作 $x$ 等於 $y$。

關係通常使用中綴表示法 $(xRy)$ 來表示，而不是字首表示法 $(R(x,y))$。這個公理實際上只是保留了 “=” 符號，賦予它一個特殊的含義。

公理 E1（同一性）： 對於所有 $x$，$x=x$。

鑑於對等式的直觀概念，這似乎是不言而喻的。安·蘭德的粉絲可能會認出這是《阿特拉斯聳聳肩》中的 “A 是 A” 這句話。這也被稱為自反性。

公理 E2（替換）： 如果 $P(x),$ 是一個謂詞，那麼對於所有 $x$ 和 $y$，$x=y$ 並且 $P(x)$ 意味著 $P(y)$。

這實際上不是一個單獨的公理，而是一個所謂的公理模式。（這裡的 “模式” 這個詞是一個非常專業的術語，基本上是指食譜或藍圖；只要每次看到它就用 “食譜” 來代替 “模式”，你就不會錯得太遠。） 對於每個謂詞，你都會得到一個新的公理，因此，這是一種獲得任意數量公理的緊湊方式。 我們在這裡開始放鬆邏輯形式主義，並在措辭中使用它。 它的意思很清楚，因此沒有必要嚴格遵守前幾頁中使用的措辭和括號。

等式的性質

我們現在可以從公理中證明等式的兩個最重要的性質。

定理 E3（對稱性）： 對於所有 $x$ 和 $y$，$x=y$ 意味著 $y=x$。

證明： 選擇 $a$ 和 $b$，並假設 $a=b$。 令 $P(z)$ 為謂詞 $z=a$。 那麼根據公理 E1，$P(a)$ 成立。 同時，$a=b$，所以 $P(a)$ 意味著 $P(b)$。 所以 $P(b)$，這等同於說 $b=a$。 我們有 $a=b$ 意味著 $b=a$，對於任意 $a$ 和 $b$，因此對於所有 $x$ 和 $y$，$x=y$ 意味著 $y=x$。

請注意，我們將在文字中逐漸淘汰表格式證明，將其作為讀者練習來完成所有細節。

定理 E4 (傳遞性)： 對於所有 $x$，$y$ 和 $z$，$x=y$ 和 $y=z$ 意味著 $x=z$。

證明： 這個問題留作練習，以下是一點提示。選擇 $a$，$b$ 和 $c$，並假設 $a=b$ 以及 $b=c.Let<math>P(w)$ 是謂詞 $a=w$。（此時，我們留給讀者完成證明的剩餘部分。）

定義物件

除了公理之外，數學家還將定義作為基本原則。我們可以像一直以來那樣，使用邏輯聯結詞和之前定義的語句和謂詞來定義新的語句和謂詞。但我們還想能夠根據一個物件的屬性來定義它。那麼，要使這樣的定義有意義，需要哪些條件？讓我們考慮一個謂詞 $P(x)$，並試著找出使以下語句成為有效定義所需的條件。

定義 $X$ 為使 $P(X)$ 為真的物件。

成為一個有意義的定義。

首先，我們需要這樣的 $X$ 存在。因此，我們需要以下語句

(存在性) 對於某個 $x$，$P(x)$

為真。要求這一點是合理的，否則我們將同時擁有 $P(X)$ 和 對於所有 $x$，非 $P(x)$，這將導致矛盾。

不過，我們還需要另一個要求。假設一個人選擇了一個 $X$ 作為使 $P(X)$ 為真的 “唯一” 物件，而另一個人選擇了一個 $Y$ 作為使 $P(Y)$ 為真的 “唯一” 物件。現在假設 $X$ 具有某種 $Y$ 不具備的屬性，換句話說，存在一個謂詞 $Q(x)$，使得 $Q(X)$ 為真，而 $Q(Y)$ 為假。這再次導致矛盾，因為 $X$ 和 $Y$ 被認為是同一個物件，但 $Q$ 對其中一個為真，而對另一個為假。因此，我們需要確保如果 $P(X)$ 和 $P(Y)$ 為真，那麼不存在一個謂詞 $Q(x)$，使得 $Q(X)$ 為真，而 $Q(Y)$ 為假。但公理 E2 在 $X=Y$ 時就給出了這個條件。因此，我們添加了另一個條件，即該語句

(唯一性) 對於所有 $x$ 和 $y$，$P(x)$ 和 $P(y)$ 意味著 $x=y$

為真。

這兩個條件，存在性和唯一性，似乎就足夠了。我們可以說這個表示式

滿足 $P(X)$ 的 $X$

是定義明確的，如果 $P(x)$ 具有存在性和唯一性屬性。我們可以宣佈 $X$，或者任何我們想要使用的其他符號，作為我們論域中物件的名稱，並取

$P(X)$

作為公理。如果 $P(x)$ 不具有存在性和唯一性屬性，那麼我們當然可以寫下這個表示式，但它沒有任何意義，換句話說，它是未定義的。我們將在後面介紹更簡潔的符號，但首先我們將推廣這個想法。

函式關係

不用謂詞，我們從關係 $P(x,y)$ 開始。這一次我們想知道是否

定義 $Y(x)$ 是滿足 $P(x,y)$ 為真的物件。

是有意義的。這開始接近函式的概念，但我們將“函式”這個詞保留到下一章中涉及集合的更復雜結構中。我們已經使用過“函式”這個詞，但只是作為直覺的引導，而不是定義。

遵循上一節中的類似推理，我們說

滿足 $P(x,y)$ 的 $Y(x)$

是定義明確的，如果

對於某些 $y$，$P(x,y)$

並且

對於所有 $x$，$y$ 和 $z$，$P(x,y)$ 和 $P(x,z)$ 意味著 $y=z.$

我們說一個關係 $P(x,y)$ 是一個函式關係，如果它滿足第二個條件。

類似地，對於一個三變數的關係 $P(x,y,z)$，我們說

對於那些 $Z(x,y)$，使得 $P(x,y,z)$

是定義明確的，如果

對於某個 $z$，$P(x,y,z)$

並且

對於所有 $x$，$y$，$z$ 和 $w$，$P(x,y,z)$ 和 $P(x,y,w)$ 意味著 $z=w.$

我們可以將此擴充套件到任意多個變數。關係 $P(x,y,z)$ 是一個函式關係，如果它像之前一樣滿足第二個條件。

如果表示式 "The $Z(u,v,\dots )$ for which $P(u,v,\dots ,z)$" 是定義良好的，那麼我們將 $P(u,v,\dots )$ 寫作該 $Z$ 的標準符號。我們在這裡過載了括號符號，但這不應該是一個問題，因為您可以透過計數引數來判斷其含義。

回到謂詞，我們將 $P()$ 解釋為 $X$，對於它 $P(X)$。

概括一下，如果 $P(u,v,\dots ,z)$ 是至少一個變數的關係，我們將 $P(u,v,\dots )$ 解釋為 $z$ 的值，對於它 $P(u,v,\dots ,z)$，前提是

對於某些 $z$，$P(u,v,\dots ,z)$

並且

對於所有 $u$，$v$，... $z$ 和 $w$，$P(u,v,\dots ,z)$ 和 $P(u,v,\dots ,w)$ 意味著 $z=w$.

如果兩個條件不滿足，則表示式 $P(u,v,\dots )$ 未定義，不代表任何有意義的東西。如果 $P(u,v,\dots )$ 已定義，則

$P(u,v,\dots ,P(u,v,\dots ))$

是一個公理。

作為一個練習，將此應用於相等關係。也就是說，如果 $E(x,y)$ 被定義為 $x=y$，那麼證明對於所有的 $x$，$E(x)$ 已定義，並且 $E(x)=x$.

其他方法（可選）

我們在這裡使用的方法並不是唯一可用的方法。另一種方法是簡單地宣告一個函式接受 0 個或多個物件作為引數並返回另一個物件，而不是像關係那樣返回一個真值。因此，0 個變數的函式與常數相同。在這種情況下，您需要一個額外的公理用於 '='

如果 $F(x)$ 是任何函式，那麼對於所有的 $x$ 和 $y$，$x=y$ 並且 $F(x)$ 已定義意味著 $F(y)$ 已定義並且 $F(x)=F(y)$.

注意，我們不想假設 $F(x)$ 對於所有的 $x$ 都具有一個值，因為這會過分限制概念的有用性。

另一種方法是 Bourbaki 採用的方法，它遵循 Hilbert 的 epsilon 演算，不過使用了不同的符號。在這種情況下，短語

一些 $X$，對於它 $P(X)$

“總是”定義了一個$X$。為了避免不同的人可能選擇不同值的問題，假設值$X$ 由謂詞$P(x)$ 以某種方式確定，因此每個人選擇一個$X$ 都將得到相同的答案。這需要以下額外的公理

(對於所有$x$，$P(x)$ 當且僅當$Q(x)$) 意味著 (存在一個$X$ 使得$P(X)$)=(存在一個$X$ 使得$Q(X)$)

選擇滿足$P(X)$ 的每個人都得到相同的$X$ 似乎要求很高。當$P(X)$ 具有存在性和唯一性屬性時，短語“存在一個$X$ 使得$P(X)$” 和 “滿足$P(X)$ 的$X$” 等同於同一個東西。

我們選擇這裡使用的這種方法，因為在後面的章節中，我們會遇到一些情況，很容易被錯誤的定義所欺騙。換句話說，你可能認為你已經定義了一個函式，但實際上並沒有定義任何東西，因為邏輯要求沒有滿足。我們使用的方法明確地列出了這些要求，這樣一旦這些要求被檢查，我們就可以放心地繼續前進，因為沒有隱藏的錯誤。