08w5019 Computability, Reverse Mathematics and Combinatorics

Arriving Sunday, December 7 and departing Friday, December 12, 2008

Organizers: Peter Cholak (University of Notre Dame), Barbara Csima (University of Waterloo), Steffen Lempp (University of Wisconsin--Madison), Manuel Lerman (University of Connecticut-Storrs), Richard Shore (Cornell University), Theodore A. Slaman (University of California at Berkeley).

Confirmed Participants

Press Release: Computability, Reverse Mathematics and Combinatorics

Information for Participants

Schedule & Abstracts

List of Problems

Mailing List

Workshop Files

Final Report (PDF file)

Workshop Videos

Objectives

Reverse mathematics is rapidly developing beyond the primarily foundational concerns of its founders H. Friedman and S. Simpson. Under the influence of an influx of researchers from computability theory, new techniques are being introduced and examples studied that are computationally complex in various ways. This work shows that a number of interesting classical combinatorial results are proof-theoretically (computationally) strictly weaker than arithmetic comprehension, ACA$_{0}$ (solving the halting problem) and different from all the standard systems. The leading examples are Ramsey's theorem for pairs (RT$_{2}^{2}$) and some of its consequences for linear and partial orderings. The computational analysis began independently in the 70's and 80's with work of Jockusch, Lerman, Downey and others. Recent advances have established the reverse mathematical results as well as proved new computational ones.

There are still a number of fundamental questions about these principles that remain open. A major piece fell into place at a computability workshop in Singapore in 2005 that included some reverse mathematics. A combination of results done at the meeting by about half a dozen people showed that CAC (Dilworth's chain/antichain theorem) is strictly weaker than RT$_{2}^{2}$. One goal of the workshop would be to continue this attack. For example, CAC is known to be incomparable with the compactness principle WKL$_{0}$, but RT$_{2}^{2}$ is not. The classical combinatorial results suggest that just as Dilworth's theorem is less complicated than RT$_{2}^{2}$, so ErdH{o}s-Szekeres is less complicated than Dilworth. Does this correspond to a computational and proof-theoretic difference between ADS and CAC as it did for CAC and RT$_{2}^{2}$? Are there other combinatorial principles whose proofs or growth rate behavior suggest that they might also have interesting proof theoretic or computational properties?

This area has become very active in recent years, attracting both long established senior people from computability theory as well as a large strong active group of junior people. Among these are winners of the Sacks prize for the best logic thesis worldwide for the past two years (Mileti and Montalb'{a}n). An obvious goal of the workshop is to bring these people and others together to discuss new problems, techniques and lines of attack. The only workshop devoted to this area was an AMS-IMS-SIAM joint summer research conference some twenty years ago. That meeting and its proceedings volume provided a major push for the field. The Singapore meeting provided an important venue but a workshop solely devoted to this topic should make a real impact on the field.

In addition to this spate of research on principles weaker than ACA$_{0}$, Montalb'{a}n has provided a new impetus at the higher end with the discovery of a number of theorems in the region of ATR$_{0}$. This work is closely connected to the old problem about characterizing the strength of Laver's theorem that linear orderings are wellquasiordered under embeddability. A second long-standing open problem possibly at this level is the Carlson-Simpson Dual Ramsey Theorem. Here all that is known is that the underlying combinatorial principles follow from $Pi_{1}^{1}$-CA$_{0}$ (Slaman) some versions imply ACA$_{0}$ others only that they do not follow from WKL$_{0}$ (Miller-Solomon). Carlson's subsequent strengthenings present wide open problems. A natural candidate for a new problem at this level is the recent proof of Aharoni and Berger of the infinite version of Menger's theorem. It is intuitively stronger than K"{o}nig's Duality theorem which is known to be equivalent to ATR$_{0}$. This area of the subject is difficult and needs development. Completing these analyses at both ends of the spectrum will shed important light on basic foundational, computational and combinatorial issues.

New techniques from other areas are also needed. A primary issue is the difficulty of working with nonstandard models. There are two likely sources of new ideas and researchers. The first is proof theory. H. Friedman has been almost the only important serious user of ordinal analysis in the area (and with great success on the Robertson-Seymour graph minor theorems). A goal of the workshop would be to invite some traditional proof theorists such as A. Weiermann, to expose the communities to each other and hope for a transfer of techniques and problems between them. In addition to ordinal analysis, proof-theoretic techniques that have been applied and should be represented include some for conservation results (J. Avigad) and the development of new higher order systems for analyzing complicated principles (U. Kohlenbach).

A very recent approach by H. J. Keisler (outlined in emph{B. Symb. Logic}, March 2006) uses a direct analysis of nonstandard models and methods in arithmetic. It may also hold significant promise for attacking old and new problems. We hope to expose the community to this approach.

Finally, we hope to include a number of combinatorists with interests in logic, computability and reverse mathematics. The hope would be to provide a source of new problems from combinatorics and direct insight into their nature that would facilitate computational and reverse mathematical analysis. In addition, a number of seemingly new variants on Ramsey's theorem have been suggested by the reverse mathematical investigations that may be of interest to combinatorists. Natural candidates include R. Aharoni, E. Berger, N. Hindman, H. Kierstead and J. Remmel.