Twierdzenie Erdősa-Dushnika-Millera

Twierdzenie Erdősa-Dushnika-Millera – wariant twierdzenia Ramseya mówiący, że dla każdej nieskończonej liczby kardynalnej $\kappa$ zachodzi relacja podziałowa

$\kappa \longrightarrow (\kappa ,\omega )^{2},$

tzn. dla każdego kolorowania $c\colon [\kappa ]^{2}\to \{0,1\}$ rodziny $[\kappa ]^{2}$ dwuelementowych podzbiorów $\kappa$ na dwa kolory 0 i 1 zachodzi co najmniej jeden z warunków:

i) istnieje podzbiór $A\subseteq \kappa$ typu porządkowego $\kappa$ dla którego $c{\big [}[A]^{2}{\big ]}=\{0\},$

ii) istnieje podzbiór $B\subseteq \kappa$ typu porządkowego $\omega$ dla którego $c{\big [}[B]^{2}{\big ]}=\{1\}.$

(tj. istnieje zbiór monochromatyczny koloru 0 typu porządkowego $\kappa$ bądź istnieje zbiór monochromatyczny koloru 1 typu porządkowego $\omega$).

Twierdzenie to zostało udowodnione przez Dushnika i Millera w 1941 dla regularnych liczb kardynalnych i rozszerzone na singularne liczby kardynalne przez Erdősa.

Uwagi

W przypadku, gdy $\kappa$ jest liczbą kardynalną o przeliczalnej kofinalności (tj. cf $\kappa =\omega$), to liczby $\omega$ w sformułowaniu twierdzenia Erdősa-Dushnika-Millera nie można zastąpić przez $\omega +1.$

Dowód. Ponieważ cf $\kappa =\omega ,$ istnieje zatem ściśle rosnący ciąg liczb kardynalnych $(\lambda _{n})$ zbieżny do $\kappa$ (tj. $\sup \lambda _{n}=\kappa$). Niech $f\colon \kappa \to \omega$ będzie funkcją daną wzorem $f(\alpha )=\min\{n<\omega :\lambda _{n}>\alpha \}(\alpha \in \kappa ).$ Kolorowanie $c\colon [\kappa ]^{2}\to \{0,1\}$ dane wzorem

$c(\{\alpha ,\beta \})=0,$ gdy $f(\alpha )=f(\beta )$ oraz $c(\{\alpha ,\beta \})=1$ w przeciwnym przypadku,

przeczy relacji podziałowej $\kappa \to (\kappa ,\omega +1)^{2}.$ Rzeczywiście, dla każdego zbioru $B\subseteq \kappa$ koloru 1, funkcja $f$ zacieśniona do $B$ zachowuje porządek, a więc każdy zbiór koloru 1 ma typ porządkowy co najwyżej $\omega$ (w szczególności, nie może mieć typu porządkowego $\omega +1,$ bo $\omega$ nie zawiera takich podzbiorów). Z drugiej strony, dla każdej liczby naturalnej $n,$ moc przeciwobrazu $f^{-1}[{n}]$ jest ściśle mniejsza od $\kappa ,$ a więc nie istnieje zbiór monochoromatyczny koloru 0. □

Przykładowe zastosowanie

Z twierdzenia Erdősa-Dushnika-Millera wynika, że w zbiorze nieskończonym $X$ każde dwie relacje dobrego porządku pokrywają się na zbiorze mocy $\kappa =|X|.$ Istotnie, niech $<$ i $\sqsubset$ będą dwiema relacjami dobrego porządku na $X.$ Rozważmy zbiory par

$P_{0}=\{\{x,y\}:x<y$ oraz $x\sqsubset y\},$

$P_{1}=\{\{x,y\}:x<y$ oraz $x\sqsupset y\}.$

Zbiory $P_{0}$ i $P_{1}$ stanowią partycję zbioru $[X]^{2},$ tj. $[X]^{2}=P_{0}\cup P_{1}.$ Istnieje więc zbiór $A\subseteq \kappa$ mocy $\kappa$ dla którego $[A]^{2}\subseteq P_{0}$ bądź istnieje zbiór nieskończony $B$ dla którego $[B]^{2}\subseteq P_{1}.$ Druga część alternatywy nie jest jednak możliwa, bo każdy ściśle malejący podzbiór zbioru dobrze uporządkowanego jest skończony. □

Bibliografia

• Aleksander Błaszczyk, Sławomir Turek: Teoria Mnogości. Warszawa: PWN, 2007. ISBN 978-83-01-15232-1. Brak numerów stron w książce
• Thomas Jech: Set theory. The Third Millennium Edition, revised and expanded. Berlin: Springer-Verlag, 2002. ISBN 3-540-44085-2. Brak numerów stron w książce