Ćwiczenia 12: dobre ufundowanie

Zadania

1. Niech \(B \subseteq \mathbb{R}_{+}\). Udowodnić, że istnieje zbiór \(C \subseteq \mathbb{R}_{+}\) taki, że
   
   • \(\forall_{x,y \in C}(x\neq y \to | x - y | \in B\),
   • \(\forall_x (x\not \in C \to \exists y \in C | x - y | \not\in B\).
2. Czy zbiór \(\langle \mathbb{N}^*, \leq_{lex}\rangle\) jest dobrze ufundowany?
3. Czy zbiór \(\langle \mathbb{N}^2, \leq_{lex}\rangle\) jest dobrze ufundowany?
4. Podaj trzy przykłady zbiorów dobrze uporządkowanych mocy \(\aleph_0\) tak, aby żadne dwa nie były ze sobą izomorficzne.
5. Niech  \(\langle A, \leq \rangle\) będzie zbiorem dobrze uporządkowanym, w którym wszystkie antyłańcuchy są skończone. Niech \(\{a_i\}_{i\in \mathbb{N}}\) będzie dowolnym ciągiem elementów. Udowodnić, że istnieją i, j takie, że i<j i \(a_i \leq a_j\).

Praca domowa

Ostatnia praca domowa zostanie ogłoszona w poniedziałek po południu. Termin oddania: czwartek 23 stycznia 2014 r. Praca domowa zostanie zebrana na wykładzie.

Ćwiczenia 11: porządki cz. 2

Przypominam, że jutro o 16 w sali 4420 jest klasówka poprawkowa.

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{Q} - \{0\}\), \(\mathbb{R}\), \(\mathbb{R} - \{0\}\). Które z nich są izomorficzne?
2. 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ą?
3. Udowodnij, że \(\langle A \leadsto B, \leq \rangle\) jest częściowym porządkiem zupełnym.
4. Niech A będzie dowolnym zbiorem i niech \(B \subseteq A \times A\). Udowodnić, że istnieje maksymalny zbiór \(C \subseteq A\) taki, że \(C \times C \subseteq B\).

Praca domowa

Kolejna praca domowa pojawi się w poniedziałek po południu na stronie wykładu. Termin oddania: 20 stycznia 2014 r.

Ciekawe zadanie dodatkowe - dla chętnych

Udowodnić, że każdy porządek częściowy można rozszerzyć do porządku liniowego.

Ćwiczenia 10: porządki (niekoniecznie świąteczne)

Zadania

1. Które z następujących zbiorów są równoliczne:
   \[\mathbb{Q}\times\mathbb{Z},\mathbb{R}\times\mathbb{Q}, \mathbb{R}-\mathbb{Q}, 2^{\mathbb{N}}, 2^{\mathbb{R}}, P(\mathbb{Q}\times\mathbb{Z}), \bigcup_{n\in \mathbb{N}}\mathbb{N}^n ? \]
2. W zbiorze \(\{1,2,3,5,12,18,120,300\}\) uporządkowanym przez relację podzielności wskazać elementy minimalne, maksymalne, najmniejsze, największe. Czy istnieją w tym zbiorze trzyelementowe łańcuchy lub antyłańcuchy? Wskaż kres dolny zbioru \(\{5,12\}\) oraz kres górny zbioru \(\{3,12\}\).
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\}^{\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?
5. Czy zbiór \(\{01^n \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
6. Czy zbiór \(\{0^n1 \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
7. Czy relacja równoważności może być częściowym porządkiem?
8. Znaleźć moc zbioru wszystkich porządków częściowych w \(\mathbb{N}\).

Praca domowa

Praca domowa pojawi się w poniedziałek po południu na stronie wykładu. Termin oddania: 13.01.2014 r.

Życzę Państwu odpoczynku w czasie przerwy świątecznej. Nie zapomnijcie, że łańcuch to nie tylko ozdoba choinkowa :)

Wesołych Świąt! 
Szczęśliwego Nowego Roku 2014!

Więcej matematycznych choinek