No Cover Image

Journal article 609 views 235 downloads

Connected choice and the Brouwer fixed point theorem

Vasco Brattka, Stéphane Le Roux, Joseph S. Miller, Arno Pauly Orcid Logo

Journal of Mathematical Logic, Volume: 19, Issue: 01, Start page: 1950004

Swansea University Author: Arno Pauly Orcid Logo

Check full text

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...

Full description

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&#x151;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&#x151;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&#xE9;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.013641

Similar Items