Ph.D XXXIX

Supervisor: Alberto Marcone

Phone: 

Room: Rizzi L2-07-ND 

Mail: osso.gianmarco@spes.uniud.it

Research Project

The Weihrauch lattice at high levels of reverse mathematical strength

Reverse mathematics is a framework which allows us to classify mathematical theorems on the basis of their logical strength, i.e., the weakest axioms necessary to prove them. The framework is formulated in the language of second order arithmetic and it has a strong connection with computability theory, i.e., the study of functions on the natural numbers which we can calculate effectively. Many cornerstone results in several areas of mathematics turn out to be equivalent to one of five subsystems of second order arithmetic. The two strongest systems among these are the system of arithmetical transfinite recursion and that of \Pi^1_1 comprehension.

Weihrauch reducibility is a tool to rank relations on so-called represented spaces (typically of size continuum) based on their uniform computational content: we say that R uniformly computes S if there are computable functions F (playing the role of preprocessing) and G (playing the role of postprocessing) such that, given any x in the domain of S, and any y such that F(x) R y, we have that x S G(x, y). Through the interpretation of mathematical theorems as relations between suitable represented spaces, we can use Weihrauch reductions to define when theorem A uniformly computes theorem B. This yields another approach to the classification of theorems, this time based on computational (as opposed to logical) strength.

Recent work has highlighted a strong connection between the two approaches, and researchers have started looking at theorems which have been previously classified in reverse mathematics through the lens of Weihrauch reducibility. This line of investigation has found that, generally, Weihrauch classification detects finer differences that are invisible to reverse mathematics. Therefore, the study of Weihrauch degrees can give us more insight on the relative logical strength of mathematical theorems. The Weihrauch classification of mathematical theorems which correspond to axiom systems stronger than arithmetical transfinite recursion (typically results linked to descriptive set theory) is still in its early stages and that is where my research will focus most.