Measuring the Relative Complexity of Mathematical Constructions and Theorems

We investigate the relative complexity of mathematical constructions and theorems using the frameworks of computable reducibilities and reverse mathematics. First, 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 computable reducibilities, in particular Weihrauch reducibility. We show 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. We obtain a similar result for Fra\"iss\'e's conjecture restricted to well-orderings. We then turn our attention to K\"onig's duality theorem, which generalizes K\"onig's theorem about matchings and covers to infinite bipartite graphs. We show that the problem of constructing a K\"onig cover of a given bipartite graph is roughly as hard as the following ``two-sided'' version of the aforementioned jump hierarchy problem: given a \emph{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). Next, we investigate three known ways to formalize the notion of solving a problem by applying other problems in series: the compositional product, the reduction game, and the step product. We clarify the relationships between them by giving sufficient conditions for them to be equivalent. We also show that they are not equivalent in general. Next, we turn our attention to the parallel product. In joint work with Dzhafarov, Hirschfeldt, Patey and Pauly, we investigate the infinite pigeonhole principle for different numbers of colors and how these problems behave under Weihrauch reducibility with respect to parallel products. Finally, we leave the setting of computable reducibilities for the setting of reverse mathematics. First, we define a $\Sigma^1_1$ axiom of finite choice and investigate its relationships with other theorems of hyperarithmetic analysis. For one, we show that it follows from Arithmetic Bolzano-Weierstrass. On the other hand, using an elaboration of Steel's forcing with tagged trees, we show that it does not follow from $\Delta^1_1$ comprehension. Second, in joint work with James Barnes and Richard A.\ Shore, we analyze a theorem of Halin about disjoint rays in graphs. Our main result shows that Halin's theorem is a theorem of hyperarithmetic analysis, making it only the second ``natural'' (i.e., not formulated using concepts from logic) theorem with this property