Liczba skończonych podzbiorów zbioru liczb naturalnych

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
MichalMozejko
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 18 cze 2021, o 10:43
Płeć: Mężczyzna
wiek: 36

Liczba skończonych podzbiorów zbioru liczb naturalnych

Post autor: MichalMozejko »

Jak w temacie? Ile jest skończonych podzbiorów zbioru liczb naturalnych?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Liczba skończonych podzbiorów zbioru liczb naturalnych

Post autor: Janusz Tracz »

Niech \(\displaystyle{ \mathsf{p}(\NN)}\) oznacza zbiór skończonych podzbiorów \(\displaystyle{ \NN}\). Istnieje różnowartościowa funkcja \(\displaystyle{ \phi:\mathsf{p}(\NN)\to\NN}\). Powiedzmy, że \(\displaystyle{ A\in \mathsf{p}(\NN)}\) niech \(\displaystyle{ \phi(A)= \prod_{k\in A}^{} p_k}\), gdzie \(\displaystyle{ p_k}\) jest \(\displaystyle{ k}\)-tą liczbą pierwszą. Różnowartościowość \(\displaystyle{ \phi}\) wynika z jednoznaczności rozkładu. Wszak jeśli \(\displaystyle{ A \neq B}\) dla pewnych \(\displaystyle{ A,B\in \mathsf{p}(\NN)}\) to w iloczynach \(\displaystyle{ \prod_{k\in A}^{} p_k, \prod_{k\in B}^{} p_k}\) wystąpią inne liczby pierwsze, a zatem \(\displaystyle{ \prod_{k\in A}^{} p_k \neq \prod_{k\in B}^{} p_k}\) czyli \(\displaystyle{ \phi(A) \neq \phi(B)}\). Udało się więc zanurzyć \(\displaystyle{ \mathsf{p}(\NN)}\) w \(\displaystyle{ \NN}\) zatem \(\displaystyle{ \left| \mathsf{p}(\NN)\right|<\left| \NN\right|=\aleph_0 }\). Z drugiej strony oczywiście zbiór wszystkich singletonów jest podzbiorem \(\displaystyle{ \mathsf{p}(\NN)}\) więc oszacowanie dolne to też \(\displaystyle{ \aleph_0}\). Więc \(\displaystyle{ \left| \mathsf{p}(\NN)\right|=\aleph_0}\).
MichalMozejko
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 18 cze 2021, o 10:43
Płeć: Mężczyzna
wiek: 36

Re: Liczba skończonych podzbiorów zbioru liczb naturalnych

Post autor: MichalMozejko »

To moje drugie pytanie:
Mamy zbiór (oznaczmy go przez \(\displaystyle{ P_{s}}\)) \(\displaystyle{ P_{s} \subset P(\mathbb{N})}\) skończonych podzbiorów zbioru liczb naturalnych, dla każdego elementu tego zbioru istnieje dokładnie jeden nieskończony podzbiór zbioru liczb naturalnych np.:
\(\displaystyle{ p=\{1,2,3\} \in P_{s} }\)
\(\displaystyle{ x=\mathbb{N}-p=\{4,5,6,7,...\} ,\ x \in P(\mathbb{N})}\)

co by sugerowało że x-ów jest też \(\displaystyle{ \aleph_{0}}\)

Gdzieś popełniam błąd?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Liczba skończonych podzbiorów zbioru liczb naturalnych

Post autor: Janusz Tracz »

MichalMozejko pisze: 28 lip 2021, o 17:44 Gdzieś popełniam błąd?
Wszystko jest ok. Zbiór \(\displaystyle{ x}\)-ów też ma moc \(\displaystyle{ \aleph_0}\).
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Liczba skończonych podzbiorów zbioru liczb naturalnych

Post autor: Jakub Gurak »

Dopełnienie zbioru nieskończonego do zbioru liczb naturalnych może być nieskończone- rozważ zbiór liczb parzystych.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Liczba skończonych podzbiorów zbioru liczb naturalnych

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 28 lip 2021, o 17:59 Dopełnienie zbioru nieskończonego do zbioru liczb naturalnych może być nieskończone- rozważ zbiór liczb parzystych.
A co to ma do rzeczy?

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Liczba skończonych podzbiorów zbioru liczb naturalnych

Post autor: Jakub Gurak »

To pokazuje różnicę między skończonymi podzbiorami zbioru liczb naturalnych, a nieskończonymi podzbiorami, o co, przynajmniej tak przeczuwałem, chodziło autorowi. Gdyż:

Dopełnienie skończonego podzbioru zbioru liczb naturalnych jest zawsze nieskończone, a dopełnienie nieskończonego podzbioru może być nieskończone, czyli nie musi być skończone.

:lol:
krl
Użytkownik
Użytkownik
Posty: 609
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 135 razy

Re: Liczba skończonych podzbiorów zbioru liczb naturalnych

Post autor: krl »

Jan Kraszewski pisze: 28 lip 2021, o 18:53
Jakub Gurak pisze: 28 lip 2021, o 17:59 Dopełnienie zbioru nieskończonego do zbioru liczb naturalnych może być nieskończone- rozważ zbiór liczb parzystych.
A co to ma do rzeczy?
Wcześniej MichałMozejko zastanawiał się nad rodziną zbiorów \(\displaystyle{ A=\{\mathbb{N}\setminus P:P\subseteq\mathbb{N}}\) skończony\(\displaystyle{ \}}\) i był zaskoczony, że rodzina \(\displaystyle{ A}\) jest przeliczalna. Gdyby każdy nieskończony podzbiór \(\displaystyle{ \mathbb{N}}\) należał do \(\displaystyle{ A}\), to byłby problem (bo nieskończonych podzbiorów \(\displaystyle{ \mathbb{N}}\) jest nieprzeliczalnie wiele). Uwaga Jakuba Guraka wskazuje, że nie każdy nieskończony podzbiór \(\displaystyle{ \mathbb{N}}\) należy do \(\displaystyle{ A}\).
ODPOWIEDZ