3 papers
math.LO2025
The uniform Kruskal theorem over RCA
Patrick Uftring
Kruskal's theorem famously states that finite trees (ordered using an infima-preserving embeddability relation) form a well partial order. Freund, Rathjen, and Weiermann extended t…
math.LO2023
Weihrauch degrees without roots
Patrick Uftring
We answer the following question by Arno Pauly: "Is there a square-root operator on the Weihrauch degrees?". In fact, we show that there are uncountably many pairwise incomparable…
math.LO2022
The uniform Kruskal theorem: between finite combinatorics and strong set existence
Anton Freund, Patrick Uftring
The uniform Kruskal theorem extends the original result for trees to general recursive data types. As shown by A. Freund, M. Rathjen and A. Weiermann, it is equivalent to -c…