Erdős–Dushnik–Miller theorem

Erdős–Dushnik–Miller theorem Not to be confused with Dushnik–Miller theorem.

In the mathematical theory of infinite graphs, the Erdős–Dushnik–Miller theorem is a form of Ramsey's theorem stating that every infinite graph contains either a countably infinite independent set, or a clique with the same cardinality as the whole graph.[1] The theorem was first published by Ben Dushnik and E. W. Miller (1941), in both the form stated above and an equivalent complementary form: every infinite graph contains either a countably infinite clique or an independent set with equal cardinality to the whole graph. In their paper, they credited Paul Erdős with assistance in its proof. They applied these results to the comparability graphs of partially ordered sets to show that each partial order contains either a countably infinite antichain or a chain of cardinality equal to the whole order, and that each partial order contains either a countably infinite chain or an antichain of cardinality equal to the whole order.[2] The same theorem can also be stated as a result in set theory, using the arrow notation of Erdős & Rado (1956), as {displaystyle kappa rightarrow (kappa ,aleph _{0})^{2}} . This means that, for every set {displaystyle S} of cardinality {displaystyle kappa } , and every partition of the ordered pairs of elements of {displaystyle S} into two subsets {displaystyle P_{1}} and {displaystyle P_{2}} , there exists either a subset {displaystyle S_{1}subset S} of cardinality {displaystyle kappa } or a subset {displaystyle S_{2}subset S} of cardinality {displaystyle aleph _{0}} , such that all pairs of elements of {displaystyle S_{i}} belong to {displaystyle P_{i}} .[3] Here, {displaystyle P_{1}} can be interpreted as the edges of a graph having {displaystyle S} as its vertex set, in which {displaystyle S_{1}} (if it exists) is a clique of cardinality {displaystyle kappa } , and {displaystyle S_{2}} (if it exists) is a countably infinite independent set.[1] If {displaystyle S} is taken to be the cardinal number {displaystyle kappa } itself, the theorem can be formulated in terms of ordinal numbers with the notation {displaystyle kappa rightarrow (kappa ,omega )^{2}} , meaning that {displaystyle S_{2}} (when it exists) has order type {displaystyle omega } . For uncountable regular cardinals {displaystyle kappa } (and some other cardinals) this can be strengthened to {displaystyle kappa rightarrow (kappa ,omega +1)^{2}} ;[4] however, it is consistent that this strengthening does not hold for the cardinality of the continuum.[5] The Erdős–Dushnik–Miller theorem has been called the first "unbalanced" generalization of Ramsey's theorem, and Paul Erdős's first significant result in set theory.[6] References ^ Jump up to: a b Milner, E. C.; Pouzet, M. (1985), "The Erdős–Dushnik–Miller theorem for topological graphs and orders", Order, 1 (3): 249–257, doi:10.1007/BF00383601, MR 0779390, S2CID 123272176; see in particular Theorem 44 ^ Dushnik, Ben; Miller, E. W. (1941), "Partially ordered sets", American Journal of Mathematics, 63 (3): 600–610, doi:10.2307/2371374, JSTOR 2371374, MR 0004862; see in particular Theorems 5.22 and 5.23 ^ Erdős, Paul; Rado, R. (1956), "A partition calculus in set theory", Bulletin of the American Mathematical Society, 62 (5): 427–489, doi:10.1090/S0002-9904-1956-10036-0, MR 0081864 ^ Shelah, Saharon (2009), "The Erdős–Rado arrow for singular cardinals", Canadian Mathematical Bulletin, 52 (1): 127–131, doi:10.4153/CMB-2009-015-8, MR 2494318 ^ Shelah, Saharon; Stanley, Lee J. (2000), "Filters, Cohen sets and consistent extensions of the Erdős–Dushnik–Miller theorem", The Journal of Symbolic Logic, 65 (1): 259–271, arXiv:math/9709228, doi:10.2307/2586535, JSTOR 2586535, MR 1782118, S2CID 2763013 ^ Hajnal, András (1997), "Paul Erdős' set theory", The mathematics of Paul Erdős, II, Algorithms and Combinatorics, vol. 14, Berlin: Springer, pp. 352–393, doi:10.1007/978-3-642-60406-5_33, MR 1425228; see in particular Section 3, "Infinite Ramsey theory – early papers", p. 353 Categories: Order theoryRamsey theorySet theory