Pith. sign in

The tree pigeonhole principle in the Weihrauch degrees

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

We study versions of the tree pigeonhole principle, $\mathsf{TT}^1$, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics. Two outstanding questions from the latter investigation are whether $\mathsf{TT}^1$ is $\Pi^1_1$-conservative over the ordinary pigeonhole principle, $\mathsf{RT}^1$, and whether it is equivalent to any first-order statement of second-order arithmetic. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate, and answer in the affirmative, the analogue of the first question for Weihrauch reducibility. We then use this, in combination with other results, to answer in the negative the analogue of the second question. Our proofs develop a new combinatorial machinery for constructing and understanding solutions to instances of $\mathsf{TT}^1$.

fields

math.LO 1

years

2024 1

verdicts

ACCEPT 1

representative citing papers

Effectiveness and strong graph indivisibility

math.LO · 2024-11-25 · accept · novelty 6.0

The paper shows Cameron's classification of strongly indivisible graphs is effective up to a change of computable presentation, partially holds in the omega-model REC, and requires the induction scheme I-Sigma-0-2 in Cameron's original proof.

citing papers explorer

Showing 1 of 1 citing paper.

  • Effectiveness and strong graph indivisibility math.LO · 2024-11-25 · accept · none · ref 11 · internal anchor

    The paper shows Cameron's classification of strongly indivisible graphs is effective up to a change of computable presentation, partially holds in the omega-model REC, and requires the induction scheme I-Sigma-0-2 in Cameron's original proof.