Friday, 31 July 2009

co.combinatorics - Applications of infinite Ramsey's Theorem (on N)?

Beyond the infinite Ramsey's theorem on N, there is, of course, a kind of super-infinite extension of it to the concept of Ramsey cardinals, one of many large cardinal concepts.



Most of the large cardinal concepts, including Ramsey cardinals, generalize various mathematical properties of the countably infinite cardinal ω to uncountable cardinals. For example, an uncountable cardinal κ is a Ramsey cardinal if every coloring of finite subsets of kappa into 2 colors (or indeed, less than κ many colors) admits a homogeneous set of size κ. Such cardinals are necessarily inaccessible, Mahlo, and much more. The somewhat weaker property, that every coloring of pairs (or for any fixed finite size) from κ to 2 colors has a homogeneous set, is equivalent to κ being weakly compact, a provably weaker notion, since every Ramsey cardinal is a limit of weakly compact cardinals. Similarly, the concept of measurable cardinals generalize the existence of ultrafilters on ω, for an uncountable cardinal κ is said to be a measurable cardinal if there is a nonprincipal κ-complete ultrafilter on κ.



Ramsey cardinals figure in many arguments in set theory. For example, if there is a Ramsey cardinal, then V is not L, and Ramsey cardinals are regarded as a natural large cardinal notion just exceeding the V=L boundary. Another prominent result is the fact that every measurable cardinal is Ramsey (which is not obvious from first notions). Further, if there is a Ramsey cardinal, then 0# exists. Indeed, this latter argument proceeds as a pure Ramsey style argument, using a coloring. Namely, if κ is Ramsey, then we may color every finite increasing sequence of ordinals with the type that they realize in L. By the Ramsey property, there must be a set of size κ, all of whose increasing finite subsequences realize the same type. That is, there is a large class of order indiscernibles for L. By results of Silver, this is equivalent to the assertion that 0# exists.



The fact that Ramsey cardinals are strictly stronger than weakly compact cardinals suggests to my mind that there is something fundamentally more powerful about finding homogeneous sets for colorings of all finite subsets than just for pairs or for subsets of some fixed size. This difference is not revealed at ω, for which both are true by the infinite Ramsey theorem. But perhaps it suggests that we will get more power from Ramsey by using the more powerful colorings, since this is provably the case for higher cardinals.



Another point investigated by set theorists is that finding homogeneous sets in the case of infinite exponents---that is, coloring infinite subsets---is known to be inconsistent with the axiom of choice. However, in models of set theory where the Axiom of Choice fails, these infinitary Ramsey cardinals are fruitfully investigated. For example, under the Axiom of Determinacy, there are a great number of cardinals realizing an infinite exponent paritition relation.

No comments:

Post a Comment