Kurt Gödel Research Center

2017 seminar talk: Some results about the higher levels of the Weihrauch lattice

Talk held by Alberto Marcone (Università di Udine, Italy) at the KGRC seminar on 2017-04-27.

Abstract

In the last few years Weihrauch reducibility and the ensuing Weihrauch lattice have emerged as a useful tool for studying the complexity of mathematical statements viewed as "problems" or multi-valued functions. This approach complements nicely the reverse mathematics approach, and has been very successful for statements which are provable in ${\mathsf{ACA}_0}$. The study the Weihrauch lattice for functions arising from statements laying at higher levels, such as ${\mathsf{ATR}_0}$, of the reverse mathematics spectrum is instead in its infancy. We will present some results (work in progress with my graduate student Andrea Cettolo).

In some cases we obtain the expected finer classification, but in other we observe a collapse of statements that are not equivalent with respect to provability in subsystems of second order arithmetic. This is in part due to the increased syntactic complexity of the statements. Our preliminary results deal with comparability of well‑orderings, $\Sigma^1_1$‑separation, and $\Delta^1_1$‑comprehension.