求真分享 http://blog.sciencenet.cn/u/zlyang 求真务实

博文

否证“连续统假设”?

已有 7379 次阅读 2012-7-12 22:35 |系统分类:科研笔记|关键词:NPI,否证,连续统假设,无穷化| NPI, 否证, 连续统假设, 无穷化

否证“连续统假设”?
 
        从陈绥阳教授的《千虑一失,一虑百得》,以及闵应骅教授的《[转载]转载:科学出版社竟然出版如此反智的书》,听说***教授“断定自然数集与实数集等势”。
        这是徐建良教授建议我看看的
  
        主流数学认为:
        “连续统假设在ZF(或GB)中是不可判定的,它即不能被证明,也不能被否证。”“Formal unsolvability is understood in the sense that there does not exist a formal derivation in the
Zermelo–Fraenkel system ZF either for the continuum hypothesis or for its negation. ”
  
        既然这样,否证连续统假设也不是什么太创新的东西。只要您愿意,就可以构造些“接受连续统假设”、“不接受连续统假设”的不同的公理系统。
 
        实际上,在理论计算机科学里,NPI(NP-Intermediate,NP里不属于P类且不属于NP-完全问题)的无穷化版本就是Cantor原本意义下的连续统假设:
        The hypothesis, due to G. Cantor (1878), stating that every infinite subset of the continuum R is either equivalent to the set of natural numbers or to R itself.
        An equivalent formulation (in the presence of the axiom of choice) is:

(see Aleph).

        不难看出,Hilbert 等人在“承认选择公理”条件下的这一表述(请求来源),引来无穷多的麻烦。陈绥阳教授写道:“1947年,Sierpinski发表证明说,广义连续统假设可以推出选择公理。那么,如果选择公理出问题,自然就产生对广义连续统假设的质疑。这从Zermelo—Fraenkel公理集合论中承认与不承认选择公理可以看出矛盾。”

        问题在于:Cantor原本意义下的连续统假设,与axiom of choice有关系吗?

        所以1975年 Ladner 证明“如果P≠NP,则 NPI = (NP–P) 不是空集”以及1993年 Zimand 证明如果NP–P不空则很大(If not empty, NP - P is topologically large),都不能给出确定的结果。
   
        从前俺想要国家出钱,买一台10~20万的工作站,进行NPI的数值实验寻找工作。写了申请书,专家说俺水平不够,没有批准。所以到现在也没有进行NPI的构造研究。
        上帝说:不着急,留给你慢慢做吧!上帝真的说过吗?俺也不很清楚。
        尊敬的看官:不建议您用20万以上的工作站去寻找NPI。担心您找不出来。李未教授1999年04期《中国科学E辑》的“SAT问题的相变现象”都没有找到NPI,您可得小心啊!
   
        其实俺要说NPI和否证连续统假设是有密切关系的。
  
        请您提供有关的最新动态。谢谢!
 
 
相关链接:
[2] 闵应骅《[转载]转载:科学出版社竟然出版如此反智的书》
http://bbs.sciencenet.cn/home.php?mod=space&uid=290937&do=blog&id=588795&cid=1944227
[3] 《A FULL PROOF to the P versus NP problem》
http://bbs.sciencenet.cn/blog-107667-486692.html
[4] Continuum hypothesis - Encyclopedia of Mathematics
http://www.encyclopediaofmath.org/index.php/Continuum_hypothesis
[5] ZFC - Encyclopedia of Mathematics
http://www.encyclopediaofmath.org/index.php/ZFC
[6] Axiomatic set theory - Encyclopedia of Mathematics
http://www.encyclopediaofmath.org/index.php/Axiomatic_set_theory
[7] Cantor theorem - Encyclopedia of Mathematics
http://www.encyclopediaofmath.org/index.php/Cantor_theorem
[8] 《[请教] P对NP:请郝克刚教授等专家指教(一)》
http://bbs.sciencenet.cn/home.php?mod=space&uid=107667&do=blog&id=550859
[9] Alternative Axiomatic Set Theories - Stanford Encyclopedia of Philosophy
http://plato.stanford.edu/entries/settheory-alternative/
 
 
相关的讨论与交流:
        “连续统假设”出来50多年之后,才有Gödel的【数学-逻辑系统】的不可判定性。由1931年的不完全性定理引发。
        您说的【不可判定问题理论】,应该是Turing在1936年之后的理论计算机科学里的【不可判定问题理论】吧? 后者似乎是前者的具体化。
        实际上,Gödel 也研究过计算机理论,据说【P对NP】最早是Gödel 于 20 March 1956 给 von Neumann的信件中提出的,可惜该信目前找不到原件了。
这个说法出自:
Michael Sipser, The history and status of the P versus NP question, in Proceedings of ACM STOC'92, pp. 603–618, 1992.
以及一些网上资源。
 
        图灵在他的重要论文《论可计算数及其在判定问题上的应用》(英语:On Computable Numbers, with an Application to the Entscheidungsproblem,1936年5月28日提交)里,对哥德尔1931年在证明和计算的限制的结果作了重新论述,他用现在叫做图灵机的简单形式装置代替了哥德尔的以通用算术为基础的形式语言。由于速度很慢,尽管没有一台图灵机会有实际用途,图灵还是证明了这样的机器有能力解决任何可想像的数学难题,如果这些难题是用一种算法来表达。现今,图灵机还是计算理论研究的中心课题。他继续证明了判定问题(Entscheidungsproblem)是没有答案的。他的证明首先展示了图灵机的停机问题(halting problem)是没有答案的,这是说不可能用一个算法来决定一台指定的图灵机是否会停机。尽管他的证明比阿隆佐·邱奇在λ演算方面相等的证明晚发表了几个月,图灵的著作是更易于理解和直观的。 他的通用(图灵)机的概念也是新颖的。这一通用机能够完成任何其他机器所能做的任务。这篇论文还介绍了可定义数的概念。
http://zh.wikipedia.org/wiki/%E8%89%BE%E4%BC%A6%C2%B7%E5%9B%BE%E7%81%B5


http://blog.sciencenet.cn/blog-107667-591577.html

上一篇:[CCTV拍片邀请] CCTV-10原来如此栏目的制片人薛建峰老师邀请拍片
下一篇:向您推荐《摄影频道_新华网》:新华摄影

6 陈小润 曾新林 徐建良 张树风 苏德辰 dulizhi95

该博文允许注册用户评论 请点击登录 评论 (7 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-1-20 13:23

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部