Ćwiczenia 8: porządki cz. 2

Zadania

1.  Udowodnić, że jeśli w porządku częściowym każdy dwuelementowy podzbiór ma kres górny, to każdy niepusty podzbiór ma kres górny.
2. Podać przykład zupełnego porządku częściowego, który nie jest kratą zupełną. (Wskazówka: takim porządkiem jest zbiór funkcji częściowych z relacją zgodności.)
3. 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\), że \(a \leq b\).

Praca domowa

Zadania 381 i 366 (bez pytania o bijekcję).

Dla chętnych: zadanie 386. Definicja: Krata - częściowy porządek, w którym każdy dwuelementowy podzbiór ma kres górny.

Ćwiczenia 7: porządki

Zadania

1. (Utajnione) Zadanie z kartkówki. 
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\}^{\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?
4. Czy zbiór \(\{01^n \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?
5. Czy zbiór \(\{0^n1 \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?

Praca domowa

Zadania 352 i 353 ze zbioru zadań.

Ćwiczenia 6: równoliczość i relacje

Zadania

1. Pokazać, że jeśli \(A \sim B\), to \(P(A) \times P(B) \sim \{0,1,2,3\}^A\).
2. Znaleźć przykład pięcioelementowej relacji na zbiorze liczb naturalnych, która jest
   a) przechodnia,
   b) symetryczna,
   c) zwrotna.
3. Niech \(r = \{ \langle A, B\rangle \in P(\NN) \times P(\NN) \mid A \subseteq B\}\) i \(s = \{ \langle A, B\rangle \in P(\NN) \times P(\NN) \mid A \cap B = \emptyset\}\).
   a) Czy \(r \cdot s  = s \cdot r\)?
   b) Czy \(r^{-1} = r\)?
   c) Czy \(s^{-1} = s\)?
4. Dla jakich relacji \(r \subseteq A \times A\) zachodzą równości \(r \cdot r^{-1} = r^{-1} \cdot r = id_{A}\)?

Praca domowa

Zadania 163 i 491 a,b,e ze zbioru zadań.

Ćwiczenia 5: funkcje

Zadania

1. Niech funkcja \(f : P(\NN) \to (\NN \to \NN) \) będzie taka, że
   \[f(S)(n) = max\{ x \in S \cup \{0\} \mid x \leq n \}.\]
   a) Czy f jest różnowartościowa?
   b) Czy f jest na \(\NN \to \NN\)?
   c) Udowodnić, że \(f(\NN)(\NN) = \NN\).
   d) Udowodnić, że dla dowolnego \(S \subseteq \NN\) zachodzi
   \[f(S)^{-1}(S) = \NN \hbox{ wtw. } 0 \in S\]
   e) Udowodnić, że \(f^{-1}(C) = \{\emptyset, \{0\}\}\), gdzie C to zbiór funkcji stałych.
2. Funkcję \(F : (\NN \to P(\NN)) \to P(\NN)\) jest określona warunkiem
   \[ F(x) = \bigcup \{x(i) \mid i \in \NN\}.\]
   a) Czy F jest różnowartościowa?
   b) Czy F jest na \(P(\NN)\)?
   c) Czy istnieje zbiór \(A \subseteq \NN\) taki, że \(F^{-1}(\{A\})\) jest jednoelementowy?
   d) Czy istnieje zbiór \(A \subseteq \NN\) taki, że \(F^{-1}(\{A\})\) jest czteroelementowy?
3. Podać przykład pary funkcji \(f,g : \NN \to \NN\) spełniających wszystkie poniższe warunki:
   a)\(\forall x( g(x) \neq x)\),
   b) \(g \circ g = id_{\NN}\),
   c) \(f \circ g = g\),
   d) \(f\) jest na \(\NN\),
   e) obrazem zbioru liczb parzystych przy przekształceniu g jest zbiór liczb nieparzystych.
4. Podać przykład pary funkcji \(f,g : \NN \to \NN\) spełniających wszystkie poniższe warunki:
   a)\(\forall x( g(x) \neq x)\),
   b) \(g \circ g = id_{\NN}\),
   c) \(f \circ g = f\),
   d) \(f\) jest na \(\NN\),
   e) obrazem zbioru liczb parzystych przy przekształceniu g jest zbiór liczb nieparzystych.
5.  Pokazać, że funkcja \(\varphi:P(A)^B \to P(A\times B)\) taka, że
   \[ \varphi(f) = \{\langle a,b\rangle \in A \times B \mid  a \in f(b)\} \]
   jest bijekcją.
6. Znaleźć przykład takiej funkcji \(f: \NN\to\NN\), że przeciwobraz każdego zbioru jednoelementowego jest
   a) jednoelementowy,
   b) dwuelementowy,
   c) nieskończony.

Praca domowa

Zadania 79 i 116 ze zbioru zadań.