Logic Colloquium: Transfinite Ramsey Theorem

Colloquium | September 6 | 4-5 p.m. | 60 Evans Hall

 Antonio Montalban, UC Berkeley

 Department of Mathematics

We consider a version of the Ramsey Theorem for coloring of tuples within a finite set where the exponent is transfinite. That is, the tuples we color are gamma-large for some ordinal gamma. As in Ramsey theorem we ask: How large should a finite set of numbers be to ensure that, for all colorings of the gamma-large tuples with a certain finite number of colors, there exists a homogeneous set that is alpha-large? Again, alpha being an ordinal. The answer should be an ordinal, and its existence follows from the Galvin-Prikry Theorem. What we ask is about the precise value of the bound, given as a function of the ordinals alpha and gamma. We also consider computability theoretic and reverse mathematics issues related to this.