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 ⟶(\kappa ,\omega {)}^2,$

tzn. dla każdego kolorowania $c:[\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[[A{]}^2]=\{0\},$

ii) istnieje podzbiór $B\subseteq \kappa$ typu porządkowego $\omega$ dla którego $c[[B{]}^2]=\{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:\kappa \to \omega$ będzie funkcją daną wzorem $f(\alpha )=\min \{n<\omega :{\lambda }_n>\alpha \}(\alpha \in \kappa ).$ Kolorowanie $c:[\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

Szablon:Osobny artykuł 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 $⊏$ będą dwiema relacjami dobrego porządku na $X.$ Rozważmy zbiory par

$P_0=\{\{x,y\}:x<y$ oraz $x⊏y\},$

$P_1=\{\{x,y\}:x<y$ oraz $x⊐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

• Szablon:Cytuj książkę
• Szablon:Cytuj książkę