Infinitary combinatorics

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

${\displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}$

as a shorthand way of saying that every partition of the set [κ]ⁿ of n-element subsets of ${\displaystyle \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

${\displaystyle \kappa \rightarrow (\lambda )_{m}^{<\omega }}$

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

${\displaystyle \kappa \rightarrow (\lambda ,\mu )^{n}}$

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

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

${\displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}}$ for all finite n and k (Ramsey's theorem).

${\displaystyle \beth _{n}^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{n+1}}$ (Erdős–Rado theorem.)

${\displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}}$ (Sierpiński theorem)

${\displaystyle 2^{\kappa }\not \rightarrow (3)_{\kappa }^{2}}$

${\displaystyle \kappa \rightarrow (\kappa ,\aleph _{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

${\displaystyle \aleph _{1}\rightarrow (\aleph _{1})_{2}^{\aleph _{1}}}$

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

• Weakly compact cardinals κ are those that satisfy κ→(κ)²
• α-Erdős cardinals κ are the smallest that satisfy κ→(α)^<ω
• Ramsey cardinals κ are those that satisfy κ→(κ)^<ω

• Dushnik, Ben; Miller, E. W. (1941), "Partially ordered sets", American Journal of Mathematics, 63 (3): 600–610, doi:10.2307/2371374, hdl:10338.dmlcz/100377, ISSN 0002-9327, JSTOR 2371374, MR 0004862
• Erdős, Paul; Hajnal, András (1971), "Unsolved problems in set theory", Axiomatic Set Theory ( Univ. California, Los Angeles, Calif., 1967), Proc. Sympos. Pure Math, XIII Part I, Providence, R.I.: Amer. Math. Soc., pp. 17–48, MR 0280381
• Erdős, Paul; Hajnal, András; Máté, Attila; Rado, Richard (1984), Combinatorial set theory: partition relations for cardinals, Studies in Logic and the Foundations of Mathematics, 106, Amsterdam: North-Holland Publishing Co., ISBN 0-444-86157-2, MR 0795592
• Erdős, P.; Rado, R. (1956), "A partition calculus in set theory", Bull. Amer. Math. Soc., 62 (5): 427–489, doi:10.1090/S0002-9904-1956-10036-0, MR 0081864
• Kanamori, Akihiro (2000). The Higher Infinite (second ed.). Springer. ISBN 3-540-00384-3.
• Kunen, Kenneth (1980), Set Theory: An Introduction to Independence Proofs, Amsterdam: North-Holland, ISBN 978-0-444-85401-8