Connected choice and the Brouwer fixed point theorem
Connected choice and the Brouwer fixed point theorem
复制标题
DOI：
10.1142/s0219061319500041
复制
发表时间：
2019-06-01
影响因子：
0.9
通讯作者：
Pauly, Arno
中科院分区：
文献类型：
--
作者：
Brattka, Vasco;Le Roux, Stephan;Pauly, Arno
我们研究 Weihrauch 晶格中 Brouwer 不动点定理的计算内容。连通选择是在由负信息给定的非空连通闭集中找到点的操作。我们的主要结果之一是，对于任何固定维度，该维度的布劳威尔不动点定理在计算上等价于相同维度的欧几里得单位立方体的连通选择。另一个主要结果是，对于大于或等于 2 的维度，连通选择是完整的，因为它在计算上等同于 Weak Konig 引理。虽然我们可以基于简单的几何构造或组合论证来提出第三维及以上维度的两个独立证明，但第二维的证明基于更复杂的逆极限构造。已知一维中的连通选择运算等价于中值定理；我们证明，与二维及以上的情况相比，这个问题不是幂等的。我们还证明，利普希茨常数严格大于 1 的利普希茨连续性并不能简化寻找不动点的过程。最后，我们证明寻找任何维度大于或等于一的欧氏单位立方体的闭子集的连通性分量等价于弱柯尼希引理。为了描述这些结果，我们引入了有理复数树对单位立方体的封闭子集的表示。
We study the computational content of the Brouwer Fixed Point Theorem in the Weihrauch lattice. Connected choice is the operation that finds a point in a non-empty connected closed set given by negative information. One of our main results is that for any fixed dimension the Brouwer Fixed Point Theorem of that dimension is computably equivalent to connected choice of the Euclidean unit cube of the same dimension. Another main result is that connected choice is complete for dimension greater than or equal to two in the sense that it is computably equivalent to Weak Konig's Lemma. While we can present two independent proofs for dimension three and upward that are either based on a simple geometric construction or a combinatorial argument, the proof for dimension two is based on a more involved inverse limit construction. The connected choice operation in dimension one is known to be equivalent to the Intermediate Value Theorem; we prove that this problem is not idempotent in contrast to the case of dimension two and upward. We also prove that Lipschitz continuity with Lipschitz constants strictly larger than one does not simplify finding fixed points. Finally, we prove that finding a connectedness component of a closed subset of the Euclidean unit cube of any dimension greater than or equal to one is equivalent to Weak Konig's Lemma. In order to describe these results, we introduce a representation of closed subsets of the unit cube by trees of rational complexes.