文章快速检索 高级检索

Fixed terms and undecidable propositions in logical and mathematical calculus (Ⅱ)
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 mathematics. 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 Gödel'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 U has changed relative to U and 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 Gödel'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.
Key words: positive term     inverse term     fixed term     paradox     fixed term outside U     undecidable proposition     incomplete theorem     diagonal method     uncountable set     halting problem

4 正反命题与谓词演算系统 4.1 正反命题演算系统Lα

1)初始符号(略)；

2)命题的形成规则(略)；

3)定义(略)；

4)公理。

(1)正集公理

(2)正反集对偶变换公理

L0：(P是+α,－α的一个完全划分)；

(3)反集公理

5)演绎推理规则

 A+α ¬A+α 1 0 0 1

 A+α B+α A+α→B+α 1 0 0 1 1 1 0 0 1 0 1 1

 A－α ¬A－α 1 0 0 1

 A－α B－α A－α→B－α 1 0 0 1 1 1 0 0 1 0 1 1

 P+α P－α 1 0 0 1

4.2 正反谓词演算系统Kα

1)基本符号(略)

2)定义(略)

3)公理

(1)正集公理

(2)正反集对偶变换公理

K0：(P是+α,－α的一个对称划分)；

(3)反集公理

4)系统内推理规则

R1 分离规则：若，则

R2 概括规则：若，则

Kα的语义解释(略)[3]

4.3 系统LαKα的完全性与不可判定命题

，则；所以，若V(Pα)=1则

1)虽然系统Lα中出现了悖论Pe，但是，Pe是未定义命题，不参与系统演算，不会导致系统Lα演算崩溃，系统Lα仍然是有效的。

2)虽然系统Lα中出现了不可判定Pe，但是，Pe与系统完全性无关，系统Lα仍然是完全的，系统Lα的定理集合是可判定的。

，则；所以，若V(Pα)=1则

1)虽然系统Kα中出现了悖论P(xP)，但是，P(xP)是未定义命题，不参与系统演算，不会导致系统Kα演算崩溃，系统Kα仍然是有效的。

2)虽然系统Kα中出现了不可判定P(xP)，但是，P(xP)与系统完全性无关，系统Kα仍是完全的。

4.4 经典逻辑定理的适用范围

U=x1,x2,x3,…,xn,…是一个已经定义集合，经典逻辑的所有定理只适用于已经定义的集合U上。

U=x1,x2,x3,…,xn,…是一个已经定义集合，“反证法”只适用于已经定义的集合U上。

U=x1,x2,x3,…,xn,…是一个已经定义集合，不动项矛盾不能作为“反证法”在已定义的集合U上的推理依据。

P(x)代表谓词“x是偶数”，¬P(x)代表谓词“x是奇数”；n∈+α，或者n∈－α；定义一个新数T=1－n；自指代T=nn=1－nn是偶数↔n是奇数；产生悖论，不可判定命题；即

U为全体整数集合，P(x)：表示x是偶数；则P(0),P(2),P(7),…等都是有定义、有意义的命题；,,,…都是无定义、无意义的命题。

U=x1,x2,x3,…,xn,…是一个已经定义集合，如果，且xiU，可以使用“反证法”，，这是正确的证明方法。

1)U外不动项所产生的矛盾，使用“反证法”只能得出xPU。即把xPU看成假设时，可以使用“反证法”进行推理，正确的推理形式是：

2)U外不动项所产生的矛盾，不能作为任何“U内演算的推理依据”即把xPU看成真命题时，使用“反证法”是错误的。不正确的推理形式是：

3)一般使用“自指代”所产生的矛盾，都是域外矛盾，不能作为反证法的依据。

5 无穷集合的幂集中的不可判定命题

yM的子集之一，yM

xy，或者xy；规定：xyxTxyxT

5.1 无穷集合演算中的不动项

，或者

