文摘
在1883 - 1884年,亨利·庞加莱宣布结果的结构组0的功能,或者方程的解的存在。在的情况下庞加莱定理是众所周知的博尔扎诺定理。1940年米兰达找回了庞加莱定理。除了一些孤立的结果,它本质上是non-algorithmic理论。本文的目的是介绍一个algorithmical证明这个定理”链的存在”,algorithmical Bolzano-Poincare定理的证明和展示庞加莱的等价,这和“链”的存在定理。
1。介绍
众所周知有影响力的拓扑结构是如何发展的其他许多数学和经济学的分支。在众多国家中,让我们回忆的重要地方的这和巴拿赫不动点定理作为主要工具在微分方程解决问题,分形理论和市场均衡的问题。其中的一些应用程序提出了一个不动点的可计算性问题。在[1,2]Steinhaus指出了以下猜想:让棋盘的一些部分已被敌军布上了地雷。假设国王不能棋盘对面的左边缘向右一个没有开采广场见面。然后车可以从上边缘到下一个移动开采领域。
根据Surowka [3]Steinhaus指出棋盘定理的几种证明似乎不完整或使用感应在棋盘的大小4]。
Steinhaus指出棋盘定理的简单证明了在5]。在[6)以下Steinhaus指出棋盘定理发表的泛化:定理(在链的存在)对任意分解的n维立方体 到 多维数据集和任意着色功能 对于一些自然数 存在一个 th的链 这样 和 。
这个定理在证明的主要工具(见[6(见[])的Bolzano-Poincare定理7,8])。在论文的第一部分我们的算法发现链将会证明这个定理”链的存在”,Bolzano-Poincare定理,这不动点定理是等价的(更多信息见9,10])。
2。定理
让是n -多维数据集的。
它的th相反的脸定义如下: 让 是边界立方体的。
让是一个任意的自然数。
我们所说的家庭 的分解成多维数据集。
地图据说是一个着色功能的分解。
序列在哪里为据说是一个th的链,如果对所有和为。
一组据说是吗n维立方体组合。
它的th相反的脸定义如下: 让 是边界的n维立方体组合。
让是基本向量。
有序集合据说是一个n单形如果存在排列的设置这样。
任何子集据说是一个(n−1) n单形的脸 。
每一个地图据说是一个彩色地图的。
一组我们称之为n的颜色如果。
观察1。让是一个n -单纯形。然后为每个如果为每一个,那么存在一个n -单纯形这样不存在存在。
观察2。任何(n−1)面对的n -单纯形是一个(n−1)面临的一个或两个n -单形的这取决于是否位于对于一些,。
观察3。每一个n -彩色的n -单工正好有两个n -彩色(n−1)面。
定理2.1(链)的存在。对于任意分解的n维立方体到多维数据集和任意着色功能对于一些自然数存在一个th的链这样和。
的算法(基于证据(6])如下。
步骤1。让我们定义彩色地图:
步骤2。让我们以n -彩色的n -单纯形在哪里,
我们说的n -彩色(n−1)的脸“使用”。
让。
步骤3。采取“未使用”n -彩色(n−1的脸n -单纯形。
是否包含在这张脸对于一些,然后去一步5。这是(n−1)面临的一个n -单纯形不同。
自从那一刻这个(n−1)面对据说是“使用”。去一步4。
步骤4。让我们创建的顺序n -单形。
让。
去一步3。
第5步。有限多次迭代后得到的序列这样为。和n -单纯形有n -彩色(n−1)面临的一个子集对于一些,。因此在哪里,。
让我们以最小的指数这样对于一些,然后让我们找到最大的指数这样。
步骤6。然后从链选择先后分的方式为和为,和,。
步骤7。的序列我们有链在哪里和为。
结束
定理2.2 (Bolzano-Poincar)。让,是一个连续的地图,这样和为然后存在这样。
定理2.3(这不动点定理)。让,是一个连续的地图然后存在这样。
定理2.4。下面的定理是等价的:
(1)在链的存在定理(2)Bolzano-Poincare定理(3)这的不动点定理。
证明。”(1)(2)“让我们假设为每个。让我们定义集:
为,每组是开着的。
我们有。
让我们考虑的空间与度量。勒贝格引理的覆盖,存在这样,每和我们对每一个存在这样。
让我们定义着色功能:
从定理”的现有链”存在th彩色序列连接相反的立方体的面孔。
一组关闭连接。
的十字路口,因此存在这样和。自是连续映射,因此连接在。因此,设置是一个区间,其中包含。博尔扎诺定理存在这样。
矛盾。
”(2)(3)“让。这个函数满足的假设Bolzano-Poincare定理。因此存在这样。
所以。
”(3)(1)“让我们假设存在分解维数据集到多维数据集和着色功能这样,每没有th彩色链连接和。
让。
让家庭的组成部分。
的子集:
关闭,不相交。
欧几里得度量是一个正常的空间,因此存在一个连续的地图这样和。
为每一个让我们定义映射在哪里。
观察到是连续映射。把一个任意。
存在这样。多维数据集是的一个子集或对于一些。我们有或。
因此,函数没有固定的点。矛盾。
3所示。庞加莱定理
3.1。基本的算法
让是一个任意的自然数。
我们的分解成多维数据集。
w.l.o.g.假设和为。让欧几里得度量。
观察到存在这样,每对于每个我们有,,。
3.1.1。表面
让是一个自然数,这样。
每一个的中心定义如下: 让我们定义彩色地图 表面算法如下。
步骤1。让
步骤2。如果然后结束。
否则做一步3。
步骤3。添加元素的集合来。
下一个
然后转到步骤2。
自是有限的,因此在有限步骤设置多少是空的(程序结束)。
让我们考虑家庭。我们可以假设是下封闭有限的十字路口。
的元素,这样被称为广场、边缘和顶点。
观察4。的将多维数据集之间的和。
观察5。每条边如果这是一个完全的边缘1平方,否则这是一个2或4平方的边缘。
3.1.2。修改
让我们分裂的每个元素到27个立方体(自然地)。
表示所有这些数据集的组成。
创建颜色映射如下: 现在。
观察6。任何的边缘是一个边缘的一个或两个正方形的这取决于是否位于。
让我们定义着色:
在哪里广场的中心吗。
边缘据说2-coloured如果存在广场这样和。
观察7。2-coloured边缘的顶点是一个子集的一个甚至2-coloured边数取决于是否位于。
观察8。的组件没有self-cutting断了线。
观察9。虚线躺在的数量和连接和是奇数。
引理3.1。2-coloured边的数量,哪一个顶点位于是奇数。
证明。让我们考虑的组件集。
我们有奇数的破碎的线路连接和和其他组件的数量是任意的。
让我们看到。
所以,2-coloured边的数量,哪一个顶点位于如果它位于折线连接是奇数和其他人甚至(使用的定义)。
根据观察9这结束了证据。
3.1.3。折线连接和
步骤1。让,
步骤2。取。
添加来。
顶点据说是使用。
去一步3。
步骤3。把不用的顶点最后的边缘添加到集合。
如果结束。
否则,
如果去一步2。
去其他步骤4。
步骤4。把不用的顶点最后的边缘添加到集合。
接下来把2-coloured边缘这样。
现在顶点据说是使用。
添加集。
去一步3。
首先2-coloured边的数量,哪一个顶点位于是奇数(引理3.1)。
2-coloured第二每个顶点的边缘是一个甚至一个子集2-coloured边数取决于是否位于(观察7)。
该参数允许一个说过程是定义良好的。
现在我们的折线连接和创建如下:
让是最后一个元素。
如果然后之前添加元素
其他的停止。
我们获得的序列边缘。让我们定义着色在哪里:
很容易看到和。
所以从我们搜索顺序第一优势这样。
3.2。拓扑的一部分
为每一个,我们有(我) 这样和,(2) 这样和在哪里从广场和,(3) 这样和在哪里是一个立方体,是一个立方体和。
定义集。
为每一个存在这样 不失一般性,我们可以假设。
此外,。所以对于每一个这样的事实收益率 所以结束的证明。