逻辑

虚幻的着色

对于非逻辑学家而言,选择公理,良性琐碎性使数学家感到困惑。今天,它以一种奇怪的方式展示自己:根据公理的变体,它需要两种或无限种颜色来解决着色问题!

让·保罗·德拉海 对于科学N°328
本文仅供《 对于科学》的订户使用
正如类似的假设似乎毫无疑问地作为几何证据一样,选择公理经常被认为是真实的,并且不容讨论。集合论的发明者Georg Cantor(1845-1918)在没有意识到的情况下使用了几次。朱塞佩·皮亚诺(Giuseppe Peano(1858-1932))于1890年以有意识的方式使用它,当时它是一个有意识的方式,但它是Ernst Zermelo(1871-1953)的开始。 xxe 世纪,明确地确定和研究了它。

该公理断言,如果给定一组不相交和非空的集合,例如包含三个集合{1,2},{a,b,c},{x,y}的集合E,则存在由每个E集的一个元素组成的集C,例如C = {2,a,y}。图3解释了选择公理的两种不同形式以及使之成为微妙公理的原因。

选择公理独立于集合论的其他公理,因为平行的假设独立于几何学的其他公理。这些其他公理都可以接受,您可以在没有矛盾风险的情况下接受选择公理,也可以接受其否定。

这些所谓的“相对一致性”结果在1939年由KurtGödel(可以在不引入任何矛盾的情况下添加选择公理)和Paul Cohen在1963年(也可以在对选择公理而不引入矛盾)。与平行假设一样,它们意味着几个不同的宇宙是可能的。

就几何而言,平行假设的独立性证明,非欧几里得几何值得研究,甚至可以在物理学中使用:阿尔伯特·爱因斯坦(Albert Einstein)在1907年至1915年间利用这一点发展了这一点。他的广义相对论。

关于选择公理,一个类似的逻辑结论引人注目:需要探索不满足选择公理的宇宙,这可能对物理学感兴趣。

迈向既定的革命?

但是,数学家相对于选择公理的态度并不是他们今天在几何学中所采用的。在集合论中,主要观点是坚持选择公理是正确的,几乎完全忽略了竞争公理,其中一些很有趣(参见图3)。一切都发生了,好像集合论中还没有发生非欧几里德几何的革命一样,而集合论如今已成为所有数学的基础。

证明这种不感兴趣的隐含论点是,选择公理在处理简单问题以及处理更细微的问题(例如分析问题)时很少具有重要性。 -,最好采用它,因为我们确实需要它来建立我们无法想象的基本定理。

普林斯顿大学的Alexander 索菲和耶路撒冷大学的Saharon 谢拉分别于2003年和2004年发布了一系列有关图论的结果,这应该证明我们的态度并激发我们对以下问题的好奇心提供给选择公理的替代方案。对A. 索菲和S. 谢拉的论证应迫使数学家考虑基础问题:建立物理学家和数学家的数学应遵循哪些公理?

对于着色图的简单问题,

两位数学家表明,所需的颜色数量取决于我们选择的是公理还是它的较弱版本之一:在一种情况下,两种颜色允许所需要的着色,在另一种情况下,有限数量的颜色颜色的数量(无论大小)不足。

知道集合世界满足选择公理还是竞争公理,对于解决没有人想到的问题是决定性的。新结果提出的问题与布景世界的深层本质有关。相信集合的数学世界是真实的,这是否合理?如果存在,那么现实的世界-我们给我们留下活生生的印象的世界-是否允许S. 谢拉和A. 索菲用两种颜色着色,还是需要它们的无限性?

为了了解A. 索菲和S. 谢拉的结果所造成的情况的陌生性,让我们看看数学家感兴趣的着色问题。

着色图

上色练习是甚至幼儿也存在的数学问题之一。如何在避免两个相邻区域合并的同时为几何设计着色?如何为两个连续的区域选择不同的颜色? 4色定理给出了答案:无论要着色的区域多么复杂-与地图上绘制的国家一样-总是可以用4种颜色进行着色。请注意,当在圆环上(车轮内胎的表面)绘制地图时,该定理(全部使用计算机的证明)不再成立,其中一些地图需要5、6甚至7。颜色。

每个地图着色问题(在平面图上,复曲面上或其他上)都与通过在每个国家/地区创建一个节点并通过弧形将两个相邻国家/地区连接而获得的图形相对应。图的颜色比较笼统,我们只研究它:给定一个图,我们必须为每个节点找到一种颜色,以便由弧链接的两个节点具有不同的颜色。