，(设TM=F(x0)；

，或者

，(设Tω=F(k)；

P[F(n)]表示nF(n)；则表示

F(1)=1,∗,3,4,∗,…，该集合包含1，3，4，不包含2，5，(空缺的用“∗”标注)；

F(2)=1,∗,3,∗,∗,…，该集合包含1，3，不包含2，4，5；

F(3)=1,∗,3,∗,5,…，该集合包含,1，3，5，不包含2，4；

F(4)=1,2,3,∗,5,…，该集合包含1，2，3，5，不包含,4；

F(5)=∗,2,3,∗,5,…，该集合包含2，3，5，不包含1,4；

,F(n)都是ω的子集，F(n)∈P(ω)；

Tω也是ω的子集，TωP(ω),它也在上表中，设它对应F(k)，Tω=F(k)；

1)自然数集合的任意一个子集都可以与一个0与1的序列建立一一映射关系。

A2=1,∗,3,∗,∗,…该集合包含1，3，不包含2，4，5，该序列为F(A2)=01011…；

A3=1,∗,3,∗,5,…该集合包含,1，3，5，不包含2，4，该序列为F(A3)=01010…；

A4=1,2,3,∗,5,…该集合包含1，2，3，5，不包含,4，该序列为F(A4)=00010…；

A5=∗,2,3,∗,5,…该集合包含2，3，5，不包含1，4，该序列为F(A5)=10010…；

2)全体实数与全体自然数集合的子集具有一一映射关系。

F(A1)=x1=01001…

F(A2)=x2=01011…

F(A3)=x3=01010…

F(A4)=x4=x00010…

F(A5)=x5=x10010…

Tn表示TR的第n个数字，xnn表示xn的第n行，第n个数字，则TR的定义可以表示为

，即所有第n行，第n项为1的实数序列；

，即所有第n行，第n项为0的实数序列。

P(xk)：xkk=1(xk的第k项为1)；xkk=0(xk的第k项为0)。

5.2 “对角线方法”的逻辑分析

Cantor对角线方法是经典集合论、证明论、模型论、递归论中的一个重要方法，如：实数不可数、图灵机不可判定、存在非递归函数等很多定理的证明都是使用这种方法。然而，以下的证明表明，对角线方法产生的是U外不动项，这说明使用对角线方法证明的定理的证明是错误的。

“广义U外不动项定理”可以简化为：

PTU上可定义，

TU

“对角线方法”还可以看成一种非对称的分类方法，也是“广义U外不动项定理”的特例。

1)假设，——P(x)表示x在列表中，假设所有U的元素有一个列表，即存在与双射关系：F:ωU

2) ，——xU等价一个谓词P(x)“x在列表中”，即：存在双射关系：F:ωU

3) ，——对角线方法构造一个新元素TTU中所有元素都不同。

4) ，——(2)(3)。

5)假设TU——问TU吗？假设TU成立，那么存在某个xx=T

6) ，——(5)代入，得到矛盾。

PTU上可定义”，即“U上元素上可列表”，即双射关系F:ωU成立。

“对角线证明方法”可以简化为

P(xi)表示谓词表中的第i个元素。

TU吗？假设TU成立，那么存在某个xkxk=T

U=x1,x2,…,xi,…，如果U内演算是一致的，“对角线证明方法”可以得到以下3个结论：

(A)；(B) ；(C) 。证明在以上“广义U外不动项定理”中假设+α=U，则

 (1)

(A)，表示如果双射关系成立，那么TU；即

(B)，表示如果TU成立，那么双射关系不成立；即

(C) ，表示TU，双射关系都不成立。

U=x1,x2,…,xi,…，如果U内演算是一致的，则Cantor“对角线证明方法”F:ωU，不动项矛盾的存在与双射关系：F:ωU无关。

1)假设P(x)表示x是整数，假设所有J的元素有一个列表，即：存在与双射关系：F:ωJ

2) xJ等价一个谓词P(x)“x在列表中”，即存在双射关系：F:ωJ

3) ，对角线方法构造一个新元素TTJ中所有元素都不同，

U=J分成偶数集合与奇数集合：

xJ，即：x∈+α，或者x∈－α定义一个新数等价，即：

4) ，——(2)(3)，

5)假设TJ——问TJ吗？假设TJ成立，那么存在某个xx=T

6) ，——(5)代入，得到矛盾，

7)

1)在以上定理证明过程中，根据“反证法的使用规则”，把xPU看成假设时，可以使用“反证法”进行推理，只能得出xPU；把xPU看成真命题时，使用“反证法”是错误的。

2)“U外不动项定理”与“广义U外不动项定理”都是用二分法把全集U分成两类性质集合，命题P是关于U的一个划分，，即：

3)“U外不动项定理”与“广义U外不动项定理”的本质是：一个U中已经定义的项与其否定项不能自指代。如果自指代，就会变异成一个新项“T”，这个新项“T”不再是U的元素，即：TU

4)“U外不动项定理”与“广义U外不动项定理”的区别是：“U外不动项定理”要求+α,－α之间存在双射关系，即：f:+α～－α；“广义U外不动项定理”没有这个要求。

