如何证明根号2是无理数（我就是教皇）

这是芝加哥大学数学系Hirschfeldt一篇文章的引言部分，原文的全文地址是http://math.uchicago.edu/~drh/Papers/Papers/rm.pdf。该文全文是非常专业学术文章，但这篇文章的引言写的非常有趣，实际上可以作为可计算理论和反推数学的一个科普级别的介绍。

原文作者：Hirschfeldt，芝加哥大学数学系。

译文作者：Math001，哆嗒数学网网主。

文章校对：小米，就读于纽约大学柯朗数学研究所。

微信、手机QQ搜索关注 DuoDaaMath 每获得更多数学趣文

每个数学家都知道如果 2 + 2 = 5 ， 那么罗素就是教皇。据说罗素曾经在一个讲座上用下面的方式证明上述结论：如果2 + 2 = 5，那么，在等式两边同时减去3，得到 1 = 2。 因为教皇和罗素是两个人，于是他们是同一个人。当然，按经典逻辑学的观点，我们根本不需要这样的一个证明，因为一个永假式的前提可以推出任何一个命题。 从逆否命题的角度看，如果结论永远都是真命题，那么任何前提假设都能推导出它。但是，假如我们真的认真地对待一个需要证明的命题，比如说，如果四色定理成立那么质数就有无限多个，那么你们之中谁又能回答如下问题：证明上述命题的时候，在哪些地方会“真正用到”四色定理？这类问题看起来又难又没意义，但是数学老师总会把类似的基础练习布置给你。“用波尔查诺-维尔斯特拉斯定理证明[0,1]闭区间上的连续实函数是一致连续的。”就是这样一道数学分析中的经典习题。另一个类似的问题是“哥德尔第一不完备定理的蔡廷信息理论版本是否能证明出哥德尔第二不完备定理”，这则是Kritchman和Raz最近一篇有趣的论文。

还有一类常见的问题，要求你不能使用一些特定的数学方法来证明一些数学命题，比如，不使用算数基本定理证明根号2是无理数，或者，用初等方法证明质数定理。我们也听到数学老师以及同学会谈及类似这样的事情：“定理A和定理B是等价的。”、“定理D并不能直接推导出定理C”或者“用引理E证明定理F非常方便，但定理E并不是必要的。”。这些东西往往能成为理解某个数学领域的关键。

还有一些东西能帮助我们把不同领域的数学联系起来。比如我们来思考一下下面的一系列定理：[0,1]闭区间上的连续函数上确界存在定理、常微分方程局部解的存在定理、哥德尔完备定理、可数交换环的素理想存在定理、布劳威尔不动点定理。这些不同的定理证明过程可能是相似的，本质核心都是围绕紧性在讨论问题，同时，也可以把他们看成基本组合思想在不同数学分支中的反映，都用一个叫做弱柯尼希引理的东西来解释——这个我们在后面的部分会详细讨论。我们会在4.4章节把这个问题严格化。

本文里，我们将讨论两种紧密联系的数学方法:可计算数学与反推数学。通过它们我们可以在各个可证明的命题之间，给出关于“蕴含”和“不蕴含”概念的严格精确的数学意义。 我们会将目光集中在一些组合原理上，它们易于陈述和理解，但从这些观点来看却展示出错综复杂而又美丽迷人的一面。这篇文章并非关于这个领域的一些研究成果的综述，而是一系列该领域思想和方法的介绍。文章更多的会依照我自己的兴趣（尤其是可计算理论和反推数学的组合分析以及拉姆齐二染色定理相关的模型论原理）来写，但是我还是希望尽可能的吸引和刺激一些新人进入这个领域；特别地，虽然反推数学的逆推过程和数学基础密切联系，但我并不想对这个方面的事情说太多。

虽然我会在2.1章节简要回顾一些可计算理论的基本结论，但我还是假设读者已经知道一些数理逻辑的背景，尤其是可计算理论的基础知识。否则，这篇文章需要写的东西会包含得太多。文章中间会散布一些习题，解答这些习题也是阅读这篇文章不可或缺的工作。文章中还会提到一些没有解决的公开问题，我们鼓励读者去挑战他们。没人知道一个睿智的思想什么时候会闪现并攻克一个长期没有解决的问题。