Ćwiczenia 6: porządki cz. 1

Zadania

1.  Niech funkcja \(\varphi: P(\NN \times \NN) \to P(\NN \times \NN)\) będzie taka, że
   \[ \varphi(r) = \bigcap \{ r^n \mid n > 0 \}. \]
   Niech Z to rodzina relacji zwrotnych w \(\NN\). Znaleźć \(\varphi(Z)\).
2. (Utajnione) Zadanie z kartkówki.
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\}^{\NN}\) takie, że
   \[ 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 w nim antyłańcuch nieskończony?
   d) Czy ma element maksymalny, minimalny, najmniejszy, największy?
5. Czy zbiór \(\{01^n \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?
6. Czy zbiór \(\{0^n1 \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?

Warianty - do przemyślenia w domu dla chętnych

1. Zadanie 1 dla rodziny relacji przechodnich, symetrycznych, antysymetrycznych, ...
2. Zadanie 1: znaleźć \(\varphi^{-1}(Z)\).
3. Zadanie 4: jaki dostaniemy porządek, gdy utożsamimy ciągi zerojedynkowe z funkcjami charakterystycznymi podzbiorów liczb naturalnych?

Praca domowa

Zadania 351 i 353.