证明(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{m2}{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\) 中的最小元素。