Zbiór przeliczalny

[max123321]

Rozstrzygnij, który zbiór jest przeliczalny
a) \(\displaystyle{ \left\{ -1,1\right\}^\NN }\)
b) \(\displaystyle{ \NN^\NN}\)
c) \(\displaystyle{ P(\NN_+)}\)
d) \(\displaystyle{ (0,1) \cap \QQ_+}\)
e) \(\displaystyle{ \QQ \setminus (0,1)}\)
f) zbiór wszystkich ciągów geometrycznych o wyrazach całkowitych ujemnych.

No to przeliczalne są d) e) f). Czy można to jakoś łatwo uzasadnić bez wskazywania odpowiedniej bijekcji?

[Jan Kraszewski]

No to przeliczalne są d) e) f). Czy można to jakoś łatwo uzasadnić bez wskazywania odpowiedniej bijekcji?

Oczywiście - d) i e) prosto idą z Cantora-Bernsteina.

Jeśli chodzi o f), każdy ciąg geometryczny jest jednoznacznie wyznaczony przez pierwszy wyraz i iloraz, więc o bijekcję nietrudno.

JK

[max123321]

A jak to d) zrobić z Cantora-Bernsteina? Powinienem pokazać, że zbiór liczb naturalnych jest równoliczny z jakimś podzbiorem zbioru \(\displaystyle{ (0,1) \cap \QQ_+}\) i jakiś podzbiór \(\displaystyle{ (0,1) \cap \QQ_+}\) jest równoliczny ze zbiorem liczb naturalnych? Jak to zrobić? Może jakaś wskazówka?

[Hir]

Wskazówka: \(\displaystyle{ \{\frac 1{n+1} : n \in \mathbb N_+\} \subseteq (0, 1) \cap \mathbb Q_+ \subseteq \mathbb Q}\).

[max123321]

Aha to chyba korzystasz z tego lematu co jest na wikipedii, to jest chyba wniosek z twierdzenia Cantora-Bernsteina, że jak \(\displaystyle{ C \subseteq B \subseteq A}\) i \(\displaystyle{ |A|=|C|}\), to \(\displaystyle{ |A|=|B|}\).

Zbiór \(\displaystyle{ \{\frac 1{n+1} : n \in \mathbb N_+\}}\) jest mocy alef zero i zbiór \(\displaystyle{ \QQ}\) jest mocy alef zero, zatem zbiór \(\displaystyle{ (0, 1) \cap \mathbb Q_+}\) też jest mocy alef zero.

O to chodzi?

Dodano po 28 minutach 16 sekundach:
No ok, a jak uzasadnić, że \(\displaystyle{ \left\{ -1,1\right\}^\NN}\) nie jest przeliczalny?

[Jan Kraszewski]

Zbiór \(\displaystyle{ \{\frac 1{n+1} : n \in \mathbb N_+\}}\) jest mocy alef zero i zbiór \(\displaystyle{ \QQ}\) jest mocy alef zero, zatem zbiór \(\displaystyle{ (0, 1) \cap \mathbb Q_+}\) też jest mocy alef zero.

O to chodzi?

Tak, choć w zasadzie powinieneś jeszcze szybko uzasadnić, że \(\displaystyle{ \left| \left\{ \frac 1{n+1} : n \in \NN_+\right\}\right| =\aleph_0.}\)

No ok, a jak uzasadnić, że \(\displaystyle{ \left\{ -1,1\right\}^\NN}\) nie jest przeliczalny?

To zależy, z czego możesz korzystać. Zawsze można bezpośrednio zrobić rozumowanie przekątniowe, ale prościej skorzystać z wiedzy o tym, że inne zbiory są mocy continuum.

JK

[max123321]

Ok to uzasadnienie, że \(\displaystyle{ \left| \left\{ \frac 1{n+1} : n \in \NN_+\right\}\right| =\aleph_0}\), to można powiedzieć, że istnieje bijekcja \(\displaystyle{ f:\NN_+ \rightarrow \left\{ \frac 1{n+1} : n \in \NN_+\right\}: f(n)=\frac 1{n+1}}\) i chyba to wystarczy?


Ok, a jak uzasadnić, że \(\displaystyle{ \left\{ -1,1\right\}^\NN}\) korzystając z wiedzy o tym, że inne zbiory są mocy continuum?

[Janusz Tracz]

Bo \(\displaystyle{ \left\{ -1,1\right\}^\NN}\) to jest to samo co \(\displaystyle{ \left\{ 0,1\right\}^\NN}\) i jest to w zasadzie to samo co zbiór Cantora, który jest nieprzeliczalny. Jeśli nie można korzystać ze zbioru Cantora to można każdą liczbę \(\displaystyle{ \left[ 0,1\right] }\) rozwinąć w systemie dwójkowym. Co prawda nie jest to różnowartościowe przypisanie ale nie różnowartościowość objawi się jedynie \(\displaystyle{ \aleph_0}\) razy bowiem dla liczb zakończonych od pewnego miejsca jedynką lub zerem (ciągi skończone). Jednak już wiesz, że usunięcie ze zbioru mocy \(\displaystyle{ \mathfrak{c}}\) zbioru mocy \(\displaystyle{ \aleph_0}\) nie zmieni mocy (a).

[Jakub Gurak]

Ok to uzasadnienie, że \(\displaystyle{ \left| \left\{ \frac 1{n+1} : n \in \NN_+\right\}\right| =\aleph_0}\), to można powiedzieć, że istnieje bijekcja \(\displaystyle{ f:\NN_+ \rightarrow \left\{ \frac 1{n+1} : n \in \NN_+\right\}: f(n)=\frac 1{n+1}}\) i chyba to wystarczy

Taka funkcja jest silnie malejąca, a zatem jest różnowartościowa, i oczywiście jest to funkcja 'na'. A zatem jest ona bijekcją, i zbiór takich odwrotnści liczb naturalnych jest równoliczny ze zbiorem liczb naturalnych, jest to więc zbiór nieskończony. A zatem zbiór \(\displaystyle{ \left( 0,1\right) \cap \QQ _{+}, }\) jako nieskończony podzbiór przeliczalnego zbioru liczb wymiernych, jest przeliczalny.

Dodano po 17 minutach 48 sekundach:
e) Wskazówka:
\(\displaystyle{ \QQ \setminus \left( 0,1\right)\supset \ZZ _{-}\sim\NN _{+}\sim\NN.}\)
(\(\displaystyle{ \ZZ _{-} }\) oznacza zbiór liczb całkowitych ujemnych).

[Jan Kraszewski]

e) Wskazówka:
\(\displaystyle{ \QQ \setminus \left( 0,1\right)\supset \ZZ _{-}\sim\NN _{+}\sim\NN.}\)
(\(\displaystyle{ \ZZ _{-} }\) oznacza zbiór liczb całkowitych ujemnych).

Dziwna ta wskazówka, skoro \(\displaystyle{ \QQ \setminus \left( 0,1\right)\supseteq \NN .}\)

JK

[Jakub Gurak]

Pomyliłem się tutaj wyrzucając końce \(\displaystyle{ 0}\) I \(\displaystyle{ 1}\) takiego przedziału otwartego że zbioru liczb wymiernych...