汉语是联合国官方正式使用的 6 种同等有效语言之一。请不要歧视汉语!
Chinese is one of the six equally effective official languages of the United Nations.
Not to discriminate against Chinese, please!
[请教,讨论,笔记] “四色定理 four color theorem”和“康托定理 Cantor theorem”有关系吗?
四色定理: four color theorem
图论: graph theory
康托定理: Cantor theorem
策梅洛-弗伦克尔-选择公理公理集合论: ZFC, Zermelo–Fraenkel set theory with the axiom of choice
幂集公理: axiom of power set
我试了试,好像有关系。
图1 裁剪自《第二类计算机构想》 第 371 页:
http://qikan.cqvip.com/Qikan/Article/Detail?id=39096952&from=Qikan_Search_Index
https://www.cnki.com.cn/Article/CJFDTotal-KJPL201104010.htm
2007-11-13 在《科学网》BBS贴出的一个图片?
图2 Four-Colour Problem
It is an especial case of Cantor theorem
四色问题
是康托定理的一个特例
图3 孔子老师《论语·卫灵公篇》:“工欲善其事,必先利其器。”
https://www.chinasource.org/wp-content/uploads/2020/04/Confucius_Sculpture__Nanjing-2-scaled.jpg
狄利克雷(Johann Peter Gustav Lejeune Dirichlet):
“用清晰的思想代替盲目的计算
Replacing blind calculations by clear ideas.”
不仅如此,作为哥德尔第一不完全性定理的详细化,1966~1974年的 Chaitin 定理里也说:
Unfortunately, any formal system in which it is possible to determine each string of complexity less than n has either one grave problem or another. Either it has few bits of axioms and needs incredibly long proofs, or it has short proofs but an incredibly great number of bits of axioms. 不幸的是,任何一个可以确定每个复杂度小于n的字符串的形式系统都有一个或另一个严重的问题。要么它有很少的公理,需要非常长的证明,要么它有很短的证明,但有非常多的公理。
这可以看做是对孔子老师“工欲善其事,必先利其器。”的一个现代化的细致的解释。
参考资料:
[1] 2023-08-23,四色定理/four color theorem/魏美芹,中国大百科全书,第三版网络版[DB/OL]
https://www.zgbk.com/ecph/words?SiteID=1&ID=115136&Type=bkzyb&SubID=61825
直到1976年,美国数学家K.阿佩尔(Kenneth Appel,1932-10-08~2013-04-19)和德国-美国数学家W.哈肯(Wolfgang Haken,1928-06-21~2022-10-02)借助计算机得到了四色猜想的证明,也就得到了著名的四色定理。
除了泰特以外,还有很多数学家为四色猜想的证明进行了大量工作。直到现在,数学家们仍在寻求四色定理的一个不借助计算机的纯粹数学的证明。
[2] 2022-12-03,图论/graph theory/吴迪,李学良,中国大百科全书,第三版网络版[DB/OL]
https://www.zgbk.com/ecph/words?SiteID=1&ID=113666&Type=bkzyb&SubID=61823
图论中还有一个最著名的问题——四色问题。四色问题又称为四色定理、四色猜想,是世界三大数学猜想之一。通俗地说,四色问题指每个地图都可以用不多于四种颜色来染色,而且任何两块邻接的区域不会染相同的颜色,其中邻接的两块区域是指它们有一段公共的边界,而不仅仅只是一个公共的顶点。
直到1976年,数学家凯尼斯·阿佩尔和沃夫冈·哈肯利用伊利诺伊大学的电子计算机运行了1200小时得到了该问题第一个完整的证明,从此四色问题也成为了四色定理,这也是第一个借助计算机证明的定理。不久,伊利诺伊大学数学系的邮戳上加上了“Four Colors Suffice”(四种颜色就够了),以庆祝四色猜想得到解决。
[3] 科普中国,2021-12-31,四色定理
https://www.kepuchina.cn/article/articleinfo?business_type=100&classify=0&ar_id=285922
[4] 科普中国,2023-07-25,四色定理:古典着色问题的新时代算法
https://www.kepuchina.cn/article/articleinfo?business_type=100&classify=0&ar_id=427866
[5] Four-colour problem. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Four-colour_problem
[6] The four colour theorem, MacTutor History of Mathematics Archive
https://mathshistory.st-andrews.ac.uk/HistTopics/The_four_colour_theorem/
[7] Weisstein, Eric W. "Four-Color Theorem." From MathWorld--A Wolfram Web Resource.
https://mathworld.wolfram.com/Four-ColorTheorem.html
[8] 2022-07-13,策梅洛-弗兰克尔集合论/Zermelo-Fraenkel set theory/杜国平,中国大百科全书,第三版网络版[DB/OL]
https://www.zgbk.com/ecph/words?SiteID=1&ID=229361&Type=bkzyb&SubID=104156
[9] 2023-08-22,数学基础/foundations of mathematics/何浩平,中国大百科全书,第三版网络版[DB/OL]
https://www.zgbk.com/ecph/words?SiteID=1&ID=456822&Type=bkzyb&SubID=137849
E.F.F.策梅洛、A.A.弗伦克尔(Adolf Abraham Fraenkel)等人发展出的ZFC(策梅洛-弗伦克尔-选择公理)公理集合论,是今天通行的公理集合论。ZFC公理集合论是万有理论,能够推导出经典数学的所有理论。
[10] ZFC ( Zermelo–Fraenkel set theory with the axiom of choice ) . Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/ZFC
[11] Ernst Friedrich Ferdinand Zermelo, MacTutor History of Mathematics Archive
https://mathshistory.st-andrews.ac.uk/Biographies/Zermelo/
[12] A history of set theory, MacTutor History of Mathematics Archive
https://mathshistory.st-andrews.ac.uk/HistTopics/Beginnings_of_set_theory/
[13] Cantor theorem. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Cantor_theorem
[14] 2023-04-11,康托尔,G. /Georg (Ferdinand Ludwig Philipp) Cantor/王宪钧 撰程钊 修订,中国大百科全书,第三版网络版[DB/OL]
https://www.zgbk.com/ecph/words?SiteID=1&ID=182825&Type=bkzyb&SubID=61733
1879~1884年,发表题为“关于无穷线性点集”的系列论文6篇,提出了良序集、序数及数类的概念,定义了一个比一个大的超穷序数和超穷基数的无穷序列,还提出良序定理(每一集合都能被良序)。
1891年发表“集合论的一个根本问题”,证明了一集合的幂集的基数较原集合的基数大,由此可知没有包含一切集合的集合。
[15] Weisstein, Eric W. "Cantor's Theorem." From MathWorld--A Wolfram Web Resource.
https://mathworld.wolfram.com/CantorsTheorem.html
[16] Gregory John Chaitin. Information-theoretic computation complexity [J]. IEEE Transactions on Information Theory, 1974, 20(1): 10-15.
DOI: 10.1109/TIT.1974.1055172
https://ieeexplore.ieee.org/document/1055172
https://dl.acm.org/doi/10.1109/TIT.1974.1055172
[17] Gregory J. Chaitin. On the length of programs for computing finite binary sequences [J]. Journal of the ACM, 1966, 13(4): 547-569.
doi:10.1145/321356.321363
https://dl.acm.org/doi/10.1145/321356.321363
[18] 杨东屏. 哥德尔不完全性定理剖析[J]. 曲阜师范大学学报:自然科学版,1993,19(1):31-36.
https://kns.cnki.net/KCMS/detail/detail.aspx?dbcode=CJFD&filename=QFSF199301005
[19] 杨正瓴. 第二类计算机构想 [J]. 中国电子科学研究院学报, 2011, 6(4): 368-374.
http://qikan.cqvip.com/Qikan/Article/Detail?id=39096952&from=Qikan_Search_Index
https://www.cnki.com.cn/Article/CJFDTotal-KJPL201104010.htm
相关链接:
[1] 2023-03-01,[打听] 四色定理计算机“证明”的“诗、电话簿”原文
https://blog.sciencenet.cn/blog-107667-1378486.html
https://wap.sciencenet.cn/blog-107667-1378486.html
[2] 2023-01-13,[???] 为什么在“四色问题 The four colour theorem”上长期不肯吱声?
https://wap.sciencenet.cn/blog-107667-1371830.html
[3] 2013-10-04,数学证明的长度:与公理系统能力负相关 精选
https://blog.sciencenet.cn/blog-107667-729907.html
[4] 2022-09-20,[新闻] Science 发文:同行评议偏见的定量实证
https://blog.sciencenet.cn/blog-107667-1356141.html
[5] 2020-08-17,小忆“第2类数学(智能数学)”的提出
https://blog.sciencenet.cn/blog-107667-1246726.html
[6] 2022-03-01,[科普 + 备课] Chaitin定理(1966年)
https://blog.sciencenet.cn/blog-107667-1327564.html
感谢您的指教!
感谢您指正以上任何错误!
感谢您提供更多的相关资料!
转载本文请联系原作者获取授权,同时请注明本文来自杨正瓴科学网博客。
链接地址:https://wap.sciencenet.cn/blog-107667-1441104.html?mobile=1
收藏