Pokazywanie postów oznaczonych etykietą porządki. Pokaż wszystkie posty
Pokazywanie postów oznaczonych etykietą porządki. Pokaż wszystkie posty

4 grudnia 2017

Ćwiczenia 10: powtórzenie przed klasówką

Zadania

  1. Czy zbiór \(\{0^n1 \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?
  2. Udowodnić, że nie istnieje słowo w takie, że \(a \cdot w = w \cdot b\).
  3. Zdefiniować na listach operację dopisania liczby n na końcu listy.
  4. 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?
  5. Podać przykład funkcji \(f : \NN \to \NN\) i zbioru \(X \subseteq \NN\), aby funkcja \(g:\NN\to P(\NN)\) określona wzorem:
    \[ g(i) = (f^i)^{-1}(X)\]
    była różnowartościowa.

Ze względu na klasówkę w tym tygodniu nie ma pracy domowej.

27 listopada 2017

Ćwiczenia 9: porządki cz. 3

Zadania

  1. Niech funkcja \(f: P(\NN \times \NN) \to P(\NN \times \NN)\) będzie określona tak:
    \[ f(s) = s \cdot s.
    \]
    Udowodnić, że f jest ciągła ze względu na uporządkowanie przez inkluzję, tj.
    \[ f(\bigcup X) = \bigcup f(X) \]
    dla dowolnej skierowanej rodziny relacji \(X \subseteq P(\NN\times\NN)\).
  2. 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\). 
  3. W zbiorze funkcji \(\NN \to \{2,3\}\) dany jest następujący porządek częściowy:
    \[ f \leq g \hbox{ wtw. } f^{-1}(\{2\}) \subseteq g^{-1}(\{2\}). \]
    Czy ten porządek:
    a) jest liniowy?
    b) ma elementy minimalne, maksymalne, najmniejsze, największe?
    c) jest kratą zupełną?

Praca domowa

Zadania 406 abdc i 487.

20 listopada 2017

Ćwiczenia 8: porządki cz. 2

Zadania

  1.  Niech \(A = \{ 3 - \frac{1}{2n} \mid n \in \mathbb{N} - \{0\}\}\),
    \(B = \{ \pi - \frac{2}{n} \mid n \in \mathbb{N} - \{0\}\} \cup \{4\}\),
    \(C = \{0\} \cup \{ \frac{1}{n} \mid n \in \mathbb{N} - \{0\}\} \cup \{ 2 - \frac{1}{n} \mid n \in \mathbb{N} - \{0\}\}\).
    Rozpatrzmy zbiory A, B, C, \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\),  \(\mathbb{R}\). Które z nich są izomorficzne? 
  2. Rozpatrzmy porządek częściowy \(\langle P(\NN)^{\NN}, \leq \rangle\), gdzie
    \[ f \leq g \hbox{ wtw. } \forall n(f(n) \subseteq g(n)). \]
    a) Wskazać elementy najmniejsze, największe, minimalne, maksymalne.
    b) Czy ten porządek jest liniowy?
    c) Czy ten porządek jest kratą zupełną.
  3. Podać przykład częściowego porządku zupełnego, który nie jest kratą zupełną. (Odpowiedź: funkcje częściowe z porządkiem rozszerzania.)
  4. Niech \(r\) będzie częściowym porządkiem w A i niech \(f : A \to A\) będzie bijekcją. Rozpatrzmy funkcję \(g: A \times A \to A \times A\):
    \[ g(x,y) = \langle f(x), f(y) \rangle. \]
    Udowodnić, że \(g(r) \subseteq r\) wtedy i tylko wtedy, gdy f jest monotoniczna.

Praca domowa

Zadania 364 i 399 a,c,d.

13 listopada 2017

Ć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\}^{*}\) uporządkowanym leksykograficznie?

Praca domowa

Zadanie 358 ze zbioru zadań.

Uwaga: Relacja \(r \subseteq A \times A\) jest przeciwzrotna wtedy i tylko wtedy, gdy \(\forall x \in A (\langle a, a\rangle \not\in r)\) .