Reverse mathematics of combinatorial principles over a weak base theory

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.

logic

Audience: researchers in the topic

---

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.

---