Some computability-theoretic reductions between principles around ${\mathsf{ATR}}_0$

Abstract

We study the computational content of various theorems with reverse mathematical strength around Arithmetical Transfinite Recursion (${\mathsf{ATR}}_0$) from the point of view of computability-theoretic reducibilities, in particular Weihrauch reducibility. Our first main result states that it is equally hard to construct an embedding between two given well-orderings, as it is to construct a Turing jump hierarchy on a given well-ordering. This answers a question of Marcone. We obtain a similar result for Fraïssé's conjecture restricted to well-orderings. We then turn our attention to König's duality theorem, which generalizes König's theorem about matchings and covers to infinite bipartite graphs. Our second main result shows that the problem of constructing a König cover of a given bipartite graph is roughly as hard as the following "two-sided" version of the aforementioned jump hierarchy problem: given a linear ordering $L$, construct either a jump hierarchy on $L$ (which may be a pseudohierarchy), or an infinite $L$-descending sequence. We also obtain several results relating the above problems with choice on Baire space (choosing a path on a given ill-founded tree) and unique choice on Baire space (given a tree with a unique path, produce said path).