第5期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·625. x生F(x)x∈TM: 即：P(T,n)→P(xn,n), 定理17规定：n∈F(n)n华TN; 问T∈U吗？假设T∈U成立，那么存在某个 n使F(n)neTw; xk,x=T, 定理18规定：xm=0Tn=1, 即：P(x,k)→P(x,k)或 xm=1Tn=0。 P(T,k)P(T,k)矛盾，所以，T庄U。 以上构造项TM、T。、TR都满足： 对角线方法使用全集（补集合为空集非对称分 x∈+a→P(T),x∈-aP(T) 类方法)，所有“对角线方法”都是一个类型，它们都 所以，TM、T。、T都是U外不动项。 是“广义U外不动项定理”的特例。所以，“Cantor “对角线方法”还可以看成一种非对称的分类 对角线方法”构造的实数也是“广义U外不动项定 方法，也是“广义U外不动项定理”的特例。 理”的特例。 定理20“对角线证明方法”的非对称分类 推论5如果实数集R上的演算是一致的，那 如果集U上的演算是一致的，+a=U,-a= 么，“康托的对角线方法”所构造的项T满足：(F:ω ☑，构造项T满足x∈UP(T),那么，T不是U ~R)∧(T∈R)FP(T)P(T)。 的元素，即：TU。 定理21“对角线证明方法”的3个结论 证明在以上“广义U外不动项定理”中假设 设U={1,x2,…,x,…},如果U内演算是一 +a=U,则-a=☑，+a={xIP(x)},代入即有 致的，“对角线证明方法”可以得到以下3个结论： TU,或者列出以下过程： (A)上(F:w~U)A(T∈U); 1)假设U={xIP(x)},一P(x)表示x在 (B)卜(F:w~U)∧T∈U; 列表中，假设所有的元素有一个列表，即存在与 (C)上(F:w~U)A(T∈U)。 双射关系：F:w~U。 证明在以上“广义U外不动项定理”中假设 2)x∈U-P(x),一x∈U等价一个谓词 +a=U,则 P(x)“x在列表中”，即：存在双射关系：F:w~U。 -a=⑦ 3)x∈UP(T),一对角线方法构造一个 +a={xI P(x)} 新元素T,T与U中所有元素都不同。 F:w~U,T∈U上P(T)P(T) 4)P(x)P(T),—(2)(3)。 上[(F:w~U)A(T∈U)] (1) 5)假设T∈U一问T∈U吗？假设T∈U成 由于(MΛN) 立，那么存在某个x,x=T。 (M AN)V(MA N)V(MAN) 6)P(T)P(T),—(5)代入，得到矛盾。 由式(1)可以得到以下3个结论： 根据“广义U外不动项定理”的形式：P、T在 (A)F:w~U上(T∈U),表示如果双射关 U上可定义，TeU上P(T)P(T)。 系成立，那么T庄U:即 “P、T在U上可定义”，即“U上元素上可列 上(F:ω~U)A(T∈U) 表”，即双射关系F:ω~U成立。 (B)T∈U上(F:w~U),表示如果T∈U “对角线证明方法”可以简化为 成立，那么双射关系不成立：即 (F:w~U)A(T∈U)FP(T)→P(T)。 上(F:w~U)∧(TeU) 注记8“对角线证明方法”的二元谓词表示法 (C)上(F:w~U)∧(T∈U),表示T∈ 设U={x1,x2,…,x,…}={x1P(x)},P(x) U,双射关系都不成立。 表示谓词表中的第i个元素。 注记9 Cantor的断定 表中的第i个元素x的第n项记为P(x,n), 在“对角线证明方法”A、B、C3个结论中，如果 T∈U成立，那么，双射关系F:w~U一定不成立， 可以把按对角线方法排列如下： 这就是Cantor的断定，即B结论正确： P(x1,1),P(x1,2),P(x1,3),P(x1,4),… 另外一种情况是：如果TU,那么，双射关系 P(x2,1),P(x2,2),P(x2,3),P(x2,4),… F:w~U可能成立，也可能不成立，即：A、C都可能 P(x3,1),P(x3,2),P(x3,3),P(x3,4),… 正确，这说明矛盾P(T)一P(T)和双射关系F:ω P(x4,1),P(x4,2),P(x4,3),P(x4,4), ~U无关，矛盾是由T∈U引起的。 下面的证明表明：矛盾恰恰是由T∈U引起的， 定义一个新的项T,满足T的第n项，不同于xm Cantor的断定是错误的。 的第n项， 定理22不动项矛盾与双射关系无关ｘ ∉ Ｆ（ｘ）↔ｘ ∈ ＴＭ ； 定理 １７ 规定： ｎ ∈ Ｆ（ｎ）↔ｎ ∉ ＴＮ ； ｎ ∉ Ｆ（ｎ）↔ｎ ∈ ＴＮ ； 定理 １８ 规定： ｘｎｎ ＝ ０↔Ｔｎ ＝ １， ｘｎｎ ＝ １↔Ｔｎ ＝ ０。 以上构造项 ＴＭ 、 Ｔω 、 ＴＲ 都满足： ｘ ∈＋ α↔¬ Ｐ（Ｔ） ， ｘ ∈－ α↔Ｐ（Ｔ） 所以， ＴＭ 、 Ｔω 、 ＴＲ 都是 Ｕ 外不动项。 “对角线方法”还可以看成一种非对称的分类 方法，也是“广义 Ｕ 外不动项定理” 的特例。 定理 ２０ “对角线证明方法”的非对称分类 如果集 Ｕ 上的演算是一致的， ＋ α ＝ Ｕ ， － α ＝ ∅ ，构造项 Ｔ 满足 ｘ ∈ Ｕ↔¬ Ｐ（Ｔ） ，那么， Ｔ 不是 Ｕ 的元素，即： Ｔ ∉ Ｕ 。 证明 在以上“广义 Ｕ 外不动项定理”中假设 ＋ α ＝ Ｕ ，则 － α ＝ ∅ ， ＋ α ＝ {ｘ ｜ Ｐ（ｘ）} ，代入即有 Ｔ ∉ Ｕ ，或者列出以下过程： １）假设 Ｕ ＝ {ｘ ｜ Ｐ（ｘ）} ，——— Ｐ（ｘ） 表示 ｘ 在 列表中，假设所有 Ｕ 的元素有一个列表，即存在与 双射关系： Ｆ：ω ～ Ｕ 。 ２） ｘ ∈ Ｕ↔Ｐ（ｘ） ，——— ｘ ∈ Ｕ 等价一个谓词 Ｐ（ｘ） “ ｘ 在列表中”，即：存在双射关系： Ｆ：ω ～ Ｕ 。 ３） ｘ ∈ Ｕ↔¬ Ｐ（Ｔ） ，———对角线方法构造一个 新元素 Ｔ ， Ｔ 与 Ｕ 中所有元素都不同。 ４） Ｐ（ｘ）↔¬ Ｐ（Ｔ） ，———（２）（３）。 ５）假设 Ｔ ∈ Ｕ ———问 Ｔ ∈ Ｕ 吗？ 假设 Ｔ ∈ Ｕ 成 立，那么存在某个 ｘ ， ｘ ＝ Ｔ 。 ６） Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ，———（５）代入，得到矛盾。 根据“广义 Ｕ 外不动项定理”的形式： Ｐ 、 Ｔ 在 Ｕ 上可定义， Ｔ ∈ Ｕ├Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 。 “ Ｐ 、 Ｔ 在 Ｕ 上可定义”，即“ Ｕ 上元素上可列 表”，即双射关系 Ｆ：ω ～ Ｕ 成立。 “对角线证明方法”可以简化为 （Ｆ：ω ～ Ｕ） ∧ （Ｔ ∈ Ｕ）├Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 。 注记 ８ “对角线证明方法”的二元谓词表示法 设 Ｕ ＝ ｘ１ ，ｘ２ ，…，ｘ { ｉ，…} ＝ {ｘ ｜ Ｐ（ｘ）} ， Ｐ（ｘｉ） 表示谓词表中的第 ｉ 个元素。 表中的第 ｉ 个元素 ｘｉ 的第 ｎ 项记为 Ｐ（ｘｉ，ｎ） ， 可以把按对角线方法排列如下： Ｐ（ｘ１ ，１），Ｐ（ｘ１ ，２），Ｐ（ｘ１ ，３），Ｐ（ｘ１ ，４），… Ｐ（ｘ２ ，１），Ｐ（ｘ２ ，２），Ｐ（ｘ２ ，３），Ｐ（ｘ２ ，４），… Ｐ（ｘ３ ，１），Ｐ（ｘ３ ，２），Ｐ（ｘ３ ，３），Ｐ（ｘ３ ，４），… Ｐ（ｘ４ ，１），Ｐ（ｘ４ ，２），Ｐ（ｘ４ ，３），Ｐ（ｘ４ ，４），… … 定义一个新的项 Ｔ ，满足 Ｔ 的第 ｎ 项，不同于 ｘｎ 的第 ｎ 项， 即： Ｐ（Ｔ，ｎ）↔¬ Ｐ（ｘｎ ，ｎ） ， 问 Ｔ ∈ Ｕ 吗？ 假设 Ｔ ∈ Ｕ 成立，那么存在某个 ｘｋ ， ｘｋ ＝ Ｔ ， 即： Ｐ（ｘｋ，ｋ）↔¬ Ｐ（ｘｋ，ｋ） 或 Ｐ（Ｔ，ｋ）↔¬ Ｐ（Ｔ，ｋ） 矛盾，所以， Ｔ ∉ Ｕ 。 对角线方法使用全集（补集合为空集非对称分 类方法），所有“对角线方法”都是一个类型，它们都 是“广义 Ｕ 外不动项定理” 的特例。 所以，“Ｃａｎｔｏｒ 对角线方法”构造的实数也是“广义 Ｕ 外不动项定 理”的特例。 推论 ５ 如果实数集 Ｒ 上的演算是一致的，那 么，“康托的对角线方法”所构造的项 Ｔ 满足： （Ｆ：ω ～ Ｒ） ∧ （Ｔ ∈ Ｒ）├Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 。 定理 ２１ “对角线证明方法”的 ３ 个结论 设 Ｕ ＝ ｘ１ ，ｘ２ ，…，ｘ { ｉ，…} ，如果 Ｕ 内演算是一 致的，“对角线证明方法”可以得到以下 ３ 个结论： （Ａ）├ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） ； （Ｂ）├ ¬ （Ｆ：ω ～ Ｕ） ∧ Ｔ ∈ Ｕ ； （Ｃ）├ ¬ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） 。 证明 在以上“广义 Ｕ 外不动项定理”中假设 ＋ α ＝ Ｕ ，则 － α ＝ ∅ ＋ α ＝ {ｘ ｜ Ｐ（ｘ）} Ｆ：ω ～ Ｕ，Ｔ ∈ Ｕ├ Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ├ ¬ ［（Ｆ：ω ～ Ｕ） ∧ （Ｔ ∈ Ｕ）］ （１） 由于 ¬ （Ｍ ∧ Ｎ）↔ （Ｍ ∧ ¬ Ｎ） ∨ （¬ Ｍ ∧ Ｎ） ∨ （¬ Ｍ ∧ ¬ Ｎ） 由式（１）可以得到以下 ３ 个结论： （Ａ） Ｆ：ω ～ Ｕ ├ ¬ （Ｔ ∈ Ｕ） ，表示如果双射关 系成立，那么 Ｔ ∉ Ｕ ；即 ├ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） （Ｂ） Ｔ ∈ Ｕ ├ ¬ （Ｆ：ω ～ Ｕ） ，表示如果 Ｔ ∈ Ｕ 成立，那么 双射关系不成立；即 ├ ¬ （Ｆ：ω ～ Ｕ） ∧ （Ｔ ∈ Ｕ） （Ｃ）├ ¬ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） ，表示 Ｔ ∈ Ｕ ， 双射关系都不成立。 注记 ９ Ｃａｎｔｏｒ 的断定 在“对角线证明方法”Ａ、Ｂ、Ｃ ３ 个结论中，如果 Ｔ ∈ Ｕ 成立，那么， 双射关系 Ｆ：ω ～ Ｕ 一定不成立， 这就是 Ｃａｎｔｏｒ 的断定，即 Ｂ 结论正确； 另外一种情况是：如果 Ｔ ∉ Ｕ ，那么，双射关系 Ｆ：ω ～ Ｕ 可能成立，也可能不成立，即：Ａ、Ｃ 都可能 正确，这说明矛盾 Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 和双射关系 Ｆ：ω ～ Ｕ 无关，矛盾是由 Ｔ ∈ Ｕ 引起的。 下面的证明表明：矛盾恰恰是由 Ｔ ∈ Ｕ 引起的， Ｃａｎｔｏｒ 的断定是错误的。 定理 ２２ 不动项矛盾与双射关系无关 第 ５ 期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·６２５·