Leaf management

Abstract

Finding the set of leaves for an unbounded tree is a nontrivial process in both the Weihrauch and reverse mathematics settings. Despite this, many combinatorial principles for trees are equivalent to their restrictions to trees with leaf sets. For example, let $\widehat{\mathsf{WF}}$ denote the problem of choosing which trees in a sequence are well-founded, and let $\mathsf{PK}$ denote the problem of finding the perfect kernel of a tree. Let ${\widehat{\mathsf{WF}}}_{\mathit{L}}$ and ${\mathsf{PK}}_{\mathit{L}}$ denote the restrictions of these principles to trees with leaf sets. Then $\widehat{\mathsf{WF}}$ , ${\widehat{\mathsf{WF}}}_{\mathit{L}}$ , $\mathsf{PK}$ , and ${\mathsf{PK}}_{\mathit{L}}$ are all equivalent to ${\mathrm{\Pi }}_1^1\text{–}{\mathsf{CA}}_0$ over ${\mathsf{RCA}}_0$ , and all strongly Weihrauch equivalent.