Leaf management

Issue title: Dagstuhl Seminar on Measuring the Complexity of Computational Content 2018

Guest editors: Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone and Arno Pauly

Article type: Research Article

Authors: Hirst, Jeffry L.^{; *}

Affiliations: Mathematical Sciences Department, Appalachian State University, NC, 28068, USA. [email protected]

Correspondence: [*] Corresponding author. [email protected].

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 WFˆ denote the problem of choosing which trees in a sequence are well-founded, and let PK denote the problem of finding the perfect kernel of a tree. Let WFˆL and PKL denote the restrictions of these principles to trees with leaf sets. Then WFˆ, WFˆL, PK, and PKL are all equivalent to Π11–CA0 over RCA0, and all strongly Weihrauch equivalent.

Keywords: Reverse mathematics, computability, Weihrauch

DOI: 10.3233/COM-180243

Journal: Computability, vol. 9, no. 3-4, pp. 309-314, 2020