数学归纳原理与最小数原理相互关系破解.pdf

中学数学杂志2 0 0 9年第 3期 嚣 16 霓 毛 愿 数学归纳原理与最小数原理相互关 系破 解 北京 1 0 1中学 1 0 0 0 9 1 王树茗 0 绪 言 数学归纳原理是数学归纳法的根据 它断言 任 何有关 自然数的命题 如果对于 0真 而且每当对于 某个 自然数 真 都有对于作为其随从 的自然数 k 也真 那么对于所有 自然数都真 最小数原理断言 如果某个 由自然数组成 的集 合不空 那么它必含有一个最小的数 关于这两个原理 的相互关 系迄今盛行等价说 即认为两者可以相互推出 此说 的源起可追 溯到上 一 世纪 四十年代 出版 指原著 下 同 的 1 利用最 小数原理 证 明 数学归纳原理 这在事实上认可了 等价说 因为前此十年 以上出版的 2 业 已权威地 证明了由数学归纳原理 可以推 出最小数原理 对等 价说第一个予 以确认 的是前苏联 于 1 9 5 0年出版的 3 该书在叙述了雷 同于 1 中的推理之后指 出 容易看到 最小数原理又可作为数学归纳原理 的推论而得到 因此 这两个命题是等价 的 此说 由于随后 3 的多种译本陆续 出版而传播至我国和 东欧并反馈到西方 1 9 6 3年 我国一本与 3 同名的 书问世 其中 自 然数的性质 一节对等价说的叙述 看上去颇为系统完整 作为基础的是 P e a n o 算术 公理体系的五条公理 即 1 1是 自然数 按 P e a n o 最初提法如此 后来已将 1 换成 0 可参看 4 2 每个 自然数都有一个确定的随从 3 1非任何 自然 数的随从 4 若两个 自然数的随从相等 则这两个 自然数相等 5 即作为数学归纳原理形式之一的 归纳公理 紧跟 着这些公 理展开 的是 已经 出现 在 1 和 3 中的 由最小数原理推 出数学归纳原理 以及新补充的 由数学归纳原理推出最小数原理 此书的这一特色 它 的多次重印和再版 最近一 次 作为 数学小丛书 中的一册再版于 2 0 0 2年 都极 大地促进了等价说在 国内的广泛流行与深入人心 唯其如此 曾经多次有人提出 数学归纳法教学应先 介绍最小数原理 即在它的基础上来讲授 在近期 的 课改讨论 中 还有人借题发挥 强调最小数原理 是 保证数学归纳法成立的基本性质 然而 反对等价说的声音也一直存在 在国内 表达最突出的是最近十几年来流传很广的 5 见 其中附录一 以及此书两作者之一所写的 6 前者 指出 由最小 数原理到数学 归纳原理的推导 有在 前提 中已包含 了结论 的毛病 后者则进一步断言 事实上这两个原 理是不等价 的 给出的所有这类 证明 都 是错误 的 在 国外 这种声音 出现得更 早 1 9 5 4年发表 的 7 指出 等价说所依 据的不是 P e a n o 公理的前四条 7 将其记作 P 而是该 四 条有所加强的情形 记作 P 这些意见都是有份量 的 尤其是 7 的意见 已经接近于得 出正确的结果 断定这两个原理孰强孰弱 当然 不能仅 限于 猜想 还必须 同时给出相应的证明 然而这样的结 果始终没有得出 所 有意见也就没有引起人们足够 的注意 本文拟就这个悬而未决的问题进行讨论并请求指 正 在讨论中假定读者具有数理逻辑 的最初步知识 为 了行文简便 数学归纳原理和最小数原理将分别记作 i n d和 m i n 英文 i n d u c t i o n和 m i n i mu m的缩写 1 讨论的基础与实质 在自然数算术公理体系中迄今唯一得到公认的 P e a n o 体 系可依现代观点重述如下 参阅 8 元词共五个 即表示 自然数集合的 N 此后 凡无特别说明处 字母 b c z 都指 N中的任一 个体 即任一 自然数 作 为特定 自然数专名 的 0 和 1 作 为 特 定 二 元 运 算 专 用 符 号 的 和 对于 和 Y执行这两种运算的结果分别写作 Y与 Y 读作 与 Y的和 与 与 Y的积 公理共七条 公 理 1 V 1 0 公 理 2 V Y 1 Y 1 Y 公 理 3 V X 0 公理 4 V Y Y 1 Y 1 公 理 5 V 0 0 公理 6 V Y Y 1 Y 1 公理 7 即 i n d P 0 八 V k P k 一 P 1 一 Vx P P 表示任一个有关 的命题 与前一节提及的五条公理相 比较 这里缺少开 端的两条 原因是它们的内容已经含在此前对于元 词的说明中 这里又多出来后面四条 则是由于将原 先隐含在 加法 和 乘法 定义中的一些假设明文 地列成 了公理 正 因为那些假设成了公理 而 l 3 黩 1 窘 冀 嚣 7 中学数学杂志2 0 0 9年第 3期 1是那些假设中的一条 随从 不再是元词 由于要讨论 小 于 关 系 P e a n o体 系 还需补充以下两个定义 定义 1 Y 渎作 小 于Y 表示 j 0八 Y 定义 2 Y 读作 小于或等于 Y 表示 v V y P e a n o 公理组既然含有 i n d 对于 i n d 和mi n 双方 即非不偏不倚 因此 关于 i n d与 mi n相互关 系的讨 论不应 以该公理组 而应以其中的公理 1 6 作为基 础 讨论的实质则是要对以下两个问题作出回答 1 由 公理 l 6 定义 1 2 i n d 即P e a n o 体系 可否推出 ra i n 2 由 公理 1 6 定 义1 2 mi n 可否推出 i n d 如果对两者的回答都是肯定 的 则 i n d 与 mi 13 等 价 如果对 1 肯定而对 2 否定 则 i n d强于 m i n 如果对 1 否定而对 2 肯定 则 i n d 弱于 ra i n 如果 对两者的回答都是否定的 则 i n d与 m i n互相独立 2 由 公理 1 6 定义 2 i n d 可推出 ra i n 这一推理过程实际是 P e a n o体 系的一 个片断 可由以下六个定理严格而简练地构成 定 理 1 V 0 证 对 施行归纳 1 由公理 3 0 0 0 2 假设 0 则先后引用公理 4及本假 设 得 0 1 0 l k 1 可见 V 0 证毕 定理 2 V Y 1 Y Y 1 证 对 Y施行归纳 i 由公理 3 x 1 0 1 0 十1 2 假设 1 k 1 9 1 4 先后弓 I 用公理 4 及本假设 并再次引用公理 4 得 1 1 i 1 l 十l j 1 f 1 1 呵见 V Y 1 y 1 证 毕 定理 3 V 0 3 Y J 证 以 表示 0一 y Y 1 I f 盯 对 施行归纳 1 0 即0 0 一 j Y 1 0 此命题由 于前件似 真 2 假设 k 真 以 表示 k 则 u 1 k 1 因而 3 l 1 1 即 k l 0一 Y Y 1 1 此命题由于后件真而真 1 4 可见 V 真 即 V 0 一 j Y Y 1 证毕 定理 4 V 0 证 若 0 则由定理 1 及定义 1 0 若 0 则 0 因而 Vx 0 V 0 再引用定义 2 V 0 征毕 定理 5 V y y 1 y 证 先假设 y而求证 1 y 因为 y 所以由定义 l 有 0 使 d Y 而由于 H 0 依定理 3又有 使 I 1 于是 Y 戈 1 1 1 先后引用了公理 4及定理 2 从 而 1 Y 若 0 则由公理3 1 若 d 0 则由 定义 1 l Y 因此 1 再考虑到假设条件 Y 即得 V Y Y 1 Y 证毕 定理 6即 m i n j A 一 Y A Vz z A一 y A表示任一个 由自然数组成的 集合 证 用反证法 假设有 A使 鲑A 真而 j Y y A八 Vz z A 不真 意即 假设 有 使得不但有 自然数 在A中 而且没有这样 的自 然数 Y 它既在 A中又符合条件 V A一 Y 令 M Y l Vz z A 9 由 二 述假设 没有既在 4中又在 中的 自然数 故 4 n M 0 由定理4 无论 z 怎样取值 z A一 0 z 恒真 因而 Vz z A一 0 z 真 故 0 任取 k M 又任取0 A 则由 的定义知k 再 由A n M 0 知 k 口 故 k 6 又由定理 5 十1 8 考虑到 0所表示的 A中数的任意性即得 V A i 1 z 真 因而 k 1 因为 0 M V M 1 M 所 以 V M 即 N c 而 c 故 A c M 又假 设 j A 真 即 l 故 l4 n 此结果 与前述 L4 n M 0 相矛盾 证毕 3 由 公理 l 6 定义 l 2 m i n 不可能推出i n d 确立关于 不可能推出 的命题通常倚靠凭借 解释的证 明方法 其要领是 所谓由某个公理体系 前件假的条件命题真 和 后件真 的条件命题真 分别是这 一 步及下一步 的根据 其来历 都见关于 若 则 逻辑联结词之 一 的真值表 后件真 的条件命题真 还将在定理 6证 明的个别步 骤中发挥关键作用 能否推出某个命题 P纯属形式方面的问题 与各个 公理以及 P的内容毫不相干 因此 可把 中各个元 词都不拘原意地给以解释 唯一要求是不使原有命 题变得无意义 如果 由 可 以推出 P 则永远不会 出现 中公理都真而 P却不真的情况 而只要该情 况一旦出现 就表明不可能 由 推出P 详释见 9 对 于 P e a n o算 术 的 元 词 作 这 样 的 解 释 N 自然数集合 由无穷数列 0 1 1 1 2 2 吉 3 3 寺 n n 1 中的一切项组成 0 和 1 都按在普通数学 中的原意 两个 自然数 的相加 和相乘 分 别依照普通有理数的加法法则 和乘法法则 不过作 一 点补充 即 相乘结果中所出现的加数 一律当作 0 在这种解释之下 公理 l 5都不难验证其真 公 理 6也能通过检验以下四种情形而确知其真 和 b 都表示普通意义的自然数 1 n b 1 b a 2 b 1 0 6 b 口 告 6 6 b 3 b 1 1 6 詈 0 0 b rz n 6 詈 0 4 n b 1 1 0 6 詈 妻 b 1 0 一 口 6 一 口 n 6 号 6 1 争 此外 由于 保持在普通数学中的原意 定义 1 又是普通数学中固有的 故 也保持原意 从而易 见 对于上述解释下的 自然数 m i n真 然而 设 p x 表示 指不超过 的最大整数 则尽管 P O 和 V P 一P 1 都易证其真 但却由于 对于非整数的 自然数 例如 1 1 P 不真而 不能断定 Vx P 之真 因此 由 公理 1 6 定义 1 2 mi n 不能推出 i n d 证毕 4 结语与附白 综括 以上两节结论 i n d与 mi n的关 系是且只能 是i n d强于mi n 读过上 一节 的朋友想必急于知道 前述那些文 献所一致给出的由 mi n推及 i n d的过程究竟错在何 处 那一过程大都写得异常简略 含混 因而其 中的 错误十分难以发觉 现将它稍加明细化如下 假设 in d不成立 即有关于自然数的命题虽然 它对于0 真 若它对于 真则它对于k 1 也真 但是它并非对于所有 自然数都真 由m i n 使该命题 不真 的自然数中必有最小数 可设该数为 m 由于该 命题对于 m不真而由假设 它对于0 真 所以m 0 从而 m一1 为一 自然数 因m一1 m 故该命题对 于 m一1 真 于是 该命题对于 m 一1真而对于 m不 真 与前面所假设的 相矛盾 推毕 这个推理引用 了 若一 自然数非 0 则必有一 自 然数较它少 1 亦即 V 0一 j Y Y 1 然而 这个命题尽管根据 公理 1 6 定义 1 2 i n d 可证 而且就是本文第 2 节中的定理 3 但是 根据 公理 1 6 定义 1 2 m i n 却不能证 理 由 是 沿用上一节对各个元词 的解释 则公理 1 6和 1 n i n 都真而这个命题假 作为 自然数 的 既 二 不是 0 又不能 由某一 自然数 加 1而得 由此看 出 那些文献在由mi n 推 出i n d 时暗中引用了需要 由 i n d推 出的命题 类似 晴节还有 留供读者探索 参 考文献 1 R 柯朗 H 罗宾斯 数学是什么 M 长沙 湖南教育 出版 社 1 9 8 5 p p 2 5 2 6 2 艾 兰道 分析基础 M 高等教育出版社 1 9 5 8 p p 1 2 一 l 3 3 F I C 索明斯基 数学归纳法 最新译文载丁石孙主 编之 9 3 纳 递推 无字证明 坐标 复数 M 北京大 学 出版社 1 9 9 5 P P 3 6 3 7 4 宋文坚 西方形式逻辑史 M 中国社会科学出版 社 1 9 9 1 P 3 0 2 5 潘承洞 潘承彪 初等数论 M 北京大学出版社 1 9 9 2 P 4 8 5 6 潘承彪 关于数学9 3 纳原理的一点注记 同 2 所载 书 即 9 l一9 2 7 B H 摩洛希 关于 自然数算术中归纳法