Obliczyć moc zbioru

[Ropoocha]

Jakie są moce zbiorów:
a) \(\displaystyle{ A = \left \{ X\subset \mathbb{N}: \left | X \right | < \aleph_{0} \right \} }\)
b) \(\displaystyle{ B = \left \{ X\subset \mathbb{R}: \left | X \right | < \aleph_{0} \right \} }\)
c) \(\displaystyle{ C = \left \{ X\subset \mathbb{R}: \left | X \right | \leqslant \aleph_{0} \right \} }\)

Rozwiązałem przykład a) w następujący sposób:
\(\displaystyle{ A\subseteq P(\mathbb{N}) }\), a \(\displaystyle{ X\subset \mathbb{N} }\), więc \(\displaystyle{ \left | X \right | < \left | \mathbb{N} \right | = \aleph_{0} }\), czyli \(\displaystyle{ A = P(\mathbb{N}) }\) i stąd wiadomo, że \(\displaystyle{ \left | A \right | = \left | P(\mathbb{N}) \right | = \mathfrak{c} }\)

W przykładzie b) niestety zatrzymuję się w takim momencie:
\(\displaystyle{ B\subseteq P(\mathbb{R}) }\), a \(\displaystyle{ X\subset \mathbb{R} }\), więc \(\displaystyle{ \left | X \right | < \mathfrak{c} }\)

Nie wiem czy powinienem go rozwiązywać taką samą metodą jak przykład a), a jeśli tak to nie wiem jak, dlatego proszę o jakieś wskazówki.

[Jan Kraszewski]

Rozwiązałem przykład a) w następujący sposób:
\(\displaystyle{ A\subseteq P(\mathbb{N}) }\), a \(\displaystyle{ X\subset \mathbb{N} }\), więc \(\displaystyle{ \left | X \right | < \left | \mathbb{N} \right | = \aleph_{0} }\), czyli \(\displaystyle{ A = P(\mathbb{N}) }\) i stąd wiadomo, że \(\displaystyle{ \left | A \right | = \left | P(\mathbb{N}) \right | = \mathfrak{c} }\)

Przykro mi, ale to zupełnie nie ma sensu. To co napisałeś niestety wskazuje, że nie było to rozumowanie, tylko żonglowanie znaczkami - wyciągasz zupełnie niepoprawne wnioski. I powinieneś zauważyć, że stwierdzenie (które uczyniłeś), że wszystkie podzbiory liczb naturalnych są skończone jest błędne.

W przykładzie b) niestety zatrzymuję się w takim momencie:
\(\displaystyle{ B\subseteq P(\mathbb{R}) }\), a \(\displaystyle{ X\subset \mathbb{R} }\), więc \(\displaystyle{ \left | X \right | < \mathfrak{c} }\)

Jak wyżej.

Tych zadań nie da się tak zrobić, trzeba najpierw zrozumieć, co masz policzyć. W a) masz zbiór skończonych podzbiorów liczb naturalnych, w b) zbiór skończonych podzbiorów liczb rzeczywistych, a w c) zbiór (co najwyżej) przeliczalnych podzbiorów liczb rzeczywistych. I na wyznaczenie ich mocy trzeba mieć pomysł. Np. w a) masz

\(\displaystyle{ A= \bigcup_{n\in\NN}A_n,}\) gdzie \(\displaystyle{ A_n=\left\{ X\subset \mathbb{N}: \left | X \right | =n \right \} .}\)

JK

[Kordyt]

Nie rozumiem twoich wniosków z przykładu a)
Skąd wniosek, że jeśli rodzina podzbiorów zbioru liczb naturalnych i takich, że są zbiorami skończonymi jest równa rodzinie wszystkich podzbiorów zbioru liczb naturalnych ?
Przecież mamy też podzbiory liczb naturalnych które są zbiorami przeliczalnymi (mocy alef-zero), choćby zbiór liczb dodatnich podzielnych przez \(\displaystyle{ m\in\mathbb{N}}\), a to przeczy twojej równości.

[Ropoocha]

Dziękuję za wyjaśnienie i podpowiedź.
Rozumiem, że dzięki rozpisaniu zbioru \(\displaystyle{ A }\) na \(\displaystyle{ A = \bigcup _{n\in\mathbb{N}}A_{n}=\left \{ X \subset \mathbb{N}: \left | X \right | = 1 \right \} \cup \left \{ X \subset \mathbb{N}: \left | X \right | = 2 \right \} \cup \left \{ X \subset \mathbb{N}: \left | X \right | = 3 \right \} \cup \cdots }\)
widać, że jest to rodzina przeliczalnych zbiorów, a więc sam zbiór \(\displaystyle{ A }\) jest przeliczalny.
Jednak nie wiem jak z takiego rozpisania przejść do pokazania mocy tego zbioru.

