Leszek Kołodziejczyk (University of Warsaw)

When:
October 13, 2020 @ 10:00 am – 11:00 am
2020-10-13T10:00:00-10:00
2020-10-13T11:00:00-10:00

Title: Reverse mathematics of combinatorial principles over a weak base theory
by Leszek Kołodziejczyk (University of Warsaw) as part of Computability theory and applications

Abstract
Reverse mathematics studies the strength of axioms needed to prove various
mathematical theorems. Often, the theorems have the form $forall X exists
Y psi(X,Y)$ with $X, Y$ denoting subsets of $mathbb{N}$ and $psi$
arithmetical, and the logical strength required to prove them is closely
related to the difficulty of computing $Y$ given $X$. In the early decades
of reverse mathematics, most of the theorems studied turned out to be
equivalent, over a relatively weak base theory, to one of just a few typical
axioms, which are themselves linearly ordered in terms of strength. More
recently, however, many statements from combinatorics, especially Ramsey
theory, have been shown to be pairwise inequivalent or even logically
incomparable.

The usual base theory used in reverse mathematics is $mathrm{RCA}_0$, which
is intended to correspond roughly to the idea of “computable mathematics”.
The main two axioms of $mathrm{RCA}_0$ are: comprehension for computable
properties of natural numbers and mathematical induction for c.e.
properties. A weaker theory in which induction for c.e. properties is
replaced by induction for computable properties has also been introduced,
but it has received much less attention. In the reverse mathematics
literature, this weaker theory is known as $mathrm{RCA}^*_0$.

In this talk, I will discuss some results concerning the reverse mathematics
of combinatorial principles over $mathrm{RCA}^*_0$. We will focus mostly on
Ramsey’s theorem and some of its well-known special cases: the
chain-antichain principle CAC, the ascending-descending chain principle ADS,
and the cohesiveness principle COH.

The results I will talk about are part of a larger project joint with Marta
Fiori Carones, Katarzyna Kowalik, Tin Lok Wong, and Keita Yokoyama.