证明(MCS)

数学课本的行文思路

基本元素

公理: 公理化几何(欧式几何)
定义: 点, 线...
性质: 某些有趣的发现
定理: 有些不平凡(有用, 有价值的)发现
证明: 说说你的发现为什么是对的

回顾高中

命题的数学证明: _命题_的_数学证明_是从公理开始的, 经过一连串_逻辑推理_得到的.
命题?
逻辑推理?
公理?
命题: 命题是一个确定的要么真, 要么假的陈述
悖论不是命题
真假性随时间变化的也不是
验证命题的正确性
通常不容易!

命题的限制太强了, 有时候希望引入不确定性增加表达能力. (数$\to$函数, ...)

谓词(predicate): 真假性取决于一个或多个__变量__值的命题
不一定是真的, 由变量决定
$P(n)::=$ " $n$ 是一个完全平方数"
- $::=$定义做... 是$\iff$
- $P(4)$为真, $P(5)$为假
公理化方法
一些公理
公理的_推演_
- 定理: 重要的真命题
- 引理: 准备证明定理的命题
- 推论: 从定理出发, 只需要几步就可以得出的
ZFC: $2+2=4$要推理~20000步.
我们的推理规则(逻辑推理规则)
假言推理$\frac{P, \quad P \text { IMPLIES } Q}{Q}$
- 上面: 前提
- 下面: 结论
- 表示: 如果上面的成立的话, 那么下面的也是成立的
一连串: $\frac{P \text { IMPLIES } Q, Q \text { IMPLIES } R}{P \text { IMPLIES } R}$
逆否命题: $\frac{\operatorname{NOT}(P) \text { IMPLIES NOT }(Q)}{Q \text { IMPLIES } P}$

常见的证明方法

$\newcommand\imp{\text{ implies }}$对于$\to$

(1) 若$P$则$Q$写作$P \imp Q$, 要证明它:
写``假设$P$成立''
然后证明$P\to Q$.
(2) 证明逆否命题:
写``我们证明这个命题的逆否命题''
然后按照(1)继续

例子: 如果$r$是无理数, 那么$\sqrt r$也是无理数

证明. 我们证明逆反命题: 如果 $\sqrt{r}$ 是有理数, 那么 $r$ 也是有理数。假设 $\sqrt{r}$ 是有理数，则存在整数 $m, n$, 使： $$ \sqrt{r}=\frac{m}{n} $$

两边同时平方, 得: $$ r=\frac{m^2}{n2} $$

由于 $m^2$ 利 $n^2$ 是整数, 所以 $r$ 是有理数。

对于$\iff$

(3) 证明两个语句互相蕴含$P \iff Q$
证明$P \to Q$
证明$Q\to P$
(4) 构建if and only if(iff)链条
$P \iff P_1 \iff P_2 \iff \cdots \iff Q$

分类讨论(中译本的案例证明法不应该这样翻译)

保证你补充不漏地(不是一件简单的事情!)考虑了你的样本空间

定理. 任意给定两个人，他们要么见过面，要么没有见过。如果团体中任意两个人都见过面，则称这个团体为俱乐部组（club）。如果团体中任意两个人都没有见过面, 则称之为陌生人组 (stranger)。任何一个 6 人的团体中一定包含一个 3 人的俱乐部组或一个 3 人的陌生人组。

证明. 分类讨论。令 $x$ 表示 6 人团体。存在以下两种情形: 1. 除了 $x$ 以外的其他 5 人, 至少有 3 人都见过 $x$ 。 2. 其他 5 人中, 至少有 3 人都没见过 $x$ 。

那么,必须确保上述两种情形中至少有一个成立 ,很简单:将这 5 人分成两组,即见过 $x$ 的以及没有见过 $x$ 的, 那么, 这两组中必然有一组至少是 3 人。

假设至少有 3 人见过 $x$ 。
A) 这些人相互之间都没见过对方。那么, 这些人就是至少 3 人的陌生人组。这时定理成立。
B) 这些人之中有的见过对方。那么, 见过面的两个人, 再加上 $x$, 构成了一个 3 人的俱乐部组。所以，这时定理成立。
假设至少有 3 人都没见过 $x_{\text {。 }}$
A) 这些人相互之间都见过对方。那么, 他们便构成一个至少 3 人的俱乐部组。因此, 这时定理成立。
B) 这些人中有的没见过对方。那么, 没见过面的两个人, 再加上 $x$, 构成了一个至少 3 人的陌生人组。所以，这时定理成立。

反证法

方法: 采用反证法证明命题 $P$,
写“我们采用反证法证明。”
写 “假设 $P$ 是假的。”
推导得出某些已知的假事实 (即逻辑矛盾)。
写 “得出矛盾。因此, $P$ 一定是真的。”

良序原理(Well Ordering Principle)

非负整数集中的每个非空子集都有一个最小元素。

这不是废话?
- 空集没有最小元素 — 连元素都没有
- 对$\R$不成立 — 最小的正实数是什么?

良序证明

回顾: 证明$\sqrt 2$是无理数

