数学证明/证明方法/直接证明

附录

构造性证明是最基本的证明类型。它是一种从假设开始的证明，一个人使用一系列逻辑步骤和公理列表，来得到一个结论。

定理的组成部分

一个定理是一个经过证明的陈述，它使用先前证明的陈述（如定理）或公理构建。一些定理非常复杂和复杂，因此我们将讨论它们的不同部分。

假设

假设是定理的“如果”语句。在某种程度上，它类似于公理，因为它被假定为真，以便证明一个定理。我们将考虑一个简单的例子。

定理 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 .$ 时，等式成立。