如何证明反证法是正确的？一个经典的反证法例子

欢迎大家来到IT世界,在知识的湖畔探索吧!

反证法是数学证明强有力的方式，为什么它是有效的，你怎么证明这个证明方法本身是正确的？

先大致说一下：考察证明方法的领域一般都在现代逻辑学中。逻辑学一般包括命题逻辑、词项逻辑和谓词逻辑。它们的层次是不同：命题逻辑是最大的层次，后两个都是它的细致化，词项逻辑好比分子层次，谓词逻辑是原子层次。震撼数学、逻辑学、哲学的哥德尔不完全性定理是谓词逻辑层次的。

一般来说我们是在命题逻辑的层次使用反证法的，因此我们也在这个层次进行证明。证明本身不复杂，但仍需要一些基础知识。

我们用p→q表示命题p能推出命题q；用
欢迎大家来到IT世界,在知识的湖畔探索吧!├ p表示命题集合存在一个对于命题p的证明，它意味着从里我们可以用逻辑推理公理【即推理法则】和中的某些【可以是全部】命题来证明p。

为了简洁起见，我们需要承认一个定理、一个规则和两个永真式。

一个定理叫“演绎定理”，它是命题逻辑的经典定理。它不是某个具体的数学定理，而是命题逻辑这个逻辑系统本身的定理，属于对于该系统性质的描述。具体表述为：

├ (p→q)当且仅当∪{p}├ q。∪{p}表示在命题集中添加一个新命题p。

一个规则叫“分离规则”：若q以及q→p，则p。

这个规则是我们认可的推理规则，它很好理解：如果我们有命题q→p并且承认它的前提q，那么自然能得到它的结论p。

永真式也叫重言式。举三个经典的永真式【¬p读作非p，表示命题p的否定】：

排中律：p∨¬p

同一律：p→p

双重否定律：¬¬p↔p

所谓永真，指的是在我们给出的逻辑命题法则之下，无论参与命题表述的命题p有几个、以什么命题形式存在【前提是要以命题逻辑允许的“合法形式”存在】，当每个命题取遍真假二值后，整个命题表述都是真的。以排中律为例：

情况一：p是真，¬p就是假，p∨¬p是真【对于p∨q，p、q只要有一个是真的那么p∨q就是真的】

情况二：p是假，¬p就是真，p∨¬p是真。

下面两个永真式是后面证明需要的，承认即可。

¬q→(q→p)【否定前件律】

(¬p→p)→p【否定肯定律】

能给出名字的，一般都不是普通的永真式，它们都是比较基本的永真式。

下面我们进入正题。

反证法的命题逻辑表述为：若∪{¬p}├ q和¬q，则├ p。

它其实就是在说：给定一个命题集，如果我们在中添加某个命题p的否定命题¬p，并且能从这个新的命题集∪{¬p}推出一对相互否定的命题q和¬q，那么我们能从原命题集中推出p。

证明：（每一步后面【】是解释这一步是怎么得到的）

由已知∪{¬p}├ q和¬q以及永真式“否定前件律”¬q→(q→p)，

由此有∪{¬p}├ q和q→p【对¬q和¬q→(q→p)利用分离规则】，

由此有∪{¬p}├ p【对q和q→p利用分离规则】

由此有├ (¬p→p)【演绎定理】

由此有├ p【否定肯定律】。证毕。

上面的证明就是我们站在“元数学”的角度给出数学证明本身一个逻辑证明！反证法是不可靠的，当且仅当你不承认现有的命题逻辑体系。直接证明、逆否命题证明、反证法都是数学认可的、可靠的证明方法。你可以认为反证法不那么“美丽”从而去寻求更“美丽”的直接证明，但是你无法怀疑它的正确性。

是无理数只能用反证法证明，费马大定理只能用反证法证明【到目前为止】。这两个定理就是很好的例子。当涉及集合论及“高阶无穷大”的大多数命题时，基本清一色是反证法。

最后，我们给出一个很深刻的定理：实数集是不可数的。我们不用康托尔的对角线法。只要你承认实数集具有连续性【也就是上确界存在性】。连续性即完备性，更严格地说是序完备性，它是实数集在我们约定的序性质下的结果，图片里的证明只考虑了实数集的这个序完备性。这个证明不依赖于实数的任意q进制展开。【学过数学分析的人会知道，这就是康托尔的闭区间套，它和连续性是等价的】。这个证明言简意赅，无懈可击。【证明里的自然数指的是正整数】

出自菲茨帕特里克之手的证明

这个证明的反证法要素为：

可以理解为我们定义的实数体系的公理及一些简单的推论。

命题p：非退化的区间是不可数的。

命题¬p：非退化的区间是可数的。

命题q：对于任意自然数n，上确界x*∈。

命题¬q：存在自然数，上确界x*∉。

把它们带入反证法公式——∪{¬p}├ q和¬q——我们的证明思路就清晰可见：

∪{非退化的区间是可数的}├

对于任意自然数n，上确界x*∈

和

存在自然数，上确界x*∉

于是根据已经证明的反证法，我们有├ 非退化的区间是不可数的。