凭什么对任何正整数$m$, $n$, 分数$m/n$可以化成最简的$m'/n'$?
反证法:
- 存在正整数 $m, n$, 满足 $m / n$ 不能被写成最简分数形式, 这些分数的分子构成的集合是$\mathcal C$
- 良序原理说: $\exists 最小的 m_0\in \mathcal C $
- 由 $C$ 的定义可知, 存在整数 $n_0>0$, 满足: 分数 $\frac{m_0}{n_0}$ 不能被写成最简形式。
- 也就是说, $m_0$ 和 $n_0$ 一定有公因子 $p>1$ , 因此$\frac{m_0 / p}{n_0 / p}=\frac{m_0}{n_0}$.
  - 只要$\frac{m_0 / p}{n_0 / p}$表达不成最简分数的形式, $m_0 / n_0$也能
  - 也就是: 分数 $\frac{m_0 / p}{n_0 / p}$ 也不能被写成最简形式
- 根据 $C$ 的定义可知, 分子部分 $m_0 / p$ 也在 $C$ 中。但 $m_0 / p<m_0$, 这与 $m_0$ 是 $C$ 中的最小元, 矛盾!

良序证明模板

使用良序原理, 证明 “对所有 $n \in \mathbb{N}, P(n)$ 为真”: - 定义 $C$ 是 $P$ 为真的反例集合, 即 $$ C::={n \in \mathbb{N} \mid \mathrm{NOT}(P(n)) \text { 为真 }} $$ (符号 $\{n \mid Q(n)\}$ 表示 “使 $Q(n)$ 为真的所有 $n$ 构成的集合”，参考4.1.4 节。) - 假设 $C$ 是非空集进行反证。 - 根据良序原理, 一定存在一个最小元素 $n \in C$ 。 - 得出矛盾一一通常是 $P(n)$ 为真, 或者 $C$ 中存在另一个比 $n$ 小的元素。这部分取决于具体的证明任务。 - 得出结论, $C$ 一定是空集, 即不存在反例。

例子1

对任意非负整数 $n$, $$ 1+2+3+\cdots+n=n(n+1) / 2 $$

反证法: 存在一些非负整数是反例。令反例的集合为:$C::=\left\{n \in \mathbb{N} \left\lvert\, 1+2+3+\cdots+n \neq \frac{n(n+1)}{2}\right.\right\}$
假设反例是存在的, 即 $C$ 是一个非负整数的非空集合。那么, 根据良序原理, $C$ 有一个最小元素, 用 $c$ 表示。即在这些非负整数之中, $c$ 是最小的反例。
由于 $c$ 是最小的反例, 所以当 $n=c$ 时上面的式子为假, 但是对所有 $n<c$ 的非负整数, 式 2.1 为真。所以 $c-1$ 是非负整数, 而 $c-1$ 比 $c$ 小, 因此对 $c-1$ 来说上式为真。即, $$ 1+2+3+\cdots+(c-1)=\frac{(c-1) c}{2} $$

两边同时加 $c$, 得 $$ 1+2+3+\cdots+(c-1)+c=\frac{(c-1) c}{2}+c=\frac{c^2-c+2 c}{2}=\frac{c(c+1)}{2} $$

由上式可知，式上式对 $c$ 成立。与假设矛盾，证毕。

例子2. 质因数分解

每一个大于1的整数都能被分解成质因数的乘积.(注记: 这里没有说可以被唯一分解)

采用良序证明。令 $C$ 表示所有大于 1 但不能被分解成质因数乘积的整数集合。假设 $C$ 不为空, 然后推导出矛盾。
如果 $C$ 不为空, 那么由良序性可知, 存在一个最小元素 $n \in C$ 。由于质数是 1 和它自己的乘积，而质数的乘积不属于 $C$ ，所以 $n$ 一定不是质数。
因此, $n$ 一定是两个整数 $a, b$ 的乘积, 而且 $1<a 、 b<n_{\circ}$ 由于 $a, b$ 都比 $C$ 中的最小元素要小, 可知 $a, b \notin C$ 。也就是说, $a$ 可以写成质数的乘积形式, $p_1 p_2 \cdots p_k$, 同理 $b$ 可以写成质数乘积形式 $q_1 q_2 \cdots q_l$ 。所以, $n=p_1 p_2 \cdots p_k q_1 q_2 \cdots q_l$, 即 $n$ 可以写成质数的乘积形式, 这与 $n \in C$ 矛盾。所以, 原假设 $C$ 不为空不成立。

良序集合

如果一个集合的任意非空子集都有一个最小元素,我们称这个集合是良序的

例子1

对任意非负整数 $n$ ，大于等于 $-n$ 的整数构成的集合是良序的。

证明. 令 $S$ 表示 $\geqslant-n$ 的整数构成的非空集合。将集合 $S$ 中的每一个元素都加上 $n$; 将这个新集合表示为 $S+n$, 从而 $S+n$ 是一个非负整数构成的非空集合。根据良序原理, 它存在一个最小元素 $m$ 。因此容易得出, $m-n$ 是集合 $S$ 中的最小元素。