Przeliczalność zbiorów

[dachowiec]

Borykam się z zadaniem do którego posiadam odpowiedź z klucza, jednak nie potrafię zinterpretować odpowiedzi.

Wskaż zbiory przeliczalne:
a) zbiór wszystkich skończonych zbiorów ciągów ternarnych
b) zbiór potęgowy zbioru \(\displaystyle{ \{-4, 0, 3, 2\}}\)
c) zbiór wszystkich podzbiorów zbioru liczb całkowitych \(\displaystyle{ \ZZ}\)

Rozwiązanie z klucza to wyłącznie odpowiedź a).
Jednak ja bym zaznaczył a) oraz b), ale być może nie doszukałem się wystarczająco informacji na temat zbiorów potęgowych. Czy jest szansa na uzyskanie uzasadnienia czemu zbiór potęgowy podanego zbioru jest nieprzeliczalny? Osobiście rozważam to jako zbiór \(\displaystyle{ 2^{4}}\) elementów co sprawia wrażenie przeliczalnego.

[Premislav]

Ciocia Wiki wyjaśnia sprawę jak Korwin lewaków i samego siebie:

Istnieją dwie nierównoważne konwencje użycia terminu zbiór przeliczalny w matematyce:

* zbiór przeliczalny to zbiór skończony lub zbiór równoliczny ze zbiorem liczb naturalnych (tzn. taki zbiór, że istnieje funkcja wzajemnie jednoznaczna między nim a zbiorem liczb naturalnych. Zbiór równoliczny ze zbiorem liczb naturalnych jest zbiorem nieskończonym).
* zbiór przeliczalny to zbiór równoliczny ze zbiorem liczb naturalnych (definicja ta wyklucza możliwość bycia zbiorem skończonym ponieważ nie istnieje funkcja różnowartościowa określona w zbiorze liczb naturalnych o wartościach w zbiorze skończonym). W przypadku tej konwencji zbiory przeliczalne według pierwszej definicji nazywa się zbiorami co najwyżej przeliczalnymi.

Widocznie autorzy klucza przyjęli tę drugą konwencję.

[Jakub Gurak]

Czy jest szansa na uzyskanie uzasadnienia czemu zbiór potęgowy podanego zbioru jest
nieprzeliczalny? Osobiście rozważam to jako zbiór \(\displaystyle{ 2^{4}}\) elementów co sprawia wrażenie przeliczalnego.

Oj nie, on na pewno nie jest nieprzeliczalny, on jest skończony. Zbiór jest nieprzeliczalny gdy jest większy niż przeliczalny.

I taki jest zbiór z podpunktu c. Mamy \(\displaystyle{ P\left( \ZZ\right)\sim P\left( \NN\right),}\) bo \(\displaystyle{ \NN\sim\ZZ}\), i oczywiście \(\displaystyle{ \left| P\left( \NN\right) \right| >\left| \NN\right|,}\) czyli \(\displaystyle{ P\left( \ZZ\right)}\) jest nieprzeliczalny.

[krl]

Gdy za zbiory przeliczalne uważamy tylko te równoliczne ze zbiorem liczb naturalnych, prowadzi to do nieporozumień (jak u dachowca). Wtedy zbiór nieprzeliczalny (w znaczeniu uznanym w matematyce) to nie jest po prostu zbiór, który nie jest przeliczalny, lecz dodatkowo taki, który jest nieskończony. Kłóci się to z logiką języka.
Ja opowiadam się za pierwszą definicją przeliczalności: zbiór jest przeliczalny, gdy możemy go przeliczyć przy pomocy kolejnych liczb naturalnych (niekoniecznie wszystkich). W szczególności zbiór skończony jest przeliczalny. Wtedy zbiór nieprzeliczalny to dokładnie taki zbiór, który nie jest przeliczalny.

[Jakub Gurak]

Jedyna korzyść takiego ujęcia, jaką widzę (ale też już wcześniej to zauważyłem) . No tak, w ujęciu za którym ja się opowiadam- czyli zbiór przeliczalny jako zbiór równoliczny z \(\displaystyle{ \NN}\), trzeba by powiedzieć, że zbiór jest nieprzeliczalny, gdy nie jest co najwyżej przeliczalny. To taka jedna niezręczność. Dla mnie wygodniej jednak rozumieć przez zbiory przeliczalne zbiory równoliczne z \(\displaystyle{ \NN}\) (nie trzeba rozważać zbiorów skończonych różnych mocy) też słowo "przeliczalny" bardziej mi tu tak pasuje, niż do zbiorów skończonych( tu nie trzeba przeliczać- wystarczy policzyć (choć gdy zbiór ma moc skończoną, ale równą np. \(\displaystyle{ 10^{100}}\))...).

A ta niezręczność językowa o której Pan krl piszę nie jest rzeczą nową, np. są funkcje parzyste i funkcje nieparzyste (I jeszcze inne funkcje). Kto dobrze rozumie te pojęcia nie będzie miał z tym problemu, bo rozumie na przykład , że zbiór nieprzeliczalny oznacza zbiór większy niż jakikolwiek zbiór przeliczalny.

A czy zbiór pusty jest przeliczalny? Na pewno nie jest nieprzeliczalny, ale jestem daleki od również takiego stwierdzenia. To pokazuje, że czasem warto nie rozstrzygać na zasadzie językowej tak-nie gdy rozważana własność nie ma specjalnego odniesienia do danego obiektu. Wiemy też np., że \(\displaystyle{ 1}\) nie jest liczbą pierwszą ani złożoną.

Takich definicji, że np. zbiór jest nieskończony gdy nie jest skończony, należy chyba mieć świadomość