Infinitary combinatorics

In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom. Recent developments concern combinatorics of the continuum[1] and combinatorics on successors of singular cardinals.[2]

Ramsey theory for infinite sets

Write κ, λ for ordinals, m for a cardinal number and n for a natural number. Erdős & Rado (1956) introduced the notation

\kappa\rightarrow(\lambda)^n_m

as a shorthand way of saying that every partition of the set [κ]n of n-element subsets of \kappa into m pieces has a homogeneous set of order type λ. A homogeneous set is in this case a subset of κ such that every n-element subset is in the same element of the partition. When m is 2 it is often omitted.

Assuming the Axiom of Choice, there are no ordinals κ with κ→(ω)ω, so n is usually taken to be finite. An extension where n is almost allowed to be infinite is the notation

\kappa\rightarrow(\lambda)^{<\omega}_m

which is a shorthand way of saying that every partition of the set of finite subsets of κ into m pieces has a subset of order type λ such that for any finite n, all subsets of size n are in the same element of the partition. When m is 2 it is often omitted.

Another variation is the notation

\kappa\rightarrow(\lambda, \mu)^n

which is a shorthand way of saying that every coloring of the set [κ]n of n-element subsets of κ with 2 colors has a subset of order type λ such that all elements of [λ]n have the first color, or a subset of order type μ such that all elements of [μ]n have the second color.

Some properties of this include: (in what follows \kappa is a cardinal)

\alef_0\rightarrow(\alef_0)^n_k for all finite n and k (Ramsey's theorem).
\beth_n^+\rightarrow(\alef_1)_{\alef_0}^{n+1} (Erdős–Rado theorem.)
2^\kappa\not\rightarrow(\kappa^+)^2 (Sierpiński theorem)
2^\kappa\not\rightarrow(3)^2_\kappa
\kappa\rightarrow(\kappa,\alef_0)^2 (Erdős–Dushnik–Miller theorem).

In choiceless universes, partition properties with infinite exponents may hold, and some of them are obtained as consequences of the Axiom of determinacy (AD). For example, Donald A. Martin proved that AD implies

\alef_1\rightarrow(\alef_1)^{\alef_1}_2

Large cardinals

Several large cardinal properties can be defined using this notation. In particular:

References

Notes

  1. Andreas Blass, Combinatorial Cardinal Characteristics of the Continuum, Chapter 6 in Handbook of Set Theory, edited by Matthew Foreman and Akihiro Kanamori, Springer, 2010
  2. Todd Eisworth, Successors of Singular Cardinals Chapter 15 in Handbook of Set Theory, edited by Matthew Foreman and Akihiro Kanamori, Springer, 2010
This article is issued from Wikipedia - version of the Tuesday, April 09, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.