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