Równoliczność zbiorów, zbiory przeliczalne

Liczby naturalne 

 słuŜą do liczenia elementów zbiorów skończonych. Zbiory skończone to

właśnie zbiory, które mają   elementów dla pewnej liczby naturalnej  . Pozostaje problem, jak określić
liczbę elementów zbioru nieskończonego. MoŜemy to zrobić posługując się w pewnym sensie zasadą
abstrakcji. Mianowicie, zamiast definiować, co to jest liczba elementów danego zbioru, najpierw
definiujemy, co to znaczy, Ŝe dwa zbiory 

 i 

 mają tę samą liczbę elementów (tzn. są równoliczne).

Definicja 11..1   Mówimy, Ŝe zbiory 

 i 

 są równoliczne (symbolicznie: 

), gdy istnieje bijekcja

.

Uwaga 11..2   Dla dowolnych zbiorów 

 mamy:

(1) (zwrotność) 
(2) (symetryczność) 
(3) (przechodniość) 

Dowód. Funkcja identycznościowa 

 świadczy o (1). Dla dowodu (2) zauwaŜmy, Ŝe jeśli 

jest bijekcją, to funkcja odwrotna 

 istnieje i teŜ jest bijekcją. (3) wynika z tego, Ŝe złoŜenie

bijekcji jest bijekcją. 

Widzimy, Ŝe równoliczność zbiorów ma własności relacji równowaŜności. Czy jednak 

 jest relacją

równowaŜności ? W ścisłym sensie nie, gdyŜ jej dziedzina i obraz nie są zbiorami, nie istnieje bowiem
zbiór wszystkich zbiorów. (Gdyby bowiem taki zbiór 

 istniał, to funkcja zdaniowa 

zdefiniowałaby nam zbiór z antynomii Russella.)

Jeśli jednak ograniczymy zakresy zmiennych 

 i 

 w funkcji zdaniowej 

 do zbioru podzbiorów

pewnej ustalonej przestrzeni 

, to wówczas 

 staje się relacją równowaŜności na zbiorze 

.

Intuicyjnie, liczba elementów zbioru 

 (zwana inaczej mocą zbioru 

) to wspólna własność wszystkich

zbiorów równolicznych ze zbiorem 

. Gdy ograniczamy 

 do zbioru 

, dla 

 moglibyśmy

przyjąć (stosując zasadę abstrakcji), Ŝe moc 

 to po prostu klasa abstrakcji relacji 

. W ten sposób

wykluczylibyśmy jednak z rozwaŜań zbiory równoliczne z 

, które nie zawierają się w przestrzeni 

.

W teorii mnogości rozwiązuje się ten problem nieco sztucznie: tworzy się mianowicie dla wszystkich
zbiorów 

 pewne zbiory oznaczane przez 

. Obiekty te mają następującą własność:

Dla dowolnych zbiorów 

 mamy 

W ten sposób grają one rolę ``nazw'' klas zbiorów równolicznych. 

 nazywamy mocą zbioru 

 lub

liczbą kardynalną zbioru 

.

Liczby naturalne to po prostu liczby kardynalne zbiorów skończonych. A więc na przykład, gdy zbiór 
jest trzyelementowy, to 

. W przypadku liczb naturalnych moŜna łatwo wyjaśnić, w jaki sposób są

one konstruowane. Mianowicie w teorii mnogości przyjmuje się, Ŝe

i tak dalej. Widzimy, Ŝe liczba naturalna   jest pewnym zbiorem  -elementowym, a mianowicie

. Jest więc ona jakby wzorcowym zbiorem  -elementowym. Przyrównując zbiór

skończony do jednego z takich wzorców stwierdzamy, ile ma elementów. ZauwaŜmy, Ŝe formalnie liczba

 to zbiór 

.

Niektóre inne liczby kardynalne mają specjalne nazwy i oznaczenia. Przykładowo liczbę kardynalną 

