Journal article 659 views 244 downloads
Connected choice and the Brouwer fixed point theorem
Journal of Mathematical Logic, Volume: 19, Issue: 01, Start page: 1950004
Swansea University Author:
Arno Pauly
-
PDF | Accepted Manuscript
Download (448.58KB)
DOI (Published version): 10.1142/s0219061319500041
Abstract
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 Theo...
Published in: | Journal of Mathematical Logic |
---|---|
ISSN: | 0219-0613 1793-6691 |
Published: |
World Scientific Pub Co Pte Lt
2019
|
Online Access: |
Check full text
|
URI: | https://cronfa.swan.ac.uk/Record/cronfa48651 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
first_indexed |
2019-01-30T20:04:02Z |
---|---|
last_indexed |
2023-01-11T14:24:23Z |
id |
cronfa48651 |
recordtype |
SURis |
fullrecord |
<?xml version="1.0"?><rfc1807><datestamp>2022-12-05T12:45:29.4785550</datestamp><bib-version>v2</bib-version><id>48651</id><entry>2019-01-30</entry><title>Connected choice and the Brouwer fixed point theorem</title><swanseaauthors><author><sid>17a56a78ec04e7fc47b7fe18394d7245</sid><ORCID>0000-0002-0173-3295</ORCID><firstname>Arno</firstname><surname>Pauly</surname><name>Arno Pauly</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2019-01-30</date><deptcode>SCS</deptcode><abstract>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 Kőnig's Lemma. While we can present two independent proofs for dimension three and upwards 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 upwards. 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 or equal to one is equivalent to Weak Kőnig's Lemma. In order to describe these results, we introduce a representation of closed subsets of the unit cube by trees of rational complexes.</abstract><type>Journal Article</type><journal>Journal of Mathematical Logic</journal><volume>19</volume><journalNumber>01</journalNumber><paginationStart>1950004</paginationStart><paginationEnd/><publisher>World Scientific Pub Co Pte Lt</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>0219-0613</issnPrint><issnElectronic>1793-6691</issnElectronic><keywords>Computable analysis; Weihrauch lattice; reverse mathematics; choice principles; connected sets; fixed point theorems</keywords><publishedDay>1</publishedDay><publishedMonth>6</publishedMonth><publishedYear>2019</publishedYear><publishedDate>2019-06-01</publishedDate><doi>10.1142/s0219061319500041</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders/><projectreference/><lastEdited>2022-12-05T12:45:29.4785550</lastEdited><Created>2019-01-30T15:06:42.8131710</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Vasco</firstname><surname>Brattka</surname><order>1</order></author><author><firstname>Stéphane Le</firstname><surname>Roux</surname><order>2</order></author><author><firstname>Joseph S.</firstname><surname>Miller</surname><order>3</order></author><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>4</order></author></authors><documents><document><filename>0048651-04022019084435.pdf</filename><originalFilename>1206.4809.pdf</originalFilename><uploaded>2019-02-04T08:44:35.5900000</uploaded><type>Output</type><contentLength>501104</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2020-01-10T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807> |
spelling |
2022-12-05T12:45:29.4785550 v2 48651 2019-01-30 Connected choice and the Brouwer fixed point theorem 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2019-01-30 SCS 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 Kőnig's Lemma. While we can present two independent proofs for dimension three and upwards 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 upwards. 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 or equal to one is equivalent to Weak Kőnig's Lemma. In order to describe these results, we introduce a representation of closed subsets of the unit cube by trees of rational complexes. Journal Article Journal of Mathematical Logic 19 01 1950004 World Scientific Pub Co Pte Lt 0219-0613 1793-6691 Computable analysis; Weihrauch lattice; reverse mathematics; choice principles; connected sets; fixed point theorems 1 6 2019 2019-06-01 10.1142/s0219061319500041 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2022-12-05T12:45:29.4785550 2019-01-30T15:06:42.8131710 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Vasco Brattka 1 Stéphane Le Roux 2 Joseph S. Miller 3 Arno Pauly 0000-0002-0173-3295 4 0048651-04022019084435.pdf 1206.4809.pdf 2019-02-04T08:44:35.5900000 Output 501104 application/pdf Accepted Manuscript true 2020-01-10T00:00:00.0000000 true eng |
title |
Connected choice and the Brouwer fixed point theorem |
spellingShingle |
Connected choice and the Brouwer fixed point theorem Arno Pauly |
title_short |
Connected choice and the Brouwer fixed point theorem |
title_full |
Connected choice and the Brouwer fixed point theorem |
title_fullStr |
Connected choice and the Brouwer fixed point theorem |
title_full_unstemmed |
Connected choice and the Brouwer fixed point theorem |
title_sort |
Connected choice and the Brouwer fixed point theorem |
author_id_str_mv |
17a56a78ec04e7fc47b7fe18394d7245 |
author_id_fullname_str_mv |
17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly |
author |
Arno Pauly |
author2 |
Vasco Brattka Stéphane Le Roux Joseph S. Miller Arno Pauly |
format |
Journal article |
container_title |
Journal of Mathematical Logic |
container_volume |
19 |
container_issue |
01 |
container_start_page |
1950004 |
publishDate |
2019 |
institution |
Swansea University |
issn |
0219-0613 1793-6691 |
doi_str_mv |
10.1142/s0219061319500041 |
publisher |
World Scientific Pub Co Pte Lt |
college_str |
Faculty of Science and Engineering |
hierarchytype |
|
hierarchy_top_id |
facultyofscienceandengineering |
hierarchy_top_title |
Faculty of Science and Engineering |
hierarchy_parent_id |
facultyofscienceandengineering |
hierarchy_parent_title |
Faculty of Science and Engineering |
department_str |
School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science |
document_store_str |
1 |
active_str |
0 |
description |
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 Kőnig's Lemma. While we can present two independent proofs for dimension three and upwards 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 upwards. 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 or equal to one is equivalent to Weak Kőnig's Lemma. In order to describe these results, we introduce a representation of closed subsets of the unit cube by trees of rational complexes. |
published_date |
2019-06-01T03:59:13Z |
_version_ |
1763753017659621376 |
score |
11.021648 |