Z definicji wynika, że zbiory nieprzeliczalne to te, które nie są ani skończone, ani nie są równoliczne ze zbiorem liczb naturalnych.

Dowód.

Gdyby zbiór liczb rzeczywistych z przedziału (0,1) był przeliczalny, wtedy moglibyśmy ustawić te liczby w ciąg d=(d_i)_i=1,2,..., 0<d_i<1. Kolejne cyfry po przecinku w normalnej dziesiętnej reprezentacji liczby di oznaczmy przez d_i1, d_i2, d_i3, ... Skonstruujemy liczbę c = 0,c₁c₂c₃..., w której i-ta cyfra po przecinku została oznaczona przez c_i i określona następująco:

Oczywiście liczba c jest różna od liczby d₁, bo gdy pierwszą cyfrą po przecinku w liczbie c jest 7, to w liczbie d pierwszą cyfrą jest 5, jeśli natomiast pierwszą cyfrą w c jest 5, to w d₁ nie jest to cyfra 5. Analogicznie dla wszystkich liczb z ciągu d₁, d₂, d₃,... : liczba d_i różni się od c na i-tym miejscu po przecinku. Zatem c, chociaż jest to liczba należąca do przedziału (0,1), a jej rozwinięcie dziesiętne jest normalne, nie występuje w ciągu d. Uzyskana sprzeczność dowodzi, że zbiór liczb z przedziału (0,1) nie jest przeliczalny. ♦

Pytanie 10.3.1: Czy zbiór liczb rzeczywistych jest przeliczalny?

Dowód.

Zamiast mówić o funkcjach, możemy mówić o nieskończonych ciągach zerojedynkowych. Gdyby zbiór 2^N był przeliczalny, wtedy moglibyśmy ustawić wszystkie ciągi zerojedynkowe z tego zbioru w ciąg. Oznaczmy go przez (c_i)_{i ∈N}, a kolejne elementy i-tego ciągu przez c_i0, c_i1 c_i2 , ... Konstruujemy ciąg d = (d₀, d₁ d₂ ,...) w taki sposób, by różnił się on i-tym wyrazem od i-tego wyrazu ciągu c_i

Ciąg d składa się tylko z zer i jedynek i jest rzeczywiście różny od wszystkich ciągów c_i, bo na i-tej pozycji ma 0 tylko wtedy, gdy w ciągu c_i na i-tej pozycji jest jedynka. Sprzeczność. ♦

Uwaga. W obu lematach 10.3.1 i 10.3.2 zastosowano tę samą metodę rozumowania, zwaną metodą przekątniową.

Pytanie 10.3.2: Czy zbiór wszystkich podzbiorów zbioru N jest przeliczalny?

Na zakończenie przeglądu najważniejszych faktów dotyczących zbiorów nieprzeliczalnych zanotujmy jeszcze wniosek, który można otrzymać z lematu 10.2.1 przez zastosowanie prawa transpozycji.

Wniosek Każdy nadzbiór zbioru nieprzeliczalnego jest nieprzeliczalny.

Przykład 10.3.1

Udowodnimy, że przedział [0,1] zbioru liczb rzeczywistych jest zbiorem nieprzeliczalnym. Oczywiście, fakt ten jest natychmiastową konsekwencją zanotowanego przed chwilą wniosku i lematu 10.3.1, jednak, przedstawiony tu dowód jest na tyle ciekawy, że warto go mimo to przytoczyć.

Dowód. Gdyby zbiór [0,1] był przeliczalny, to jego elementy można by było ustawić w ciąg np. (c_i) _{i ∈N} . Podzielmy przedział [0, 1] na trzy równe przedziały i wybierzmy ten z nich, do którego nie należy c₀. Oznaczmy końce tego przedziału przez a₀ i b₀ odpowiednio. Teraz przedział [a₀,b₀] podzielimy na trzy równe części i wybierzemy tę z nich, do której nie należy c₁, itd. Utworzymy w ten sposób ciąg przedziałów [a₀,b₀], [a₁,b₁], [a₂,b₂], [a₃,b₃],... takich, że

1. Ciąg (a_i) _{i ∈N} jest niemalejący,
2. Ciąg (b_i) _{i ∈N} jest nierosnący,
3. Oba ciągi są ograniczone.

Wynika stąd, że oba ciągi(a_i)_{i ∈N,} (b_i)_{i ∈N} są zbieżne. Ponieważ długości wybieranych przedziałów maleją (za każdym razem trzykrotnie), to lim _{i →∞} |a_i - b_i| = 0. W konsekwencji istnieje liczba c= lim_{i → ∞} a_i = lim_{i → ∞} b_i. Oczywiście, dla wszystkich i, c ∈ [a_i ,b_i ] oraz c ∈ [0,1]. Jednak liczbę c skonstruowaliśmy tak, że c jest różna od każdej liczby z ciągu (c_i)_{i ∈ N} (c ≠ c₀, bo c ∈ [ a₀ ,b₀] a c₀ ∉ [ a₀ ,b₀]; c ≠ c₁, bo c ∈ [ a₁ ,b₁] a c₁ ∉ [ a₁ ,b₁]; itd. ). Sprzeczność. ♦

Zadanie 10.3.1 Udowodnić, że zbiór wszystkich funkcji f: N → N jest nieprzeliczalny.

Podpowiedź: Zastosować metodę przekątniową.

Rozwiązanie: Załóżmy, że istnieje ciąg f₁,f₂,f₃... wszystkich funkcji z N w N. Skonstruujemy funkcję f :N → N następująco: f(i) = f_i(i) +1. Funkcja f różni się od i-tej funkcji ciągu f₁,f₂,f₃... wartością i-tego argumentu. Czyli nie jest prawdą, że udało się nam ustawić wszystkie funkcje w ciąg.