ObjectivesConfirmed ParticipantsPress Release
Schedule and Abstracts (PDF)
Mailing List
Workshop Videos
Final Report (PDF)

# Computability, Reverse Mathematics and Combinatorics (08w5019)

Arriving in Banff, Alberta 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 Slaman (University of California, Berkeley)

## 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.

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.