Leaf management

DOI10.3233/COM-180243MaRDI QIDQ5131654zbMATH OpenOpenAlexFDO

Authors Jeffry L. Hirst

Publication date 9 November 2020

Published in Computability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.09762

zbMATH Keywords

computabilityreverse mathematicsWeihrauch

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Other degrees and reducibilities in computability and recursion theory (03D30) Second- and higher-order arithmetic and fragments (03F35)

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 $widehatsfWF$ 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 ${widehatsfWF}_L$ and ${sfPK}_L$ denote the restrictions of these principles to trees with leaf sets. Then $widehatsfWF$, ${widehatsfWF}_L$, $sfPK$, and ${sfPK}_L$ are all equivalent to $P{i}_1^{1}m-{sfCA}_0$ over ${sfRCA}_0$, and all strongly Weihrauch equivalent.

Recommendations

• Reverse mathematics and Ramsey's property for trees
• Products of Infinitely Many Perfect Trees
• Finding paths through narrow and wide trees
• scientific article; zbMATH DE number 4158596
• Generalizations of the Kruskal-Friedman theorems

Cited in

(5)

• Computability theory. Abstracts from the workshop held April 25 -- May 1, 2021 (hybrid meeting)
• Finding paths through narrow and wide trees
• Reverse mathematics and Weihrauch analysis motivated by finite complexity theory
• Algebraic properties of the first-order part of a problem
• The Weihrauch lattice at the level of \(\boldsymbol{\Pi }^1_1{-}\mathsf{CA}_0\): the Cantor-Bendixson theorem

This page was built for publication: Leaf management

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5131654)