Twierdzenie Dilwortha

[Kate2410]

Udowodnij, korzystając z twierdzenia Dilwortha, że spośród dowolnych \(\displaystyle{ 13}\) (różnych) liczb naturalnych da się wybrać albo ciąg siedmiu (różnych) liczb, z których każda kolejna jest wielokrotnością poprzedniej, lub trzy liczby, z których żadne dwie nie dzielą się przez siebie.

Znam wypowiedź twierdzenia, ale nie wiem jak je wykorzystać.

[Gosda]

Zapisz sformułowanie twierdzenia. Mówi ono coś o łańcuchach, więc potrzebujesz relacji częściowego porządku. Naturalnym kandydatem jest oczywiście \(\displaystyle{ a \le b \iff a | b}\).

[Kate2410]

Twierdzenie brzmi:
W skończonym zbiorze częściowo uporządkowanym minimalna liczba łańcuchów pokrywających zbiór jest równa maksymalnej liczebności antyłańcucha w tym zbiorze.

Czyli ustalamy relacje częściowego porządku tak jak mówisz, przy czym każda następna liczba musi dzielić się przez poprzednia tak ?
Nie wiem jak to powiązać z łańcuchami i antyłańcuchami, żeby skorzystać z twierdzenia.

[Gosda]

ciąg siedmiu (różnych) liczb, z których każda kolejna jest wielokrotnością poprzedniej

To jest definicja łańcucha.

trzy liczby, z których żadne dwie nie dzielą się przez siebie.

A to antyłańcucha

[Kate2410]

Ale jak pokazać, że minimalna liczba łańcuchów pokrywających będzie równa maksymalnej liczebności antyłańcucha . Nie widzę tego

[Gosda]

Ty tego nie dowodzisz - to jest twierdzenie Dilwortha - zakładasz, że jest prawdziwe (bo jest) i dzięki temu masz pokazać, że w Twoim zbiorze trzynastu liczb...

Podpowiedź: załóż nie wprost, że nie istnieje antyłańcuch o mocy trzy, co wtedy?

[Kate2410]

Wtedy na pewno istnieje para liczb , w której jedna jest wielokrotnością drugiej