poniedziałek, 16 grudnia 2013

Ćwiczenia 10: porządki (niekoniecznie świąteczne)

Zadania

  1. Które z następujących zbiorów są równoliczne:
    \[\mathbb{Q}\times\mathbb{Z},\mathbb{R}\times\mathbb{Q}, \mathbb{R}-\mathbb{Q}, 2^{\mathbb{N}}, 2^{\mathbb{R}}, P(\mathbb{Q}\times\mathbb{Z}), \bigcup_{n\in \mathbb{N}}\mathbb{N}^n ? \]
  2. W zbiorze \(\{1,2,3,5,12,18,120,300\}\) uporządkowanym przez relację podzielności wskazać elementy minimalne, maksymalne, najmniejsze, największe. Czy istnieją w tym zbiorze trzyelementowe łańcuchy lub antyłańcuchy? Wskaż kres dolny zbioru \(\{5,12\}\) oraz kres górny zbioru \(\{3,12\}\).
  3. Podać przykład zbioru częściowo uporządkowanego z dwoma elementami maksymalnymi, jednym minimalnym, bez elementu najmniejszego i z takim czteroelementowym antyłańcuchem, który jest ograniczony z góry, ale nie ma kresu górnego.
  4. Rozpatrzmy częściowe uporządkowanie zbioru \(\{0,1\}^{\mathbb{N}}\):
    \[ f \leq g \hbox{ wtw. } \forall_x f(x) \leq g(x)\]
    a) Czy ten porządek jest liniowy?
    b) Czy istnieje w nim łańcuch nieskończony?
    c) Czy istnieje antyłańcuch nieskończony?
    d) Czy ma element największy, najmniejszy, minimalny, maksymalny?
  5. Czy zbiór \(\{01^n \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
  6. Czy zbiór \(\{0^n1 \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
  7. Czy relacja równoważności może być częściowym porządkiem?
  8. Znaleźć moc zbioru wszystkich porządków częściowych w \(\mathbb{N}\).

Praca domowa

Praca domowa pojawi się w poniedziałek po południu na stronie wykładu. Termin oddania: 13.01.2014 r.

Życzę Państwu odpoczynku w czasie przerwy świątecznej. Nie zapomnijcie, że łańcuch to nie tylko ozdoba choinkowa :)

Wesołych Świąt! 
Szczęśliwego Nowego Roku 2014!



Brak komentarzy:

Prześlij komentarz