Alberto Marcone: Some results about the higher levels of the Weihrauch lattice

KGRC Research Seminar – 2017‑04‑27 at 4pm

Speaker: Alberto Marcone (Università di Udine, Italy)

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.

Attachments

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.