Ramsey theorem (set theory)

The set of Ramsey is one of FP Ramsey proven in 1929 set out the mathematical field of set theory . He generalizes the simple fact that if an infinite set is broken down into finitely many subsets, at least one of these subsets must also be infinite.

Formulation of the sentence

If an infinite set denotes the set of all -element subsets of . If one breaks down into finitely many subsets, one of the subsets must again be infinite. In addition, one can make the following stronger statement, known as the Ramsey Theorem: ${\displaystyle A}$ ${\displaystyle [A]^{n}}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle [A]^{n}}$

• Is the set of natural numbers and is a division into subsets, where and are natural numbers, then there is one and an infinite subset with . ${\displaystyle \omega }$ ${\displaystyle [\omega ]^{n}=X_{1}\cup \ldots \cup X_{m}}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle j\in \{1,\ldots ,m\}}$ ${\displaystyle H\subset \omega }$ ${\displaystyle [H]^{n}\subset X_{j}}$

Remarks

Subsets of the form are called homogeneous. According to Ramsey's theorem, every decomposition of into finitely many subsets contains at least one infinite homogeneous subset. The case is reduced to the fact mentioned in the introduction that when an infinite set is broken down into finitely many subsets, at least one of these subsets must also be infinite. ${\displaystyle [\omega ]^{n}}$ ${\displaystyle H^{n}}$ ${\displaystyle [\omega ]^{n}}$ ${\displaystyle n=1}$

${\displaystyle \omega }$is the prototype of a set of power (see Aleph function ) and can of course be replaced by any other set of this power in Ramsey's theorem. If a set is cardinal , then one could ask, by analogy with the above theorem, whether if the set is broken down into subsets, at least one of the subset must contain a homogeneous subset of the cardinality . For, of course , the answer is yes, but for it must be denied. The existence of cardinal numbers , so that when dividing into two subsets, at least one of these subsets must include a homogeneous subset of the cardinality , can not be proven in ZFC set theory . Such cardinal numbers are called weakly compact and their non-existence is at least relatively consistent, that is, if ZFC set theory is free of contradictions, then it is also free of contradictions together with the additional axiom of the non-existence of weakly compact cardinal numbers. ${\displaystyle \aleph _{0}}$ ${\displaystyle A}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle [A]^{n}}$ ${\displaystyle m}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle n=1}$ ${\displaystyle m=n=2}$ ${\displaystyle \kappa >\aleph _{0}}$ ${\displaystyle [\kappa ]^{2}}$ ${\displaystyle \kappa }$

See also

• Ramsey's theorem , a theorem from combinatorial graph theory
• Erdős-Rado's theorem , a theorem on partitions of sets of form . ${\displaystyle [\kappa ]^{n}}$

literature

• Thomas Jech : Set Theory , Springer-Verlag (2003), ISBN 3-540-44085-2 , especially chapter 9
• FP Ramsey: On a Problem of Formal Logic , Proc. London Mathematical Society 1929/1930, Volume 30, pages 264-186