數學證明/證明方法/直接證明

附錄

構造性證明是最基本的證明型別。它是一種從假設開始的證明，一個人使用一系列邏輯步驟和公理列表，來得到一個結論。

定理的組成部分

一個定理是一個經過證明的陳述，它使用先前證明的陳述（如定理）或公理構建。一些定理非常複雜和複雜，因此我們將討論它們的不同部分。

假設

假設是定理的“如果”語句。在某種程度上，它類似於公理，因為它被假定為真，以便證明一個定理。我們將考慮一個簡單的例子。

定理 2.1.1. 如果 A 和 B 是集合，使得 $A\subseteq B$ 並且 $B\subseteq A$ ，那麼 A=B.

在這個定理中，假設是“then”這個詞之前的任何內容。這是一個非常簡單的證明。我們需要證明對於每一個x， $x\in A\Leftrightarrow x\in B$ 。為了分析證明的目的，我們將定義 $P(x)=x\in A$ 並且 $Q(x)=x\in B$ 。證明“當且僅當”語句最常見的方法是分別證明必要性和充分性

所以我們首先證明 $P(x)\Rightarrow Q(x).$ 因此，我們假設P(x)為真。也就是說， $x\in A.$ 由於我們根據假設假設了 $A\subseteq B,$ ，我們知道 $x\in B$ ，這意味著Q(x)為真。

現在我們證明 $Q(x)\Rightarrow P(x)$ ，所以我們假設Q(x)為真。這意味著 $x\in B$ 。由於我們知道 $B\subseteq A,$ ，我們知道 $x\in A,$ 所以P(x)為真。

透過這兩個結論，我們看到 $P(x)\Leftrightarrow Q(x).$

現在，根據公理 3，A=B，因為 $x\in A\Leftrightarrow x\in B.$ 這就完成了證明。這是一個非常簡單的證明，但它的目的是說明如何使用假設或一組假設來得出所需的結論。這裡的方法是證明兩個集合相等最常見的方法。你需要證明每個集合都是另一個集合的子集。

結論

定理中“則”字後的部分稱為結論。定理的證明僅僅是假設和結論之間的邏輯聯絡。一旦你看到並證明了一些定理，結論幾乎是可預測的。例如，你會從以下兩個陳述中自然得出什麼結論？

所有美國人都是人。
所有的人都住在地球上。

這兩個陳述是假設。為了將此表述為一個定理，我們將寫成“如果所有美國人都是人，並且所有的人都住在地球上，那麼所有美國人都住在地球上”。這種說法大多數人認為是完全顯而易見的，不需要證明。然而，為了展示如何在數學中應用這個概念，我們將抽象這個定理並證明它。

定理 2.1.2. 如果 $A\subset B$ 且 $B\subset C$ ，則 $A\subset C$ 。

為了瞭解這與我們的問題有什麼關係，設A為所有美國人的集合，B為所有人的集合，C為所有居住在地球上的事物的集合。

為了證明 $A\subset C$ ，我們需要證明 $\forall x\in A,x\in C.$ 因此，我們假設 $x\in A.$ 根據假設， $A\subset B,$ 所以 $x\in B.$ 同樣根據假設， $B\subset C$ ，所以 $x\in C.$ 由於這對任何任意的 $x\in A,$ 都成立，我們已經證明了 $A\subset C.$

定義

雖然定義通常不是定理的一部分，但它們通常在定理之前立即引入，以幫助定義你使用的符號或幫助證明它。

定義 2.1.3. 如果一個集合A只有有限個元素，那麼A的階，記作|A|，是A中元素的個數。

這個定義賦予了以下定理意義。

定理 2.1.4. 如果 A 和 B 是有限集合，使得 A = B，那麼 |A|=|B|。

