Wprowadźmy w zbiorze relację
Podciąg jest niemalejący wtedy i tylko wtedy, gdy odpowiadający mu zbiór par tworzy łańcuch w i nierosnący, gdy zbiór ten tworzy antyłańcuch. Jeśli najliczniejszy antyłańcuch w ma co najmniej elementów, to natychmiast otrzymujemy tezę. W przeciwnym wypadku zbiór jest sumą łańcuchów. Wówczas na mocy zasady szufladkowej Dirichleta istnieje łańcuch o mocy nie mniejszej niż czyli co najmniej To kończy dowód.
Rozkład zbioru potęgowego na sumę łańcuchów Rozważmy – rodzinę wszystkich podzbiorów zbioru uporządkowaną przez relację zawierania. Twierdzenie Spernera mówi, że najliczniejszy antyłańcuch w tym zbiorze ma elementów. Z twierdzenia Dilwortha wynika, że można przedstawić jako sumę łańcuchów. Ponadto jest to najmniejsza liczba o tej własności.
Zobacz też twierdzenie Spernera częściowy porządek krata
Przypisy
Dilwortha Kategoria:Twierdzenia teorii porządku