2018/12/23 by Jeffry L. Hirst, Hirst, Jeffry L.
Computer Science · Mathematics · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Mathematical and Theoretical Analysis
paper · pdf · doi:10.48550/arxiv.1812.09762
openalex publication_date 2018/12/23 · openalex created_date 2022/09/11 · openalex updated_date 2026/07/28
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\sfWF denote the problem of choosing which trees in a sequence are well-founded, and let \sfPK denote the problem of finding the perfect kernel of a tree. Let \widehat\sfWFL and \sfPKL denote the restrictions of these principles to trees with leaf sets. Then \widehat\sfWF, \widehat\sfWFL, \sfPK, and \sfPKL are all equivalent to Π11 \rm - \sfCA0 over \sfRCA0, and all strongly Weihrauch equivalent.