zbiory nieprzeliczalne

[prawyakapit]

Dlaczego zbiór \(\displaystyle{ \left\{ 0,1\right\} ^{\NN}}\) jest nieprzeliczalny ?

[Premislav]

Odcinek \(\displaystyle{ [0,1]}\) jest rzecz jasna nieprzeliczalny, gdyż możemy łatwo wskazać suriekcję zeń na \(\displaystyle{ \RR}\) (przeskalowany tangens). To teraz przedstaw każdy ułamek z \(\displaystyle{ [0,1]}\) w zapisie dwójkowym. Taka reprezentacja jest surjekcją z \(\displaystyle{ \left\{ 0,1\right\}^{\NN}}\) w \(\displaystyle{ [0,1]}\).

[Slup]

To jest jedno z najpiękniejszych i najbardziej klasycznych rozumowań matematyki. Załóżmy, że udało nam się ustawić elementy tego zbioru w ciąg \(\displaystyle{ \{a_n\}_{n\in \NN}}\). Napiszmy:
\(\displaystyle{ a_n=(a(i)_n)_{i\in \NN}}\)
gdzie \(\displaystyle{ a(i)_n\in \{0,1\}}\) dla \(\displaystyle{ i\in \NN}\). Dla każdego \(\displaystyle{ i\in \NN}\) weźmy liczbę \(\displaystyle{ b(i)=|a(i)_i-1|\in \{0,1\}}\). Niech:
\(\displaystyle{ b=(b(i))_{i\in \NN}\in \{0,1\}^{\NN}}\)
Musi istnieć \(\displaystyle{ n\in \NN}\) takie, że:
\(\displaystyle{ b=a_n}\)
Wówczas:
\(\displaystyle{ a(n)_n=b(n)=|a(n)_n-1|}\)
co jest niemożliwe. To daje sprzeczność.