Partition Relation
   HOME

TheInfoList



OR:

In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
to
infinite set In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Properties The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only ...
s. Some of the things studied include
continuous graph GraphOn GO-Global is a multi-user remote access application for Windows. Overview GO-Global allows multiple users to concurrently run Microsoft Windows applications installed on a Windows server or server farm  from network-connected lo ...
s and
trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
, extensions of
Ramsey's theorem In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (s ...
, and
Martin's axiom In the mathematical field of set theory, Martin's axiom, introduced by Donald A. Martin and Robert M. Solovay, is a statement that is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, but it is consi ...
. Recent developments concern combinatorics of the continuum and combinatorics on successors of singular cardinals.Todd Eisworth, ''Successors of Singular Cardinals'' Chapter 15 in Handbook of Set Theory, edited by Matthew Foreman and Akihiro Kanamori, Springer, 2010


Ramsey theory for infinite sets

Write κ, λ for ordinals, ''m'' for a
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. T ...
and ''n'' for a natural number. introduced the notation :\kappa\rightarrow(\lambda)^n_m as a shorthand way of saying that every partition of the set ºsup>''n'' of ''n''-element
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
s 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 In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
, 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)^_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 ºsup>''n'' of ''n''-element subsets of κ with 2 colors has a subset of order type λ such that all elements of »sup>''n'' have the first color, or a subset of order type μ such that all elements of ¼sup>''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 In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (s ...
). :\beth_n^+\rightarrow(\alef_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 In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game o ...
(AD). For example, Donald A. Martin proved that AD implies :\alef_1\rightarrow(\alef_1)^_2


Large cardinals

Several
large cardinal In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least ...
properties can be defined using this notation. In particular: *
Weakly compact cardinal In mathematics, a weakly compact cardinal is a certain kind of cardinal number introduced by ; weakly compact cardinals are large cardinals, meaning that their existence cannot be proven from the standard axioms of set theory. (Tarski originally ...
s κ are those that satisfy κ→(κ)2 *α-
Erdős cardinal In mathematics, an Erdős cardinal, also called a partition cardinal is a certain kind of large cardinal number introduced by . The Erdős cardinal is defined to be the least cardinal such that for every function there is a set of order type th ...
s κ are the smallest that satisfy κ→(α)<ω *
Ramsey cardinal In mathematics, a Ramsey cardinal is a certain kind of large cardinal number introduced by and named after Frank P. Ramsey, whose theorem establishes that ω enjoys a certain property that Ramsey cardinals generalize to the uncountable case. ...
s κ are those that satisfy κ→(κ)<ω


Notes


References

* * * * * *{{Citation , last1=Kunen , first1=Kenneth , author1-link=Kenneth Kunen , title= Set Theory: An Introduction to Independence Proofs , publisher=North-Holland , location=Amsterdam , isbn=978-0-444-85401-8 , year=1980 Set theory Combinatorics