一些图形需要两种颜色,另一些需要三种颜色,等等。给定一个图形,在颜色数量方面找到最经济的着色是一个困难的问题,需要很长的计算时间(例如确定复合数的除数的问题)。

如果您可以用K种颜色给有限的图着色,而用K –1则不能(仍然使连接的节点具有不同的颜色),则该图的色数为K。图2显示色数图2、3、4等找到有限图的色数仅是(长期)耐心的问题,因为它足以尝试所有可能的着色。

如果问题是有限的(即图的顶点数n是有限的)并且如果我们可以使用选择的公理来解决问题,那么我们也可以不使用它来解决它:因此,不可能发现色数取决于选择公理的有限图。只有当无穷大介入问题中的某个地方时,选择公理才是不可避免的。我们没有想到,色数问题的解决方案(更接近于算术而不是分析)可能会根据选择公理是否被接受而有所不同。这是S. 谢拉和A. 索菲的最新发现。

最简单的图,即问题A. 索菲和S. 谢拉的图G1,就是这样定义的图:G1的节点是实数(直线的点),而弧是对(x,y)对,使得(x-y-√2)是一个有理数,即两个整数的商。

我们不能完全画出A.Soifer和S.Shelah的图G1(因为它是无限的),但是要了解它不需要任何特殊的努力。例如,在x = 3和y = 1之间也没有弧,在x =√2和y =√3之间也没有弧,因为只要x-y-√2为不合理。另一方面,存在连接x =√2和y = 4/5或连接x =π+√2和π+ 3/37的弧,等等。图G1当然是无限图,但并不复杂,因为对于给定的x和y,我们可以轻松回答以下问题:“它们是否在G1中链接?” ”。尽管G1是无穷大的,但似乎并没有认为G1的着色是一个简单的问题,这与无穷大的微分方程或拓扑定理分析的复杂性相去甚远!

两种颜色还是无穷大?

A. 索菲和S. 谢拉通过推理(使用以AC表示的通用形式的选择公理)证明了G1可以用两种颜色着色:(如果AC为真,则G1的色数)(见图4)。因此,G1是2。另一方面,当您用两个经典的公理DC + LM组合起来替代AC来进行分析时,选择的公理代替G1时,G1具有无限的色数。

这种情况极为令人不安,因为这两个系统都考虑了ZF + AC(具有选择公理的Zermelo-Fraenkel集理论的公理系统)和ZF + DC + LM(1964年由Solovay提出并允许适当发展的系统)。物理学中所需的大多数数学似乎都适用于涉及具体世界的所有事物。

关于两个数字x和y的差形式为√2+ p / q的断言绝不取决于数学家的任意决定,就像22,091是质数的断言一样,并非来自人们可以做或拒绝做的行为。因此,在没有两个链接节点具有相同颜色的情况下,为图G1的节点着色所需的最小颜色数似乎预先确定,而没有给数学家任何自由。

S. 谢拉和A. 索菲根据类似原理构造的其他图G2和Gn,这次连接平面或n维空间的点,证实了选择公理和色数之间令人不安的联系。在获得这些结果之前,人们认为可着色性问题是简单,清晰和具体的问题,其解决方案不能取决于所选选择的公理的特定形式。这不是真的!

请注意,这里不是采取选择公理或完全拒绝选择公理的问题,而是要以强交流形式或较弱形式的直流形式使用它,并附带方便的公理。 ,LM,整体而言,DC + LM,构成一个系统,显然与使用AC获得的系统一样合理。突然删除AC而又不用其他公理替换它是不可能的,因为要进行分析并建立物理学必需的数学(微分系统理论,偏微分方程,Banach空间等),我们至少必须具有选择公理的弱形式。当我们选择DC + LM选项而不是AC时,我们发现自己处于一个可以形容为与AC一样合理的世界。

因此,S。Shelah和A. 索菲的研究结果触及了适用数学的敏感领域:虽然仅考虑了两种合理的理论(对于那些不想失去当代物理学基础的人),但他们表明:基本问题的答案取决于所采用的理论。

有真相吗?在哪里?

如果我们认为“ A. 索菲和S. 谢拉的图形G1需要2种颜色”的说法是对还是错,那么这意味着ZF + AC或ZF + DC + LM这两种理论之一是正确,另一个错误。我们应该知道哪一个。不幸的是,我们看不出要依据什么标准来做出这样的决定,现在绝大多数数学家都认为,试图找出两种理论中的哪一种是“正确的”是徒劳的。

关于连续体假设HC已经遇到这种情况,这是确定整数N的集合之间没有中间无限大的大小,并且尽管很精确,但是HC提出的问题-像AC一样是独立于集合论其他公理的公理-似乎无法解决。尽管由于休·伍德丁(Hugh Woodin)支持HC的虚假性而取得了一些最新进展,但如今,大多数数学家认为,提供的两种选择(采用HC或拒绝HC)都不比另一个更好或更真实。

伟大的逻辑学家库尔特·哥德尔(KurtGödel,1906-1978年)辩护说,我们尚未确定集合论的所有公理,而当我们这样做时,我们将不再有可能在交流模型之间进行选择或DC + LM(或HC与它的取反之间),因为附加公理将排除其中一个选项。但是,到目前为止,还没有施加任何公理,这只能归功于A. 索菲和S. 谢拉考虑的两个选项ZF + AC或ZF + DC + LM中的一个。遗漏公理的想法今天几乎没有得到捍卫。

它提供了另一种选择,而不是争辩说图形G1可以或不能用两种颜色着色,而最终我们将在完成设置理论时发现它们。毫无疑问,将主要采用该选项,它是根据A. 索菲和S. 谢拉的结果得出的结论,与我们先前的想法相反,在某些情况下,图的色数没有清晰的感觉,因此,例如,关于G1的色数没有绝对的真理。图G1的可着色性不是解决问题的真正问题,我们最终将发现该问题,并且每个人都将对此达成共识,而是对问题的一种幻觉,该问题最终没有意义,我们可以在哪里找到。自由选择答案。

这个结论是很难接受的,并且集合数学世界的这种陌生性被添加到大量的陌生性中(例如,那些与连续统假设相关的事物,或者与我们可以分解为同一体积的多个球体中的一个球体等)。也许最奇怪的是,尽管设置理论遇到了种种麻烦,但大多数数学家还是悄悄地依靠它,既建立了自己的理论基础,又将其用于物理学。

纳尔逊问题难度的解释?

A. 索菲和S. 谢拉展示的集合奇异性可能比连续性假设对数学更重要,因为它可以解释50多年来遇到的障碍的性质,涉及障碍物的色数。计划。 1950年,年仅18岁的爱德华·纳尔逊(Edward Nelson)成为普林斯顿大学的教授,并成为美国科学院的成员,提出了一个问题,其措辞非常简单:无限图的色度数是多少,其节点是平面的点,而其圆弧是所有MN相距一个单位的点对?

用日常语言得出的结论是:需要用多少种不同的颜色来着色平面的每个点,使得一个单位相距的两个点永远不会具有相同的颜色?

基本推理(见图1)显示平面CP的色数最多等于7(有7种颜色,我们知道如何实现所需的着色),并且至少等于4(3种颜色)还不够)。换句话说,镜头的色数为4、5、6或7。

但是,半个多世纪以来,我们试图更好地理解该色数的值,但是我们一直没有进步。保罗·埃尔多斯(PaulErdös)非常喜欢这个非常简单的问题,他对此进行了研究并大肆宣传……徒劳无功。

尽管A. 索菲和S. 谢拉的结果与Nelson问题没有直接关系,但是很明显,A。Soifer和S. 谢拉和Nelson所考虑的图具有相同的性质。因此,今天已经认真考虑了无法获得有关尼尔森图的新闻是由于逻辑上的困难的想法。如果Nelson图的色数确实取决于选择的公理,就像A. 索菲和S. 谢拉的图一样,那么数学家将很难辩称基础问题以及特别是在集合论中,附加公理的问题是无关紧要的。

在集合论中,就像在几何学中一样,所有公理系统都不相等。仔细考虑它们的含义以及它们各自的结果,并提出这样或一个这样的公理来表达和对待数学物理问题的特定效用的问题(就像在几何学中一样) ,提上议事日程,并导致(为什么不这样做?)革命性的集合论,因为存在非欧几里德几何的革命。


订阅并访问超过20年的档案!

订阅优惠

12期+ 4期特刊
纸质+数字版

+无限访问超过20年的档案

我订阅

订阅并访问超过20年的档案!

订阅优惠

12期+ 4期特刊
纸质+数字版

+无限访问超过20年的档案

我订阅

我们的最新出版物

回到顶部

已经有帐号了?

身份证明

标识自己可以访问您的内容

看到

还没有帐户 ?

注册

注册以激活您的订阅或订单问题。

创建我的账户