Twierdzenie Erdősa-Dushnika-Millera – Wikipedia, wolna encyklopedia

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

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

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

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

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

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

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

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

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

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

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

 Osobny artykuł: dobry porządek.

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

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

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

Zbiory ${\displaystyle P_{0}}$ i ${\displaystyle P_{1}}$ stanowią partycję zbioru ${\displaystyle [X]^{2},}$ tj. ${\displaystyle [X]^{2}=P_{0}\cup P_{1}.}$ Istnieje więc zbiór ${\displaystyle A\subseteq \kappa }$ mocy ${\displaystyle \kappa }$ dla którego ${\displaystyle [A]^{2}\subseteq P_{0}}$ bądź istnieje zbiór nieskończony ${\displaystyle B}$ dla którego ${\displaystyle [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. □

• 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