构造性证明
构造性证明(英語:Constructive proof)是数学证明方法的一种,通过直接或间接构造出具有命题所要求的性质的实例来完成证明。与构造性证明相对的概念是非构造性证明[註 1]。后者只证明满足命题要求的物体存在,而不提供具体的实例或构造这样的实例的方法。
构造性证明也可以指数学构成主义中被认可的一种更强的证明。数学构成主义是数学哲学的一支,它认为要证明一个对象的存在,必须将其构造出来。因此,他们拒绝使用如排中律,无穷公理和选择公理这样的公理。同时也有一些用语和以往不同,例如或的语意会比基础数学中的更强。
历史
直到十九世纪结束,所有的数学证明使用的还是构造性证明。第一个使用非构造性方法的是格奥尔格·康托尔的无限集合理论,以及对实数的形式化定义.
例子
非构造性证明
考虑对质数有无穷个的证明。欧几里得的证明本身是构造性的,不过有一种常用的方法来简化欧几里得的证明,它先假设质数的数量是有限的,那么必然会有一个最大的质数,将它记为n。然后考虑n! + 1(n阶乘加1),这个数字要么本身是质数,要么是合数且存在一个大于n的质因子,因为小于等于n的质数除它都余1。通过得出和命题的假设矛盾的结论,我们并不需要指出一个确定的质数,就可以证明存在一个大于n的质数。
再考虑证明这个命题:“存在无理数 和 ,使 是有理数”。这个证明可以被构造性地证明,也可以被非构造性地证明,我们将对比两种证明方式。
以下证明是1953年由Dov Jarden提出的,最晚从1970年开始被用作非构造性证明的经典例子:[1][2]
CURIOSA
339. 对一个无理数的无理数次方可以是有理数的简单证明
要么是有理数,要么是无理数。如果它是有理数,那么我们的命题得证。如果它是无理数, ,我们的命题得证。
Dov Jarden Jerusalem
更具体地:
- 我们在先前已经知道 是无理数,2是有理数。考虑数字 ,它要么是有理数,要么是无理数。
- 如果 是有理数,那么原命题成立,此时 和 都是 。
- 如果 是无理数,那么原命题也成立,此时 为 而 为 ,由于:
- 。
这个证明是非构造性的,因为它依赖了这样的陈述:“q要么是有理数,要么是无理数”,这是排中律的一个应用,而构造性证明里排中律是无效的。这个非构造性证明并没有构造一个实际的a和b,它只是考察了由排中律给出的两种可能性。我们并不知道这两种可能性哪个是真实的, 究竟是不是无理数。
实际上根据格尔丰德-施奈德定理,我们可以得知 是一个无理数,但是它和这个非构造性证明的正确性无关。
构造性证明
对上面的例子,构造性证明会给出一个实际的例子,如:
已知2的算术平方根是无理数,而3是有理数。 同样是无理数,因为如果他可以写作 ,那么根据对数运算法则,9n会等于2m,然而前者是奇数,后者是偶数(奇数的整数次方还是奇数,偶数的整数次方还是偶数)。
注释
参见
参考资料
- ^ J. Roger Hindley, "The Root-2 Proof as an Example of Non-constructivity", unpublished paper, September 2014, full text 互联网档案馆的存檔,存档日期2014-10-23.
- ^ Dov Jarden, "A simple proof that a power of an irrational number to an irrational exponent may be rational", Curiosa No. 339 in Scripta Mathematica 19:229 (1953)