Misplaced Pages

Infinitary combinatorics

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Arrow notation (Ramsey theory)) Extension of ideas in combinatorics to infinite sets
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (May 2024) (Learn how and when to remove this message)

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 and combinatorics on successors of singular cardinals.

Ramsey theory for infinite sets

Write κ , λ {\displaystyle \kappa ,\lambda } for ordinals, m {\displaystyle m} for a cardinal number (finite or infinite) and n {\displaystyle n} for a natural number. Erdős & Rado (1956) introduced the notation

κ → ( λ ) m n {\displaystyle \displaystyle \kappa \rightarrow (\lambda )_{m}^{n}}

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

Assuming the axiom of choice, there are no ordinals κ {\displaystyle \kappa } with κ → ( ω ) ω {\displaystyle \kappa \rightarrow (\omega )^{\omega }} , so n {\displaystyle n} is usually taken to be finite. An extension where n {\displaystyle n} is almost allowed to be infinite is the notation

κ → ( λ ) m < ω {\displaystyle \displaystyle \kappa \rightarrow (\lambda )_{m}^{<\omega }}

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

Another variation is the notation

κ → ( λ , μ ) n {\displaystyle \displaystyle \kappa \rightarrow (\lambda ,\mu )^{n}}

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

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

ℵ 0 → ( ℵ 0 ) k n {\displaystyle \displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}} for all finite n {\displaystyle n} and k {\displaystyle k} (Ramsey's theorem). ℶ n + → ( ℵ 1 ) ℵ 0 n + 1 {\displaystyle \displaystyle \beth _{n}^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{n+1}} (the Erdős–Rado theorem.) 2 κ ↛ ( κ + ) 2 {\displaystyle \displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}} (the Sierpiński theorem) 2 κ ↛ ( 3 ) κ 2 {\displaystyle \displaystyle 2^{\kappa }\not \rightarrow (3)_{\kappa }^{2}} κ → ( κ , ℵ 0 ) 2 {\displaystyle \displaystyle \kappa \rightarrow (\kappa ,\aleph _{0})^{2}} (the 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

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

Strong colorings

Wacław Sierpiński showed that the Ramsey theorem does not extend to sets of size ℵ 1 {\displaystyle \aleph _{1}} by showing that 2 ℵ 0 ↛ ( ℵ 1 ) 2 2 {\displaystyle 2^{\aleph _{0}}\nrightarrow (\aleph _{1})_{2}^{2}} . That is, Sierpiński constructed a coloring of pairs of real numbers into two colors such that for every uncountable subset of real numbers X {\displaystyle X} , [ X ] 2 {\displaystyle ^{2}} takes both colors. Taking any set of real numbers of size ℵ 1 {\displaystyle \aleph _{1}} and applying the coloring of Sierpiński to it, we get that ℵ 1 ↛ ( ℵ 1 ) 2 2 {\displaystyle \aleph _{1}\not \rightarrow (\aleph _{1})_{2}^{2}} . Colorings such as this are known as strong colorings and studied in set theory. Erdős, Hajnal & Rado (1965) introduced a similar notation as above for this.

Write κ , λ {\displaystyle \kappa ,\lambda } for ordinals, m {\displaystyle m} for a cardinal number (finite or infinite) and n {\displaystyle n} for a natural number. Then

κ ↛ [ λ ] m n {\displaystyle \displaystyle \kappa \nrightarrow _{m}^{n}}

is a shorthand way of saying that there exists a coloring of the set [ κ ] n {\displaystyle ^{n}} of n {\displaystyle n} -element subsets of κ {\displaystyle \kappa } into m {\displaystyle m} pieces such that every set of order type λ {\displaystyle \lambda } is a rainbow set. A rainbow set is in this case a subset A {\displaystyle A} of κ {\displaystyle \kappa } such that [ A ] n {\displaystyle ^{n}} takes all m {\displaystyle m} colors. When m {\displaystyle m} is 2 it is often omitted. Such statements are known as negative square bracket partition relations.

Another variation is the notation

κ ↛ [ λ ; μ ] m 2 {\displaystyle \kappa \nrightarrow _{m}^{2}}

which is a shorthand way of saying that there exists a coloring of the set [ κ ] 2 {\displaystyle ^{2}} of 2-element subsets of κ {\displaystyle \kappa } with m {\displaystyle m} colors such that for every subset A {\displaystyle A} of order type λ {\displaystyle \lambda } and every subset B {\displaystyle B} of order type μ {\displaystyle \mu } , the set A × B {\displaystyle A\times B} takes all m {\displaystyle m} colors.

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

2 κ ↛ [ κ + ] 2 {\displaystyle \displaystyle 2^{\kappa }\nrightarrow ^{2}} (Sierpiński) ℵ 1 ↛ [ ℵ 1 ] 2 {\displaystyle \displaystyle \aleph _{1}\nrightarrow ^{2}} (Sierpiński) ℵ 1 ↛ [ ℵ 1 ] 3 2 {\displaystyle \displaystyle \aleph _{1}\nrightarrow _{3}^{2}} (Laver, Blass) ℵ 1 ↛ [ ℵ 1 ] 4 2 {\displaystyle \displaystyle \aleph _{1}\nrightarrow _{4}^{2}} ( Galvin and Shelah) ℵ 1 ↛ [ ℵ 1 ] ℵ 1 2 {\displaystyle \displaystyle \aleph _{1}\nrightarrow _{\aleph _{1}}^{2}} (Todorčević) ℵ 1 ↛ [ ℵ 1 ; ℵ 1 ] ℵ 1 2 {\displaystyle \displaystyle \aleph _{1}\nrightarrow _{\aleph _{1}}^{2}} (Moore) 2 ℵ 0 ↛ [ 2 ℵ 0 ] ℵ 0 2 {\displaystyle \displaystyle 2^{\aleph _{0}}\nrightarrow _{\aleph _{0}}^{2}} ( Galvin and Shelah)

Large cardinals

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

  • Weakly compact cardinals κ {\displaystyle \kappa } are those that satisfy κ → ( κ ) 2 {\displaystyle \kappa \rightarrow (\kappa )^{2}}
  • α-Erdős cardinals κ {\displaystyle \kappa } are the smallest that satisfy κ → ( α ) < ω {\displaystyle \kappa \rightarrow (\alpha )^{<\,\omega }}
  • Ramsey cardinals κ {\displaystyle \kappa } are those that satisfy κ → ( κ ) < ω {\displaystyle \kappa \rightarrow (\kappa )^{<\,\omega }}

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
  3. Rinot, Assaf, Tutorial on strong colorings and their applications, 6th European Set Theory Conference, retrieved 2023-12-10

References

Categories: