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.