5)“Cantor对角线方法”可以看成是U上的一个特殊的分类。从“U外不动项定理”的分类看，使用自然数标号与它对应的第n项分类，这个分类恰与双射关系Uω联系在一起；从“广义U外不动项定理”的分类看，+α=R，所构造的项T不同于R中的每一个数，TR，这个分类可以不涉及双射关系Uω

5.3 无穷集合幂集合不可数证明错误

a1=0.0143634628…

a2=0.3794907237…

a3=0.2334343423…

a4=0.0005948211…

a5=0.9590129145…

ω是自然数集合，Q全体正有理数集合，假设双射关系F:ωQ成立。

,

，即否定了(TQ)。

,，否定了双射关系

 (1)
 (2)

U为全体正有理数集合U=Q，假设双射关系F:ωQ成立，ω是自然数集合，Q为全体正有理数集合。

U=Q分成正反集合，

F(n)∈+α，或者F(n)∈－α

U为不为0的全体实数集合

U分成正数集合与负数集合：

F(n)∈+α，或者F(n)∈－α

1)

2)

3)

4)

5)

6)

7) ，即无穷集合不能与它的幂集合建立一一对应关系；

8) ，即自然数集合不能与它的幂集合建立一一对应关系；

9) ，即自然数集合不能与实数集合建立一一对应关系。

10)

11)

12)

1)不动项命题矛盾的存在，不影响集合之间元素的一一对应关系，所以，Cantor对角线法关于无穷集合的幂集不可数证明；自然数的幂集不可数证明；实数不可数的证明都是错误。

2)如果能够构造出实数与自然数的一一映射关系，那么，实数就是一个可数集合，Cantor没有找到这种一一映射关系，并不代表这种对应关系就不存在。前面的证明中，已经知道，不动项TR是一个U外不动项，它相对于已经定义的集合，是一个未定义项，根据不动项的两种形式，这里意味着，要么，在实数集合之外存在着一种尚未定义、没有构造的新数TR；要么，这个构造数TR根本就不存在。

6 递归论中的一些定理的错误证明 6.1 N上存在非递归函数证明错误

1)递归函数集合是可数的，考察一元递归函数的一个枚举f0,f1,f2,…，定义一个函数g(m,n)=fm(n)，假设g(m,n)=fm(n)是递归的，h(m)=g(m,m)+1，mω是递归的，

h(k)=fk(k)=g(k,k)+1=fk(k)+1，矛盾，所以，g(m,n)=fm(n)不是递归函数[3]

2)不存在一元递归函数的能行可枚举，是“对角线证明方法”。

h(n)=fn(n)+1，nω是递归的，

h(k)=fk(k)=fk(k)+1，矛盾，所以，不存在一元递归函数的能行可枚举[3]

3)以下定理是“对角线证明方法”，证明错误：

D(x,y)是一元原始递归函数的通用函数，则D(x,y)不是二元原始递归函数。

 x y 0 1 2 3 … 0 D(0,0) D(0,1) D(0,2) D(0,3) … 1 D(1,0) D(1,1) D(1,2) D(1,3) … 2 D(2,0) D(2,1) D(2,2) D(2,3) … 3 D(3,0) D(3,1) D(3,2) D(3,3) … … … … … … …

x=ng(n)=D(n,n)

g(n)=D(n,n)=D(n,n)+1，矛盾，所以，D(x,y)

6.2 Turing机“停机问题”证明错误

Turing证明，Turing机“停机问题”是不可判定的，即：不存在算法对以下问题类提供答案，{Turing机Tm在输入n后是否会停机| m,nN}。

Turing机Tm在输入n后是否会停机的各种情况排列如表 7(表中的所有情况与二进制表示的实数等价)。

 T0 T1 T2 T3 T4 … f(0) 0 1 0 0 1 … f(1) 0 1 0 1 1 … f(2) 0 1 0 1 0 … f(3) 0 0 0 1 0 … f(4) 1 0 0 1 0 … … … … … … … …

T输入n后输出1⇔Tg输入n后会停机。

Tg是一个新的图灵机，Tg必然出现在T0,T1,T2,…,Tm,…中，设Tg=Tk

Tk输入k后会停机⇔T输入k后输出1⇔f(k)=1⇔Tk输入k后不停机。

P(Tn)⇔Tn在输入n后会停机；在输入n后不会停机。

xP满足x=f(x)，xP是不动项。

U是所有Turing机对所有输入后的状态，这些状态可分为正反两个集合。

