Computability, Reverse Mathematics and Combinatorics (08w5019)

Arriving in Banff, Alberta Sunday, December 7 and departing Friday December 12, 2008


(University of Notre Dame)

(University of Waterloo)

(University of Wisconsin--Madison)

(University of Connecticut-Storrs)

(Cornell University)

(University of California, Berkeley)


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.