oznacza się symbolem 

 (czytaj: alef zero), zaś moc zbioru liczb rzeczywistych nazywa się continuum i

oznacza mała gotycką literą  . Podamy teraz przykłady zbiorów równolicznych.

Przykład 1. Niech 

. 

 jest zbiorem liczb parzystych. Są to zbiory

równoliczne, świadczy o tym bijekcja 

 dana wzorem 

.

Przykład 2. Dowolne dwa przedziały 

 są równoliczne. świadczy o tym funkcja liniowa

dana wzorem

która przekształca przedział 

 wzajemnie jednoznacznie na przedział 

.

Przykład 3. Dowolny przedział 

 jest równoliczny z 

. Istotnie, funkcja 

jest bijekcją, która świadczy o tym, Ŝe 

. Z drugiej strony na mocy przykładu 2. mamy

, więc z przechodniości 

 równieŜ 

.

Przykład 4. 

, czyli przedziały otwarty i domknięty są równoliczne. By to uzasadnić,

znajdujemy bijekcję 

. Najpierw określamy pewien ciąg róŜnowartościowy 

 liczb z

przedziału 

, na przykład niech

Funkcję 

 określamy wzorem

zaś dla 

 róŜnych od 

 kładziemy 

.

Przykład 5. Przedział otwarty 

 i ``kwadrat'' 

 są równoliczne. By to

uzasadnić, określamy bijekcję 

.

Niech 

. W rozwinięciu dziesiętnym liczba   ma postać

gdzie 

. W przypadku, gdy w zapisie tym od pewnego miejsca występują same zera,

zastępujemy go zapisem, w którym od pewnego miejsca są same dziewiątki. Na przykład

W ten sposob kaŜdej liczbie   przypisane jest jedyne rozwinięcie dziesiętne nieskończone, w którym
dowolnie daleko pojawiają się cyfry niezerowe. Teraz dzielimy ciąg 

 na kolejne skończone

bloki cyfr 

 w następujący sposób. Blok cyfr 

 zaczyna się zaraz po bloku 

 (blok 

zaczyna się od 

) i kończy na  -tej kolejnej niezerowej cyfrze w ciągu 

. Wówczas tworzymy

dwie nowe liczby rzeczywiste   i   określając ich rozwinięcia dziesiętne następująco:

Przykładowo, dla

mamy

Definujemy 

. Widzimy, Ŝe 

. Z dowolnej pary 

 potrafimy odczytać

 takie, Ŝe 

. Na przykład, gdy

to widzimy, Ŝe istnieje dokładnie jeden ciąg bloków 

 taki, Ŝe kaŜdy blok składa się z

pewnej liczby zer na początku (być moŜe liczby zerowej) a następnie jednej cyfry niezerowej, i taki, Ŝe

Mianowicie, z zapisu dziesiętnego liczby   odczytujemy, Ŝe 

 i tak dalej, podczas

gdy z zapisu dziesiętnego liczby   odczytujemy, Ŝe 

 i tak dalej. Zatem

istnieje jedyne   takie, Ŝe 

, a mianowicie

Dlatego funkcja   jest bijekcją.

Twierdzenie 11..3 (Cantor-Bernstein)   Jeśli 

 i 

, to 

.

Dowód. Niech 

 będzie bijekcją. Skoro 

, to 

 i ogólniej 

. Z

drugiej strony 

, więc 

. Dlatego mamy 

 dla

 Innymi słowy dostajemy malejący ciąg zbiorów:

Niech 

. Widzimy, Ŝe 

. Dlatego 

 i ogólniej 

.

 jest róŜnowartościowa, dlatego

zatem dla 

 mamy

Z 

 dostajemy więc, Ŝe zbiory 

 są parami rozłączne. Ponadto

 jest bijekcją. Niech

Zatem   ograniczone do 

 jest bijekcją ze zbioru 

 na zbior 

 zawarty w

. Ponado 

. MoŜemy teraz określić funkcję 

 wzorem

Widzimy, Ŝe funkcja   jest róŜnowartościowa i ``na''. Dlatego świadczy ona o równoliczności zbiorów 

 i

. 

Przykład 6. Niech 

 (jest to więc ``pełny kwadrat''). Wtedy zbiory 

 i 

 (z przykładu

5.) są równoliczne. By to uzasadnić, rozwaŜmy jednokładność   płaszczyzny 

 o środku w punkcie

 i skali  . Jest to bijekcja płaszczyzny. Mamy

Skoro 

, to na mocy twierdzenia Cantora-Bernsteina dostajemy 

.

Uwaga 11..4   Jeśli 

 i 

, to 

.

Dowód. Dowód pozostawiamy jako ćwiczenie.

Wniosek 11..5   

.

Dowód. Niech   oznacza przedział domknięty 

. Korzystając z powyŜszych przykładów i uwagi

mamy więc

Zbiory przeliczalne.

Definicja 11..6   Zbiór 

 nazywamy przeliczalnym, gdy jest skończony lub równoliczny z 

.

Zatem zbiory przeliczalne to zbiór pusty, niepuste zbiory skończone i te zbiory nieskończone, które są
równoliczne z 

.

Uwaga 11..7   ZałóŜmy, Ŝe 

. Wtedy następujące warunki są równowaŜne.

(1) 

 jest przeliczalny.

(2) Istnieje surjekcja 

.

(3) Elementy zbioru 

 moŜna ustawić w ciąg (ewentualnie z powtórzeniami): 

.

Dowód. By udowodnić równowaŜność warunków (1)-(3), wystarczy pokazać implikacje 

,

 i 

.

. Jeśli 

 ma   elementów (

), to 

 dla pewnych 

.

Definiujemy wtedy surjekcję 

 wzorem:

Gdy 

 jest równoliczny z 

, to istnieje nawet bijekcja 

.

. ZałóŜmy, Ŝe 

 jest ``na''. Wtedy

.

. ZałóŜmy, Ŝe 

 Gdy 

 jest skończony (wtedy ciąg 

 musi mieć

powtórzenia), to jest oczywiście przeliczalny. ZałóŜmy więc, Ŝe 

 jest nieskończony. Wtedy w ciągu

 jest nieskończenie wiele wyrazów. Skreślając w ciągu 

 te wyrazy, które

wystąpiły juŜ wcześniej, dostajemy nowy ciąg, tym razem juŜ bez powtórzeń. Ten nowy ciąg jest więc
bijekcją między 

 a 

. 

Uwaga 

11.7

 tłumaczy nazwę zbioru przeliczalnego. Mianowicie, zbiór przeliczalny to taki zbiór, którego

elementy moŜemy przeliczyć uŜywając liczb naturalnych (być moŜe wszystkich, gdy nasz zbiór jest
nieskończony).

Przykład 1. Zbiór liczb całkowitych   jest przeliczalny. Istotnie, 

.

Przykład 2. Zbiór liczb wymiernych 

 jest przeliczalny. MoŜe to być zaskakujące, Ŝe jest tyle samo liczb

wymiernych, co liczb naturalnych (tzn. Ŝe 

). By to uzasadnić, najpierw układamy dodatnie liczby

wymierne w nieskończonej tablicy :

Na kolejnych przekątnych leŜą ułamki o stałej sumie licznika i mianownika, kaŜda taka przekątna składa
się ze skończenie wiele takich ułamków. KaŜdy ułamek leŜy na jakiejś przekątnej. Dlatego układając
kolejno ułamki najpierw z pierwszej przekątnej, potem z drugiej, potem z trzeciej i tak dalej, ustawimy
liczby wymierne dodatnie w ciąg (z powtórzeniami):

Następnie, podobnie jak w przykładzie 1., moŜemy ustawić w ciąg wszystkie liczby wymierne.