這裡我們利用了A是一個有限集的事實。令n為使得|A| = n的整數。然後對A的元素進行索引，使得 $A=\{x_{1},x_{2},\ldots ,x_{n}\}.$ 現在 $\forall i=1,2,\ldots ,n$ ，我們有 $x_{i}\in B$ 。因此我們看到B至少有n個元素，也就是說 $|B|\geq n.$ 同時，B的每個元素都屬於A（根據假設），因此B中的元素數量不會超過A中的元素數量，所以 $|B|\leq n$ ，因此|B| = n = |A|，這完成了證明。

給定條件

有時，定理的第一部分列出了證明定理所需的條件。因此，這個列表在定理中被描述為給定的條件。這有助於讀者準確理解定理陳述中的假設和結論是什麼。例如，定理 2.1.4 可以改寫，以便它列出事先需要的條件。

定理 2.1.4. 給定有限集 A 和 B，如果 A = B，則 |A|=|B|。

此陳述清楚地突出了假設和結論是什麼，在本例中。

定理分類

數學家在陳述數學結果時喜歡使用不同的術語。定理可能是最常見且最廣為人知的，尤其是對於非數學家來說。然而，數學中還有一些其他相關的術語。它們都是定理，但有更具體的用法。

引理

一個引理是一個“小定理”。當一個結果不太深刻，更瑣碎，或更無聊時，它可以被稱為一個引理。引理也用於使定理的證明更簡潔。也就是說，如果證明的一部分可以單獨提取出來證明，那麼它被稱為一個引理，而定理的證明則會說類似“如引理中證明的那樣”的話。

例如，以下引理將有助於使定理 2.1.4 的證明更簡潔。

引理 2.1.5. 如果 A 和 B 是有限集且 $A\subset B$ 則 $|A|\leq |B|$ 。

正如你可能猜到的，這是使用符號 $\subset$ 的一個動機，因為它在外觀上類似於 <。

令 n = |A|。然後對A的元素進行編號，使得 $A=\{x_{1},x_{2},\ldots ,x_{n}\}.$ 然後對於從 1 到 n 的每個 i，我們看到 $x_{i}\in B$ ，這意味著 B 至少有 n 個不同的元素，或者 $|B|\geq n=|A|,$ 這就是我們要證明的。

現在如果我們對定理 2.1.4 使用這個引理兩次，我們將得到一個非常簡短的證明。由於 $A\subset B$ 我們知道 $|A|\leq |B|.$ 此外，由於 $B\subset A$ ，我們看到 $|B|\leq |A|.$ 現在我們使用一個關於數字的事實，即如果 $x\leq y$ 且 $y\leq x$ ，那麼必然有 x = y。

推論

一個推論與引理類似，它通常很小，不像定理那樣重要。但是，推論通常是一個緊隨定理而來的結果。推論往往利用一些眾所周知或已確立的定理和主要定理來證明。這就是為什麼推論經常出現在一個大定理後面。

例如，假設我們證明了“所有人都是豬”這個定理。那麼一個推論將是“有頭的人是豬”，這顯然來自第一個結果，因為“人有頭”是眾所周知的事實（一個沒有頭的人會很奇怪，不是嗎？）。另一個稍微有趣一點的推論是“人死後可以賣成培根”，因為“培根來自豬”是眾所周知的事實。

所以我們看到，推論是從前面的定理中得出的，只需要很少的論據來支援它。請注意，你宣稱的推論可能在其他人看來不是推論，因為推論是主觀的。然而，將推論視為依賴於“常識”或“對讀者來說顯而易見”的直接定理結果，這是在確定將什麼歸類為推論時的正確思路。

練習

證明以下集合相等。用真值表或韋恩圖驗證。你可以假設 A、B 和 C 是非空集合。還假設 U 是全集。
1. $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
2. $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
3. $A^{c}-B=(A\cup B)^{c}$
4. $A-B^{c}=A\cap B$
5. $(A-B)\cup (A\cap C)=A-(B-C)$
證明如果 A 和 B 是有限集，那麼 $|A\cup B|\leq |A|+|B|$ ，並且當 $A\cap B=\varnothing .$ 時，等式成立。