[Jan Kraszewski]

Zgubiłeś jeszcze \(\displaystyle{ A_0.}\)

widać, że jest to rodzina przeliczalnych zbiorów, a więc sam zbiór \(\displaystyle{ A }\) jest przeliczalny.

Istotne jest pokazanie, że zbiory w tej sumie są przeliczalne i skorzystanie z twierdzenia o mocy przeliczalnej sumy zbiorów przeliczalnych.

Acha, może być wygodniej zdefiniować \(\displaystyle{ A_n}\) w ten sposób: \(\displaystyle{ A_n=\left\{ X\subset \mathbb{N}: \left | X \right | \le n \right \}}\).

JK

[Ropoocha]

Aby pokazać przeliczalność zbiorów \(\displaystyle{ A_{n} }\) powinienem znaleźć jakąś surjekcję z \(\displaystyle{ \mathbb{N} }\) w zbiór \(\displaystyle{ A_{n} }\), czy może pokazać, że są to zbiory skończone?

[Jan Kraszewski]

Naprawdę myślisz, że są to zbiory skończone? To nie rokuje dobrze na przyszłość...

Najprościej chyba znaleźć surjekcję z \(\displaystyle{ \NN^n}\) (o którym to zbiorze powinieneś wiedzieć, że jest przeliczalny) na \(\displaystyle{ A_n}\) (w tej drugiej wersji).

JK

[Ropoocha]

Dla wersji \(\displaystyle{ A_{n}=\left \{ X\subset\mathbb{N}: \left | X \right | = n \right \} }\) wymyśliłem taką surjekcję:
\(\displaystyle{ f_{n}: \mathbb{N}^{n} \rightarrow A_{n} }\),
\(\displaystyle{ f_{n}\underbrace{\left ( x,y,z,... \right )}_{n} = \underbrace{\left \{ x,y,z,... \right \}}_{n} }\)
\(\displaystyle{ f_{1}\left ( x \right ) = \left \{ x \right \} }\)
\(\displaystyle{ f_{2}\left ( x, y \right ) = \left \{ x, y \right \} }\)
\(\displaystyle{ \vdots\ itd.}\)

[Jan Kraszewski]

Dla wersji \(\displaystyle{ A_{n}=\left \{ X\subset\mathbb{N}: \left | X \right | = n \right \} }\) wymyśliłem taką surjekcję:
\(\displaystyle{ f_{n}: \mathbb{N}^{n} \rightarrow A_{n} }\),
\(\displaystyle{ f_{n}\underbrace{\left ( x,y,z,... \right )}_{n} = \underbrace{\left \{ x,y,z,... \right \}}_{n} }\)

No właśnie dla tej wersji zbioru \(\displaystyle{ A_n}\) jest źle - to nie jest poprawna definicja funkcji, bo wartości nie muszą być elementami zbioru \(\displaystyle{ A_n}\). Np. dla \(\displaystyle{ n=2}\) masz \(\displaystyle{ f(1,1)=\{1\}\notin A_2.}\)

JK

[Ropoocha]

Racja, oczywiście \(\displaystyle{ \left \{ x,x \right \} = \left \{ x \right \} }\), także trzeba użyć definicji \(\displaystyle{ A_{n}=\left \{ X\subset\mathbb{N}: \left | X \right | \leqslant n \right \} }\).
Czyli teraz jak już jest udowodnione, że elementy sumy są przeliczalne, to wiadomo że sam zbiór \(\displaystyle{ A }\) jest przeliczalny, jednak czy to już wystarcza, aby stwierdzić że \(\displaystyle{ \left | A \right | = \aleph_{0} }\)?

[Jan Kraszewski]

Po pierwsze, wypadałoby ustalić, której definicji terminu "przeliczalny" używasz. Po drugie, wypadałoby znać dokładną treść twierdzenia, które chcesz użyć.

JK

[Ropoocha]

