实数上的可数颜色染色问题

作者: , 共 699 字

命题:实数集 \( \mathcal{R}\) 上的任何一个可数种颜色染色方案,都存在四个不等的同色点 \( x, y, z, w\) 使得 \( x+y=z+w\)

这个问题是一个月前在 Computational Complexity 看到的。前两天在 测不准原理还是不确定性原理 我提到了不可证明问题,今天顺便把上面这个问题拿出来溜一溜。

这是一个非常非常自然的问题,看上去就是一个普通的组合问题,类似于 Ramsey 问题的变种,而且研究这个问题的(包括 Erdos !)也多数是组合学家。但其答案却出人意料,因为这个问题被证明是 不可证明的 ,它 独立于 ZFC 公理体系 :

定理:此命题成立当且仅当 连续统假设 不成立。

而连续统假设在上个世纪七十年代便已经证明了独立于 ZFC。

上面等价性定理的证明在 这里 (pdf ,英文 ) 。证明过程很短。即便我对集合论了解甚少,对我来说除了 Fact 1.3 之外,其余的都很好懂。

PS :做算法和复杂性的不要错过这个 blog : Computational Complexity 。从 blog 标题就能看出它的内容了。

PS2 :网友 yue 给我推荐了一个信息和数学类的 blog , Matrix67 ,据称内容为 50% Informatics, 50% Mathematics, and 50% Imagination。令人惊奇的是, blog 作者居然是 北大中文系 的。这位兄弟如此喜欢数学,完全可以向其前辈学习一下,从中文系转系到数学系去,这是有过先例的。

Q. E. D.

类似文章:
注 : 这个问题来自 China Theory Week 2008 的 Open Problems Session。
上篇文章 已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP- 完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
"Good mathematics" could refer (in no particular order) to
相似度: 0.047
注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是 Andrew Yao 的研究方向
Game Theory 即博弈论,目前在经济学中运用得最多 ( 纳什更因为他在这上面的工作拿到了诺贝尔经济学奖 )。但在最近几年,理论计算机界对它的研究也很热。
碎碎念 » 收入, 科研, 教育
昨天无意中得知了清华某中心博士后的收入为 3300( 津贴 )+1000( 房补 )。多乎哉?不多也。