·628. 智能系统学报 第9卷 以上证明表明，即使一一对应关系成立，矛盾仍 w~R)上(Te∈R),即：双射关系F:w~R仍然 然存在，Cantor的对角线方法也是一样，以下将证 可能成立，实数集合可能是可数的。 明：产生矛盾的根源是不动项xp∈U,而不是那个 注记11实数不可数”证明错误 假设的双射关系。在以上Cantor证明的3个关系， 1)不动项命题矛盾的存在，不影响集合之间元 可以总结如下： 素的一一对应关系，所以，Cantor对角线法关于无穷 1)(F:M~PM)A(Tg∈PM)F 集合的幂集不可数证明：自然数的幂集不可数证明： P(T)P(TM); 实数不可数的证明都是错误。 2)(F:0 ~P(w))A(T.EP(@))H 2)如果能够构造出实数与自然数的一一映射 P(T)P(T.); 关系，那么，实数就是一个可数集合，Cantor没有找 3)(F:w~R)A(TR∈R)FP(TR)P(TR)。 到这种一一映射关系，并不代表这种对应关系就不 在以上Cantor证明的3个关系中，Cantor误认 存在。前面的证明中，已经知道，不动项T。是一个 为TM∈PM,T。∈P(w),TR∈R都是真命题，这 U外不动项，e={T.}它相对于已经定义的集合，是 样他误认为证明了以下3个命题： 一个未定义项，根据不动项的两种形式，这里意味 4)(F:M ~PM)FP(Ty)P(Ty); 着，要么，在实数集合之外存在着一种尚未定义、没 5)(F:w~P(w))上P(T)P(T.); 有构造的新数TR;要么e=☑，这个构造数T.根本 6)(F:w~R)上P(TR)P(TR)。 就不存在。 进而把矛盾产生的根源当成“假设双射关系” 推论16如果无穷集合、自然数集合、实数集 引起的，所以，否定双射关系，得到以下结论： 合演算是一致的，则Cantor关于“无穷集合的幂集 7)卜(F:M~PM),即无穷集合不能与它的 不可数，自然数的幂集不可数，实数不可数”等命题 幂集合建立一一对应关系： 的证明是错误。 8)上(F:w~P(w)),即自然数集合不能与 它的幂集合建立一一对应关系： 6递归论中的一些定理的错误证明 9)上(F:w~R),即自然数集合不能与实数 6.1N上存在非递归函数证明错误 集合建立一一对应关系。 我们知道，Cantor使用对角线方法，证明“系统 产生矛盾的根源Cantor误认为是(F:M~ N是不完全”的Gdl定理，自然数的幂集合是不可 PM),(F:ω~P(w)),(F:w~R)引起的。 数集合，实数集合是不可数集合。因为“Cantor对角 所以，Cantor证明的3个关系上(F:M~ 线方法”是数学证明中的一个重要方法，与此相关 PM),上(F:w~P(w),上(F:w~R)都是 的重要定理还有“存在非递归集合”、“存在非递归 错误的。 函数”、Tuing机“停机问题”不可判定定理。而对角 使用正反集合分析，以上证明满足正反集合的 线方法产生的项是域外不动项，这些定理的证明都 条件，正反集合上的不动项，都是U外不动项，产生 是错误的。 矛盾的根源实际上是TM∈PM,T.∈P(ω)，TR∈ 定理23设全部的一元递归函数集合： R引起的。所以，在以上推理中，Cantor实际上只证 U=f(n),f(n),f5(n)f(n),…} 明了以下3个关系： 则存在不动项函数h(k),h()主U。 10)(F:M ~PM)(TyE PM); 证明一元函数集合，定义域、值域都是可数集合： 11)(F:ω~P(ω))上(T。∈P(ω)； U=fo(n)f(n),f2(n),fs(n),. 12)(F:w~R)F(TR∈R)。 全部函数的枚举如下： 由以上分析可以得到以下推论： f(0)f(0),f3(0),f5(0),… 推论13如果无穷集合演算是一致的，则(F: M~PM)F(TM∈PM),即：双射关系F:M~ f(1)f(1)f(1)f(1),… PM仍然可能成立，无穷集合的幂集合可能是可数 f(2)f(2)f(2)f5(2),… 集合。 f(3)f(3),f(3),(3),… 推论14如果自然数集合演算是一致的，则 。44 (F:w~P(w)上(T。eP(w),即：(F:w 取对角线值的序列，并加1，改为别的值， P(ω))仍然可能成立，自然数集合的幂集合可能是 h(n)=f(n)+1, 可数集合。 假设h(n)=f(n)+1,在这个序列之中，得到 推论15如果实数集合演算是一致的，则(F: 如下矛盾，h(k)=f(k)=f(k)+1。以上证明表明，即使一一对应关系成立，矛盾仍 然存在，Ｃａｎｔｏｒ 的对角线方法也是一样，以下将证 明：产生矛盾的根源是不动项 ｘＰ ∈ Ｕ ，而不是那个 假设的双射关系。 在以上 Ｃａｎｔｏｒ 证明的 ３ 个关系， 可以总结如下： １） （Ｆ：Ｍ ～ ＰＭ） ∧ （ＴＭ ∈ ＰＭ） ├ Ｐ（ＴＭ ）↔¬ Ｐ（ＴＭ ） ； ２） （Ｆ：ω ～ Ｐ（ω）） ∧ （Ｔω ∈ Ｐ（ω）） ├ Ｐ（Ｔω）↔¬ Ｐ（Ｔω） ； ３） （Ｆ：ω ～ Ｒ） ∧（ＴＲ ∈Ｒ）├Ｐ（ＴＲ）↔¬ Ｐ（ＴＲ） 。 在以上 Ｃａｎｔｏｒ 证明的 ３ 个关系中，Ｃａｎｔｏｒ 误认 为 ＴＭ ∈ ＰＭ ， Ｔω ∈ Ｐ（ω） ， ＴＲ ∈ Ｒ 都是真命题，这 样他误认为证明了以下 ３ 个命题： ４） （Ｆ：Ｍ ～ ＰＭ） ├ Ｐ（ＴＭ ）↔¬ Ｐ（ＴＭ ） ； ５） （Ｆ：ω ～ Ｐ（ω）） ├ Ｐ（Ｔω）↔¬ Ｐ（Ｔω） ； ６） （Ｆ：ω ～ Ｒ） ├ Ｐ（ＴＲ ）↔¬ Ｐ（ＴＲ ） 。 进而把矛盾产生的根源当成“假设双射关系” 引起的，所以，否定双射关系，得到以下结论： ７）├ ¬ （Ｆ：Ｍ ～ ＰＭ） ，即无穷集合不能与它的 幂集合建立一一对应关系； ８）├ ¬ （Ｆ：ω ～ Ｐ（ω）） ，即自然数集合不能与 它的幂集合建立一一对应关系； ９）├ ¬ （Ｆ：ω ～ Ｒ） ，即自然数集合不能与实数 集合建立一一对应关系。 产生矛盾 的 根 源 Ｃａｎｔｏｒ 误 认 为 是 （Ｆ：Ｍ ～ ＰＭ） ， （Ｆ：ω ～ Ｐ（ω）） ， （Ｆ：ω ～ Ｒ） 引起的。 所以， Ｃａｎｔｏｒ 证明的 ３ 个关系 ├ ¬ （Ｆ：Ｍ ～ ＰＭ） ，├ ¬ （Ｆ：ω ～ Ｐ（ω）） ，├ ¬ （Ｆ：ω ～ Ｒ） 都是 错误的。 使用正反集合分析，以上证明满足正反集合的 条件，正反集合上的不动项，都是 Ｕ 外不动项，产生 矛盾的根源实际上是 ＴＭ ∈ ＰＭ ， Ｔω ∈ Ｐ（ω） ， ＴＲ ∈ Ｒ 引起的。 所以，在以上推理中，Ｃａｎｔｏｒ 实际上只证 明了以下 ３ 个关系： １０） （Ｆ：Ｍ ～ ＰＭ） ├ ¬ （ＴＭ ∈ ＰＭ） ； １１） （Ｆ：ω ～ Ｐ（ω）） ├ ¬ （Ｔω ∈ Ｐ（ω）） ； １２） （Ｆ：ω ～ Ｒ） ├ ¬ （ＴＲ ∈ Ｒ） 。 由以上分析可以得到以下推论： 推论 １３ 如果无穷集合演算是一致的，则 （Ｆ： Ｍ ～ ＰＭ） ├ ¬ （ＴＭ ∈ ＰＭ） ，即：双射关系 Ｆ：Ｍ ～ ＰＭ 仍然可能成立，无穷集合的幂集合可能是可数 集合。 推论 １４ 如果自然数集合演算是一致的，则 （Ｆ：ω ～ Ｐ（ω）） ├ ¬ （Ｔω ∈ Ｐ（ω）） ，即： （Ｆ：ω ～ Ｐ（ω）） 仍然可能成立，自然数集合的幂集合可能是 可数集合。 推论 １５ 如果实数集合演算是一致的，则 （Ｆ： ω ～ Ｒ） ├ ¬ （ＴＲ ∈Ｒ） ，即：双射关系 Ｆ：ω ～ Ｒ 仍然 可能成立，实数集合可能是可数的。 注记 １１ 实数不可数”证明错误 １）不动项命题矛盾的存在，不影响集合之间元 素的一一对应关系，所以，Ｃａｎｔｏｒ 对角线法关于无穷 集合的幂集不可数证明；自然数的幂集不可数证明； 实数不可数的证明都是错误。 ２）如果能够构造出实数与自然数的一一映射 关系，那么，实数就是一个可数集合，Ｃａｎｔｏｒ 没有找 到这种一一映射关系，并不代表这种对应关系就不 存在。 前面的证明中，已经知道，不动项 ＴＲ 是一个 Ｕ 外不动项， ｅ ＝ ＴＲ { } 它相对于已经定义的集合，是 一个未定义项，根据不动项的两种形式，这里意味 着，要么，在实数集合之外存在着一种尚未定义、没 有构造的新数 ＴＲ ；要么 ｅ ＝ ∅ ，这个构造数 ＴＲ 根本 就不存在。 推论 １６ 如果无穷集合、自然数集合、实数集 合演算是一致的，则 Ｃａｎｔｏｒ 关于“无穷集合的幂集 不可数，自然数的幂集不可数，实数不可数”等命题 的证明是错误。 ６ 递归论中的一些定理的错误证明 ６．１ Ｎ 上存在非递归函数证明错误 我们知道，Ｃａｎｔｏｒ 使用对角线方法，证明“系统 Ｎ 是不完全”的 Ｇöｄｅｌ 定理，自然数的幂集合是不可 数集合，实数集合是不可数集合。 因为“Ｃａｎｔｏｒ 对角 线方法”是数学证明中的一个重要方法，与此相关 的重要定理还有“存在非递归集合”、“存在非递归 函数”、Ｔｕｉｎｇ 机“停机问题”不可判定定理。 而对角 线方法产生的项是域外不动项，这些定理的证明都 是错误的。 定理 ２３ 设全部的一元递归函数集合： Ｕ ＝ ｆ ０（ｎ），ｆ １（ｎ），ｆ ２（ｎ），ｆ { ３（ｎ），…} 则存在不动项函数 ｈ（ｋ） ， ｈ（ｋ） ∉ Ｕ 。 证明 一元函数集合，定义域、值域都是可数集合： Ｕ ＝ ｆ ０（ｎ），ｆ １（ｎ），ｆ ２（ｎ），ｆ { ３（ｎ），…} 全部函数的枚举如下： ｆ ０（０），ｆ １（０），ｆ ２（０），ｆ ３（０），… ｆ ０（１），ｆ １（１），ｆ ２（１），ｆ ３（１），… ｆ ０（２），ｆ １（２），ｆ ２（２），ｆ ３（２），… ｆ ０（３），ｆ １（３），ｆ ２（３），ｆ ３（３），… … 取对 角 线 值 的 序 列， 并 加 １， 改 为 别 的 值， ｈ（ｎ） ＝ｆ ｎ（ｎ） ＋ １， 假设 ｈ（ｎ） ＝ ｆ ｎ（ｎ） ＋ １，在这个序列之中，得到 如下矛盾， ｈ（ｋ） ＝ ｆ ｋ（ｋ） ＝ ｆ ｋ（ｋ） ＋ １。 ·６２８· 智 能 系 统 学 报 第 ９ 卷