No Cover Image

Journal article 95 views 4 downloads

THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES

DAMIR D. DZHAFAROV, REED SOLOMON Orcid Logo, Manlio Valenti Orcid Logo

The Journal of Symbolic Logic, Pages: 1 - 23

Swansea University Author: Manlio Valenti Orcid Logo

  • 69108.VOR.pdf

    PDF | Version of Record

    © The Author(s), 2025. Published by Cambridge University Press on behalf of The Association for Symbolic Logic. This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (CC BY).

    Download (344.94KB)

Check full text

DOI (Published version): 10.1017/jsl.2025.11

Abstract

We study versions of the tree pigeonhole principle, TT1, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether TT1 is Π11-conservative over the ordin...

Full description

Published in: The Journal of Symbolic Logic
ISSN: 0022-4812 1943-5886
Published: Cambridge University Press (CUP) 2025
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa69108
Abstract: We study versions of the tree pigeonhole principle, TT1, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether TT1 is Π11-conservative over the ordinary pigeonhole principle, RT1. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination with other results, we use this to show that unlike RT1, the problem TT1 is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of TT1.
Keywords: tree pigeonhole principle, Weihrauch reducibility, computable analysis
College: Faculty of Science and Engineering
Funders: D.D.D. and D.R.S. were partially supported by a Focused Research Group grant from the National Science Foundation of the United States, DMS-1854355.
Start Page: 1
End Page: 23

Similar Items