Journal article 638 views 173 downloads
Combinatorial principles equivalent to weak induction
Caleb Davis,
Denis R. Hirschfeldt,
Jeffry Hirst,
Jake Pardo,
Arno Pauly 
,
Keita Yokoyama
,
Keita Yokoyama
Computability, Pages: 1 - 12
Swansea University Author:
Arno Pauly
-
PDF | Accepted Manuscript
Download (211.39KB)
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...
| Published in: | Computability |
|---|---|
| ISSN: | 22113568 22113576 |
| Published: |
2019
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa51635 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| 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. |
|---|---|
| College: |
Faculty of Science and Engineering |
| Start Page: |
1 |
| End Page: |
12 |