“人是社会关系的总和,人不能脱离社会而存在。”
物质世界是“普遍联系”和“永恒发展”的。
数学是现实世界中的“数量关系”和“空间形式”的科学。
真理越辩越明。
汉语是联合国官方正式使用的 6 种同等有效语言之一。请不要歧视汉语!
Chinese is one of the six equally effective official languages of the United Nations.
Not to discriminate against Chinese, please!
[请教,讨论] P对NP(六):无穷化版本与连续统假设CH
谈到无穷时,“无穷公理”、“选择公理”的争议就无法回避了。下面一律采用主流观点。
一、连续统假设的基本含义
康托 1878年提出的“连续统假设, CH, Continuum hypothesis”,基本含义是:
连续统 R 的每个无限子集,要么等势于自然数集,要么等势于 R 本身。
换言之,在“连续统的基数”、“自然数集的基数”之间,是否存在别的基数?假如存在别的无穷级数,则连续统假设不正确。
哥德尔在1938年发表的论文“选择公理与广义连续统假设的相容性”中指出选择公理和广义连续统假设相对于通常的集合论公理系统是相容的(详细证明在1940年发表)。
1966年 Paul Joseph Cohen (科恩)在专著《Set theory and the continuum hypothesis》里证明了“the independence of the continuum hypothesis and the axiom of choice. 连续统假设、选择公理,独立于ZF里面的其它公理。”
综上:
“连续统假设正确”、“连续统假设错误”都是可以的。取决于您的选择。
二、“P对NP的无穷化”版本与“连续统假设”
其实很简单:
在无穷化情况下,例如允许 NTM 等的输入字符、运算时间等都取为“可数无穷”多个,即自然数集多个,那么在多项式时间内 NTM 产生的总状态数可以达到“连续统”的,而它对应的 DTM 产生的总状态数只能是“自然数集”的。
这样,假如存在“NPI,NP-Intermediate”,则其无穷化的结果就是“连续统假设错误”。
假如能够构造一个时间复杂性为 2lgn 的问题,则其无穷化就是介于“可数无穷、连续统”之间的无穷级数。这里n为自然数。
目前看:这种可能性是存在的。因此否证“连续统”假设是可能的。
三、将“P对NP”联系上“连续统假设”:实属无奈
上个世纪,“P对NP”已经是著名难题了。
进入本世纪,“P对NP”更是被炒作的无与伦比。
除非您是名家,否则谁会认真对待一个普通教师的研究结果的?
历史上伽罗华(Evariste Galois)、阿贝尔(Niels Henrik Abel)已经悲剧数次了。
人类历史上数学家综合排行榜第一的柯西(Augustin Louis Cauchy),对伽罗华、阿贝尔的做法是“仓促的、肮脏的、肤浅的 hasty, nasty, and superficial”。
Again his treatment of Galois and Abel during this period was unfortunate. Abel, who visited the Institute in 1826, wrote of him:-
Cauchy is mad and there is nothing that can be done about him, although, right now, he is the only one who knows how mathematics should be done.
Belhoste in [4] says:-
When Abel's untimely death occurred on April 6, 1829, Cauchy still had not given a report on the 1826 paper, in spite of several protests from Legendre. The report he finally did give, on June 29, 1829, was hasty, nasty, and superficial, unworthy of both his own brilliance and the real importance of the study he had judged.
https://mathshistory.st-andrews.ac.uk/Biographies/Cauchy/
就算您是喀山大学校长(罗巴切夫斯基, Nikolay Ivanovich Lobachevsky),人类历史上数学家综合排行榜第二的高斯(Johann Carl Friedrich Gauss),也未必肯公开支持您的非欧几何!并且私下表态:“您这玩意,我 15 岁时就知道!”
In 1831 Farkas Bolyai sent to Gauss his son János Bolyai's work on the subject. Gauss replied
to praise it would mean to praise myself .
Again, a decade later, when he was informed of Lobachevsky's work on the subject, he praised its "genuinely geometric" character, while in a letter to Schumacher in 1846, states that he
had the same convictions for 54 years
indicating that he had known of the existence of a non-Euclidean geometry since he was 15 years of age (this seems unlikely).
https://mathshistory.st-andrews.ac.uk/Biographies/Gauss/
哥德尔是超级幸运儿啊!立刻得到了道德楷模希尔伯特的支持。人家希尔伯特可是人类历史上数学家综合排行榜第四。哥德尔在1931年淘气时,前三(柯西、高斯、庞加莱)都已经去世多年。道德楷模希尔伯特尽管是历史排名第四,在当时可是第一啊!
只有将“P对NP”和名题、名人挂钩,才有利于引起别人的重视。
赫胥黎说过“历史告诫我们说,一种崭新的真理惯常的命运是:始于异端,终于迷信。”History warns us, however, that it is the customary fate of new truths to begin as heresies and to end as superstitions. --- Thomas Henry Huxley, 1880
“一切真理开始时总是在少数人手里,总是受到多数人的压力。这是一个规律。”
“一万年以后,先进的东西开始也还是要挨骂的。”
所以,尽管无穷化后必定引起争议,也实在没有别的办法了。从1993年下半年开始,“NTM 相当于 DTM 的幂集”这个主要结论一直隐藏在各个材料里。不用“连续统假设”进行炒作,“NTM 相当于 DTM 的幂集”也未必会让别人信服。
用“连续统假设”去吓唬别人!
为了故作高深,必须把“P对NP”复杂化!“拉大旗作虎皮,包着自己,去吓唬别人。”(鲁迅《且介亭杂文末编·答徐懋庸并关于抗日统一战线问题》)
参考资料:
[1] Continuum hypothesis. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Continuum_hypothesis
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.
[2] 2023-04-27,哥德尔,K./王宪钧 撰、程钊 修订,中国大百科全书,第三版网络版[DB/OL]
https://www.zgbk.com/ecph/words?SiteID=1&ID=182832&Type=bkzyb&SubID=61734
[3] Kurt Godel. The consistency of the axiom of choice and of the generalized continuum-hypothesis [J]. Proceedings of the National Academy of Sciences of the United States of America, 1938, 24(12): 556-557
doi: 10.1073/pnas.24.12.556
[4] Paul Joseph Cohen, MacTutor History of Mathematics archive
https://mathshistory.st-andrews.ac.uk/Biographies/Cohen/
[5] Paul Joseph Cohen. Set theory and the continuum hypothesis [M]. W. A. Benjamin, Inc., New York and Amsterdam, 1966, vi + 154 pp.
[6] Augustin Louis Cauchy, MacTutor History of Mathematics Archive
https://mathshistory.st-andrews.ac.uk/Biographies/Cauchy/
[7] Home | The Abel Prize
[8] The History of the Abel Prize, The Abel Prize
https://abelprize.no/page/history-abel-prize
[9] A mathematical genious, The Abel Prize
https://abelprize.no/page/about-niels-henrik-abel
发表的论文:
[1] A non-canonical example to support that P is not equal to NP. Transactions of Tianjin University, 2011, 17(6): 446-449.
doi: 10.1007/s12209-011-1593-5
https://link.springer.com/article/10.1007/s12209-011-1593-5
[2] 第二类计算机构想. 中国电子科学研究院学报, 2011, 6(4): 368-374.
doi: 10.3969/j.issn.1673-5692.2011.04.009
https://d.wanfangdata.com.cn/periodical/dzkxjspl201104009
[3] 密码学与非确定型图灵机. 中国电子科学研究院学报, 2008, 3(6): 558-562.
http://qikan.cqvip.com/Qikan/Article/Detail?id=28856183&from=Qikan_Search_Index
相关链接:
[1] [讨论] P对NP(五):宇宙“热寂”之前,“幂集公理”不会有太大的毛病?
https://blog.sciencenet.cn/blog-107667-1394169.html
[2] 2023-07-04,[请教] P对NP(四):相关要点小结(问答式)
https://blog.sciencenet.cn/blog-107667-1394027.html
[3] 2023-06-29,[请教] P对NP(三):“NP完全性, NP-completeness”之后
https://blog.sciencenet.cn/blog-107667-1393466.html
[4] 2022-06-10,[请教] P对NP(二):结果的相对性与“1+3”种证明
https://blog.sciencenet.cn/blog-107667-1342404.html
[5] 2012-03-23,[请教] P对NP:请***教授等专家指教(一)
https://blog.sciencenet.cn/blog-107667-550859.html
[6] 2023-01-16,[搞笑?搞哭?汇集] 怎样判断“原创”和“诺贝尔奖成果”?
https://blog.sciencenet.cn/blog-107667-1372203.html
[7] 2015-05-22,The kernel of "P vs NP Problem": Axiom of power set!
https://blog.sciencenet.cn/blog-107667-892400.html
感谢您的指教!
感谢您指正以上任何错误!
感谢您提供更多的相关资料!
转载本文请联系原作者获取授权,同时请注明本文来自杨正瓴科学网博客。
链接地址:https://wap.sciencenet.cn/blog-107667-1394463.html?mobile=1
收藏