动机
离散数学中的证明必须解释:为什么由有限多个步骤可以推出无穷多个情形。仅仅检验例子做不到这一点;缺少有效起点的归纳步骤同样做不到。在讨论归纳法之前,我们必须准确说明一个命题对什么对象加了量词,以及哪些选择可以依赖于先前的选择。
定义
定义 1.1.1
(谓词、量词与依赖关系)
谓词 在给定 的值,或在指定论域上对 加量词后,就成为命题。命题 要求 中每个 都满足 ; 则要求至少有一个见证元。在 中,见证元 可以依赖于 ;在 中,则必须有单一的见证元对所有 都成立。
概念视角结构
把依赖的见证元看作函数
命题 断言可以为每个 选出一个见证元,也就是存在函数 ,使每个 都有 。当 由明确的规则给出时,例如对“每个整数都有更大的整数”取 ,这个函数本身就是证明;对任意的无穷论域,从命题过渡到这样的函数需要用到选择公理。反过来的命题 要求的是一个常值函数。用这种语言,两种量词次序的差别就是函数与常数的差别;而否定 则指出一个输入,在那里不存在任何见证元,因此不可能有这样的函数。
我们取 。蕴涵式 仅当 为真而 为假时才为假。它的逆否命题 与它等价,但它的逆命题 则不一定等价。全称命题的反例必须满足其假设并违反其结论;无关的例子并不能反驳它。
定理/命题
定理 1.1.2
(量词的否定)
对任意指定论域上的谓词,
因此 即 ,各论域保持不变。
定理 1.1.3
(普通归纳法与强归纳法)
设对每个 , 都是一个命题。若 成立,且对每个 都有 成立,则所有 都成立。由 以及假设更强的归纳步骤也能得到同样的结论:对每个 , 合起来蕴涵 。
证明思路
证明
(否定律)
全称命题恰好在至少有一个元素不满足谓词时不成立;这证明了第一条否定律。存在命题恰好在没有元素满足谓词时不成立,等价于每个元素都不满足谓词,这证明了第二条。这两条定律在空论域上依然成立:此时全称命题为真,存在命题为假。由外向内逐层应用这些定律,可以保持依赖关系的次序。
证明
(经由最小不成立指标的归纳法)
对于归纳法,设某个 为假,并取最小的不成立指标 。基础情形排除了 。在普通归纳法中,由最小性知 为真,于是归纳步骤使 为真,矛盾。在强归纳法中,每个更早的 都为真,于是假设更强的归纳步骤给出同样的矛盾。
强归纳法也可由普通归纳法推出:令 表示对所有 , 均成立。强归纳步骤证明了 。这说明“强”指的是可用的归纳假设,而不是另一种真值原理。
证明透视
最小不成立指标提供了什么
论证用到 的一个性质,而定理本身并没有写出它:非负整数的每个非空集合都有最小元。基础情形只用了一次,用来说明 ,这样 才是一个指标;缺少它,论证便失效,而事实上即使每个 都为假,步骤 也可以对每个 成立。最小性负责保证归纳步骤的前提:普通归纳法只需要 ,强归纳法需要 全部,而两者成立的理由相同。然后归纳步骤恰好在 处使用一次,与 的选取矛盾。由普通归纳法推出强归纳法,也证实了两者的区别只在于步骤可以假设什么: 把全部历史打包成一个命题。
归纳证明必须保持所归纳的命题固定不变。如果归纳步骤需要比所述假设更强的事实,就应当加强命题并证明新的基础情形;不可以悄悄假定缺失的事实。
例题详解
例题 1.1.4
(一个见证元,还是一族见证元?)
在整数范围内, 为真:取 即可。但 为假:对任何给定的 ,取 即可。其否定为 ,同样的取法可以验证。仅仅交换量词的次序,就改变了数学问题。
例题 1.1.5
(代数过程清晰可见的归纳法)
对 ,有 ,其中 时的空和为 。若公式在 时成立,则加上下一项得 。基础情形与这一计算证明了所有情形。该论证恰好使用了前一个等式,而没有在 处假定所要证明的等式。
例题 1.1.6
(为什么强归纳法与因数分解相匹配)
每个整数 都是若干素数的乘积。 时成立。假设命题对从 到 的所有整数都成立,则 要么是素数,要么 且 。在后一种情形,归纳假设分别适用于 ,把它们的分解相乘便证明了命题。若只知道 的情形,则无法直接控制这两个因数。
陈述的论域是其内容的一部分
仅有一个公式还不是数学断言。论域决定了哪些对象可以充当例子、见证元和反例。关于整数平方的陈述可能为真,而同样的文字用于任意实数则可能为假。例如,“平方不小于原数”这一断言对非负整数成立,但对严格介于零与一之间的实数不成立。去掉论域限制会改变定理,即使代数表达式完全相同。
当证明引入一个任意对象时,必须尊重该论域,并且只使用所述的假设。“任意”一词并不意味着随手挑选一个方便的测试例子。在全称命题的证明中,论证必须对每个允许的对象都有效,而不能再做额外的、缺乏依据的选择。相反,在存在性证明中,方便的显式构造是受欢迎的,只要它满足对见证元所施加的每一项条件。
否定使这些义务格外清楚。要反驳全称命题,一个反例就够了。要反驳存在命题,则每一个可能的见证元都必须失败。因此,几次失败的尝试并不能证明不存在见证元。不存在性的证明需要结构性的障碍,例如奇偶性、整除性,或对所有候选者一致适用的界。这一区别将在计数论证和算法不可能性的论断中反复出现。
蕴涵与空洞情形
蕴涵式并不断言其假设会出现。如果没有任何对象满足假设,则该蕴涵式在整个论域上都为真。这就是为什么关于空集中所有元素的全称命题为真:没有反例,因为没有元素能够满足假设而违反结论。而对同一空集的存在命题为假,因为它没有见证元。
空洞真并非例外,而是有用的工具。它使得关于序列所有更早项的陈述在第一项处也有意义,也使得关于孤立顶点所关联的全部边的断言无需虚构特殊对象即可理解。证明的书写者仍须检查所要得到的结论是全称的还是存在的。一个空的构造可能对每个被选中的对象都满足某个条件,却不满足至少要选出一个对象这一另外的要求。
反例模式
逆命题改变了断言
命题“若一个整数能被四整除,则它是偶数”为真。其逆命题为假:整数二是偶数,但不能被四整除。逆否命题“若一个整数不是偶数,则它不能被四整除”与原命题等价。若要修正一个无意中使用了逆命题的证明,要么补充更强的假设,要么找到只使用有效蕴涵的论证。
需要多少个基础情形?
基础情形的个数由递推式或证明步骤决定。如果证明由紧邻的前一情形推出下一情形,则一个有效的起点就可以向前传递。如果由前两个情形推出一个情形,则必须给出两个初始情形。一个每次前进二的步骤,从单个起点出发只能到达一个奇偶类;要覆盖另一个奇偶类,还需要第二个起点。
这可以不借助非正式的“传递”之类的说法来表达。考虑由已证明的起始情形出发,利用允许的步骤所能到达的指标集合。只有在这个集合中的指标处,结论才是有依据的。如果所要求的论域包含无法到达的指标,证明就有缺口。对于强归纳法,通常的表述涵盖所有更早的指标,但具体的论证仍可能需要若干个小的情形,因为所设想的分解对最小的输入并不存在。
作为一个具体应用,每个不小于十二的整数都可以写成四和五的非负整数组合。四个初始值十二、十三、十四和十五都有这样的表示。任何更大的整数都比某个仍不小于十二的较小整数大四。于是强归纳法通过再加一个四给出该表示。单个基础值无法证明其他余数类,因为加四不改变模四的余数。
有意地加强归纳命题
有时所要的结论太弱,不足以支撑它自己的下一步。标准的做法是证明一个更强的断言,其中包含所需的额外信息。只有当这个更强的断言有自己的证明(包括其基础情形)时,这样做才是正当的。把一个没有依据的断言加入归纳假设,等于假定了结果的一部分。
例如,序列的证明可能需要关于相邻两项的界,而不是一项的界。可以定义一个新的谓词,同时断言这两个界。在归纳步骤中,原来的第二个界成为新的第一个界,而递推式证明新的第二个界。这样便把递推式恰好需要的信息打包在一起。该方法与在算法中引入循环不变量相同:记录足够多的状态,使更新可以被证明。
审查任何归纳证明也遵循同样的纪律。确定正在证明的指标,并列出实际用到的更早指标。检查每个指标都严格更早,并且位于假设的论域之内。然后单独检查最小的指标,因为在那里分解或递推式可能尚不适用。最后验证当前指标处的任何断言都没有在被证明之前就被使用。这一审查可以找出隐藏的循环论证和缺失的基础情形。
从例子到有用的猜想
在证明之前,例子有富有成效的作用:它们可以揭示规律,提示正确的起始指标,或暴露缺失的假设。在公式推出之后,它们也可以用来检验所提出的公式。它们的局限是逻辑上的而非实际上的:任何有限的表格都留下无穷多个未检验的后续输入。证明必须提供一种机制来涵盖这些未检验的输入。
一个好的反例往往比一长串的验证性情形更有启发性。当猜想不成立时,要问:什么样的假设可以防止这一失败?如果除法步骤在零处失败,也许需要一个非零的假设来修复。如果消去律在合数模下失败,也许可逆性就是缺失的条件。修复后的陈述应当由其修订后的假设来证明;排除第一个反例并不能保证其他所有失败都已被排除。
这些习惯说明了为什么精确的陈述应当出现在证明的开头,而不是事后重构。陈述记录了论证必须兑现的确切承诺,证明则记录了每项承诺如何得出。将这两种角色分开,才使日后的推广成为可能:人们可以检查哪些假设被用到了,哪些只是出于方便。
常见错误
常见错误
(检验个别情形不是归纳步骤)
证明 并检验 不是归纳步骤。反过来,即使所有 都为假,蕴涵 对每个 也可能为真:假设为假的蕴涵式对结论的真假什么也没有说明。
常见错误
(马群论证在哪一步失效)
“任何有限的马群中所有的马颜色都相同”这一断言有一个著名的错误归纳:在两端各去掉一匹马,再通过共有的一匹马比较两个较小的马群。当原集合的大小为 时,这两个马群并不重叠。因此,所谓从大小 到大小 的步骤是失败的。应当指出究竟是哪个假设失败,而不是仅仅报告结论看起来不合理。
总结
量词的次序记录了允许的依赖关系。否定改变每个量词,同时保持这一次序。归纳法之所以能证明无穷多个情形,是因为假设的最小失败情形与归纳步骤矛盾;归纳步骤与基础情形必须涵盖所断言的每个指标。
练习
快速检查
(证明对每个非负整数 , 整除 。)
使用恒等式 。
解答 · 答案
当 时, 能被 整除。若对某个整数 有 ,则 ,同样能被 整除。由归纳法,命题对所述的每个指标都成立。
快速检查
(否定下列命题:对每个整数 ,存在整数 ,使得 。判定原命题及其否定的真假。)
保持两个论域以及量词的次序。
解答 · 答案
其否定为 。它为假。对任意整数 ,取 ,则 。这一取法证明了原命题,并排除了其否定中每一个被提出的界。
快速检查
(设 ,且对 有 。证明对每个 都有 ,并说明归纳步骤需要多少个基础情形。)
归纳步骤用到前两项。
解答 · 答案
两个基础情形都成立:,。需要两个,是因为在 处证明公式的步骤要用到 与 处的公式;若只检验 ,步骤连一次都无法应用。若公式在 与 处成立,则 ,而 ,所以这正是 处的公式。例如 ,。