第9卷第5期 智能系统学报 Vol.9 No.5 2014年10月 CAAI Transactions on Intelligent Systems 0ct.2014 D0:10.3969/j.issn.1673-4785.201310076 逻辑及数学演算中的不动项与不可判定命题（Ⅱ） 张金成 (中央党校函授学院广德教学点，安徽广德242200) 摘要：不动点是一个广泛而深刻的数学现象，它已经渗透到数学的各个领域。文中把不动点推广到逻辑思维领 域，证明Russel悖论是集合论中的不动项，Gdel不可判定命题是自然数系统N中的不动项，Cantor对角线方法构造 的项是不动项，不可判定的Tuig机也是不动项。进一步可以证明，当一个已知集合U可以分割成正、反集合时，不 动项不在正集或反集之中，不动项一定是U外不动项，·外不动项的逻辑性质相对于0已经发生变异，是未定义项， ·外不动项命题是不可判定的，这是系统的固有现象。自然数系统N中同样存在不动项，不动项的存在与不可判 定，并不影响正、反集合的递归性与系统的完全性，因此，Gdel不完全定理的证明不成立，Cantor对角线方法证明是 错误的，Turing停机问题证明也是错误的。“系统N能否完全”、实数是否可数、Turing停机问题是否可判定都必须 重新思考。 关键词：正项；反项；不动项：悖论；U外不动项；不可判定命题：不完全定理；对角线方法；不可数：停机问题。 中图分类号：B813;TP18文献标志码：A文章编号：1673-4785(2014)05-0618-14 中文引用格式：张金成.逻辑及数学演算中的不动项与不可判定命题（Ⅱ）[J].智能系统学报，2014,9(5)：618-631. 英文引用格式：ZHANG Jincheng.Fixed terms and undecidable propositions in logical and mathematical calculus(Ⅱ)[J].CAAI Transactions on Intelligent Systems,2014,9(5):618-631. Fixed terms and undecidable propositions in logical and mathematical calculus (II ZHANG Jincheng (Correspondence School,Communist Party College,Guangde 242200,China) Abstract:As a kind of broad and deep mathematical phenomenon,fixed point has penetrated into all fields of math- ematics.This paper extends the fixed point to the logical thinking.It proves that Russell's paradox is the fixed term in accordance with the set theory.It also proves that Godel's undecidable proposition is the fixed term within the natural number system N.The term formed by Cantor's diagonal method is fixed term and undecidable Turning is also fixed term.Furthermore,it can be proven that when a known set U is divided into a positive set and an inverse set and if the fixed term is neither in the positive set nor in the inverse set,then this fixed term must be that outside U.Thus,it is an inherent phenomenon of the system that the logical property of the fixed term excluded from Uhas changed relative to Uand the theorem of fixed term outside U is undecidable.In addition,there are also fixed terms in the natural number system N,where the existence and undecidability do not exert effect on the recursive nature of positive and inverse sets and the completeness of system.Therefore,the mathematical proof for Godel's theorem cannot be true and Cantor's diagonal method is proved to be false and Turning's halting problem is proved to be false.Whether the system N can be complete,real number is countable or not,whether Turning's halt problem can be decided should be reconsidered. Keywords:positive term;inverse term;fixed term;paradox;fixed term outside U;undecidable proposition;in- complete theorem;diagonal method;uncountable set;halting problem 收稿日期：2013-11-26. 通信作者：张金成.E-mail:656790205@qg.com
第 ９ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．５ ２０１４ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３１００７６ 逻辑及数学演算中的不动项与不可判定命题（Ⅱ） 张金成 （中央党校函授学院 广德教学点，安徽 广德 ２４２２００） 摘 要：不动点是一个广泛而深刻的数学现象，它已经渗透到数学的各个领域。 文中把不动点推广到逻辑思维领 域，证明 Ｒｕｓｓｅｌ 悖论是集合论中的不动项，Ｇöｄｅｌ 不可判定命题是自然数系统 Ｎ 中的不动项，Ｃａｎｔｏｒ 对角线方法构造 的项是不动项，不可判定的 Ｔｕｒｉｎｇ 机也是不动项。 进一步可以证明，当一个已知集合 Ｕ 可以分割成正、反集合时，不 动项不在正集或反集之中，不动项一定是 Ｕ 外不动项， Ｕ 外不动项的逻辑性质相对于 Ｕ 已经发生变异，是未定义项， Ｕ 外不动项命题是不可判定的，这是系统的固有现象。 自然数系统 Ｎ 中同样存在不动项，不动项的存在与不可判 定，并不影响正、反集合的递归性与系统的完全性，因此，Ｇöｄｅｌ 不完全定理的证明不成立，Ｃａｎｔｏｒ 对角线方法证明是 错误的，Ｔｕｒｉｎｇ 停机问题证明也是错误的。 “系统 Ｎ 能否完全”、实数是否可数、Ｔｕｒｉｎｇ 停机问题是否可判定都必须 重新思考。 关键词：正项；反项；不动项；悖论； Ｕ 外不动项；不可判定命题；不完全定理；对角线方法；不可数；停机问题。 中图分类号： Ｂ８１３； ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０５⁃０６１８⁃１４ 中文引用格式：张金成． 逻辑及数学演算中的不动项与不可判定命题（Ⅱ）［Ｊ］． 智能系统学报， ２０１４， ９（５）： ６１８⁃６３１． 英文引用格式：ＺＨＡＮＧ Ｊｉｎｃｈｅｎｇ． Ｆｉｘｅｄ ｔｅｒｍｓ ａｎｄ ｕｎｄｅｃｉｄａｂｌｅ ｐｒｏｐｏｓｉｔｉｏｎｓ ｉｎ ｌｏｇｉｃａｌ ａｎｄ ｍａｔｈｅｍａｔｉｃａｌ ｃａｌｃｕｌｕｓ （Ⅱ） ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（５）： ６１８⁃６３１． Ｆｉｘｅｄ ｔｅｒｍｓ ａｎｄ ｕｎｄｅｃｉｄａｂｌｅ ｐｒｏｐｏｓｉｔｉｏｎｓ ｉｎ ｌｏｇｉｃａｌ ａｎｄ ｍａｔｈｅｍａｔｉｃａｌ ｃａｌｃｕｌｕｓ （Ⅱ） ＺＨＡＮＧ Ｊｉｎｃｈｅｎｇ （Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ Ｓｃｈｏｏｌ， Ｃｏｍｍｕｎｉｓｔ Ｐａｒｔｙ Ｃｏｌｌｅｇｅ， Ｇｕａｎｇｄｅ ２４２２００， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｓ ａ ｋｉｎｄ ｏｆ ｂｒｏａｄ ａｎｄ ｄｅｅｐ ｍａｔｈｅｍａｔｉｃａｌ ｐｈｅｎｏｍｅｎｏｎ， ｆｉｘｅｄ ｐｏｉｎｔ ｈａｓ ｐｅｎｅｔｒａｔｅｄ ｉｎｔｏ ａｌｌ ｆｉｅｌｄｓ ｏｆ ｍａｔｈ⁃ ｅｍａｔｉｃｓ． Ｔｈｉｓ ｐａｐｅｒ ｅｘｔｅｎｄｓ ｔｈｅ ｆｉｘｅｄ ｐｏｉｎｔ ｔｏ ｔｈｅ ｌｏｇｉｃａｌ ｔｈｉｎｋｉｎｇ． Ｉｔ ｐｒｏｖｅｓ ｔｈａｔ Ｒｕｓｓｅｌｌ’ｓ ｐａｒａｄｏｘ ｉｓ ｔｈｅ ｆｉｘｅｄ ｔｅｒｍ ｉｎ ａｃｃｏｒｄａｎｃｅ ｗｉｔｈ ｔｈｅ ｓｅｔ ｔｈｅｏｒｙ． Ｉｔ ａｌｓｏ ｐｒｏｖｅｓ ｔｈａｔ Ｇöｄｅｌ’ ｓ ｕｎｄｅｃｉｄａｂｌｅ ｐｒｏｐｏｓｉｔｉｏｎ ｉｓ ｔｈｅ ｆｉｘｅｄ ｔｅｒｍ ｗｉｔｈｉｎ ｔｈｅ ｎａｔｕｒａｌ ｎｕｍｂｅｒ ｓｙｓｔｅｍ Ｎ． Ｔｈｅ ｔｅｒｍ ｆｏｒｍｅｄ ｂｙ Ｃａｎｔｏｒ’ｓ ｄｉａｇｏｎａｌ ｍｅｔｈｏｄ ｉｓ ｆｉｘｅｄ ｔｅｒｍ ａｎｄ ｕｎｄｅｃｉｄａｂｌｅ Ｔｕｒｎｉｎｇ ｉｓ ａｌｓｏ ｆｉｘｅｄ ｔｅｒｍ． Ｆｕｒｔｈｅｒｍｏｒｅ， ｉｔ ｃａｎ ｂｅ ｐｒｏｖｅｎ ｔｈａｔ ｗｈｅｎ ａ ｋｎｏｗｎ ｓｅｔ Ｕ ｉｓ ｄｉｖｉｄｅｄ ｉｎｔｏ ａ ｐｏｓｉｔｉｖｅ ｓｅｔ ａｎｄ ａｎ ｉｎｖｅｒｓｅ ｓｅｔ ａｎｄ ｉｆ ｔｈｅ ｆｉｘｅｄ ｔｅｒｍ ｉｓ ｎｅｉｔｈｅｒ ｉｎ ｔｈｅ ｐｏｓｉｔｉｖｅ ｓｅｔ ｎｏｒ ｉｎ ｔｈｅ ｉｎｖｅｒｓｅ ｓｅｔ， ｔｈｅｎ ｔｈｉｓ ｆｉｘｅｄ ｔｅｒｍ ｍｕｓｔ ｂｅ ｔｈａｔ ｏｕｔｓｉｄｅ Ｕ ． Ｔｈｕｓ， ｉｔ ｉｓ ａｎ ｉｎｈｅｒｅｎｔ ｐｈｅｎｏｍｅｎｏｎ ｏｆ ｔｈｅ ｓｙｓｔｅｍ ｔｈａｔ ｔｈｅ ｌｏｇｉｃａｌ ｐｒｏｐｅｒｔｙ ｏｆ ｔｈｅ ｆｉｘｅｄ ｔｅｒｍ ｅｘｃｌｕｄｅｄ ｆｒｏｍ Ｕ ｈａｓ ｃｈａｎｇｅｄ ｒｅｌａｔｉｖｅ ｔｏ Ｕ ａｎｄ ｔｈｅ ｔｈｅｏｒｅｍ ｏｆ ｆｉｘｅｄ ｔｅｒｍ ｏｕｔｓｉｄｅ Ｕ ｉｓ ｕｎｄｅｃｉｄａｂｌｅ． Ｉｎ ａｄｄｉｔｉｏｎ， ｔｈｅｒｅ ａｒｅ ａｌｓｏ ｆｉｘｅｄ ｔｅｒｍｓ ｉｎ ｔｈｅ ｎａｔｕｒａｌ ｎｕｍｂｅｒ ｓｙｓｔｅｍ Ｎ， ｗｈｅｒｅ ｔｈｅ ｅｘｉｓｔｅｎｃｅ ａｎｄ ｕｎｄｅｃｉｄａｂｉｌｉｔｙ ｄｏ ｎｏｔ ｅｘｅｒｔ ｅｆｆｅｃｔ ｏｎ ｔｈｅ ｒｅｃｕｒｓｉｖｅ ｎａｔｕｒｅ ｏｆ ｐｏｓｉｔｉｖｅ ａｎｄ ｉｎｖｅｒｓｅ ｓｅｔｓ ａｎｄ ｔｈｅ ｃｏｍｐｌｅｔｅｎｅｓｓ ｏｆ ｓｙｓｔｅｍ． Ｔｈｅｒｅｆｏｒｅ， ｔｈｅ ｍａｔｈｅｍａｔｉｃａｌ ｐｒｏｏｆ ｆｏｒ Ｇöｄｅｌ’ｓ ｔｈｅｏｒｅｍ ｃａｎｎｏｔ ｂｅ ｔｒｕｅ ａｎｄ Ｃａｎｔｏｒ’ｓ ｄｉａｇｏｎａｌ ｍｅｔｈｏｄ ｉｓ ｐｒｏｖｅｄ ｔｏ ｂｅ ｆａｌｓｅ ａｎｄ Ｔｕｒｎｉｎｇ’ｓ ｈａｌｔｉｎｇ ｐｒｏｂｌｅｍ ｉｓ ｐｒｏｖｅｄ ｔｏ ｂｅ ｆａｌｓｅ． Ｗｈｅｔｈｅｒ ｔｈｅ ｓｙｓｔｅｍ Ｎ ｃａｎ ｂｅ ｃｏｍｐｌｅｔｅ， ｒｅａｌ ｎｕｍｂｅｒ ｉｓ ｃｏｕｎｔａｂｌｅ ｏｒ ｎｏｔ， ｗｈｅｔｈｅｒ Ｔｕｒｎｉｎｇ’ｓ ｈａｌｔ ｐｒｏｂｌｅｍ ｃａｎ ｂｅ ｄｅｃｉｄｅｄ ｓｈｏｕｌｄ ｂｅ ｒｅｃｏｎｓｉｄｅｒｅｄ． Ｋｅｙｗｏｒｄｓ：ｐｏｓｉｔｉｖｅ ｔｅｒｍ； ｉｎｖｅｒｓｅ ｔｅｒｍ； ｆｉｘｅｄ ｔｅｒｍ； ｐａｒａｄｏｘ； ｆｉｘｅｄ ｔｅｒｍ ｏｕｔｓｉｄｅ Ｕ ； ｕｎｄｅｃｉｄａｂｌｅ ｐｒｏｐｏｓｉｔｉｏｎ； ｉｎ⁃ ｃｏｍｐｌｅｔｅ ｔｈｅｏｒｅｍ； ｄｉａｇｏｎａｌ ｍｅｔｈｏｄ； ｕｎｃｏｕｎｔａｂｌｅ ｓｅｔ； ｈａｌｔｉｎｇ ｐｒｏｂｌｅｍ 收稿日期：２０１３⁃１１⁃２６． 通信作者：张金成．Ｅ⁃ｍａｉｌ：６５６７９０２０５＠ ｑｑ．ｃｏｍ．
第5期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·619 表1单一正集上“蕴含”的真值 4正反命题与谓词演算系统 Table 1 The truth value table of "implication"for the sin- gle positive se 4.1正反命题演算系统L“ Ata AAta 在经典系统L上引入“正反集对偶变换公理 0 P+“Pa”,组建一个新的逻辑系统一命题系 0 1 统L“: 表2单一正集上“否定”的真值 1)初始符号（略）； Table 2 The truth value table of "negation"for the single 2)命题的形成规则（略）： positive se 3)定义（略）； ta B*a A*a→B*a 4)公理。 0 0 (1)正集公理 1 1 1 L1+:A→(Ba→A): 00 1 L2*:(Aa→(B*a→C*a))→ 0 1 1 (Aa→Ba)→(Aa→C+)); 定义3单一反集上的真值表（如表3、4）。 L3*:(A→B*m)→ 表3单一反集上“蕴含”的真值 Table 3 The truth value table of "implication"for the sin- ((Aa→B*a)→Ata)》 gle inverse se (2)正反集对偶变换公理 A-a 7A4 L0:PP“(P是+a,-α的一个完全划分)： 1 0 (3)反集公理 0 L1:Aa→(Ba→A-a): 表4单一正集上“否定”的真值 L2:(Aa→(B-a→C-))→ Table 4 The truth value table of "negation"for the single (A→B“)→(Aa→C-a): positive se L3:(Aa→B-“)→((A-→B“)→A-“) A- B-4 Aa→B4 5)演绎推理规则 S 0 分离规则：若上A且上A→B;则上B; 1 1 1 定义1系统L“ 0 0 1 由以上1)~5)几个部分组成的公理系统，可以 叫做系统L“。 0 定理1经典逻辑的定理封闭域上的有效性 定义4跨正反集上的真值表（如表5）。 在系统L“中，相同集+α，一α中的命题演算， 表5跨正反集上的真值表 所有经典逻辑的定理与演算模式都是有效的。 Table 5 The truth value table for the crossing the positive and inverse sets 证明略。 pta pa 定理2正、反集上的等价替换 1 0 系统L中，设F(M,N)表示含有变项M、N的 命题公式，则如果在相同集中的经典命题上F(P, 0 1 p)成立（即上F(Pa,P+)且上F(P-a, 在表中可以看出经典二值真值表定义仍然不 P“)成立)，则在不同集中上F(P“,P-“),且 变，增加了一个跨正反集上的真值表定义。 上F(一Pa,P)也成立。 在系统L“中，利用以上“真值表”可以证明，下 证明略。 列公式是不可证的。 系统L“的语义很简单，用二值真值表定义为 公式Pa,P-a上Ba,Pa∧P-a上Ba, 定义2单一正集上的真值表 pa→(Pa→B),Pa→(p-a→B") 都不是系统L的定理
４ 正反命题与谓词演算系统 ４．１ 正反命题演算系统 Ｌ α 在经典系统 Ｌ 上引入“正反集对偶变换公理 Ｐ ＋α↔¬ Ｐ －α ”，组建一个新的逻辑系统———命题系 统 Ｌ α ： １）初始符号（略）； ２）命题的形成规则（略）； ３）定义（略）； ４）公理。 （１）正集公理 Ｌ１ ＋ ：Ａ ＋α → （Ｂ ＋α → Ａ ＋α ）； Ｌ２ ＋ ：（Ａ ＋α → （Ｂ ＋α → Ｃ ＋α ）） → （（Ａ ＋α → Ｂ ＋α ） → （Ａ ＋α → Ｃ ＋α ））； Ｌ３ ＋ ：（¬ Ａ ＋α → ¬ Ｂ ＋α ） → （（¬ Ａ ＋α → Ｂ ＋α ） → Ａ ＋α ） （２）正反集对偶变换公理 Ｌ０： Ｐ ＋α↔¬ Ｐ －α （ Ｐ 是 ＋ α， － α 的一个完全划分）； （３）反集公理 Ｌ１ － ： Ａ －α → （Ｂ －α → Ａ －α ）； Ｌ２ － ： （Ａ －α → （Ｂ －α → Ｃ －α ）） → （（Ａ －α → Ｂ －α ） → （Ａ －α → Ｃ －α ））； Ｌ３ － ：（¬ Ａ －α → ¬ Ｂ －α ） → （（¬ Ａ －α → Ｂ －α ） → Ａ －α ） ５）演绎推理规则 分离规则：若├ Ａ 且├ Ａ → Ｂ ；则├ Ｂ ； 定义 １ 系统 Ｌ α 由以上 １） ～５）几个部分组成的公理系统，可以 叫做系统 Ｌ α 。 定理 １ 经典逻辑的定理封闭域上的有效性 在系统 Ｌ α 中，相同集 ＋ α， － α 中的命题演算， 所有经典逻辑的定理与演算模式都是有效的。 证明 略。 定理 ２ 正、反集上的等价替换 系统 Ｌ α 中，设 Ｆ（Ｍ，Ｎ） 表示含有变项 Ｍ、Ｎ 的 命题公式，则如果在相同集中的经典命题 ├ Ｆ（Ｐ α ， ¬ Ｐ α ） 成 立 （ 即 ├ Ｆ（Ｐ ＋α ，¬ Ｐ ＋α ） 且 ├ Ｆ（Ｐ －α ， ¬ Ｐ －α ） 成立），则在不同集中 ├ Ｆ（Ｐ ＋α ，Ｐ －α ） ，且 ├Ｆ（¬ Ｐ －α ，¬ Ｐ ＋α ） 也成立。 证明 略。 系统 Ｌ α 的语义很简单，用二值真值表定义为 定义 ２ 单一正集上的真值表 表 １ 单一正集上“蕴含”的真值 Ｔａｂｌｅ １ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｏｆ “ｉｍｐｌｉｃａｔｉｏｎ” ｆｏｒ ｔｈｅ ｓｉｎ⁃ ｇｌｅ ｐｏｓｉｔｉｖｅ ｓｅ Ａ ＋α ¬ Ａ ＋α １ ０ ０ １ 表 ２ 单一正集上“否定”的真值 Ｔａｂｌｅ ２ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｏｆ “ｎｅｇａｔｉｏｎ” ｆｏｒ ｔｈｅ ｓｉｎｇｌｅ ｐｏｓｉｔｉｖｅ ｓｅ Ａ ＋α Ｂ ＋α Ａ ＋α → Ｂ ＋α １ ０ ０ １ １ １ ０ ０ １ ０ １ １ 定义 ３ 单一反集上的真值表（如表 ３、４）。 表 ３ 单一反集上“蕴含”的真值 Ｔａｂｌｅ ３ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｏｆ “ｉｍｐｌｉｃａｔｉｏｎ” ｆｏｒ ｔｈｅ ｓｉｎ⁃ ｇｌｅ ｉｎｖｅｒｓｅ ｓｅ Ａ －α ¬ Ａ －α １ ０ ０ １ 表 ４ 单一正集上“否定”的真值 Ｔａｂｌｅ ４ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｏｆ “ｎｅｇａｔｉｏｎ” ｆｏｒ ｔｈｅ ｓｉｎｇｌｅ ｐｏｓｉｔｉｖｅ ｓｅ Ａ －α Ｂ －α Ａ －α → Ｂ －α １ ０ ０ １ １ １ ０ ０ １ ０ １ １ 定义 ４ 跨正反集上的真值表（如表 ５）。 表 ５ 跨正反集上的真值表 Ｔａｂｌｅ ５ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｆｏｒ ｔｈｅ ｃｒｏｓｓｉｎｇ ｔｈｅ ｐｏｓｉｔｉｖｅ ａｎｄ ｉｎｖｅｒｓｅ ｓｅｔｓ Ｐ ＋α Ｐ －α １ ０ ０ １ 在表中可以看出经典二值真值表定义仍然不 变，增加了一个跨正反集上的真值表定义。 在系统 Ｌ α 中，利用以上“真值表”可以证明，下 列公式是不可证的。 公式 Ｐ ＋α ，¬ Ｐ －α ├ Ｂ ＋α ， Ｐ ＋α ∧ ¬ Ｐ －α ├ Ｂ －α ， Ｐ ＋α → （¬ Ｐ －α → Ｂ ＋α ） ， Ｐ ＋α → （¬ Ｐ －α → Ｂ －α ） 都不是系统 Ｌ α 的定理［３］ 。 第 ５ 期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·６１９·
·620· 智能系统学报 第9卷 4.2正反谓词演算系统K 3(x)PaH(x)P-。 1)基本符号（略） Y(x)p-+(x)P*; 2)定义（略） H(x)Pa→3(x)Pa; 3)公理 V(x)P-a3(x)P+“; (1)正集公理 3(x)P-a3(x)P“; K1*:A*a→(B*a→A); 3(x)p-+Y(x)p+a; K2*:(Aa→(B*a→C*a))→ 3(x)P(x)P"。 ((Aa→B)→(A“→Ca)): K的语义解释（略）[] K3*:(Aa→7B“)→(B→A“); 4.3系统L、的完全性与不可判定命题 K4:(x:)Aa→A“: 根据“Pa→一Pa,PaPa”可以得到， K5:H(x:)A(x:)一A(t); 任一个含有-反集的命题公式全部可以转化成正 K6*:(x)(A→B)→(A0→H(x:)B“); 集+α命题公式，即可以转化成经典命题演算公式， (2)正反集对偶变换公理 即以上正反命题演算系统L“与经典命题演算系统L KO:PanP-“(P是+a,-α的一个对称划分)； 等价。 (3)反集公理 注记1P°是U外不动项命题，是未定义命 K1:Aa→(Ba→Aa）; 题，不参与演算。 K2:(A-→(B-a→C-a)）→ 定理5L“等价系统 (A→B)→(A0→C-): 系统L“在+α与一α中的全部公式可以翻译成 K3:(Aa→B-）→(Ba→A“): 经典命题演算系统L的公式，即系统L“在+α与 K4:H(x:)Aa→Aa; -α中与经典命题演算系统L等价。 证明略 K5:(x:)A(x)→A(t); 定理6K等价系统 K6:H(x:)(A-a→B-a)→(Aa→H(x)B-): 系统K中全部公式可翻译成经典谓词演算系 4)系统内推理规则 统的公式，即系统K与经典谓词演算系统K等价。 R1分离规则：若上A且A→B,则上B; 证明略 2概括规则：若上A,则上Hx,A。 由于系统K与经典谓词演算系统K等价，所以 定义5系统K 经典逻辑的元定理在系统K“仍然成立，根据“定理 由以上1)~4)几个部分组成的公理系统，叫做 5、6”很容易证明以下定理。证明方法同经典谓词 系统K。 逻辑系统方法，这里不再给出。 在系统K中，具有与L“类似的定理（证明与L“ 系统L的一致性、可判定性、完全性等元定理， 相同)，即： 在系统L“中都是有效的； 定理3经典逻辑的定理封闭域上的有效性 系统K的一致性、不可判定性、完全性等元定 在系统K中，相同集+，一α中的命题演算， 理，在系统中都是有效的： 所有经典逻辑的定理与演算模式都是有效的。 定理7P是域外命题 定理4正、反集上的等价替换 命题P在系统L中是未定义命题，是域外命 系统K中，设F(M,N)表示含有变项M、N的 题： 命题公式，则如果在相同集中的经典命题F(P“, 证明设P是U的一个完全划分， P)成立（即F(P+“,P“)且F(P-a,P-)成 在命题演算L中，若+a=-a=e(P是+a, 立)，则在不同集中F(P“,P-“),且上F(P-“, -a的一个完全划分)，PP;e={xp}是不动 Pa)也成立。 项，xp年U是未定义项，因此P是未定义命题。 在不同集中，含有量词的公式，可以用下列公式 因此，在命题演算L中，若+a=-a=e,则P 转换： 是不动命题，e,P在U上无定义； (x)Pa→H(x)P-“; 未定义命题与其他命题的混合演算，如P∧ H(x)P+a+3(x)P-“; P→Qa;P∧P→Qa;PVP;(PV Y(x)P*+3(x)P-; P)∧(PaVP-a)等都是无意义的，不合法的。 3(x)P++3(x)P-“; 定理8系统L“完全性定理 3(x)P*+Y(x)P-a; 在系统L中，若上P或V(P)=1则L上P;
４．２ 正反谓词演算系统 Ｋ α １）基本符号（略） ２）定义（略） ３）公理 （１）正集公理 Ｋ１ ＋ ：Ａ ＋α → （Ｂ ＋α → Ａ ＋α ）； Ｋ２ ＋ ：（Ａ ＋α → （Ｂ ＋α → Ｃ ＋α ）） → （（Ａ ＋α → Ｂ ＋α ） → （Ａ ＋α → Ｃ ＋α ））； Ｋ３ ＋ ：（¬ Ａ ＋α → ¬ Ｂ ＋α ） → （Ｂ ＋α → Ａ ＋α ）； Ｋ４ ＋ ：∀（ｘｉ）Ａ ＋α → Ａ ＋α ； Ｋ５ ＋ ：∀（ｘｉ）Ａ ＋α （ｘｉ） → Ａ ＋α （ｔ）； Ｋ６ ＋ ：∀（ｘｉ）（Ａ ＋α → Ｂ ＋α ） → （Ａ ＋α → ∀（ｘｉ）Ｂ ＋α ）； （２）正反集对偶变换公理 Ｋ０：Ｐ ＋α↔¬ Ｐ －α （Ｐ 是 ＋ α， － α 的一个对称划分）； （３）反集公理 Ｋ１：Ａ －α → （Ｂ －α → Ａ －α ）； Ｋ２： （Ａ －α → （Ｂ －α → Ｃ －α ）） → （（Ａ －α → Ｂ －α ） → （Ａ －α → Ｃ －α ））； Ｋ３： （¬ Ａ －α → ¬ Ｂ －α ） → （Ｂ －α → Ａ －α ）； Ｋ４：∀（ｘｉ）Ａ －α → Ａ －α ； Ｋ５：∀（ｘｉ）Ａ －α （ｘｉ） → Ａ －α （ｔ）； Ｋ６：∀（ｘｉ）（Ａ －α → Ｂ －α ） → （Ａ －α → ∀（ｘｉ）Ｂ －α ）； ４）系统内推理规则 Ｒ１ 分离规则：若├ Ａ 且├ Ａ → Ｂ ，则├ Ｂ ； Ｒ２ 概括规则：若├ Ａ ，则├ ∀ｘｉＡ 。 定义 ５ 系统 Ｋ α 由以上 １） ～４）几个部分组成的公理系统，叫做 系统 Ｋ α 。 在系统 Ｋ α 中，具有与 Ｌ α 类似的定理（证明与 Ｌ α 相同），即： 定理 ３ 经典逻辑的定理封闭域上的有效性 在系统 Ｋ α 中，相同集 ＋ α， － α 中的命题演算， 所有经典逻辑的定理与演算模式都是有效的。 定理 ４ 正、反集上的等价替换 系统 Ｋ α 中，设 Ｆ（Ｍ，Ｎ） 表示含有变项 Ｍ、Ｎ 的 命题公式，则如果在相同集中的经典命题 Ｆ（Ｐ α ， ¬ Ｐ α ） 成立（即 Ｆ（Ｐ ＋α ，¬ Ｐ ＋α ） 且 Ｆ（Ｐ －α ，¬ Ｐ －α ） 成 立），则在不同集中 Ｆ（Ｐ ＋α ，Ｐ －α ） ， 且 ├Ｆ（¬ Ｐ －α ， ¬ Ｐ ＋α ） 也成立。 在不同集中，含有量词的公式，可以用下列公式 转换： ∀（ｘ）Ｐ ＋α↔∀（ｘ）¬ Ｐ －α ； ∀（ｘ）Ｐ ＋α↔¬ ∃（ｘ）Ｐ －α ； ¬ ∀（ｘ）Ｐ ＋α↔∃（ｘ）Ｐ －α ； ∃（ｘ）Ｐ ＋α↔∃（ｘ）¬ Ｐ －α ； ∃（ｘ）Ｐ ＋α↔¬ ∀（ｘ）Ｐ －α ； ¬ ∃（ｘ）Ｐ ＋α↔∀（ｘ）Ｐ －α 。 ∀（ｘ）Ｐ －α↔∀（ｘ）¬ Ｐ ＋α ； ∀（ｘ）Ｐ －α↔¬ ∃（ｘ）Ｐ ＋α ； ¬ ∀（ｘ）Ｐ －α↔∃（ｘ）Ｐ ＋α ； ∃（ｘ）Ｐ －α↔∃（ｘ）¬ Ｐ ＋α ； ∃（ｘ）Ｐ －α↔¬ ∀（ｘ）Ｐ ＋α ； ¬ ∃（ｘ）Ｐ －α↔∀（ｘ）Ｐ ＋α 。 Ｋ α 的语义解释（略） ［３］ ４．３ 系统 Ｌ α 、 Ｋ α 的完全性与不可判定命题 根据“ Ｐ ＋α↔¬ Ｐ －α ， Ｐ －α↔¬ Ｐ ＋α ” 可以得到， 任一个含有 － α 反集的命题公式全部可以转化成正 集 ＋ α 命题公式，即可以转化成经典命题演算公式， 即以上正反命题演算系统 Ｌ α 与经典命题演算系统 Ｌ 等价。 注记 １ Ｐ ｅ 是 Ｕ 外不动项命题，是未定义命 题，不参与演算。 定理 ５ Ｌ α 等价系统 系统 Ｌ α 在 ＋ α 与 － α 中的全部公式可以翻译成 经典命题演算系统 Ｌ 的公式，即系统 Ｌ α 在 ＋ α 与 － α 中与经典命题演算系统 Ｌ 等价。 证明 略 定理 ６ Ｋ α 等价系统 系统 Ｋ α 中全部公式可翻译成经典谓词演算系 统的公式，即系统 Ｋ α 与经典谓词演算系统 Ｋ 等价。 证明 略 由于系统 Ｋ α 与经典谓词演算系统 Ｋ 等价，所以 经典逻辑的元定理在系统 Ｋ α 仍然成立，根据“定理 ５、６”很容易证明以下定理。 证明方法同经典谓词 逻辑系统方法，这里不再给出。 系统 Ｌ 的一致性、可判定性、完全性等元定理， 在系统 Ｌ α 中都是有效的； 系统 Ｋ 的一致性、不可判定性、完全性等元定 理，在系统 Ｋ α 中都是有效的； 定理 ７ Ｐ ｅ 是域外命题 命题 Ｐ ｅ 在系统 Ｌ α 中是未定义命题，是域外命 题； 证明 设 Ｐ 是 Ｕ 的一个完全划分， 在命题演算 Ｌ α 中，若 ＋ α ＝ － α ＝ ｅ （ Ｐ 是 ＋ α， － α 的一个完全划分）， Ｐ ｅ↔¬ Ｐ ｅ ； ｅ ＝ ｘＰ { } 是不动 项， ｘＰ ∉ Ｕ 是未定义项，因此 Ｐ ｅ 是未定义命题。 因此，在命题演算 Ｌ α 中，若 ＋ α ＝ － α ＝ ｅ ，则 Ｐ ｅ 是不动命题， ｅ ， Ｐ ｅ 在 Ｕ 上无定义； 未定义命题与其他命题的混合演算，如 Ｐ ｅ ∧ ¬ Ｐ ｅ → Ｑ ＋α ； Ｐ ｅ ∧ ¬ Ｐ ｅ → Ｑ －α ； Ｐ ｅ ∨ ¬ Ｐ ｅ ； （Ｐ ｅ ∨ ¬ Ｐ ｅ ） ∧ （Ｐ ＋α ∨ Ｐ －α ） 等都是无意义的，不合法的。 定理 ８ 系统 Ｌ α 完全性定理 在系统 Ｌ α 中，若 ｜＝Ｐ α 或 Ｖ（Ｐ α ） ＝ １ 则 Ｌ α ├ Ｐ α ； ·６２０· 智 能 系 统 学 报 第 ９ 卷
第5期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·621. 证明因为L“L,而系统L是完全的，即： 合，经典逻辑的所有定理只适用于已经定义的集合 若P,则L上Pa:所以，若上P或V(pa)=1 U上。 则L上Pa; 证明设U=+αU-α是一个已定义集合； 所以，系统L“也是完全的。 假设在这个已定义集合外，可以适用经典逻辑 定理9P是不可判定命题 的所有定理，根据U外不动项定理， 命题P在系统L“中是不可判定命题（证明略， 那么，有矛盾命题P(xp)P(xp)成立； 因为不动命题是不可判定命题)。 根据邓一斯各特定理（上A,上一A,那么 注记2悖论P不参与系统演算 上B),这个逻辑系统中一切命题都是定理，这是一 1)虽然系统L中出现了悖论P,但是，P是 个崩溃的系统； 未定义命题，不参与系统演算，不会导致系统L“演 所以，经典逻辑的所有定理只适用于已经定义 算崩遗，系统L“仍然是有效的。 的集合U上。 2)虽然系统L“中出现了不可判定P,但是，P 定理14“反证法”的适用范围 与系统完全性无关，系统L“仍然是完全的，系统L“ U={x,x2,x3,…,x,…}是一个已经定义集 的定理集合是可判定的。 合，“反证法”只适用于已经定义的集合U上。 定理10P(xp)是域外命题 证明因为，反证法是经典逻辑的一条定理， 命题P(xp)在系统K中是未定义命题； 即：如果A上B且A上B,那么上A; 根据定理13，“反证法”只适用于已经定义的集 证明同上，在谓词演算中，若x:=x:=xp,则 合U上。 P(xp)是不动命题，xp、P(xp)在U上无定义。 定理15不动项矛盾用于“反证法”的限制 与系统L一样，未定义命题P(x)与其他命题 U={x1,x2,x3,…,xn,…}是一个已经定义集 的混合演算，如P(xp)A一P(x)、P(xp)A 合，不动项矛盾不能作为“反证法”在已定义的集合 P(xp)→Q(x:)、P(xp)VP(xp)等都是无意 U上的推理依据。 义的，不合法的。 证明因为根据U外不动项定理，不动项矛盾 定理11系统完全性定理 是已定义集合外的矛盾： 系统K中，若=Pa或V(Pa)=1则a上P; 假设不动项矛盾能作为“反证法”在已定义的 证明因为K“一K,而系统K是完全的，即 集合上的推理依据。 若P,则K上pm;所以，若=Pa或V(P)=1 那么，有矛盾命题P(xp)P(xp)成立，而且 则K上P; 这是一个U外恒成立的矛盾； 所以，系统K也是完全的。 根据邓一斯各特定理（上A,上A,那么 定理12P(xp)是不可判定命题 上B),这个逻辑系统中一切命题都是定理，这是一 命题P(xp)在系统K中是不可判定命题（证 个崩溃的系统： 明略，因为不动命题是不可判定命题)。 如果不动项矛盾能作为“反证法”在已定义的集合 注记3悖论P(xp)不参与系统演算 U上的推理依据，将建立不起来任何足道的系统： 1)虽然系统K中出现了悖论P(xp),但是， 所以，不动项矛盾不能作为“反证法”在已定义 P(x)是未定义命题，不参与系统演算，不会导致系 的集合U上的推理依据。 统K演算崩溃，系统仍然是有效的。 在逻辑系统L“、中，若U= 2)虽然系统K中出现了不可判定P(xp),但是， {x1,x2,x3,…,xn,…}是已定义集合，P是U上的任 P(xp)与系统完全性无关，系统K仍是完全的。 意一个有定义的性质，若x:∈U,则P(x:)、一P(x:) 4.4经典逻辑定理的适用范围 是有定义、有意义的命题；若x:U,则P(x:)、 定义6超协调逻辑系统 P(x:)是无定义、无意义的命题。 正反命题演算系统“L“”与正反谓词系统 推论1构造悖论，不能作为“反证法”在已定 “”也称超协调逻辑系统。 义的集合U上的推理依据。 在超协调系统中，可以发现经典逻辑是定义在 例1构造悖论的错误证明方法 一个已知集合U上的，不能无限制地使用到U外， 举出一个具体的例子，U为全体整数集合U= 经典逻辑的推理有一个使用范围。 J,假设在n=n中，任意n∈J;把U=J分成偶数 定理13经典逻辑的适用范围 集合与奇数集合： U={x1,x2,x3,…,xn,…}是一个已经定义集 +a={x|x=2n,n∈U}
证明 因为 Ｌ α⇔Ｌ ，而系统 Ｌ 是完全的，即： 若 ｜＝Ｐ α ，则 Ｌ ├ Ｐ α ；所以，若 ├Ｐ α 或 Ｖ（Ｐ α ） ＝ １ 则 Ｌ α ├ Ｐ α ； 所以，系统 Ｌ α 也是完全的。 定理 ９ Ｐ ｅ 是不可判定命题 命题 Ｐ ｅ 在系统 Ｌ α 中是不可判定命题（证明略， 因为不动命题是不可判定命题）。 注记 ２ 悖论 Ｐ ｅ 不参与系统演算 １）虽然系统 Ｌ α 中出现了悖论 Ｐ ｅ ，但是， Ｐ ｅ 是 未定义命题，不参与系统演算，不会导致系统 Ｌ α 演 算崩溃，系统 Ｌ α 仍然是有效的。 ２）虽然系统 Ｌ α 中出现了不可判定 Ｐ ｅ ，但是， Ｐ ｅ 与系统完全性无关，系统 Ｌ α 仍然是完全的，系统 Ｌ α 的定理集合是可判定的。 定理 １０ Ｐ（ｘＰ ） 是域外命题 命题 Ｐ（ｘＰ ） 在系统 Ｋ α 中是未定义命题； 证明同上，在谓词演算中，若 ｘｉ ＝ ｘｉ ＝ ｘＰ ，则 Ｐ（ｘＰ ） 是不动命题， ｘＰ 、 Ｐ（ｘＰ ） 在 Ｕ 上无定义。 与系统 Ｌ α 一样，未定义命题 Ｐ（ｘＰ ） 与其他命题 的混 合 演 算， 如 Ｐ（ｘＰ ） ∧ ¬ Ｐ（ｘｉ） 、 Ｐ（ｘＰ ） ∧ ¬ Ｐ（ｘＰ ） → Ｑ（ｘｉ） 、 Ｐ（ｘＰ ） ∨ ¬ Ｐ（ｘＰ ） 等都是无意 义的，不合法的。 定理 １１ 系统 Ｋ α 完全性定理 系统 Ｋ α 中，若 ｜＝Ｐ α 或 Ｖ（Ｐ α ） ＝ １ 则 Ｋ α ├ Ｐ α ； 证明 因为 Ｋ α⇔Ｋ ，而系统 Ｋ 是完全的，即 若 ｜＝Ｐ α ，则 Ｋ ├ Ｐ α ；所以，若 ｜＝Ｐ α 或 Ｖ（Ｐ α ） ＝ １ 则 Ｋ α ├ Ｐ α ； 所以，系统 Ｋ α 也是完全的。 定理 １２ Ｐ（ｘＰ ） 是不可判定命题 命题 Ｐ（ｘＰ ） 在系统 Ｋ α 中是不可判定命题（证 明略，因为不动命题是不可判定命题）。 注记 ３ 悖论 Ｐ（ｘＰ ） 不参与系统演算 １） 虽然系统 Ｋ α 中出现了悖论 Ｐ（ｘＰ ） ，但是， Ｐ（ｘＰ ） 是未定义命题，不参与系统演算，不会导致系 统 Ｋ α 演算崩溃，系统 Ｋ α 仍然是有效的。 ２）虽然系统 Ｋ α 中出现了不可判定 Ｐ（ｘＰ） ，但是， Ｐ（ｘＰ） 与系统完全性无关，系统 Ｋ α 仍是完全的。 ４．４ 经典逻辑定理的适用范围 定义 ６ 超协调逻辑系统 正反命题演算系统 “ Ｌ α ” 与正反谓词系统 “ Ｋ α ”也称超协调逻辑系统。 在超协调系统中，可以发现经典逻辑是定义在 一个已知集合 Ｕ 上的，不能无限制地使用到 Ｕ 外， 经典逻辑的推理有一个使用范围。 定理 １３ 经典逻辑的适用范围 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 是一个已经定义集 合，经典逻辑的所有定理只适用于已经定义的集合 Ｕ 上。 证明 设 Ｕ ＝ ＋ α ∪－ α 是一个已定义集合； 假设在这个已定义集合外，可以适用经典逻辑 的所有定理，根据 Ｕ 外不动项定理， 那么，有矛盾命题 Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） 成立； 根 据 邓—斯 各 特 定 理 （ ├ Ａ ， ├ ¬ Ａ ， 那 么 ├ Ｂ ），这个逻辑系统中一切命题都是定理，这是一 个崩溃的系统； 所以，经典逻辑的所有定理只适用于已经定义 的集合 Ｕ 上。 定理 １４ “反证法”的适用范围 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 是一个已经定义集 合，“反证法”只适用于已经定义的集合 Ｕ 上。 证明 因为，反证法是经典逻辑的一条定理， 即：如果 Ａ ├ Ｂ 且 Ａ ├ ¬ Ｂ ，那么├ ¬ Ａ ； 根据定理 １３，“反证法”只适用于已经定义的集 合 Ｕ 上。 定理 １５ 不动项矛盾用于“反证法”的限制 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 是一个已经定义集 合，不动项矛盾不能作为“反证法”在已定义的集合 Ｕ 上的推理依据。 证明 因为根据 Ｕ 外不动项定理，不动项矛盾 是已定义集合外的矛盾； 假设不动项矛盾能作为“反证法”在已定义的 集合上的推理依据。 那么，有矛盾命题 Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） 成立，而且 这是一个 Ｕ 外恒成立的矛盾； 根 据 邓—斯 各 特 定 理 （ ├ Ａ ， ├ ¬ Ａ ， 那 么 ├ Ｂ ），这个逻辑系统中一切命题都是定理，这是一 个崩溃的系统； 如果不动项矛盾能作为“反证法”在已定义的集合 Ｕ 上的推理依据，将建立不起来任何足道的系统； 所以，不动项矛盾不能作为“反证法”在已定义 的集合 Ｕ 上的推理依据。 在 逻 辑 系 统 Ｌ α 、Ｋ α 中， 若 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 是已定义集合， Ｐ 是 Ｕ 上的任 意一个有定义的性质，若 ｘｉ ∈ Ｕ ，则 Ｐ（ｘｉ）、¬ Ｐ（ｘｉ） 是有定义、有意义的命题；若 ｘｉ ∉ Ｕ ，则 Ｐ（ｘｉ）、 ¬ Ｐ（ｘｉ） 是无定义、无意义的命题。 推论 １ 构造悖论，不能作为“反证法”在已定 义的集合 Ｕ 上的推理依据。 例 １ 构造悖论的错误证明方法 举出一个具体的例子， Ｕ 为全体整数集合 Ｕ ＝ Ｊ， 假设在 ｎ ＝ ｎ 中，任意 ｎ ∈ Ｊ ； 把 Ｕ ＝ Ｊ 分成偶数 集合与奇数集合： ＋ α ＝ {ｘ ｜ ｘ ＝ ２ｎ，ｎ ∈ Ｕ} 第 ５ 期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·６２１·
.622. 智能系统学报 第9卷 -a={xlx=1-2n,n∈U} 在假设M~PM中，任意x∈M对应一个y∈ P(x)代表谓词“x是偶数”，一P(x)代表谓词“x PM,即：x∈M→y∈PM, 是奇数”；n∈+a,或者n∈-a;定义一个新数 y是M的子集之一，yCM, T=1-n;自指代T=n,n=1-n,n是偶数n是 x∈y,或者x庄y;规定：x∈yx生T;x生 奇数；产生悖论，不可判定命题P(n)P(n);即 y→xeT; n=n FP(n)P(n) 假定T∈PM,M~PM,存在 根据反证法得到，十n≠n,这显然是荒唐的结论。 xo∈M→T∈PM; 例2相对无意义的命题 按规定：x0∈T→x0使T;x0生T→x0∈T; 设U为全体整数集合，P(x):表示x是偶数； 矛盾，所以，TPM。 则P(0),P(2),P(7),…等都是有定义、有意义的 注：这证明在很多“数理逻辑”书中都可以见 2 命题：P(,P(了)，P(),…都是无定义、无意 到，如《元数学导论》。 5.1无穷集合演算中的不动项 义的命题。 在以上证明过程中，构造的集合T,如果按照 U={x1,x2,x3,…,xn,…}是一个已经定义集 正反集合分析法，实际上是一个不动项，证明如下。 合，如果A上P(x;)AP(x),且x:∈U,可以使 定理16无穷集合演算中存在不动项 用“反证法”，上一A,这是正确的证明方法。 如果无穷集合与它的幂集合之间能建立一一映 注记5“反证法”的正确推理形式 射，那么，幂集合演算中存在一个不动项。 一般地，设U=+αU-a是一个已定义集合， 证明首先把以上证明过程，整理如下： x:∈U,K(x)是U内的任意一个命题，根据U外不 假设在双射关系F:M~PM中，任意x∈M对 动项定理，上P(xp)P(xp)。 应一个F(x)∈PM, 1)U外不动项所产生的矛盾，使用“反证法”只 即：x∈MF(x)∈PM,F(x))是M的子集 能得出xp主U。即把xp∈U看成假设时，可以使 之一，F(x)SM; 用“反证法”进行推理，正确的推理形式是： x∈F(x),或者xF(x); K(x;),%p EUFP(xp)P(xp), 规定：x∈F(x)x生TM: 上(xp∈U)。 x生F(x)x∈TM; 2)U外不动项所产生的矛盾，不能作为任何“U 假定TM∈PM,M~PM,存在 内演算的推理依据”即把xp∈U看成真命题时，使用 xo∈MF(xo)∈PM,(设TM=F(xo); “反证法”是错误的。不正确的推理形式是： 按规定：x0∈F(xo)x0生F(xo);x0 K(x;)FP(xp)P(xp),HK(x;) F(xo)x∈F(xo)。再把PM分为正反集合，设： 3)一般使用“自指代”所产生的矛盾，都是域外 +a={X:x∈M,x∈X,X∈PM,X=F(x)} 矛盾，不能作为反证法的依据。 -a={X:x∈M,xX,X∈PM,X=F(x)} 可以回顾一下，历史上“直觉主义”者，也认识到 U=PM=+aU-a 无限制地使用“反证法”会有问题，他们转向完全的 按规定：x∈F(x)x生TM;x生F(x)x∈ “构造数学”，他们也看到一些问题，但是，没有把问题 TM,自我指代：TM=F(xo),即xo∈F(xo)→x0 完全搞清。这里真正看到“反证法”的使用范围。 F(x),x0∈TM→x0生TM,P[F(x)]表示x∈ 5无穷集合的幂集中的不可判定命题 F(x);则P[F(x)]表示x生F(x)。 命题x0∈F(xo)x生F(x),TM=F(xo）, 集合论的创立者Cantor证明：无穷集合的幂集 可以表示为P(TM)P(TM);TM是不动项。 合不能与原来的集合建立一一对应关系。可以回顾 如果(TM∈PM),则有悖论 一下其证明过程，使用Cantor的对角线方法。 P(Tu)P(TM);即：如果双射关系F:M~PM 如果PM为M的幂集，且M~PM(M与PM之 成立，那么，T是不动项。 间可以建立一一对应关系，即双射关系)，则存在 这是“Cantor的对角线方法”证明，在这个证明 T,TCM,且TPM。 中，他把T,看成是一个已知项TM∈U,实际上 对于一个M子集而言，如果能够决定M的元素 TM∈U未必成立，他只证明了以下结果： 中哪些属于该子集，那么M的子集就确定了。可以 如果双射关系F:M~PM成立，且TM∈U,那 给出一个一般准则，由它可以对M的任何元素x,决 么，P(TM)nP(TM);即(F:M~PM)A(TM∈ 定该元素是否属于该子集。 U)上P(Tg)P(TM)o
－ α ＝ {ｘ ｜ ｘ ＝ １ － ２ｎ，ｎ ∈ Ｕ} Ｐ（ｘ） 代表谓词“ ｘ 是偶数”， ¬ Ｐ（ｘ） 代表谓词“ ｘ 是奇数”； ｎ ∈＋ α ，或者 ｎ ∈－ α ； 定义一个新数 Ｔ ＝１ － ｎ ；自指代 Ｔ ＝ ｎ ， ｎ ＝ １ － ｎ ， ｎ 是偶数 ↔ ｎ 是 奇数；产生悖论，不可判定命题 Ｐ（ｎ）↔¬ Ｐ（ｎ） ；即 ｎ ＝ ｎ├Ｐ（ｎ）↔¬ Ｐ（ｎ） 根据反证法得到， ├ｎ ≠ ｎ ，这显然是荒唐的结论。 例 ２ 相对无意义的命题 设 Ｕ 为全体整数集合， Ｐ（ｘ） ：表示 ｘ 是偶数； 则 Ｐ（０），Ｐ（２），Ｐ（７），… 等都是有定义、有意义的 命题； Ｐ（ １ ２ ），Ｐ（ １ ３ ），Ｐ（ ２ ３ ），… 都是无定义、无意 义的命题。 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 是一个已经定义集 合，如果 Ａ ├ Ｐ（ｘｉ） ∧ ¬ Ｐ（ｘｉ） ，且 ｘｉ ∈ Ｕ ，可以使 用“反证法”，├ ¬ Ａ ，这是正确的证明方法。 注记 ５ “反证法”的正确推理形式 一般地，设 Ｕ ＝ ＋ α ∪－ α 是一个已定义集合， ｘｉ ∈Ｕ ， Ｋ（ｘｉ） 是 Ｕ 内的任意一个命题，根据 Ｕ 外不 动项定理， ├Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） 。 １） Ｕ 外不动项所产生的矛盾，使用“反证法”只 能得出 ｘＰ ∉ Ｕ 。 即把 ｘＰ ∈ Ｕ 看成假设时，可以使 用“反证法”进行推理，正确的推理形式是： Ｋ（ｘｉ），ｘＰ ∈ Ｕ├Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） ， ├¬ （ｘＰ ∈ Ｕ） 。 ２） Ｕ 外不动项所产生的矛盾，不能作为任何“ Ｕ 内演算的推理依据” 即把 ｘＰ ∈Ｕ 看成真命题时，使用 “反证法”是错误的。 不正确的推理形式是： Ｋ（ｘｉ）├Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） ， ├¬ Ｋ（ｘｉ） 。 ３）一般使用“自指代”所产生的矛盾，都是域外 矛盾，不能作为反证法的依据。 可以回顾一下，历史上“直觉主义”者，也认识到 无限制地使用“反证法”会有问题，他们转向完全的 “构造数学”，他们也看到一些问题，但是，没有把问题 完全搞清。 这里真正看到“反证法”的使用范围。 ５ 无穷集合的幂集中的不可判定命题 集合论的创立者 Ｃａｎｔｏｒ 证明：无穷集合的幂集 合不能与原来的集合建立一一对应关系。 可以回顾 一下其证明过程，使用 Ｃａｎｔｏｒ 的对角线方法。 如果 ＰＭ 为 Ｍ 的幂集，且 Ｍ ～ ＰＭ （ Ｍ 与 ＰＭ 之 间可以建立一一对应关系，即双射关系），则存在 Ｔ ， Ｔ ⊆ Ｍ ，且 Ｔ ∉ ＰＭ 。 对于一个 Ｍ 子集而言，如果能够决定 Ｍ 的元素 中哪些属于该子集，那么 Ｍ 的子集就确定了。 可以 给出一个一般准则，由它可以对 Ｍ 的任何元素 ｘ， 决 定该元素是否属于该子集。 在假设 Ｍ ～ ＰＭ 中，任意 ｘ ∈ Ｍ 对应一个 ｙ ∈ ＰＭ ，即： ｘ ∈ Ｍ↔ｙ ∈ ＰＭ ， ｙ 是 Ｍ 的子集之一， ｙ ⊆ Ｍ ， ｘ ∈ ｙ ，或者 ｘ ∉ ｙ ；规定： ｘ ∈ ｙ↔ｘ ∉ Ｔ ； ｘ ∉ ｙ↔ｘ ∈ Ｔ ； 假定 Ｔ ∈ ＰＭ ， Ｍ ～ ＰＭ ，存在 ｘ０ ∈ Ｍ↔Ｔ ∈ ＰＭ ； 按规定： ｘ０ ∈ Ｔ↔ｘ０ ∉ Ｔ ； ｘ０ ∉ Ｔ↔ｘ０ ∈ Ｔ ； 矛盾，所以， Ｔ ∉ ＰＭ 。 注：这证明在很多“数理逻辑” 书中都可以见 到，如《元数学导论》 ［７］ 。 ５．１ 无穷集合演算中的不动项 在以上证明过程中，构造的集合 Ｔ ，如果按照 正反集合分析法，实际上是一个不动项，证明如下。 定理 １６ 无穷集合演算中存在不动项 如果无穷集合与它的幂集合之间能建立一一映 射，那么，幂集合演算中存在一个不动项。 证明 首先把以上证明过程，整理如下： 假设在双射关系 Ｆ：Ｍ ～ ＰＭ 中，任意 ｘ ∈ Ｍ 对 应一个 Ｆ（ｘ） ∈ ＰＭ ， 即： ｘ ∈ Ｍ↔Ｆ（ｘ） ∈ ＰＭ ， Ｆ（ｘ） ）是 Ｍ 的子集 之一， Ｆ（ｘ） ⊆ Ｍ ； ｘ ∈ Ｆ（ｘ） ，或者 ｘ ∉ Ｆ（ｘ） ； 规定： ｘ ∈ Ｆ（ｘ）↔ｘ ∉ ＴＭ ； ｘ ∉ Ｆ（ｘ）↔ｘ ∈ ＴＭ ； 假定 ＴＭ ∈ ＰＭ ， Ｍ ～ ＰＭ ，存在 ｘ０ ∈ Ｍ↔Ｆ（ｘ０ ） ∈ ＰＭ ，（设 ＴＭ ＝ Ｆ（ｘ０ ） ； 按 规 定： ｘ０ ∈ Ｆ（ｘ０ ）↔ｘ０ ∉ Ｆ（ｘ０ ） ； ｘ０ ∉ Ｆ（ｘ０ ）↔ｘ０ ∈ Ｆ（ｘ０ ） 。 再把 ＰＭ 分为正反集合，设： ＋ α ＝ {Ｘ：ｘ ∈ Ｍ，ｘ ∈ Ｘ，Ｘ ∈ ＰＭ，Ｘ ＝ Ｆ（ｘ）} － α ＝ {Ｘ：ｘ ∈ Ｍ，ｘ ∉ Ｘ，Ｘ ∈ ＰＭ，Ｘ ＝ Ｆ（ｘ）} Ｕ ＝ ＰＭ ＝ ＋ α ∪－ α 按规定： ｘ ∈ Ｆ（ｘ）↔ｘ ∉ ＴＭ ； ｘ ∉ Ｆ（ｘ）↔ｘ ∈ ＴＭ ，自我指代： ＴＭ ＝ Ｆ（ｘ０ ）， 即 ｘ０ ∈ Ｆ（ｘ０ ）↔ｘ０ ∉ Ｆ（ｘ０ ），ｘ０ ∈ ＴＭ↔ｘ０ ∉ ＴＭ ， Ｐ［Ｆ（ｘ）］ 表 示 ｘ ∈ Ｆ（ｘ）； 则 ¬ Ｐ［Ｆ（ｘ）］ 表示 ｘ ∉ Ｆ（ｘ） 。 命题 ｘ０ ∈ Ｆ（ｘ０ ）↔ｘ０ ∉ Ｆ（ｘ０ ） ， ＴＭ ＝ Ｆ（ｘ０ ）， 可以表示为 Ｐ（ＴＭ ）↔¬ Ｐ（ＴＭ ） ； ＴＭ 是不动项。 如 果 （ＴＭ ∈ ＰＭ） ， 则 有 悖 论 Ｐ（ＴＭ ）↔¬ Ｐ（ＴＭ ）； 即：如果双射关系 Ｆ：Ｍ ～ ＰＭ 成立，那么， ＴＭ 是不动项。 这是“Ｃａｎｔｏｒ 的对角线方法”证明，在这个证明 中，他把 ＴＭ 看成是一个已知项 ＴＭ ∈ Ｕ ，实际上 ＴＭ ∈Ｕ 未必成立，他只证明了以下结果： 如果双射关系 Ｆ：Ｍ ～ ＰＭ 成立，且 ＴＭ ∈ Ｕ ，那 么， Ｐ（ＴＭ ）↔¬ Ｐ（ＴＭ ） ；即 （Ｆ：Ｍ ～ ＰＭ） ∧ （ＴＭ ∈ Ｕ） ├ Ｐ（ＴＭ ）↔¬ Ｐ（ＴＭ ） 。 ·６２２· 智 能 系 统 学 报 第 ９ 卷
第5期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·623. 上面命题中出现了两个假设，到底是哪个假设 F(2)={1,*,3,*,*,…},该集合包含1,3， 引起的矛盾，还要分析。 不包含2,4,5； 这个定理和下面的定理等价，下面证明“Cantor F(3)={1,*,3,*,5,…},该集合包含，1,3， 的对角线方法”表现更清晰。 5,不包含2,4： 定理17自然数集合演算中存在不动项 F(4)={1,2,3,*,5,…},该集合包含1,2,3， 如果自然数集合与它的幂集合之间能建立 一一一 5,不包含，4： 映射，那么，它的幂集合演算中存在一个不动项。 F(5)={*,2,3,*,5,…},该集合包含2,3， 证明这个定理可以看成定理16的特例，证明 5,不包含1,4： 过程与定理16相同。 双射关系F:w~P(w),w是自然数集合， F(n)Cw,F(n)都是w的子集，F(n)e P(w)是w的幂集合。 P(ω)； 假设在F:w~P(w)中，任意n∈w对应一个 定义一个新集合T:n∈F(n)n年T。,n F(n)∈P(w), F(n)n∈T。; 即：n∈wF(n)∈P(w),F(n))是w的子 显然集合T。={*,2,*,4,*,…}是上面集 集之一，F(n)Sw: 合序列对角线元素的集合在ω上的补集； n∈F(n),或者n年F(n); T.也是ω的子集，T。∈P(ω)，它也在上表 按规定：n∈F(n)n生T。。n使F(n) 中，设它对应F(k),T。=F(k): n∈Ta; 得到矛盾：k∈F(k)k生F(k)。 假定T,∈P(w),F:w~P(w),存在 注记7 Cantor的两个定理 k∈w→F(k)∈P(ω)，（设T.=F(k); 1)自然数集合的任意一个子集都可以与一个0 按规定：k∈F(k)k生F(k); 与1的序列建立一一映射关系。 k生F(k)k∈F(k)。 证明用一个函数来表示某自然数的集值域 再把P(ω)分为正反集合，设： 在属于该集的自然数处它取值0，在不属于该集的 +a={x:n∈x,n∈ω，x∈P(ω)，x=F(n)} 自然数处它取值1。某自然数集合代表的函数值的 -a={x:n使x,n∈w,x∈P(ω），x=F(n)} 序列便是由0与1组成的无穷序列。为表示方便把 U=P(ω)=+aU-a 自然数集合中的0排除，仅为ω= 按规定：n∈F(n)→n生T。,n生F(n)neT。: {1,2,3,4,5,6,…},P(ω)为w的幂集合。 自我指代：T=F(k); 例：A1={1,*,3,4,*,…}该集合包含1,3， 即keF(k)k使F(k),k∈Tk年T。。 4,不包含2,5，（空缺的用“*”标注）该序列为 P[F(n)]表示n∈F(n);则P[F(n)]表 F(A1)=01001…; 示n年F(n)。 A2={1,*,3,*,*,…}该集合包含1,3，不 命题k∈F(k)k生F(k),T.=F(k)可以表 包含2,4,5，该序列为F(A2)=01011…; 示为P(T.)P(T。);T。是不动项： A3={1,*,3,*,5,…}该集合包含，1,3,5， 如果(T∈P(ω))，则有悖论P(T)P(T); 不包含2,4，该序列为F(A3)=01010…; 即如果双射关系F:w~P(w)成立，那么T是 A4={1,2,3,*,5,…}该集合包含1,2,3,5， 不动项。 不包含，4，该序列为F(A,)=00010…; 同样以上证明有两个假设，可以表示为 A5={*,2,3,*,5,…}该集合包含2,3,5，不 如果双射关系F:w~P(ω)成立，且(T。∈ 包含1,4，该序列为F(A5)=10010…; P(w)),那么，P(T)P(T); 即：(F:w~P(w))∧(T,∈P(w))F 所以，自然数集合的任意一个子集都可以表示 P(T)P(T)o 成一个0与1的序列，即自然数集合的任意一个子 注记6“Cantor的对角线方法” 集都可以与一个0与1的序列建立一一映射关系。 假设自然数和它的幂集合有一一对应关系，即 2)全体实数与全体自然数集合的子集具有一 n∈wF(n)∈P(w),可以把自然数的所有子集 一映射关系。 排成如下集合序列。 以上两个定理已经被Cantor等证明，自然数集 F(1)={1,*,3,4,*,…},该集合包含1,3， 合的任意一个子集都可以表示成一个0与1的序 4,不包含2,5，（空缺的用“*”标注）： 列，任意实数都可以表示二进制0与1的序列，它们
上面命题中出现了两个假设，到底是哪个假设 引起的矛盾，还要分析。 这个定理和下面的定理等价，下面证明“Ｃａｎｔｏｒ 的对角线方法”表现更清晰。 定理 １７ 自然数集合演算中存在不动项 如果自然数集合与它的幂集合之间能建立一一 映射，那么，它的幂集合演算中存在一个不动项。 证明 这个定理可以看成定理 １６ 的特例，证明 过程与定理 １６ 相同。 双射关系 Ｆ：ω ～ Ｐ（ω） ， ω 是自然数集合， Ｐ（ω） 是 ω 的幂集合。 假设在 Ｆ：ω ～ Ｐ（ω） 中，任意 ｎ ∈ ω 对应一个 Ｆ（ｎ） ∈ Ｐ（ω） ， 即： ｎ ∈ ω↔Ｆ（ｎ） ∈ Ｐ（ω） ， Ｆ（ｎ） ）是 ω 的子 集之一， Ｆ（ｎ） ⊆ ω ； ｎ ∈ Ｆ（ｎ） ，或者 ｎ ∉ Ｆ（ｎ） ； 按规定： ｎ ∈ Ｆ（ｎ）↔ｎ ∉ Ｔω 。 ｎ ∉ Ｆ（ｎ）↔ ｎ ∈Ｔω ； 假定 Ｔω ∈ Ｐ（ω） ， Ｆ：ω ～ Ｐ（ω） ，存在 ｋ ∈ ω↔Ｆ（ｋ） ∈ Ｐ（ω） ，（设 Ｔω ＝ Ｆ（ｋ） ； 按规定： ｋ ∈ Ｆ（ｋ）↔ｋ ∉ Ｆ（ｋ） ； ｋ ∉ Ｆ（ｋ）↔ｋ ∈ Ｆ（ｋ） 。 再把 Ｐ（ω） 分为正反集合，设： ＋ α ＝ {ｘ：ｎ ∈ ｘ，ｎ ∈ ω，ｘ ∈ Ｐ（ω），ｘ ＝ Ｆ（ｎ）} － α ＝ {ｘ：ｎ ∉ ｘ，ｎ ∈ ω，ｘ ∈ Ｐ（ω），ｘ ＝ Ｆ（ｎ）} Ｕ ＝ Ｐ（ω） ＝ ＋ α ∪－ α 按规定： ｎ ∈ Ｆ（ｎ）↔ｎ ∉ Ｔω ， ｎ ∉ Ｆ（ｎ）↔ｎ ∈ Ｔω ； 自我指代： Ｔω ＝ Ｆ（ｋ） ； 即 ｋ ∈ Ｆ（ｋ）↔ｋ ∉ Ｆ（ｋ） ， ｋ ∈ Ｔω↔ｋ ∉ Ｔω 。 Ｐ［Ｆ（ｎ）］ 表示 ｎ ∈ Ｆ（ｎ） ；则 ¬ Ｐ［Ｆ（ｎ）］ 表 示 ｎ ∉ Ｆ（ｎ） 。 命题 ｋ ∈ Ｆ（ｋ）↔ｋ ∉ Ｆ（ｋ） ， Ｔω ＝ Ｆ（ｋ） 可以表 示为 Ｐ（Ｔω）↔¬ Ｐ（Ｔω） ； Ｔω 是不动项； 如果 （Ｔω ∈ Ｐ（ω）） ，则有悖论 Ｐ（Ｔω）↔¬ Ｐ（Ｔω） ； 即如果双射关系 Ｆ：ω ～ Ｐ（ω） 成立，那么 Ｔω 是 不动项。 同样以上证明有两个假设，可以表示为 如果双射关系 Ｆ：ω ～ Ｐ（ω） 成立，且 （Ｔω ∈ Ｐ（ω）） ，那么， Ｐ（Ｔω）↔¬ Ｐ（Ｔω） ； 即： （Ｆ：ω ～ Ｐ（ω）） ∧ （Ｔω ∈ Ｐ（ω）） ├ Ｐ（Ｔω）↔¬ Ｐ（Ｔω） 。 注记 ６ “Ｃａｎｔｏｒ 的对角线方法” 假设自然数和它的幂集合有一一对应关系，即 ｎ ∈ ω↔Ｆ（ｎ） ∈ Ｐ（ω） ，可以把自然数的所有子集 排成如下集合序列。 Ｆ（１） ＝ {１，∗，３，４，∗，…} ，该集合包含 １，３， ４，不包含 ２，５，（空缺的用“ ∗ ”标注）； Ｆ（２） ＝ {１，∗，３，∗，∗，…} ，该集合包含 １，３， 不包含 ２，４，５； Ｆ（３） ＝ {１，∗，３，∗，５，…} ，该集合包含，１，３， ５，不包含 ２，４； Ｆ（４） ＝ {１，２，３，∗，５，…} ，该集合包含 １，２，３， ５，不包含，４； Ｆ（５） ＝ {∗，２，３，∗，５，…} ，该集合包含 ２，３， ５，不包含 １，４； … Ｆ（ｎ） ⊆ ω ， Ｆ（ｎ） 都是 ω 的子集， Ｆ（ｎ） ∈ Ｐ（ω） ； 定义一个新集合 Ｔω ： ｎ ∈ Ｆ（ｎ）↔ｎ ∉ Ｔω ， ｎ ∉ Ｆ（ｎ）↔ｎ ∈ Ｔω ； 显然集合 Ｔω ＝ {∗，２，∗，４，∗，…} 是上面集 合序列对角线元素的集合在 ω 上的补集； Ｔω 也是 ω 的子集， Ｔω ∈ Ｐ（ω） ，它也在上表 中，设它对应 Ｆ（ｋ） ， Ｔω ＝ Ｆ（ｋ） ； 得到矛盾： ｋ ∈ Ｆ（ｋ）↔ｋ ∉ Ｆ（ｋ） 。 注记 ７ Ｃａｎｔｏｒ 的两个定理 １）自然数集合的任意一个子集都可以与一个 ０ 与 １ 的序列建立一一映射关系。 证明 用一个函数来表示某自然数的集值域， 在属于该集的自然数处它取值 ０，在不属于该集的 自然数处它取值 １。 某自然数集合代表的函数值的 序列便是由 ０ 与 １ 组成的无穷序列。 为表示方便把 自 然 数 集 合 中 的 ０ 排 除， 仅 为 ω ＝ {１，２，３，４，５，６，…} ， Ｐ（ω） 为 ω 的幂集合。 例： Ａ１ ＝ {１，∗，３，４，∗，…} 该集合包含 １，３， ４，不包含 ２，５， （ 空缺的用“ ∗ ” 标注） 该序列为 Ｆ（Ａ１ ） ＝ ０１００１… ； Ａ２ ＝ {１，∗，３，∗，∗，…} 该集合包含 １，３，不 包含 ２，４，５，该序列为 Ｆ（Ａ２ ） ＝ ０１０１１… ； Ａ３ ＝ {１，∗，３，∗，５，…} 该集合包含，１，３，５， 不包含 ２，４，该序列为 Ｆ（Ａ３ ） ＝ ０１０１０… ； Ａ４ ＝ {１，２，３，∗，５，…} 该集合包含 １，２，３，５， 不包含，４，该序列为 Ｆ（Ａ４ ） ＝ ０００１０… ； Ａ５ ＝ {∗，２，３，∗，５，…} 该集合包含 ２，３，５，不 包含 １，４，该序列为 Ｆ（Ａ５ ） ＝ １００１０… ； … 所以，自然数集合的任意一个子集都可以表示 成一个 ０ 与 １ 的序列，即自然数集合的任意一个子 集都可以与一个 ０ 与 １ 的序列建立一一映射关系。 ２）全体实数与全体自然数集合的子集具有一 一映射关系。 以上两个定理已经被 Ｃａｎｔｏｒ 等证明，自然数集 合的任意一个子集都可以表示成一个 ０ 与 １ 的序 列，任意实数都可以表示二进制 ０ 与 １ 的序列，它们 第 ５ 期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·６２３·
·624. 智能系统学报 第9卷 之间具有一一映射关系)。 以构造出不动项矛盾。 定理18实数集合演算中存在不动项 因为不动项命题都是不可判定命题，所以，以下 如果自然数集合与实数集合之间能建立一一映 推论成立。 射，那么，实数集合演算中存在一个不动项。 推论2如果双射关系F:M~PM成立，且 证明由于全体实数都可以化成二进制形式， TM∈PM,那么，P(TM)是不可判定命题。 只用0,1两个数字表示，注记7构造的F(A:)序列 推论3如果双射关系F:w~P(w)成立，且 实际上可以看成与实数之间有一个一一对应关系， T,∈P(ω)，那么，P(T)是不可判定命题。 用x:表示这些实数，用Cantor对角线法构造的不动 推论4如果双射关系F:w~R成立，且TR∈ 项，也可以看成实数领域的不动项。 R,那么，P(T)是不可判定命题。 把这些序列列成无穷方阵： 5.2“对角线方法”的逻辑分析 F(A1)=x1=01001… Cantor对角线方法是经典集合论、证明论、模型 F(A2)=x2=01011… 论、递归论中的一个重要方法，如：实数不可数、图灵 F(A3)=x3=01010… 机不可判定、存在非递归函数等很多定理的证明都 F(A4)=x4=00010… 是使用这种方法。然而，以下的证明表明，对角线方 F(A5)=x5=10010… 法产生的是U外不动项，这说明使用对角线方法证 年年 明的定理的证明是错误的。 用对角线法在上面方阵中构造一个对角线数： 定理19广义U外不动项定理 01010…,把这个对角线数0与1互相交换得TR, 设全集U={x1,x2,…,x,…}是一个已经定义 T。=10101…,T和上表中任何一个都不同。 的集合，P是定义在U上的一个性质，命题P是关 用T,表示TR的第n个数字，xm表示x。的第n 于+a、-a的一个划分，即：+a={xIP(x)}, 行，第n个数字，则T。的定义可以表示为 -a={xIP(x)},构造项T满足以下关系，x∈ xm=0→T。=1,xm=1→T。=0。 +aP(T),x∈-aP(T);如果U上的演算 如果TR也是实数，TR∈R,设它排列在第k 是一致的，那么，T是U外项。 行，现在考查T是序列x中第k位T,按定义得到 证明x∈+aP(x）, 以下矛盾： 假设T∈+→P(T)P(T): T4=0T=1,Tk=1Tk=0。 同理，x∈-P(x), 设+a={xn:xm=1,x。∈R},即所有第n行， 假设T∈-a→P(T)P(T); 第n项为1的实数序列： 因为，U=+U-a, -a={xn:xm=0,x。∈R},即所有第n行，第 所以，假设T∈U→P(T)P(T); n项为0的实数序列。 所以，→T主U。 按规定：xm=0一T。=1,xm=1Tn=0: “广义U外不动项定理”可以简化为： 自我指代：x=TR,xu=T,(T是T的第k P、T在U上可定义， 项)： T∈U,上P(T)P(T)。 即：T4=0T=1,Tk=1Tk=0; 在以上定理中，如果+a,-α之间存在双射关 P(x):x体=1(x的第k项为1)；P(x4): 系，即f:+a~-, x4=0(x的第k项为0)。 则x∈+af八x）∈-&， 如果TR∈R,则有“TR的第k项为1”白“T x∈+a→P(T),f八x)∈-a→P(T), 的第k项为0”； 所以，P(T)P(T), 即有TR∈+aTe∈-a,P(TR)nP(TR); 即为“U外不动项定理”，可以看出“广义U外 即如果TR∈R,则有悖论：P(TR)P(TR)。 不动项定理”是“U外不动项定理”的推广形式，“U 所以，如果自然数集合与实数集合之间能建立 外不动项定理”是它的特例。 映射，那么，实数集合演算中存在一个不动项。 例3“广义U外不动项定理”的具体例子 同样以上证明有两个假设，可以表示为： 以上定理16~18中，“Cantor对角线证明方法” 如果双射关系F:w~R成立，且T。∈R,那么， 可以看成把U分成对称的+α，-α，定义新项“T” P(TR)P(Te);即 满足x∈+aP(T),x∈-a→P(T),都是“广 (F:0-R)A(TR ER)FP(TR)P(TR) 义U外不动项定理”的具体例子。 运用这种对角线方法，在有理数集合上，同样可 定理16规定：x∈F(x)x年TM;
之间具有一一映射关系［７］ 。 定理 １８ 实数集合演算中存在不动项 如果自然数集合与实数集合之间能建立一一映 射，那么，实数集合演算中存在一个不动项。 证明 由于全体实数都可以化成二进制形式， 只用 ０，１ 两个数字表示，注记 ７ 构造的 Ｆ（Ａｉ） 序列 实际上可以看成与实数之间有一个一一对应关系， 用 ｘｉ 表示这些实数，用 Ｃａｎｔｏｒ 对角线法构造的不动 项，也可以看成实数领域的不动项。 把这些序列列成无穷方阵： Ｆ（Ａ１ ） ＝ ｘ１ ＝ ０１００１… Ｆ（Ａ２ ） ＝ ｘ２ ＝ ０１０１１… Ｆ（Ａ３ ） ＝ ｘ３ ＝ ０１０１０… Ｆ（Ａ４ ） ＝ ｘ４ ＝ ０００１０… Ｆ（Ａ５ ） ＝ ｘ５ ＝ １００１０… … 用对角线法在上面方阵中构造一个对角线数： ０１０１０… ，把这个对角线数 ０ 与 １ 互相交换得 ＴＲ ， ＴＲ ＝ １０１０１… ， ＴＲ 和上表中任何一个都不同。 用 Ｔｎ 表示 ＴＲ 的第 ｎ 个数字， ｘｎｎ 表示 ｘｎ 的第 ｎ 行，第 ｎ 个数字，则 ＴＲ 的定义可以表示为 ｘｎｎ ＝ ０↔Ｔｎ ＝ １， ｘｎｎ ＝ １↔Ｔｎ ＝ ０。 如果 ＴＲ 也是实数， ＴＲ ∈ Ｒ ，设它排列在第 ｋ 行，现在考查 ＴＲ 是序列 ｘｋ 中第 ｋ 位 Ｔｋ ，按定义得到 以下矛盾： Ｔｋ ＝ ０↔Ｔｋ ＝ １， Ｔｋ ＝ １↔Ｔｋ ＝ ０。 设 ＋ α ＝ ｘｎ ：ｘｎｎ ＝ １，ｘ { ｎ ∈ Ｒ} ，即所有第 ｎ 行， 第 ｎ 项为 １ 的实数序列； － α ＝ ｘｎ ：ｘｎｎ ＝ ０，ｘ { ｎ ∈ Ｒ} ，即所有第 ｎ 行，第 ｎ 项为 ０ 的实数序列。 按规定： ｘｎｎ ＝ ０↔Ｔｎ ＝ １， ｘｎｎ ＝ １↔Ｔｎ ＝ ０； 自我指代： ｘｋ ＝ ＴＲ ， ｘｋｋ ＝ Ｔｋ ， （ Ｔｋ 是 ＴＲ 的第 ｋ 项）； 即： Ｔｋ ＝ ０↔Ｔｋ ＝ １， Ｔｋ ＝ １↔Ｔｋ ＝ ０； Ｐ（ｘｋ） ： ｘｋｋ ＝ １（ ｘｋ 的第 ｋ 项为 １）； ¬ Ｐ（ｘｋ） ： ｘｋｋ ＝ ０（ ｘｋ 的第 ｋ 项为 ０）。 如果 ＴＲ ∈ Ｒ ，则有“ ＴＲ 的第 ｋ 项为 １” ⇔ “ ＴＲ 的第 ｋ 项为 ０”； 即有 ＴＲ ∈＋ α↔ＴＲ ∈－ α ， Ｐ（ＴＲ ）↔¬ Ｐ（ＴＲ ） ； 即如果 ＴＲ ∈Ｒ ，则有悖论： Ｐ（ＴＲ ）↔¬ Ｐ（ＴＲ ） 。 所以，如果自然数集合与实数集合之间能建立 一一映射，那么，实数集合演算中存在一个不动项。 同样以上证明有两个假设，可以表示为： 如果双射关系 Ｆ：ω ～ Ｒ 成立，且 ＴＲ ∈Ｒ ，那么， Ｐ（ＴＲ ）↔¬ Ｐ（ＴＲ ） ；即 （Ｆ：ω ～ Ｒ） ∧ （ＴＲ ∈ Ｒ） ├ Ｐ（ＴＲ）↔¬ Ｐ（ＴＲ） 运用这种对角线方法，在有理数集合上，同样可 以构造出不动项矛盾。 因为不动项命题都是不可判定命题，所以，以下 推论成立。 推论 ２ 如果双射关系 Ｆ：Ｍ ～ ＰＭ 成立，且 ＴＭ ∈ＰＭ ，那么， Ｐ（ＴＭ ） 是不可判定命题。 推论 ３ 如果双射关系 Ｆ：ω ～ Ｐ（ω） 成立，且 Ｔω ∈ Ｐ（ω） ，那么， Ｐ（Ｔω） 是不可判定命题。 推论 ４ 如果双射关系 Ｆ：ω ～ Ｒ 成立，且 ＴＲ ∈ Ｒ ，那么， Ｐ（ＴＲ ） 是不可判定命题。 ５．２ “对角线方法”的逻辑分析 Ｃａｎｔｏｒ 对角线方法是经典集合论、证明论、模型 论、递归论中的一个重要方法，如：实数不可数、图灵 机不可判定、存在非递归函数等很多定理的证明都 是使用这种方法。 然而，以下的证明表明，对角线方 法产生的是 Ｕ 外不动项，这说明使用对角线方法证 明的定理的证明是错误的。 定理 １９ 广义 Ｕ 外不动项定理 设全集 Ｕ ＝ ｘ１ ，ｘ２ ，…，ｘ { ｉ，…} 是一个已经定义 的集合， Ｐ 是定义在 Ｕ 上的一个性质，命题 Ｐ 是关 于 ＋ α 、 － α 的一个划分，即： ＋ α ＝ {ｘ ｜ Ｐ（ｘ）} ， － α ＝{ｘ ｜ ¬ Ｐ（ｘ）} ，构造项 Ｔ 满足以下关系， ｘ ∈ ＋ α↔¬ Ｐ（Ｔ） ， ｘ ∈－ α↔Ｐ（Ｔ） ；如果 Ｕ 上的演算 是一致的，那么， Ｔ 是 Ｕ 外项。 证明 ｘ ∈＋ α↔Ｐ（ｘ） ， 假设 Ｔ ∈＋ α⇒Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ； 同理， ｘ ∈－ α↔¬ Ｐ（ｘ） ， 假设 Ｔ ∈－ α⇒¬ Ｐ（Ｔ）↔Ｐ（Ｔ） ； 因为， Ｕ ＝ ＋ α ∪－ α ， 所以，假设 Ｔ ∈ Ｕ⇒Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ； 所以， ⇒Ｔ ∉ Ｕ 。 “广义 Ｕ 外不动项定理”可以简化为： Ｐ 、 Ｔ 在 Ｕ 上可定义， Ｔ ∈ Ｕ，├Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 。 在以上定理中，如果 ＋ α， － α 之间存在双射关 系，即 ｆ： ＋ α ～ － α ， 则 ｘ ∈＋ α↔ｆ（ｘ） ∈－ α ， ｘ ∈＋ α↔¬ Ｐ（Ｔ） ， ｆ（ｘ） ∈－ α↔Ｐ（Ｔ） ， 所以， Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ， 即为“ Ｕ 外不动项定理”，可以看出“广义 Ｕ 外 不动项定理”是“ Ｕ 外不动项定理”的推广形式，“ Ｕ 外不动项定理”是它的特例。 例 ３ “广义 Ｕ 外不动项定理”的具体例子 以上定理 １６～１８ 中，“Ｃａｎｔｏｒ 对角线证明方法” 可以看成把 Ｕ 分成对称的 ＋ α， － α ，定义新项“ Ｔ ” 满足 ｘ ∈＋ α↔¬ Ｐ（Ｔ） ， ｘ ∈ － α↔Ｐ（Ｔ） ，都是“广 义 Ｕ 外不动项定理”的具体例子。 定理 １６ 规定： ｘ ∈ Ｆ（ｘ）↔ｘ ∉ ＴＭ ； ·６２４· 智 能 系 统 学 报 第 ９ 卷
第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不动项矛盾与双射关系无关
ｘ ∉ Ｆ（ｘ）↔ｘ ∈ ＴＭ ； 定理 １７ 规定： ｎ ∈ Ｆ（ｎ）↔ｎ ∉ ＴＮ ； ｎ ∉ Ｆ（ｎ）↔ｎ ∈ ＴＮ ； 定理 １８ 规定： ｘｎｎ ＝ ０↔Ｔｎ ＝ １， ｘｎｎ ＝ １↔Ｔｎ ＝ ０。 以上构造项 ＴＭ 、 Ｔω 、 ＴＲ 都满足： ｘ ∈＋ α↔¬ Ｐ（Ｔ） ， ｘ ∈－ α↔Ｐ（Ｔ） 所以， ＴＭ 、 Ｔω 、 ＴＲ 都是 Ｕ 外不动项。 “对角线方法”还可以看成一种非对称的分类 方法，也是“广义 Ｕ 外不动项定理” 的特例。 定理 ２０ “对角线证明方法”的非对称分类 如果集 Ｕ 上的演算是一致的， ＋ α ＝ Ｕ ， － α ＝ ∅ ，构造项 Ｔ 满足 ｘ ∈ Ｕ↔¬ Ｐ（Ｔ） ，那么， Ｔ 不是 Ｕ 的元素，即： Ｔ ∉ Ｕ 。 证明 在以上“广义 Ｕ 外不动项定理”中假设 ＋ α ＝ Ｕ ，则 － α ＝ ∅ ， ＋ α ＝ {ｘ ｜ Ｐ（ｘ）} ，代入即有 Ｔ ∉ Ｕ ，或者列出以下过程： １）假设 Ｕ ＝ {ｘ ｜ Ｐ（ｘ）} ，——— Ｐ（ｘ） 表示 ｘ 在 列表中，假设所有 Ｕ 的元素有一个列表，即存在与 双射关系： Ｆ：ω ～ Ｕ 。 ２） ｘ ∈ Ｕ↔Ｐ（ｘ） ，——— ｘ ∈ Ｕ 等价一个谓词 Ｐ（ｘ） “ ｘ 在列表中”，即：存在双射关系： Ｆ：ω ～ Ｕ 。 ３） ｘ ∈ Ｕ↔¬ Ｐ（Ｔ） ，———对角线方法构造一个 新元素 Ｔ ， Ｔ 与 Ｕ 中所有元素都不同。 ４） Ｐ（ｘ）↔¬ Ｐ（Ｔ） ，———（２）（３）。 ５）假设 Ｔ ∈ Ｕ ———问 Ｔ ∈ Ｕ 吗？ 假设 Ｔ ∈ Ｕ 成 立，那么存在某个 ｘ ， ｘ ＝ Ｔ 。 ６） Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ，———（５）代入，得到矛盾。 根据“广义 Ｕ 外不动项定理”的形式： Ｐ 、 Ｔ 在 Ｕ 上可定义， Ｔ ∈ Ｕ├Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 。 “ Ｐ 、 Ｔ 在 Ｕ 上可定义”，即“ Ｕ 上元素上可列 表”，即双射关系 Ｆ：ω ～ Ｕ 成立。 “对角线证明方法”可以简化为 （Ｆ：ω ～ Ｕ） ∧ （Ｔ ∈ Ｕ）├Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 。 注记 ８ “对角线证明方法”的二元谓词表示法 设 Ｕ ＝ ｘ１ ，ｘ２ ，…，ｘ { ｉ，…} ＝ {ｘ ｜ Ｐ（ｘ）} ， Ｐ（ｘｉ） 表示谓词表中的第 ｉ 个元素。 表中的第 ｉ 个元素 ｘｉ 的第 ｎ 项记为 Ｐ（ｘｉ，ｎ） ， 可以把按对角线方法排列如下： Ｐ（ｘ１ ，１），Ｐ（ｘ１ ，２），Ｐ（ｘ１ ，３），Ｐ（ｘ１ ，４），… Ｐ（ｘ２ ，１），Ｐ（ｘ２ ，２），Ｐ（ｘ２ ，３），Ｐ（ｘ２ ，４），… Ｐ（ｘ３ ，１），Ｐ（ｘ３ ，２），Ｐ（ｘ３ ，３），Ｐ（ｘ３ ，４），… Ｐ（ｘ４ ，１），Ｐ（ｘ４ ，２），Ｐ（ｘ４ ，３），Ｐ（ｘ４ ，４），… … 定义一个新的项 Ｔ ，满足 Ｔ 的第 ｎ 项，不同于 ｘｎ 的第 ｎ 项， 即： Ｐ（Ｔ，ｎ）↔¬ Ｐ（ｘｎ ，ｎ） ， 问 Ｔ ∈ Ｕ 吗？ 假设 Ｔ ∈ Ｕ 成立，那么存在某个 ｘｋ ， ｘｋ ＝ Ｔ ， 即： Ｐ（ｘｋ，ｋ）↔¬ Ｐ（ｘｋ，ｋ） 或 Ｐ（Ｔ，ｋ）↔¬ Ｐ（Ｔ，ｋ） 矛盾，所以， Ｔ ∉ Ｕ 。 对角线方法使用全集（补集合为空集非对称分 类方法），所有“对角线方法”都是一个类型，它们都 是“广义 Ｕ 外不动项定理” 的特例。 所以，“Ｃａｎｔｏｒ 对角线方法”构造的实数也是“广义 Ｕ 外不动项定 理”的特例。 推论 ５ 如果实数集 Ｒ 上的演算是一致的，那 么，“康托的对角线方法”所构造的项 Ｔ 满足： （Ｆ：ω ～ Ｒ） ∧ （Ｔ ∈ Ｒ）├Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 。 定理 ２１ “对角线证明方法”的 ３ 个结论 设 Ｕ ＝ ｘ１ ，ｘ２ ，…，ｘ { ｉ，…} ，如果 Ｕ 内演算是一 致的，“对角线证明方法”可以得到以下 ３ 个结论： （Ａ）├ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） ； （Ｂ）├ ¬ （Ｆ：ω ～ Ｕ） ∧ Ｔ ∈ Ｕ ； （Ｃ）├ ¬ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） 。 证明 在以上“广义 Ｕ 外不动项定理”中假设 ＋ α ＝ Ｕ ，则 － α ＝ ∅ ＋ α ＝ {ｘ ｜ Ｐ（ｘ）} Ｆ：ω ～ Ｕ，Ｔ ∈ Ｕ├ Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ├ ¬ ［（Ｆ：ω ～ Ｕ） ∧ （Ｔ ∈ Ｕ）］ （１） 由于 ¬ （Ｍ ∧ Ｎ）↔ （Ｍ ∧ ¬ Ｎ） ∨ （¬ Ｍ ∧ Ｎ） ∨ （¬ Ｍ ∧ ¬ Ｎ） 由式（１）可以得到以下 ３ 个结论： （Ａ） Ｆ：ω ～ Ｕ ├ ¬ （Ｔ ∈ Ｕ） ，表示如果双射关 系成立，那么 Ｔ ∉ Ｕ ；即 ├ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） （Ｂ） Ｔ ∈ Ｕ ├ ¬ （Ｆ：ω ～ Ｕ） ，表示如果 Ｔ ∈ Ｕ 成立，那么 双射关系不成立；即 ├ ¬ （Ｆ：ω ～ Ｕ） ∧ （Ｔ ∈ Ｕ） （Ｃ）├ ¬ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） ，表示 Ｔ ∈ Ｕ ， 双射关系都不成立。 注记 ９ Ｃａｎｔｏｒ 的断定 在“对角线证明方法”Ａ、Ｂ、Ｃ ３ 个结论中，如果 Ｔ ∈ Ｕ 成立，那么， 双射关系 Ｆ：ω ～ Ｕ 一定不成立， 这就是 Ｃａｎｔｏｒ 的断定，即 Ｂ 结论正确； 另外一种情况是：如果 Ｔ ∉ Ｕ ，那么，双射关系 Ｆ：ω ～ Ｕ 可能成立，也可能不成立，即：Ａ、Ｃ 都可能 正确，这说明矛盾 Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 和双射关系 Ｆ：ω ～ Ｕ 无关，矛盾是由 Ｔ ∈ Ｕ 引起的。 下面的证明表明：矛盾恰恰是由 Ｔ ∈ Ｕ 引起的， Ｃａｎｔｏｒ 的断定是错误的。 定理 ２２ 不动项矛盾与双射关系无关 第 ５ 期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·６２５·
·626· 智能系统学报 第9卷 设0={x1,x2,…,x,…},如果U内演算是一 推论11如果集U上的演算是一致的，“对角 致的，则Cantor“对角线证明方法”F:w~U,T∈ 线方法构造项T”不能作为任何“U内演算的推理 U上P(T)P(T),不动项矛盾的存在与双射关 依据”。 系：F:w~U无关。 推论12如果集U上的演算是一致的，那么， 即：(A)上(F:w~U)∧(TeU),或者， 满足对角线方法的构造项T,断定T∈U的所有“对 (C)上(F:w~U)A(T∈U)。 角线方法”证明错误。 证明只要否定“结论(B)上一(F:w~U)∧ 注记10广义域外不动项定理解释 T∈U”即可，用反证法，只要举出一个反例即可，取 1)在以上定理证明过程中，根据“反证法的使 U=J整数集合。 用规则”，把xp∈U看成假设时，可以使用“反证 1)假设U=J={xIP(x)},P(x)表示x是整 法”进行推理，只能得出xp生U:把xp∈U看成真 数，假设所有J的元素有一个列表，即：存在与双射 命题时，使用“反证法”是错误的。 关系：F:ω~J。 2)“U外不动项定理”与“广义U外不动项定 2)x∈JP(x),x∈J等价一个谓词P(x)“ 理”都是用二分法把全集U分成两类性质集合，命 x在列表中”，即存在双射关系：F:w~J。 题P是关于U的一个划分，U=+U-a,即： 3)x∈JP(T),对角线方法构造一个新元 +a=(xI P(x)),-a={x1P(x))o 素T,T与J中所有元素都不同， 3)“U外不动项定理”与“广义U外不动项定 把U=J分成偶数集合与奇数集合： 理”的本质是：一个U中已经定义的项与其否定项 +a={x|x=2n,n∈J} 不能自指代。如果自指代，就会变异成一个新项 -a={x|x=1-2n,n∈J} “T”,这个新项“T”不再是的元素，即：TU。 x∈J,即：x∈+a,或者x∈-a定义一个新数x∈+ 4)“U外不动项定理”与“广义U外不动项定 a台T=1-x,x∈-a台T=1-x,x∈J台T=1- 理”的区别是：“U外不动项定理”要求+a,-α之 x等价x∈J台T生J,即：x∈J→P(T)。 间存在双射关系，即：f:+a~-a;“广义U外不动 4)P(x)P(T),—(2)(3), 项定理”没有这个要求。 5)假设T∈J—问T∈J吗？假设T∈J成 5)“Cantor对角线方法”可以看成是U上的一 立，那么存在某个x,x=T。 个特殊的分类。从“·外不动项定理”的分类看，使 6)P(T)P(T),(5)代入，得到矛盾， 用自然数标号与它对应的第项分类，这个分类恰 x∈J台T=1-x,T∈J曰T=1-T。 与双射关系U~w联系在一起：从“广义U外不动 7)F:ω~J,T∈J上 项定理”的分类看，+=R,-α=☑，所构造的项 P(T)P(T)—(1)(5)(6)。 T不同于R中的每一个数，TR,这个分类可以不 涉及双射关系U~w。 由于T=1-T,T=2,即：T∈J不正确。 5.3无穷集合幂集合不可数证明错误 所以：A)上(F:w~U)A(TeU),或者， 还可以举出一个具体的例子： C)上(F:w~U)A(T∈U)成立。 例4有理数集合上的对角线方法 即：不动项矛盾的存在与双射关系：F:w~U 假设在没有发现无理数之前，不知道有无理数， 无关。 只知道所有的数都为有理数。按照Cantor对角线 根据不动项的性质，以下推论都成立： 方法，同样可以证明：有理数集合是不可数的。 推论6如果集U上的演算是一致的，“对角线 假设把有理数区间[0,1]里的所有数按照某种 方法构造项T”一定在U外，T华U。 顺序排列起来，那么总能找到至少一个0到1之间 推论7如果集U上的演算是一致的，“对角线 的有理数不在列表里。把列表上的数全写成0到1 方法构造项T”是未定义项。 之间的小数： 推论8如果集U上的演算是一致的，“对角线 a1=0.0143634628.… 方法构造项T”,P(T)是不可判定命题。 a2=0.3794907237. 推论9如果集U上的演算是一致的，“对角线 a3=0.2334343423.… 方法构造项T”,P(T)的不可判定与U内项是否 a4=0.0005948211… 可以判定无关。 a5=0.9590129145.… 推论10如果集U上的演算是一致的，“对角线 方法构造项T”,P(T)P(T)矛盾来源于U外。 那么就构造这么一个小数T,小数点后第1位
设 Ｕ ＝ ｘ１ ，ｘ２ ，…，ｘ { ｉ，…} ，如果 Ｕ 内演算是一 致的，则 Ｃａｎｔｏｒ “对角线证明方法” Ｆ：ω ～ Ｕ ， Ｔ ∈ Ｕ ├ Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ，不动项矛盾的存在与双射关 系： Ｆ：ω ～ Ｕ 无关。 即：（Ａ）├ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） ，或者， （Ｃ）├ ¬ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） 。 证明 只要否定“结论（Ｂ）├ ¬ （Ｆ：ω ～ Ｕ） ∧ Ｔ ∈ Ｕ ”即可，用反证法，只要举出一个反例即可，取 Ｕ ＝ Ｊ 整数集合。 １）假设 Ｕ ＝ Ｊ ＝ {ｘ ｜ Ｐ（ｘ）} ， Ｐ（ｘ） 表示 ｘ 是整 数，假设所有 Ｊ 的元素有一个列表，即：存在与双射 关系： Ｆ：ω ～ Ｊ 。 ２） ｘ ∈ Ｊ↔Ｐ（ｘ） ， ｘ ∈ Ｊ 等价一个谓词 Ｐ（ｘ） “ ｘ 在列表中”，即存在双射关系： Ｆ：ω ～ Ｊ 。 ３） ｘ ∈ Ｊ↔¬ Ｐ（Ｔ） ，对角线方法构造一个新元 素 Ｔ ， Ｔ 与 Ｊ 中所有元素都不同， 把 Ｕ ＝ Ｊ 分成偶数集合与奇数集合： ＋ α ＝ {ｘ ｜ ｘ ＝ ２ｎ，ｎ ∈ Ｊ} － α ＝ {ｘ ｜ ｘ ＝ １ － ２ｎ，ｎ ∈ Ｊ} ｘ∈ Ｊ，即：ｘ ∈＋ α，或者 ｘ ∈－ α 定义一个新数 ｘ ∈＋ α⇔Ｔ ＝ １ － ｘ ， ｘ ∈－ α⇔Ｔ ＝ １ － ｘ ， ｘ ∈ Ｊ⇔Ｔ ＝ １ － ｘ 等价 ｘ ∈ Ｊ⇔Ｔ ∉ Ｊ ，即： ｘ ∈ Ｊ↔¬ Ｐ（Ｔ）。 ４） Ｐ（ｘ）↔¬ Ｐ（Ｔ） ，———（２）（３）， ５）假设 Ｔ ∈ Ｊ ———问 Ｔ ∈ Ｊ 吗？ 假设 Ｔ ∈ Ｊ 成 立，那么存在某个 ｘ ， ｘ ＝ Ｔ 。 ６） Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ，———（５）代入，得到矛盾， ｘ ∈ Ｊ⇔Ｔ ＝ １ － ｘ ， Ｔ ∈ Ｊ⇔Ｔ ＝ １ － Ｔ 。 ７） Ｆ：ω ～ Ｊ ， Ｔ ∈ Ｊ ├ Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ———（１）（５）（６）。 由于 Ｔ ＝ １ － Ｔ ， Ｔ ＝ １ ２ ，即： Ｔ ∈ Ｊ 不正确。 所以：Ａ）├ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） ，或者， Ｃ）├ ¬ （Ｆ：ω ～ Ｕ） ∧ ¬ （Ｔ ∈ Ｕ） 成立。 即：不动项矛盾的存在与双射关系： Ｆ：ω ～ Ｕ 无关。 根据不动项的性质，以下推论都成立： 推论 ６ 如果集 Ｕ 上的演算是一致的，“对角线 方法构造项 Ｔ ”一定在 Ｕ 外， Ｔ ∉ Ｕ 。 推论 ７ 如果集 Ｕ 上的演算是一致的，“对角线 方法构造项 Ｔ ”是未定义项。 推论 ８ 如果集 Ｕ 上的演算是一致的，“对角线 方法构造项 Ｔ ” ， Ｐ（Ｔ） 是不可判定命题。 推论 ９ 如果集 Ｕ 上的演算是一致的，“对角线 方法构造项 Ｔ ” ， Ｐ（Ｔ） 的不可判定与 Ｕ 内项是否 可以判定无关。 推论 １０ 如果集 Ｕ 上的演算是一致的，“对角线 方法构造项 Ｔ ” ， Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 矛盾来源于 Ｕ 外。 推论 １１ 如果集 Ｕ 上的演算是一致的，“对角 线方法构造项 Ｔ ”不能作为任何“ Ｕ 内演算的推理 依据”。 推论 １２ 如果集 Ｕ 上的演算是一致的，那么， 满足对角线方法的构造项 Ｔ ，断定 Ｔ∈Ｕ 的所有“对 角线方法”证明错误。 注记 １０ 广义域外不动项定理解释 １）在以上定理证明过程中，根据“反证法的使 用规则”，把 ｘＰ ∈ Ｕ 看成假设时，可以使用“反证 法”进行推理，只能得出 ｘＰ ∉ Ｕ ；把 ｘＰ ∈ Ｕ 看成真 命题时，使用“反证法”是错误的。 ２） “ Ｕ 外不动项定理”与“广义 Ｕ 外不动项定 理”都是用二分法把全集 Ｕ 分成两类性质集合，命 题 Ｐ 是关于 Ｕ 的一个划分， Ｕ ＝ ＋ α ∪－ α ，即： ＋ α ＝{ｘ ｜ Ｐ（ｘ）} ， － α ＝ {ｘ ｜ ¬ Ｐ（ｘ）} 。 ３） “ Ｕ 外不动项定理”与“广义 Ｕ 外不动项定 理”的本质是：一个 Ｕ 中已经定义的项与其否定项 不能自指代。 如果自指代，就会变异成一个新项 “ Ｔ ”，这个新项“ Ｔ ”不再是 Ｕ 的元素，即： Ｔ ∉ Ｕ 。 ４） “ Ｕ 外不动项定理”与“广义 Ｕ 外不动项定 理”的区别是：“ Ｕ 外不动项定理”要求 ＋ α， － α 之 间存在双射关系，即： ｆ： ＋ α ～ － α ；“广义 Ｕ 外不动 项定理”没有这个要求。 ５）“Ｃａｎｔｏｒ 对角线方法”可以看成是 Ｕ 上的一 个特殊的分类。 从“ Ｕ 外不动项定理”的分类看，使 用自然数标号与它对应的第 ｎ 项分类，这个分类恰 与双射关系 Ｕ ～ ω 联系在一起；从“广义 Ｕ 外不动 项定理”的分类看， ＋ α ＝ Ｒ ， － α ＝ ∅ ，所构造的项 Ｔ 不同于 Ｒ 中的每一个数， Ｔ ∉ Ｒ ，这个分类可以不 涉及双射关系 Ｕ ～ ω 。 ５．３ 无穷集合幂集合不可数证明错误 还可以举出一个具体的例子： 例 ４ 有理数集合上的对角线方法 假设在没有发现无理数之前，不知道有无理数， 只知道所有的数都为有理数。 按照 Ｃａｎｔｏｒ 对角线 方法，同样可以证明：有理数集合是不可数的。 假设把有理数区间［０，１］里的所有数按照某种 顺序排列起来，那么总能找到至少一个 ０ 到 １ 之间 的有理数不在列表里。 把列表上的数全写成 ０ 到 １ 之间的小数： ａ１ ＝ ０．０１４３６３４６２８… ａ２ ＝ ０．３７９４９０７２３７… ａ３ ＝ ０．２３３４３４３４２３… ａ４ ＝ ０．０００５９４８２１１… ａ５ ＝ ０．９５９０１２９１４５… … 那么就构造这么一个小数 Ｔ，小数点后第 １ 位 ·６２６· 智 能 系 统 学 报 第 ９ 卷
第5期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·627· 不等于a1的第1位，小数点后第2位不等于a2的第 F(n)∈+a,或者F(n)∈-a; 2位，总之小数点后第i位不等于a:的第i位。这个 定义一个新数F()∈+a台T=Fm' 2 数属于有理数区间[0,1]，但它显然不在你的列表 里。这样，就证明了有理数集合是不可数的。 也许你会说，你构造的这个数T已经不是有理 F(n)E-aT= 2 F(n): 数，是一个和有理数具有不同性质的新的数。当然， 因为F:w~Q成立， 现在知道有理数外还有无理数，即(TQ)。 所以，存在k∈ωF(k)∈Q: 即ω是自然数集合，Q全体正有理数集合，假 2 设双射关系F:w~Q成立。 按规定F(k)∈+a台T=F), 按照对角线方法，同样可以找到一个数T,导 致矛盾P(T)P(T),(P(T)表示数T在列表 F(k)e-QeT=-2 (k): 中)。 2 自指代，让T=F(k),T= 即(F:w~Q),(T∈Q)FP(T)P(T), ,T平方大于24 (F:ω~Q)上(TQ),即否定了(T∈Q)。 T平方小于2。 在证明实数不可数时，ω是自然数集合，R为 产生悖论，不可判定命题P(T)P(T)。 全体实数集合，假设双射关系F:ω~R成立，按照 由于这个矛盾的产生，就责怪双射关系F:ω~ 对角线方法，同样可以找到一个数T。,导致矛盾 P(TR)P(TR),(P(TR)表示数Te在列表中)。 Q不能成立，这显然是错误的。其实，7=子，7 即 √2，√迈是U外不动项。 (F:ω~R),(TR∈R)FP(TR)P(TR) 例6实数集合上的域外不动项 (Tg∈R)卜(F:w~R),否定了双射关系 仿照Cantor的对角线方法，U为不为0的全体 F:w~R。 实数集合U=(-0,0)U(0,+o), 对比这2个推理过程： 假设双射关系F:w~U成立，ω是自然数集合。 (F:w~Q),(T∈Q)F 假设在F:w~U中，任意n∈w对应一个 P(T)+P(T) (1) F(n)∈U,即：n∈wF(n)∈U。 (F:w~R),(TR∈R)上 把U分成正数集合与负数集合： P(TR)P(TR) (2) +a={x1x>0,x∈U}=(0,+0) 在前一个矛盾(1)中否定了T∈Q,没有否定 -a={x1x2,x∈Q}。 反集：平方小于2的有理数集合，即：-α= U不能成立，这显然是错误的。其实，T=-元，7= {x1x2<2,x∈Q}。 √I,√I是U外不动项
不等于 ａ１ 的第 １ 位，小数点后第 ２ 位不等于 ａ２ 的第 ２ 位，总之小数点后第 ｉ 位不等于 ａｉ 的第 ｉ 位。 这个 数属于有理数区间［０，１］，但它显然不在你的列表 里。 这样，就证明了有理数集合是不可数的。 也许你会说，你构造的这个数 Ｔ 已经不是有理 数，是一个和有理数具有不同性质的新的数。 当然， 现在知道有理数外还有无理数，即 （Ｔ ∉ Ｑ） 。 即 ω 是自然数集合， Ｑ 全体正有理数集合，假 设双射关系 Ｆ：ω ～ Ｑ 成立。 按照对角线方法，同样可以找到一个数 Ｔ ，导 致矛盾 Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ，（ Ｐ（Ｔ） 表示数 Ｔ 在列表 中）。 即 （Ｆ：ω ～ Ｑ），（Ｔ ∈ Ｑ） ├ Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ， （Ｆ：ω ～ Ｑ） ├ （Ｔ ∉ Ｑ） ，即否定了 （Ｔ ∈ Ｑ） 。 在证明实数不可数时， ω 是自然数集合， Ｒ 为 全体实数集合，假设双射关系 Ｆ：ω ～ Ｒ 成立，按照 对角线方法，同样可以找到一个数 ＴＲ ，导致矛盾 Ｐ（ＴＲ ）↔¬ Ｐ（ＴＲ ） ，（ Ｐ（ＴＲ ） 表示数 ＴＲ 在列表中）。 即 （Ｆ：ω ～ Ｒ），（ＴＲ ∈ Ｒ）├Ｐ（ＴＲ ）↔¬ Ｐ（ＴＲ ） （ＴＲ ∈ Ｒ） ├ ¬ （Ｆ：ω ～ Ｒ） ， 否 定 了 双 射 关 系 Ｆ：ω ～ Ｒ 。 对比这 ２ 个推理过程： （Ｆ：ω ～ Ｑ），（Ｔ ∈ Ｑ）├ Ｐ（Ｔ）↔¬ Ｐ（Ｔ） （１） （Ｆ：ω ～ Ｒ），（ＴＲ ∈ Ｒ）├ Ｐ（ＴＲ ）↔¬ Ｐ（ＴＲ ） （２） 在前一个矛盾（１）中否定了 Ｔ ∈ Ｑ ，没有否定 Ｆ：ω ～ Ｑ ；而后一个矛盾（２）中却否定了 Ｆ：ω ～ Ｒ ， 而没有否定 ＴＲ ∈ Ｒ 。 对角线证明方法具有统一的形式，矛盾只能有 一个统一的产生根源，实际上，前一个否定是正确 的，后一个否定是错误的。 即矛盾是由 ＴＲ ∈ Ｒ 引起的，并不是双射关系 Ｆ：ω ～ Ｒ 产生的，这说明“如果实数域演算是一致 的，那么 ＴＲ ∉ Ｒ 。 例 ５ 有理数集合上的域外不动项 Ｕ 为全体正有理数集合 Ｕ ＝ Ｑ ，假设双射关系 Ｆ：ω ～ Ｑ 成立， ω 是自然数集合， Ｑ 为全体正有理 数集合。 假设在 Ｆ：ω ～ Ｑ 中，任意 ｎ ∈ ω 对应一个 Ｆ（ｎ） ∈Ｑ ，即： ｎ ∈ ω↔Ｆ（ｎ） ∈ Ｑ 。 把 Ｕ ＝ Ｑ 分成正反集合， 正集：平方大于 ２ 的有理数集合，即： ＋ α ＝ ｘ ｜ ｘ ２ { ＞ ２，ｘ ∈ Ｑ} 。 反集：平方小于 ２ 的有理数集合，即： － α ＝ ｘ ｜ ｘ ２ { ＜ ２，ｘ ∈ Ｑ} 。 Ｆ（ｎ） ∈＋ α ，或者 Ｆ（ｎ） ∈－ α ； 定 义 一 个 新 数 Ｆ（ｎ） ∈＋ α⇔Ｔ ＝ ２ Ｆ（ｎ） ， Ｆ（ｎ） ∈ － α⇔Ｔ ＝ ２ Ｆ（ｎ） ； 因为 Ｆ：ω ～ Ｑ 成立， 所以，存在 ｋ ∈ ω↔Ｆ（ｋ） ∈ Ｑ ； 按规定 Ｆ（ｋ） ∈＋ α⇔Ｔ ＝ ２ Ｆ（ｋ） ， Ｆ（ｋ） ∈－ α⇔Ｔ ＝ ２ Ｆ（ｋ） ； 自指代，让 Ｔ ＝ Ｆ（ｋ） ， Ｔ ＝ ２ Ｔ ， Ｔ 平方大于 ２↔ Ｔ 平方小于 ２。 产生悖论，不可判定命题 Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 。 由于这个矛盾的产生，就责怪双射关系 Ｆ：ω ～ Ｑ 不能成立，这显然是错误的。 其实， Ｔ ＝ ２ Ｔ ， Ｔ ＝ ２ ， ２ 是 Ｕ 外不动项。 例 ６ 实数集合上的域外不动项 仿照 Ｃａｎｔｏｒ 的对角线方法， Ｕ 为不为 ０ 的全体 实数集合 Ｕ ＝ （ － ¥，０） ∪ （０， ＋ ¥） ， 假设双射关系 Ｆ：ω ～ Ｕ 成立， ω 是自然数集合。 假设在 Ｆ：ω ～ Ｕ 中，任意 ｎ ∈ ω 对应一个 Ｆ（ｎ） ∈Ｕ ，即： ｎ ∈ ω↔Ｆ（ｎ） ∈ Ｕ 。 把 Ｕ 分成正数集合与负数集合： ＋ α ＝ {ｘ ｜ ｘ ＞ ０，ｘ ∈ Ｕ} ＝ （０， ＋ ¥） － α ＝ {ｘ ｜ ｘ ＜ ０，ｘ ∈ Ｕ} ＝ （ － ¥，０） Ｆ（ｎ） ∈＋ α，或者 Ｆ（ｎ） ∈－ α 定义一个新数 Ｆ（ｎ） ∈＋ α⇔Ｔ ＝ － １ Ｆ（ｎ） ， Ｆ（ｎ） ∈－ α⇔Ｔ ＝ － １ Ｆ（ｎ） ； 因为 Ｆ：ω ～ Ｕ 成立，所以，存在： ｋ ∈ ω↔Ｆ（ｋ） ∈ Ｕ 按规定 Ｆ（ｋ） ∈＋ α⇔Ｔ ＝ － １ Ｆ（ｋ） ， Ｆ（ｋ） ∈－ α⇔ Ｔ ＝ － １ Ｆ（ｋ） ； 自指代 Ｔ ＝ Ｆ（ｋ） ， Ｔ ＝ － １ Ｔ ， Ｔ 是正数 ↔ Ｔ 是 负数； 产生悖论，不可判定命题 Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 。 由于这个矛盾的产生，就责怪双射关系 Ｆ：ω ～ Ｕ 不能成立，这显然是错误的。 其实， Ｔ ＝ － １ Ｔ ， Ｔ ＝ － １ ， － １ 是 Ｕ 外不动项。 第 ５ 期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·６２７·