Twierdzenie, którego tu używam, to że jeśli \(\displaystyle{ \left ( A_{n} \right )_{n\in\mathbb{N}} }\) jest rodziną zbiorów przeliczalnych, to \(\displaystyle{ \bigcup_{n\in\mathbb{N}}A_{n} }\) jest zbiorem przeliczalnym.
A jeśli chodzi o definicję przeliczalności, to zbiór \(\displaystyle{ A }\) nazywamy przeliczalnym jeśli \(\displaystyle{ A = \varnothing }\) lub istnieje surjekcja ze
zbioru \(\displaystyle{ \mathbb{N} }\) na zbiór \(\displaystyle{ A }\).
Oczywiście tutaj nie ma wprost surjekcji z \(\displaystyle{ \mathbb{N} }\) w \(\displaystyle{ A_{n} }\), jednak wiadomo, że jeśli \(\displaystyle{ X }\) jest zbiorem przeliczalnym i istnieje surjekcja ze zbioru \(\displaystyle{ X }\) na zbiór \(\displaystyle{ Y }\), to \(\displaystyle{ Y }\) jest również zbiorem przeliczalnym, a z pomocą tego można dojść z przeliczalności \(\displaystyle{ \mathbb{N} }\) do \(\displaystyle{ \mathbb{N}^{n} }\).

[Jan Kraszewski]

No dobrze, to korzystając z tych narzędzi istotnie pokażesz wyłącznie, że zbiór \(\displaystyle{ A}\) jest przeliczalny, czyli (u Ciebie) \(\displaystyle{ \left| A\right| \le\aleph_0.}\) Żeby pokazać, że \(\displaystyle{ \left| A\right| =\aleph_0}\) musisz uzasadnić nierówność \(\displaystyle{ \left| A\right| \ge\aleph_0}\) (najprościej: wskazując nieskończony podzbiór zbioru \(\displaystyle{ A}\)) i skorzystać z tw. Cantora-Bernsteina.

Oczywiście tutaj nie ma wprost surjekcji z \(\displaystyle{ \mathbb{N} }\) w \(\displaystyle{ A_{n} }\), jednak wiadomo, że jeśli \(\displaystyle{ X }\) jest zbiorem przeliczalnym i istnieje surjekcja ze zbioru \(\displaystyle{ X }\) na zbiór \(\displaystyle{ Y }\), to \(\displaystyle{ Y }\) jest również zbiorem przeliczalnym, a z pomocą tego można dojść z przeliczalności \(\displaystyle{ \mathbb{N} }\) do \(\displaystyle{ \mathbb{N}^{n} }\).

Nie jestem pewny, co masz na myśli, ale obawiam się, że nie to, co trzeba.

JK

[Ropoocha]

Więc ustalam zbiór \(\displaystyle{ K = \left \{ X \subset \mathbb{N}: X=\left \{ n \right \}\wedge n\in \mathbb{N} \right \} = \left \{ \left \{ 0 \right \}, \left \{ 1 \right \}, \left \{ 2 \right \}, ... \right \} }\)
Oczywiście tutaj bijekcja ze zbiorem liczb naturalnych jest trywialna, więc \(\displaystyle{ K }\) jest równoliczny z \(\displaystyle{ \mathbb{N} }\), czyli \(\displaystyle{ \left | K \right | = \aleph_{0} }\).
\(\displaystyle{ K \subseteq A }\), skąd \(\displaystyle{ \left | K \right | \leq \left | A \right | }\) i podstawiając \(\displaystyle{ \aleph_{0} \leq \left | A \right | }\).
Teraz połączmy obie nierówności \(\displaystyle{ \left | A \right | \leq \aleph_{0} }\) i \(\displaystyle{ \aleph_{0} \leq \left | A \right | }\).
Otrzymujemy: \(\displaystyle{ \aleph_{0} \leq \left | A \right | \leq \aleph_{0} }\), a więc z twierdzenia Cantora-Bernsteina mamy, że \(\displaystyle{ \left | A \right | = \aleph_{0} }\), co trzeba było policzyć.

[Jan Kraszewski]

Dobrze, poza tym, że zapis

\(\displaystyle{ K = \left \{ X \subset \mathbb{N}: X=\left \{ n \right \}\wedge n\in \mathbb{N} \right \}}\)

jest dość paskudny. Powinno być

\(\displaystyle{ K = \{ \{ n\}:n\in\NN \}}\)

lub ewentualnie

\(\displaystyle{ K = \left \{ X \subset \mathbb{N}: (\exists n\in \mathbb{N})\,X=\left \{ n \right \} \right \}}\).

JK