Ćwiczenia 6: porządki

Zadania

1. W zbiorze \(\{1,2,3,5,12,15,18,180\}\) uporządkowanym przez relację podzielności wskazać elementy minimalne, maksymalne, najmniejsze, największe. Czy istnieją w tym zbiorze pięcioelementowe łańcuchy? a trzyelementowe antyłańcuchy? Wskaż kres dolny zbioru \(\{3,12\}\) oraz kres górny zbioru \(\{2,5\}\).
2. 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.
3. 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?
4. Czy zbiór \(\{01^n \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
5. Czy zbiór \(\{0^n1 \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
6. Dany jest następujący częściowy porządek w zbiorze \(P(\mathbb{N} - \{\emptyset\}\):
   \[X \leq Y \hbox{wtw.} ((\min(X) < \min(Y))
   \vee (\min(X) = \min(Y) \wedge X \subseteq Y).\]
   a) Czy ten porządek jest liniowy?
   b) Czy istnieje w tym zbiorze nieskończony ciąg malejący?
   c) Wskaż elementy minimalne, maksymalne, największe, najmniejsze.

 Praca domowa

1. Jeśli \(\leq\) jest cześciowym porządkiem w A, to relację < nazywamy ostrym uporządkowaniem wyznaczonym przez \(\leq\). Pokazać, że ostre uporządkowania wyznaczone przez porządki częściowe to dokładnie te relacje, które są przechodnie i przeciwzrotne.
2. Niech \(\langle X, r \rangle, \langle Y, s \rangle \) będą niepustymi zbiorami częściowo uporządkowanymi. Pokazać, że
   a) \(\langle X \oplus Y, r \oplus s \rangle \) jest zbiorem częściowo uporządkowanym bez elementu największego.
   b) Dla dowolnego \(a \in X \oplus Y\) element a jest minimalny w \(\langle X \oplus Y, r \oplus s \rangle \) wtedy i tylko wtedy, gdy a jest elementem minimalnym w \(\langle X, r \rangle\) lub \(\langle Y, s \rangle \).