No Cover Image

Journal article 745 views 199 downloads

Combinatorial principles equivalent to weak induction

Caleb Davis, Denis R. Hirschfeldt, Jeffry Hirst, Jake Pardo, Arno Pauly Orcid Logo, Keita Yokoyama

Computability, Pages: 1 - 12

Swansea University Author: Arno Pauly Orcid Logo

Check full text

DOI (Published version): 10.3233/COM-180244

Abstract

We study the principle ERT "In an infinite sequence over finitely many colours, in some tail every colour that appears appears a second time." and ECT "In an infinite sequence over finitely many colours, in some tail every colour that appears appears infinitely." Over RCA_0*, ERT...

Full description

Published in: Computability
ISSN: 22113568 22113576
Published: 2019
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa51635
first_indexed 2019-08-30T14:48:43Z
last_indexed 2019-09-13T14:30:14Z
id cronfa51635
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2019-09-13T10:46:59.9509434</datestamp><bib-version>v2</bib-version><id>51635</id><entry>2019-08-30</entry><title>Combinatorial principles equivalent to weak induction</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-08-30</date><deptcode>MACS</deptcode><abstract>We study the principle ERT "In an infinite sequence over finitely many colours, in some tail every colour that appears appears a second time." and ECT "In an infinite sequence over finitely many colours, in some tail every colour that appears appears infinitely." Over RCA_0*, ERT is equivalent to Sigma1-induction, and ECT is equivalent to Sigma2-induction. In the Weihrauch setting, ERT is equivalent to the finite parallelization of LPO, and ECT to the finite parallelization of the total continuation of closed choice on N. Based on these results, we can speculate a bit on how the need for induction can be reflected in the Weihrauch degree of a problem.</abstract><type>Journal Article</type><journal>Computability</journal><paginationStart>1</paginationStart><paginationEnd>12</paginationEnd><publisher/><issnPrint>22113568</issnPrint><issnElectronic>22113576</issnElectronic><keywords/><publishedDay>5</publishedDay><publishedMonth>8</publishedMonth><publishedYear>2019</publishedYear><publishedDate>2019-08-05</publishedDate><doi>10.3233/COM-180244</doi><url/><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2019-09-13T10:46:59.9509434</lastEdited><Created>2019-08-30T13:56:30.4236580</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>Caleb</firstname><surname>Davis</surname><order>1</order></author><author><firstname>Denis&amp;nbsp;R.</firstname><surname>Hirschfeldt</surname><order>2</order></author><author><firstname>Jeffry</firstname><surname>Hirst</surname><order>3</order></author><author><firstname>Jake</firstname><surname>Pardo</surname><order>4</order></author><author><firstname>Arno</firstname><surname>Pauly</surname><orcid>0000-0002-0173-3295</orcid><order>5</order></author><author><firstname>Keita</firstname><surname>Yokoyama</surname><order>6</order></author></authors><documents><document><filename>0051635-30082019140335.pdf</filename><originalFilename>1812.09943.pdf</originalFilename><uploaded>2019-08-30T14:03:35.8270000</uploaded><type>Output</type><contentLength>209396</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2019-08-30T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2019-09-13T10:46:59.9509434 v2 51635 2019-08-30 Combinatorial principles equivalent to weak induction 17a56a78ec04e7fc47b7fe18394d7245 0000-0002-0173-3295 Arno Pauly Arno Pauly true false 2019-08-30 MACS We study the principle ERT "In an infinite sequence over finitely many colours, in some tail every colour that appears appears a second time." and ECT "In an infinite sequence over finitely many colours, in some tail every colour that appears appears infinitely." Over RCA_0*, ERT is equivalent to Sigma1-induction, and ECT is equivalent to Sigma2-induction. In the Weihrauch setting, ERT is equivalent to the finite parallelization of LPO, and ECT to the finite parallelization of the total continuation of closed choice on N. Based on these results, we can speculate a bit on how the need for induction can be reflected in the Weihrauch degree of a problem. Journal Article Computability 1 12 22113568 22113576 5 8 2019 2019-08-05 10.3233/COM-180244 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2019-09-13T10:46:59.9509434 2019-08-30T13:56:30.4236580 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Caleb Davis 1 Denis&nbsp;R. Hirschfeldt 2 Jeffry Hirst 3 Jake Pardo 4 Arno Pauly 0000-0002-0173-3295 5 Keita Yokoyama 6 0051635-30082019140335.pdf 1812.09943.pdf 2019-08-30T14:03:35.8270000 Output 209396 application/pdf Accepted Manuscript true 2019-08-30T00:00:00.0000000 true eng
title Combinatorial principles equivalent to weak induction
spellingShingle Combinatorial principles equivalent to weak induction
Arno Pauly
title_short Combinatorial principles equivalent to weak induction
title_full Combinatorial principles equivalent to weak induction
title_fullStr Combinatorial principles equivalent to weak induction
title_full_unstemmed Combinatorial principles equivalent to weak induction
title_sort Combinatorial principles equivalent to weak induction
author_id_str_mv 17a56a78ec04e7fc47b7fe18394d7245
author_id_fullname_str_mv 17a56a78ec04e7fc47b7fe18394d7245_***_Arno Pauly
author Arno Pauly
author2 Caleb Davis
Denis&nbsp;R. Hirschfeldt
Jeffry Hirst
Jake Pardo
Arno Pauly
Keita Yokoyama
format Journal article
container_title Computability
container_start_page 1
publishDate 2019
institution Swansea University
issn 22113568
22113576
doi_str_mv 10.3233/COM-180244
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 principle ERT "In an infinite sequence over finitely many colours, in some tail every colour that appears appears a second time." and ECT "In an infinite sequence over finitely many colours, in some tail every colour that appears appears infinitely." Over RCA_0*, ERT is equivalent to Sigma1-induction, and ECT is equivalent to Sigma2-induction. In the Weihrauch setting, ERT is equivalent to the finite parallelization of LPO, and ECT to the finite parallelization of the total continuation of closed choice on N. Based on these results, we can speculate a bit on how the need for induction can be reflected in the Weihrauch degree of a problem.
published_date 2019-08-05T19:57:30Z
_version_ 1821436753480777728
score 11.047609

Similar Items