Twierdzenie Erdősa-Dushnika-Millera

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

tzn. dla każdego kolorowania rodziny dwuelementowych podzbiorów na dwa kolory 0 i 1 zachodzi co najmniej jeden z warunków:

i) istnieje podzbiór typu porządkowego dla którego
ii) istnieje podzbiór typu porządkowego dla którego

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

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   jest liczbą kardynalną o przeliczalnej kofinalności (tj. cf  ), to liczby   w sformułowaniu twierdzenia Erdősa-Dushnika-Millera nie można zastąpić przez  

Dowód. Ponieważ cf   istnieje zatem ściśle rosnący ciąg liczb kardynalnych   zbieżny do   (tj.  ). Niech   będzie funkcją daną wzorem   Kolorowanie   dane wzorem
  gdy   oraz   w przeciwnym przypadku,
przeczy relacji podziałowej   Rzeczywiście, dla każdego zbioru   koloru 1, funkcja   zacieśniona do   zachowuje porządek, a więc każdy zbiór koloru 1 ma typ porządkowy co najwyżej   (w szczególności, nie może mieć typu porządkowego   bo   nie zawiera takich podzbiorów). Z drugiej strony, dla każdej liczby naturalnej   moc przeciwobrazu   jest ściśle mniejsza od   a więc nie istnieje zbiór monochoromatyczny koloru 0. □

Przykładowe zastosowanie

edytuj
Osobny artykuł: dobry porządek.

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

  oraz  
  oraz  

Zbiory   i   stanowią partycję zbioru   tj.   Istnieje więc zbiór   mocy   dla którego   bądź istnieje zbiór nieskończony   dla którego   Druga część alternatywy nie jest jednak możliwa, bo każdy ściśle malejący podzbiór zbioru dobrze uporządkowanego jest skończony. □

Przypisy

edytuj
  1. B. Dushnik, E.W. Miller, Partially Ordered Sets, „Amer. J. Math”. 63 (1941), s. 600–610.

Bibliografia

edytuj