Ćwiczenia 8: moce cz. 1

Zadania

1. Pokazać, że \( (A^B)^C \sim A^{B \times C}\).
2. Znaleźć moc zbioru skończonych podzbiorów \(\NN\).
3. Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
4. Znaleźć moc zbioru funkcji z \(\NN\) do \(\NN\).
5. Znaleźć moc zbioru funkcji niemalejących z \(\NN\) do \(\NN\).

Praca domowa

Zadania 262 i 327.

Ćwiczenia 7: porządki cz. 2

Zadania

1. Rozważmy częściowy porządek \(\langle A \leadsto B, \leq \rangle\), gdzie \(A \leadsto B\) to zbiór funkcji częściowych z A do B i \(f \leq g\), wtedy i tylko wtedy, gdy dla każdego \(a \in A\) albo \(f(a)\) jest nieokreślone, albo obie funkcje są określone i \(f(a) = g(a)\). Czy \(\langle A \leadsto B, \leq \rangle\) jest kratą zupełną?
2. Udowodnij, że \(\langle A \leadsto B, \leq \rangle\) jest częściowym porządkiem zupełnym.
3. Niech A i B będą zbiorami częściowo uporządkowanymi i niech funkcje \(f : A \to B\) i \(g : B \to A\) będą monotoniczne. Udowodnić, że następujące warunki są równoważne:
   a) \(\forall a \in A \forall b \in B (a \leq g(b) \leftrightarrow f(a) \leq b  )\)
   b) \(\forall a \in A (a \leq g(f(a))) \wedge \forall b \in B (f(g(b)) \leq b)\).
4. Podaj przykład takiego przekształcenia monotonicznego f w kracie \(\langle P(\mathbb{N}), \subseteq \rangle\), że kres górny zbioru \( \{ f^n(\emptyset) \mid  n \in \mathbb{N}\} \) nie jest najmniejszym punktem stałym.
   Czy można wybrać f tak, aby punkt stały f nie istniał?
5. Niech A będzie częściowym porządkiem zupełnym i niech \(f : A \to A\) będzie ciągła. Udowodnić, że jeśli \(a \leq f(a)\), to istnieje taki punkt stały b funkcji f, że \(a \leq b\).

Praca domowa

Zadania 355 i 348 (pytanie o bijekcję tylko dla chętnych).

Ć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.

Ćwiczenia 5: relacje

Zadania

1. Czy dla każdego A i dla każdej relacji \(r \subseteq A \times A\) zachodzi
   a) \(r^{-1} \cdot r \subseteq I_A\),
   b) \(I_A \subseteq r^{-1} \cdot r\)?
2. Niech \(R, S \subseteq A \times A\). Czy z tego, że \( R \cdot S = S \cdot R\) wynika, że \(R = S\) lub \(R = I_A\), lub \(S = I_A\)?
3. Podać przykład pięcioelementowej relacji na zbiorze liczb naturalnych, która jest
   a) symetryczna,
   b) przechodnia,
   c) zwrotna.
4. Niech \(\mathcal{R}\) będzie taką niepustą rodziną relacji przechodnich w zbiorze \(A\), że dla dowolnych \(r, s\in \mathcal{R}\) zachodzi \(r \subseteq s\) lub  \(s \subseteq r\). Udowodnić, że \(\bigcup  \mathcal{R}\) jest relacją przechodnią.
5. Niech \(\varphi : \NN \to P(\NN \times \NN)\) będzie zdefiniowana tak:
   \[ \varphi(n) = \{\langle x, n\rangle \mid x \leq n\} \cup \{\langle n, y\rangle \mid n \leq y\}.\]
   a) Znaleźć \(\varphi^{-1}(\mathcal{T})\), gdzie \(\mathcal{T}\) to rodzina relacji przechodnich w \(\NN\).
   b) Czy \(\bigcup \varphi(\NN)\) jest relacją przechodnią w \(\NN\)?
6. Niech funkcja \(\varphi :  P(\NN \times \NN)\) będzie określona tak:
   \[ \varphi(r) = \bigcap \{ r^n \mid n > 0\}.\]
   a) Czy \(\varphi\) jest różnowartościowa?
   b) Niech \(\mathcal{Z}\) oznacza rodzinę wszystkich relacji zwrotnych w \(\NN\). Znaleźć \(\varphi(\NN)\).

Praca domowa

Zadanie 474 a, b, e oraz zadanie 71.