Midwest Computability Seminar

XXV
Part v


The Midwest Computability Seminar is meeting remotely in the fall of 2020. The recurring Zoom link is:

https://notredame.zoom.us/j/99754332165?pwd=RytjK1RFZU5KWnZxZ3VFK0g4YTMyQT09

Meeting ID: 997 5433 2165

Passcode: midwest


Slides    Panopto video    YouTube video


This session will be held jointly with the Computability Theory and Applications Online Seminar.


DATE: Tuesday, October 13th, 2020

TIME: 3:00 - 4:00 PM CDT

SPEAKER: Leszek Kołodziejczyk - University of Warsaw

TITLE: 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 ∀X ∃Y ψ(X,Y) with X,Y denoting subsets of ℕ and ψ 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 RCA0, which is intended to correspond roughly to the idea of "computable mathematics". The main two axioms of RCA0 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 RCA0*.

In this talk, I will discuss some results concerning the reverse mathematics of combinatorial principles over RCA0*. 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.



Past and Future Sessions


Previous Seminars:

If you haven't been receiving the announcements and would like to be included in the list, send an email to drh@math.uchicago.edu.