No Cover Image

Journal article 145 views 12 downloads

Combinatorial principles equivalent to weak induction / Caleb Davis; Denis R. Hirschfeldt; Jeffry Hirst; Jake Pardo; Arno Pauly; Keita Yokoyama

Computability, Pages: 1 - 12

Swansea University Author: Arno, Pauly

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
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: College of Science
Start Page: 1
End Page: 12