苏联哲学百科
无 穷 归 纳
全称命题(或全称判断)是作为包括一切个别事例的无穷个前提的结论而获得的。 无穷归纳的例子： 1+0=0+1；1+1=1+1；1+2=2+1；1+3=3+1；1+4=4+1；1+5=5+1； l+6=6+1；…… 因此，等式1+x=x+1适用于任何一个自然数(即非负整数)x。 这个例子是以下更为一般的推理模式的特殊情况： 0具有性质S， 1具有性质S， 2具有性质S， 3具有性质S， ……… ----------------------------------- 因此，所有自然数具有性质S。 这种推理可以表示为以下形式： S(0)，S(1)，S(2)，…，S(n)，…… ------------------------------------------ S(x) 这里，横线以上列出了前提，横线以下是结论。结论的全称住就表现在其中含有用字母表示的变量x，它可以取任何一个自然数为值。 但是由于要实际列出无穷多个前提是不可能的，因此无穷归纳的纯粹形式在实践中是不会遇到的(甚至上述无穷归纳的例子和模式的陈述也不能完全精确地表达问题的实质，因为其中并没有真正列举所有前提，而是以省略号代替，列举所有前提实际上是不可能做到的)。由于这一缘故，在科学思维的实践中，无穷归纳通常或者被不完全归纳所代替，这时作为前提列举的 并不是全称性结论所需要的全部个别事例；或者被所谓完全数学归纳所代替，这是可以用以下形式来表示的一种归纳： s(0)，S(x)->S(x+1) ------------------------- S(x) [其中S(x)->S(x+1)表示“如果x具有性质s，则x+1也具有性质S”]。 但是无穷归纳在一系列理论结构中，特别是在数理逻辑和数学基础的领域内，起着重要作用。考察无穷归纳之所以必要，是因为别的归纳形式无法完全代替它：完全数学归纳比起无穷归纳来，其作用要小得多。因为它只有在前提中已经存在某个全称命题[S(x)->s(x+1)]的情况下才能适用；不完全归纳则是一种不精确的推理工具，而它的高级形式——自然科学归纳——无法利用数学方法加以精确研究，因为它和通常的不完全归纳法的区别，与其说具有形式的性质，毋宁说具有辩证的性质。 任何数学领域的论证都必须引入无穷归纳，这是因为，即使在算术那样的初等数学的论证中也存在着严重困难。这种困难和K．哥德尔1931年发现的下述现象有关：将算术形式化(这就是使算术的逻辑基础精确化，以致有可能成为数学研究的对象)后而得到的任何一种形式演算终究是不完备的和不可补足的：这种形式演算包含有限条公理和推理规则(推理模式)，并且其中每一条规则都是有限的(意即只有有限个前提，可以用算法在每一个别场合根据前提和结论来检验推理是否正确)。哥德尔证明，在任何这样的演算中都可以找到它所不能证明也不能反驳的公式。这一结果加深了从前只有直觉主义者(参见直觉主义)曾经表示过的怀疑——是否任何算术命题都非真即假(参见排中律)。此外还发现，可以构造出新而又新的算术真命题，而它们在已经设计出来的演算中却无法证明(哥德尔公式的例子正是这样)，因而这些演算的可靠性就愈来愈缺少根据了。 摆脱这些困难的尝试之一，就是将无穷归纳原理应用于数学的论证。但是这种应用并非真的按照这一原理去推理(这是根本不可能的)，而是具有比较抽象的性质，例如，将这一原理以模式(*)的形式，作为不同于通常的推理规则的非有限推理规则补充到形式演算中。同时研究如下问题：这一补充提供了什么，可证公式类因此而有什么变化。 这种方法最先是卡尔纳普1934年在研究形式“语言”(包括算术语言在内)的性质时提出的，他证明，以模式(*)补充通常的形式算术之后，算术的所有初级命题(只包含以自然数集为值域的变量而不包含其他变量的命题)就成为或者可证或者可反驳的。由于这一缘故，通常就把模式(*)算作“卡尔纳普规则”，正是这一模式(*)，通常也称为“无穷归纳规则”。不过并非所有的无穷归纳都可以归结为这一模式。可以归结为这一模式(*)的，仅仅是前提可以用自然数枚举的那种无穷归纳。后者并非在一切情况下都是可能的，因为存在着无穷集的各种不同的势(见集合论)。 在演算中补充了模式(*)之后，演算中证明的性质就发生本质的改变。证明包含的命题序列，一般说来，从有限变成无限，用数学语言更确切地说，是超限，也就是说，是按某种无穷序数类型编序的。在这种情况下，研究可构造序数将起重要作用。所谓可构造序数就是这样的序数a(有限或超限)，其中与数a对应的次序关系在某种意义上是按算法给出的。 在研究某些问题时，只需要使用有限制的无穷归纳，即证明的“长度”不超过某个固定的可构造序数的无穷归纳。例如在论证形式算术中排中律的不矛盾性时就是这样(按照G·耿称、K.胥特等人的方法)。但是，正如B.罗瑟1937年的研究以及由P.C.诺维柯夫的学生B.Y.法列维支1955年进一步的发展所证明的那样，当这个演算的命题中包含以实数集为值域的变量，或以自然数性质集为值域的变量(谓词变量)时，则任何有限制的无穷归纳都不足以克服类似于形式算术在不应用无穷归纳时所具有的那种不完备现象。 但是在无限制无穷归纳的情况下，就是说，在将模式(*)应用于任意长的超限证明的情况下，带有谓词变量(但谓词变量不用量词)的形式算术就在下述意义上成为完备的：其中任何真命题(在变量的一切值下真)都是可证的。而按照A.B.库兹涅佐夫的证明(1956年)，这一结果在只应用“构造性”的无穷归纳的情况下也同样可以成立。所谓构造性无穷归纳，是这样一种无穷归纳，对于它的每一个证明，都有某个可构造对象(参见算法)与之对应，例如一个与该证明有关的号码；而模式(*)只有在算法可以按照数竹给出第n个前提[即S(n)]的证明号码时才能应用。同时，证明号码的建立，应便于根据号码用算法恢复证明的整个过程，特别是便于用超限命题序列形式来记录该证明，这一序列在其写下的过程中，每一步都是有限的，并且随后要写的每一项，相对于已经写下的各项处于怎样的位置都是由算法指示的。 无穷归纳(包括没有限制的在内)在非可计算谓词与非可计算函数的分类问题上也可以应用。但是应用没有限制的无穷归纳，即使是可构造的无穷归纳，也有某些困难，这一方面是由于构造性无穷归纳还缺乏充分的可构造特征，而这又与可构造序数的整体概念(即不是涉及其中某些可构造序数，而是一下子涉及所有可构造序数的概念)的不可构造性紧密相关；另一方面也由于我们对以下问题还缺乏充分的研究：基于怎样的抽象和原则来处理这些概念才是适当的。 参考书目： S.C.克林 < 元数学导论 > 译自英文，莫斯科1957 年版； A.B.库兹涅佐夫 < 带有构造性无穷归纳规则的算术公理系统的完备性 > 载 < 数学科学进展> 莫斯科 1957 年版第 12卷第 4(76) 分册； R.卡尔纳普 < 语言的逻辑句法 > 维也纳1934 年德文版；英译本纽约- 伦敦 1937 年 [增订版 ] 。 作者：A.库兹涅佐夫,莫斯科 译者：吴祖增