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), wie {displaystyle kappa rightarrow (Kappa ,aleph _{0})^{2}} . Das bedeutet, dass, for every set {Anzeigestil S} of cardinality {Anzeigestil kappa } , and every partition of the ordered pairs of elements of {Anzeigestil S} into two subsets {Anzeigestil P_{1}} und {Anzeigestil P_{2}} , there exists either a subset {Anzeigestil S_{1}subset S} of cardinality {Anzeigestil kappa } or a subset {Anzeigestil S_{2}subset S} of cardinality {Anzeigestil Aleph _{0}} , such that all pairs of elements of {Anzeigestil S_{ich}} belong to {Anzeigestil P_{ich}} .[3] Hier, {Anzeigestil P_{1}} can be interpreted as the edges of a graph having {Anzeigestil S} as its vertex set, in which {Anzeigestil S_{1}} (if it exists) is a clique of cardinality {Anzeigestil kappa } , und {Anzeigestil S_{2}} (if it exists) is a countably infinite independent set.[1] Wenn {Anzeigestil S} is taken to be the cardinal number {Anzeigestil kappa } selbst, the theorem can be formulated in terms of ordinal numbers with the notation {displaystyle kappa rightarrow (Kappa ,Omega )^{2}} , bedeutet, dass {Anzeigestil S_{2}} (when it exists) has order type {Anzeigestil Omega } . For uncountable regular cardinals {Anzeigestil kappa } (and some other cardinals) this can be strengthened to {displaystyle kappa rightarrow (Kappa ,Omega +1)^{2}} ;[4] jedoch, 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] Referenzen ^ Hochspringen zu: 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, HERR 0779390, S2CID 123272176; see in particular Theorem 44 ^ Dushnik, Ben; Miller, E. W. (1941), "Partially ordered sets", Amerikanisches Journal für Mathematik, 63 (3): 600–610, doi:10.2307/2371374, JSTOR 2371374, HERR 0004862; see in particular Theorems 5.22 und 5.23 ^ Wald, Paul; Rado, R. (1956), "A partition calculus in set theory", Bulletin der American Mathematical Society, 62 (5): 427–489, doi:10.1090/S0002-9904-1956-10036-0, HERR 0081864 ^ Shelah, Sahara (2009), "The Erdős–Rado arrow for singular cardinals", Canadian Mathematical Bulletin, 52 (1): 127–131, doi:10.4153/CMB-2009-015-8, HERR 2494318 ^ Shelah, Sahara; Stanley, Lee J. (2000), "Filters, Cohen sets and consistent extensions of the Erdős–Dushnik–Miller theorem", Das Journal of Symbolic Logic, 65 (1): 259–271, arXiv:math/9709228, doi:10.2307/2586535, JSTOR 2586535, HERR 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, HERR 1425228; see in particular Section 3, "Infinite Ramsey theory – early papers", p. 353 Kategorien: Order theoryRamsey theorySet theory