，(Tg,k)是不动项。

6.3 一批错误结论及其根源

“不动项定理”表明，形形色色排除悖论的努力都是徒劳的，只要有“自指代”，就可能产生悖论。命题逻辑系统L，谓词演算系统K，只要使用“自指代”，同样会有悖论，集合论ZF系统中也没有禁止“自指代”，ZF系统根本防止不了悖论，同样会产生悖论。

“不动项定理”表明，解释清晰后的“悖论”，不但无害，反而有益。无害是因为，悖论是U外项命题，不会对原有的集合U上的演算产生破坏；有益是因为，悖论命题是U外的一种未定义命题，可能是U外的一种新知，这给科学发现指明了一种探求方向。

“不动项定理”还表明，经典逻辑只适用于已经定义的集合，不动项矛盾(悖论)不能作为“反证法”在已定义的集合上的推理依据。可以检查一下，以往的数学证明中，哪些“反证法”证明使用了不动项矛盾，这些证明都是错误的，这里我检查了一些证明，把一些错误的证明结果列表如下：

1)(Gödel不完全定理)如果系统Nω一致的，那么，存在公式μ不是N的定理，且也不是N的定理。即：系统N是不完全的[2]

2)任何充分丰富一致的系统，如果系统公理的哥德尔数集合是递归集合，那么它是不完全的。特别地，如果ZF一致的，那么它是不完全的[2]

3)停机问题是不可判定的，即：不存在算法对以下问题类提供答案：

{Turing机Tm在输入n后是否会停机[2]

4)不存在所有单变元递归函数的能行枚举[2]

5)自然数集合上存在非递归集合。

6)自然数集合上存在非递归函数。

7)自然数集合上存在半递归谓词(存在递归可枚举集合)。

8)(Cantor定理)如果PMM的幂集，且MPM，则存在TTM，且TPM。无穷集合的幂集不可数[3]

9)自然数集合与它的幂集合不可能建立一一映射关系。即：自然数集合的幂集不可数[3]

10)自然数集合与实数集合不可能建立一一映射关系。即：实数集合不可数[3]

11)对任何集合M，(任何集合的基数小于其幂集的基数)。即：超穷数存在，层次无穷存在[3]

12)(Cantor连续统假设)在之间不存在任何基数。

13)(Gödel-Rosser定理) N的任何递归无矛盾扩张N*都不完备。即：如果N*是系统N一致的扩充，并且N*系统公理的哥德尔数集合是递归集合，那么N*是不完全的[4]

14)设从N可证的公式Gödel数全体构成的集合记为，若N无矛盾，则TH是非递归集合[4]

15)所有N中的恒真公式Gödel数全体构成的集合记为，则TR是非递归集合[4]

16)(Tarski定理)TR不是算术集合[4]

《数理逻辑》中以此定理为基础的演绎理论都是错误的。

论文(Ⅰ)、(Ⅱ)有大量省略，原稿有更详细论证，需要请与作者联系。

 [1] 陈汝栋. 不动点理论及应用[M]. 北京: 国防工业出版社, 2012 : 1 -4. [2] 戴牧民, 陈海燕. 公理集合论导引[M]. 北京: 科学出版社, 2011 : 15 -17. [3] 张金成. 容纳矛盾的逻辑系统与悖论[J]. 系统智能学报 , 2012, 7 (3) : 208-209 [4] HAMILTON A G. Logic for Mathematicians[D]. Cambridge: University of Cambridge,1978:29-40,82-92. [5] 李未. 数理逻辑[M]. 北京: 科学出版社, 2008 : 105 -110. [6] 张立昂. 可计算性与计算的复杂性[M]. 北京: 北京大学出版社, 2011 : 80 -85. [7] 克林S C.元数学导论[M].莫绍揆,译.北京:科学出版社,1984:4-12. [8] 何华灿. 泛逻辑学原理[M]. 北京: 科学出版社, 2001 : 1 -15. [9] Boolos. 可计算性与数理逻辑[M]. 北京: 电子工业出版社, 2002 : 152 -160. [10] 汪芳庭. 数理逻辑[M]. 北京: 科学出版社, 2001 : 159 -163.
DOI: 10.3969/j.issn.1673-4785.201310076

0

#### 文章信息

ZHANG Jincheng

Fixed terms and undecidable propositions in logical and mathematical calculus (Ⅱ)

CAAI Transactions on Intelligent Systems, 2014, 9(5): 618-631
http://dx.doi.org/10.3969/j.issn.1673-4785.201310076