Combinatorics (and much more) in subsystems of second-order arithmetic

Hindman's theorem, first proved in 1974, states that whenever the natural numbers are colored with finitely many colors, there is an infinite set for which all non-repeating finite sums have the same color. The theorem has since been of subsequent interest in several schools of combinatorics, where each of the standard proofs involves highly ineffective methods. In 1987, Blass, Hirst, and Simpson established initial bounds on the strength of the theorem: it lies somewhere in the interval between ACA_0 and ACA^+_0. Since then, the goal of establishing the precise strength of the theorem has become one of the most well-known open problems in reverse mathematics. This talk will survey Hindman's theorem, its several proofs, and the associated work by Hirst and many others on the theorem, restrictions, and variations. [Hide]

In this talk we formulate, prove, and analyze the generalizations of Friedman's free set and thin set theorems, as well as of the rainbow Ramsey theorem, to colorings of exactly large sets and barriers. Among the many consequences of Ramsey's theorem, these theorems have attracted significant interest in recent decades. While these principles deal with colorings of finite subsets of numbers of fixed size, versions of Ramsey's theorem are known to hold for colorings of families of sets of varying -- indeed unbounded -- dimension. The first meaningful generalization in this direction interestingly features the notion of an exactly large finite set, i.e. a set X such that card(X) = min(X)+1, stemming from the famous Paris-Harrington Principle.

The natural generalization of Ramsey's theorem to colorings of exactly large sets follows from the clopen Ramsey Theorem and is known to be strictly stronger than Ramsey's theorem for fixed dimensions both in computability-theoretic and in proof-theoretic terms. It is natural then to consider the analogous generalizations of the free set and thin set theorems to colorings of the exactly large sets, which we denote !omega, and to inquire into their effective and logical strength. We show the equivalence over RCA_0 of RT^(!omega)_2, TS^(!omega), and FS^(!omega). However we do not know whether RT^(!omega)_2 is strongly Weihrauch-reducible to TS^(!omega) or to FS^(!omega). We also showed that RRT^(!omega)_2 does not imply ACA_0. This is a part of a joint work with Carlucci, Levy Patey and Le Houérou.

Exactly large sets happen to be an example of families of sets known as barriers in Ramsey theory and better quasi-ordering theory -- under the name of Schreier barrier they play a relevant role in Banach Space theory. We prove analogous generalizations of the free set and thin set theorems to colorings of barriers. We obtain weak lower bounds relative to levels of the hyperarithmetical hierarchy using a generalization of the limit lemma introduced by Clote to obtain analogous results for Nash-Williams' Ramsey theorem for barriers. These results are from my PhD Thesis and are joint with Lorenzo Carlucci. [Hide]

In 1941 Dushnik and Miller defined the dimension of a poset: the minimum number of linear extensions of the poset whose intersection is exactly the poset itself. We study the reverse mathematics of some theorems that bound the increase in the dimension of a poset when we extend it adding new points or chains. This project was started a few years ago in collaboration with Marta Fiori Carones and recently revamped jointly with Andrea Volpi. [Hide]

The logical strength of Ramsey's theorem is arguably one of the most important lines of research in reverse mathematics. The long-standing open problem of determining the first-order consequences of Ramsey's theorem for pairs and two colors over RCA_0 was an important part of our motivation to study this theorem over a weaker base theory, RCA^*_0, which is obtained from RCA_0 by restricting the induction scheme from ISigma^0_1 to IDelta^0_0.

We present our main results on the strength of RT^n_k for n,k >= 2 over RCA^*_0, including its first-order consequences and its relation to some other Ramsey-like principles. We also discuss some of our proof techniques involving nonstandard models of arithmetic with definable cuts. [Hide]

During the years 1983-1987 I served as Jeff Hirst's Ph.D. thesis advisor. In this talk I will comment on my interactions with Jeff and on some of his reverse mathematics research. In addition, I will update the audience on what I have been doing over the past 25 years. My book "Degrees of Unsolvability" will focus on Turing degrees and Muchnik degrees. The Muchnik degrees may be viewed as the completion of the Turing degrees, in much the same way as the real numbers may be viewed as the completion of the rational numbers. And just as the real number system includes many interesting numbers such as sqrt(2), e, and pi which are not rational, so the Muchnik lattice includes a great many specific, natural degrees which are not Turing degrees. [Hide]

Join me for a look at my personal selection of Jeff Hirst's most impactful theorems. Beyond mathematics, I'll share stories and insights from over 30 years of friendship and intellectual exchange with Jeff, offering a unique perspective on his work and our time together. [Hide]