Pewny częściowy porządek i jego szerokość
: 14 wrz 2023, o 21:17
Przez \(\displaystyle{ \#X}\) oznaczę liczbę elementów zbioru \(\displaystyle{ X}\). Rozpatrujemy zbiór \(\displaystyle{ Y}\) złożony z niepustych podzbiorów zbioru \(\displaystyle{ \{1, 2, 3,..., 98, 99\}}\) - to znaczy wszystkich liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ 99}\). W zbiorze \(\displaystyle{ Y}\) mamy relację częściowego porządku określoną tak
\(\displaystyle{ A<B \Leftrightarrow ( A= B \lor \#B = 99 \lor ( A \subseteq B \land \#(B \setminus A) \ge 3 ) )}\)
a) Wyznacz długość tego zbioru częściowo uporządkowanego
Wyszukaj
b) Wykaż, że szerokość tego zbioru jest większa niż \(\displaystyle{ 5000}\). Wskazówka: buduj największy antyłańcuch, jaki potrafisz - na pewno uda ci się przekroczyć \(\displaystyle{ 5000}\). Obliczenia nie są kłopotliwe, jeżeli posłużysz się np. Wolframem.
c) Wykaz, że elementów minimalnych jest dokładnie \(\displaystyle{ 161799}\). Czy jest najmniejszy, największy ?
d) Wyznacz kres dolny i kres górny pary \(\displaystyle{ \{2, 3, 4, 5\}, \{4, 5, 6, 7\}}\) lub wykaż, że tych kresów nie ma.
e) trudne. Wyznacz rozmiar największego antyłańcucha
Mam problem z punktem e)
\(\displaystyle{ A<B \Leftrightarrow ( A= B \lor \#B = 99 \lor ( A \subseteq B \land \#(B \setminus A) \ge 3 ) )}\)
a) Wyznacz długość tego zbioru częściowo uporządkowanego
Wyszukaj
b) Wykaż, że szerokość tego zbioru jest większa niż \(\displaystyle{ 5000}\). Wskazówka: buduj największy antyłańcuch, jaki potrafisz - na pewno uda ci się przekroczyć \(\displaystyle{ 5000}\). Obliczenia nie są kłopotliwe, jeżeli posłużysz się np. Wolframem.
c) Wykaz, że elementów minimalnych jest dokładnie \(\displaystyle{ 161799}\). Czy jest najmniejszy, największy ?
d) Wyznacz kres dolny i kres górny pary \(\displaystyle{ \{2, 3, 4, 5\}, \{4, 5, 6, 7\}}\) lub wykaż, że tych kresów nie ma.
e) trudne. Wyznacz rozmiar największego antyłańcucha
Mam problem z punktem e)