Zbiory przeliczalne i nieprzeliczalne

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

a) 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)

b) 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.

Poniżej pokazujemy jak możemy ustawić w ciąg zbiór liczb wymiernych, co oznacza, że jest on równoliczny ze zbiorem liczb naturalnych

UWAGA. Ułamki zaznaczone kolorem czerwonym usuwamy z ciągu jako wartości powtarzające się, np. usuwamy (2/2, 3/3, 4/4, itd., bo bylo już 1/1), podobnie (2/4, 3/6 4/8, itd. bo było już 1/2) itp.

Powyżej ustawiliśmy w ciąg  tylko liczby wymierne dodatnie. Ale korzystając z powyższego łatwo już ustawić w ciąg wszystkie liczby wymierne. Oto w jaki sposób: 0/1, -1/1, 1/1, -2/1, 2/1, -1/2, 1/2, -1/3, 1/3, -3/1, 3/1, -4/1, 4/1, -3/2, 3/2, -2/3, 2/3, -1/4, 1/4, -1/5, 1/5, -5/1, 5/1, -6/1, 6/1, -5/2, 5/2, -4/3, 4/3, -3/4, 3/4, -2/5, 2/5, -1/6, 1/6, -1/7, 1/7, -3/5, 3/5,…, itd.

Definicja  Zbiór, który nie jest co najwyżej przeliczalny nazywamy zbiorem nieprzeliczalnym 

A teraz wykażemy, że zbiór (wszystkich) liczb rzeczywistych z przedziału  (0, 1) jest nieprzeliczalny

Każdą liczbę rzeczywistą z tego przedziału można przedstawić w postaci nieskończonego ułamka dziesiętnego, czyli  w postaci:

0, b1 b2 b3 b4 b5 b6 b7…

W przypadku niejednoznacznego przedstawienia liczb postaci 0,325(9)=0,326(0) musimy się zdecydować na jedną z tych dwu postaci. Wówczas możemy powiedzieć, że wszystkie liczby są przedstawione w sposób jednoznaczny. Gdyby ten zbiór był przeliczalny moglibyśmy wszystkie jego elementy ustawić w ciąg, np. jak niżej:

Gdyby zbiór liczb rzeczywistych z przedziału (0,1) był przeliczalny, wtedy moglibyśmy ustawić te liczby w ciąg ai=(aij)j=1,2,…, 0<ai<1. Kolejne cyfry po przecinku w normalnej dziesiętnej reprezentacji liczby ai oznaczmy przez ai1, ai2, ai3, …

Skonstruujemy liczbę c = 0,c1c2c3…, w której i-ta cyfra po przecinku została oznaczona przez ci i określona następująco:

ci = 7, gdy aii = 4,
ci = 4 w przeciwnym przypadku.

Oczywiście liczba c jest różna od liczby a1, bo gdy pierwszą cyfrą po przecinku w liczbie a1 jest 4, to w liczbie c pierwszą cyfrą jest 7, jeśli natomiast pierwszą cyfrą w a1 nie jest 4, to w  c jest to cyfra 4. Analogicznie dla wszystkich liczb z ciągu a1, a2, a3,… : liczba c różni się od ai na i-tym miejscu po przecinku. Zatem c, chociaż jest to liczba należąca do przedziału (0,1), to jej rozwinięcie dziesiętne nie występuje w ciągu ai=(aij)j=1,2,…. Uzyskana sprzeczność dowodzi, że zbiór liczb z przedziału (0,1) nie jest przeliczalny.