Ć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

Ćwiczenia 9: moce cz. 2

Zadania

1. Jaka jest moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca?
2. Znaleźć moc zbioru \(\mathbb{R}^{\mathbb{Q}}\).
3. Pokazać, że \((A^{B})^C \sim A^{B \times C}\).
4. Znaleźć moc zbioru wszystkich bijekcji z \(\mathbb{N}\) do \(\mathbb{N}\).
5. Niech r będzie taką relacją w zbiorze  \(\mathbb{Q}^{\mathbb{N}}\), że \(\langle f,g \rangle \in r\) wtedy i tylko wtedy, gdy różnica f - g jest zbieżna do zera. Znaleźć moc zbioru ilorazowego i moce klas abstrakcji relacji r.

Praca domowa

Kolejna praca domowa zostanie opublikowana w poniedziałek po południu na stronie wykładu. Termin oddania: 16 grudnia 2013 r.

Ćwiczenia 8: moce

Przypominam, że w tym tygodniu, w czwartek na wykładzie, jest klasówka.

Twierdzenie Cantora-Bernsteina

Jeśli \(\overline{\overline{A}} \leq \overline{\overline{B}}\) i \(\overline{\overline{B}} \leq \overline{\overline{A}}\), to \(\overline{\overline{A}} = \overline{\overline{B}}\).

W praktyce: szukamy mocy zbioru C.

1. Znajdujemy dwa (być może różne) zbiory A, B takie, że \(\overline{\overline{A}} = \overline{\overline{B}}\). 
2. Znajdujemy dwie funkcje różnowartościowe \(f : A \to C\) i \(g: C \to B\).
3. Twierdzenie Cantora-Bernsteina mówi, że \(\overline{\overline{C}} = \overline{\overline{A}}= \overline{\overline{B}}\).

Wskazówka: dobrze jest zacząć od znalezienia typu zbioru C. Typ zbioru C daje nam zawsze ograniczenie górne na moc zbioru C.
Przykład: Znaleźć moc zbioru C wszystkich relacji w \(\mathbb{N}\), które ...
Rozwiązanie: Zbiór wszystkich relacji w \(\mathbb{N}\) to \(P(\mathbb{N}\times\mathbb{N})\). Zatem \(C \subseteq P(\mathbb{N}\times\mathbb{N})\), a stąd dostajemy:
\[\overline{\overline{C}} \leq \overline{\overline{P(\mathbb{N}\times\mathbb{N})}} = \mathfrak{C}\]
I już wiemy, że moc zbioru C nie może być równa np. \(2^{\mathbb{\mathfrak{C}}}\).

Zadania

1. Znaleźć moc zbioru funkcji z \(\mathbb{N}\) do \(\mathbb{N}\).
2. Znaleźć moc zbioru funkcji niemalejących z \(\mathbb{N}\) do \(\mathbb{N}\).
3. Znaleźć moc zbioru funkcji nierosnących z \(\mathbb{N}\) do \(\mathbb{N}\).
4. Znaleźć moc zbioru wszystkich relacji równoważności w \(\mathbb{N}\).
5. Znaleźć moc zbioru Cantora. Zbiór Cantora to przecięcie ciągu zbiorów:
   \(C_0 = (0,1)\),
   \(C_1 = (0,\frac{1}{3}) \cup (\frac{2}{3},1)\),
   \(C_2= (0,\frac{1}{9}) \cup (\frac{2}{9},\frac{1}{3}) \cup (\frac{2}{3},\frac{8}{9}) \cup (\frac{8}{9},1)\),
   ...
   \(C = \bigcap_{n\in \mathbb{N}}C_n\).
 

Zadanie do przemyślenia

Zadanie dla osób, które po przygotowaniu do klasówki będą się nudzić:

1. Znaleźć moc zbioru wszystkich funkcji ciągłych z \(\mathbb{R}\) do \(\mathbb{R}\).

W tym tygodniu nie ma pracy domowej.