Uwaga 11..8 (1)   Jeśli 

 i 

 są przeliczalne, to 

 teŜ jest przeliczalny.

(2) Jeśli 

 jest ciągiem zbiorów przeliczalnych, to zbiór 

 teŜ jest przeliczalny.

(3) Jeśli 

 i 

 są przeliczalne, to 

 jest przeliczalny.

Dowód. (1) MoŜemy załoŜyć, Ŝe 

 i 

 są niepuste. ZałóŜmy, Ŝe 

 i

. Wtedy elementy zbiou 

 ustawiamy w ciąg następująco:

(2) MoŜemy wykreślić z ciągu zbiorów 

 zbiory puste (nie wpływają one na sumę tych

zbiorów). Jeśli pozostanie tylko skończenie wiele zbiorów niewykreślonych, to ich suma będzie
przeliczalna na mocy kilkukrotnego zastosowania (1). Dlatego moŜemy załoŜyć, Ŝe pozostało
nieskończenie wiele zbiorów niewykreślonych.

Zmieniając odpowiednio ich numerację moŜemy załoŜyc, Ŝe wszystkie zbiory 

 są niepuste. MoŜemy

zatem elementy kaŜdego zbioru 

 ustawić w ciąg:

Następnie moŜemy ustawić w ciąg elementy zbioru 

 podobnie, jak zrobiliśmy to w przypadku liczb

wymiernych dodatnich.

(3) Znów moŜemy załoŜyć, Ŝe oba zbiory 

 są niepuste oraz 

 i

. Dla 

 niech 

. Zatem zbiór 

 składa się z tych par

, dla których 

. Widzimy, Ŝe 

, jest więc

przeliczalny. Ponadto 

, jest więc przeliczalny na mocy (2).

Wniosek 11..9   Zbiór wszystkich skończonych ciągów o wyrazach ze zbioru przeliczalnego 

 jest

przeliczalny.

Dowód. Dla 

 niech 

 oznacza zbiór ciągów  -wyrazowych o wyrazach z 

. Wtedy 

(jest więc jednoelementowy, składa się z ciągu pustego) oraz dla 

, więc zawsze

 jest przeliczalny. Zatem równieŜ zbiór wszystkich ciągów skończonych o wyrazach z 

, czyli zbiór

, jest przeliczalny. 

W szczególności jest przeliczalnie wiele wielomianów o współczynnikach wymiernych. KaŜdy z nich ma
skończenie wiele pierwiastków. Pierwiastki takich wielomianów nazywamy liczbami algebraicznymi.
Widzimy więc, Ŝe jest przeliczalnie wiele liczb algebraicznych. Istnieją równieŜ zbiory nieprzeliczalne.

Twierdzenie 11..10 (Cantor)   Zbiór liczb rzeczywistych jest nieprzeliczalny.

Dowód. 

, wystarczy więc pokazać, Ŝe przedział otwarty 

 jest nieprzeliczalny.

Przypuśćmy nie wprost, Ŝe 

 jest przeliczalny, tzn. jego elementy moŜna ustawić w ciąg:

. Zatem 

 to ciąg wszystkich liczb rzeczywistych z przedziału 

.

Sprzeczność osiągniemy wskazując liczbę rzeczywistą z przedziału 

, która nie jest wyrazem tego

ciągu.

KaŜdą z liczb 

 moŜemy zapisać w postaci nieskończonego rozwiniecia dziesiętnego.

Z łatwością znajdujemy teraz cyfry 

 takie, Ŝe 

 i 

. Wówczas liczba

jest róŜna od kaŜdej liczby 

 (bo róŜni się od niej na 

-wszym miejscu po przecinku: 

), co

kończy dowód. 

Skoro 

 jest nieprzeliczalny, a liczb algebraicznych jest przeliczalnie wiele, to liczb niealgebraicznych

(zwanych inaczej przestępnymi) jest nieprzeliczalnie wiele.