Arytmetyka liczb kardynalnych

Liczby kardynalne (moce zbiorów) oznaczamy zazwyczaj małymi gotyckimi literami 

 lub greckimi

, chyba Ŝe dana liczba ma specjalne oznaczenie, jak na przykład 

.

Definicja 12..1 (1)   Suma 

 liczb kardynalnych 

 jest to moc zbioru 

, gdzie

 i zbiory 

 są rozłączne.

(2) Iloczyn 

 liczb 

 to moc zbioru 

, gdzie 

.

(3)  -ta potęga liczby 

, oznaczana przez 

, to moc zbioru 

 wszystkich funkcji 

.

Jasne jest, Ŝe definicje te nie zaleŜą od wyboru zbiorów 

 i 

. Jeśli mamy 

, to łatwo

uzyskać zbiory 

 i 

, które dodatkowo są rozłączne. Mianowicie niech 

. Wówczas

moŜemy przyjąc 

 i 

. Widzimy, Ŝe bez kłopotu w punkcie (1) powyŜszej

definicji znajdziemy odpowiednie zbiory 

. Zwróćmy uwagę, Ŝe w przypadku, gdy liczby 

 i   są

skończone (czyli są liczbami naturalnymi), to suma, iloczyn i odpowiednia potęga będą liczbami
naturalnymi równymi zwykłej sumie, iloczynowi i potędze liczb naturalnych.

Łatwo pokazać, Ŝe dodawanie i mnoŜenie liczb kardynalnych są przemienne i łączne oraz mnoŜenie jest
rozdzielne względem dodawania. Definicja potęgowania liczb kardynalnych jest naturalna. Istotnie, niech

, zaś 

. Wówczas funkcję 

 moŜemy traktować jak uogólniony ciąg 

,

gdzie 

 i zbiór 

 to uogólniona potęga kartezjańska 

 kopii zbioru 

 (porównaj rozdział

10).

Znaczenie operacji potęgowania wyjaśnia następująca uwaga.

Uwaga 12..2   

.

Dowód. 

 to moc zbioru 

 wszystkich funkcji 

. Wystarczy więc pokazać, Ŝe

zbiory 

 i 

 są równoliczne.

Dla zbioru 

 definiujemy funkcje 

 wzorem

Funkcję 

 nazywamy funkcją charakterystyczną zbioru 

. Łatwo stwierdzić, Ŝe przypisanie zbiorowi

 jego funkcji charakterystycznej jest bijekcją między zbiorem 

 i 

, co kończy dowód.

Korzystając z wyników z poprzedniego rozdziału, dla kaŜdej liczby naturalnej 

 dostajemy

Korzystamy tu z tego, Ŝe 

.

Liczby kardynalne moŜemy teŜ porównywać.

Definicja 12..3 (1)   

 pewien zbiór 

 mocy   zawiera podzbiór mocy 

.

(2) Gdy 

 i 

, piszemy 

.

Uwaga 12..4 (1)   Jeśli pewien zbiór mocy   zawiera podzbiór mocy 

, to kaŜdy zbiór mocy   zawiera

podzbiór mocy 

.

(2) (przechodniość 

) Jeśli 

 i 

, to 

.

(3) (antysymetryczność 

) Jeśli 

 i 

, to 

.

Dowód. (1) Niech 

 będzie zbiorem mocy   zawierającym podzbiór 

 mocy 

. Niech 

 będzie innym

zbiorem mocy  . Zbiory 

 i 

 są równoliczne, zatem istnieje bijekcja 

. Widzimy, Ŝe zbiór

 jest podzbiorem zbioru 

, mocy 

.

(2) ZałóŜmy, Ŝe 

 jest zbiorem mocy  . Na mocy (1), 

 zawiera pewien podzbiór 

 mocy  , który z

kolei zawiera pewien podzbiór 

 mocy 

. Zatem 

 jest równieŜ podzbiorem 

 mocy 

.

(3) wynika z twierdzenia Cantora-Bernsteina. Niech 

 będzie zbiorem mocy  . Wtedy 

 zawiera

podzbiór 

 mocy 

 (bo 

). Z kolei 

 zawiera podzbiór 

 mocy   (bo 

). Dlatego

 i 

. Z twierdzenia 11.3 dostajemy, Ŝe 

, czyli 

. 

Uwagę 12.4(3) równieŜ nazywa się twierdzeniem Cantora-Bernsteina. Oczywisćie mamy 

. Z

twierdzenia Cantora mamy, Ŝe 

 (bo zbiór 

 jest nieprzeliczalny). Dlatego 

. Ta ostra

nierówność jest nieprzypadkowa. Uogólnimy ją poniŜej. Zaczniemy od dość zaskakującej uwagi.

Uwaga 12..5   

, innymi słowy zbiór liczb rzeczywistych jest równoliczny ze zbiorem wszystkich

podzbiorów 

.

Dowód. Na mocy uwagi 12.4(3) wystarczy pokazać, Ŝe 

 i 

.

. Z definicji, 

 to moc zbioru 

 wszystkich ciągów zerojedynkowych. KaŜdemu takiemu

ciągowi 

 moŜemy przypisać liczbę o rozwinięciu dziesiętnym 

. W ten sposób określamy

funkcję róŜnowartościową 

. Zatem zbiór 

 jest podzbiorem 

 mocy 

. Czyli

.

. Z rodziału 11 wiemy, Ŝe przedział 

 ma moc continuum. KaŜdej liczbie 

 przypisujemy

ciąg zerojedynkowy kolejnych cyfr w rozwinięciu   przy podstawie  . W ten sposób określamy funkcję
róŜnowartościową przekształcającą zbiór 

 w 

. Stąd dostajemy 

. 

Twierdzenie 12..6 (Cantor)   

.

Dowód. Niech 

 będzie zbiorem mocy 

. Wtedy zbiór 

 jest mocy 

. Przyporządkowanie

elementowi 

 zbioru 

 określa funkcję róŜnowartościową 

. Jej obraz jest podzbiorem

zbioru 

 mocy 

. To pokazuje, Ŝe 

. By dokończyć dowód, wystarczy więc pokazać, Ŝe

.

Przypuśćmy nie wprost, Ŝe 

, to znaczy, Ŝe zbiory 

 i 

 są równoliczne. Niech

 będzie bijekcją. By uzyskać sprzeczność, znajdziemy podzbiór 

 zbioru 

 róŜny od

 dla wszystkich 

. Zbiór 

 definiujemy wzorem

Widzimy, Ŝe istotnie dla kaŜdego 

 mamy 

, gdyŜ zbiory 

 i 

 nie mają tych samych

elementów: ``róŜnią się'' na elemencie  . 

Uwaga 12.4 mówi, Ŝe 

 jest częściowym porządkiem na klasie liczb kardynalnych. MoŜna się

zastanawiać, czy jest to porządek liniowy. Innymi słowy, czy dla wszystkich zbiorów 

 mamy

 lub 

. By to udowodnić, jako dodatkowego załoŜenia potrzebujemy tak zwanego

aksjomatu wyboru (zwanego równieŜ pewnikiem wyboru), który jest mniej oczywisty od dotychczas
rozwaŜanych własności zbiorów.

Aksjomat Wyboru. Jeśli 

 jest indeksowaną rodziną zbiorów niepustych, to

istnieje funkcja   (zwana funkcją wyboru) o dziedzinie 

, taka Ŝe dla wszystkich

.

Aksjomat wyboru, choć pozornie naturalny, ma jednak zaskakujące konsekwencje. Przykładowo wynika z
niego, Ŝe kulę moŜna podzielić na 5 części i złoŜyć z nich dwie kule identyczne z wyjściową (paradoks
Banacha-Tarskiego). Przyjmujemy jednak zazwyczaj ten aksjomat w teorii mnogości, gdyŜ bez niego
trudno byłoby udowodnić wiele naturalnych matematycznych twierdzeń (jak np. równowaŜność definicji
funkcji ciągłej wg Heinego i wg Cauchy'ego). Prostą konsekwencją aksjomatu wyboru jest następująca
uwaga.

Uwaga 12..7   Jeśli 

 jest surjekcją, to 

.

Dowód. Dla 

 definiujemy zbiór 

 jako 

. Widzimy więc, Ŝe indeksowana rodzina zbiorów

 jest partycją zbioru 

 na zbiory niepuste. Na mocy aksjomatu wyboru istnieje funkcja

wyboru 

 taka, Ŝe dla kaŜdego 

 mamy 

. Skoro zbiory 

 są rozłączne,

to funkcja   jest róŜnowartościowa. Dlatego mamy

, czyli 

. 

Zamiast aksjomatu wyboru często uŜywa się tak zwanego lematu Kuratowskiego-Zorna, który jest jego
konsekwencją.

Lemat 12..8 (Kuratowski-Zorn)   ZałóŜmy, Ŝe 

 jest częściowym porządkiem na zbiorze 

 o tej

własności, Ŝe kaŜdy łańcuch w 

 jest ograniczony z góry. Wtedy w zbiorze 

 istnieje element

maksymalny.

UŜywając lematu Kuratowskiego-Zorna moŜemy teraz udowodnić, Ŝe 

 jest liniowym porządkiem na

klasie liczb kardynalnych, tzn. Ŝe w stosunku do lematu 14.4 dodatkowo jest spójny.

Twierdzenie 12..9   

 lub 

.

Dowód. Niech 

 będzie zbiorem mocy 

, zaś 

 zbiorem mocy  . Niech

 jest bijekcją między pewnym podzbiorem 

 i pewnym podzbiorem 

.

Na zbiorze 

 określamy relację 

 wzorem

Widzimy, Ŝe 

 jest częściowym porządkiem na zbiorze 

. Ponadto spełnione są załoŜenia lematu

Kuratowskiego-Zorna.

Istotnie, jeśli 

 jest łańcuchem, to moŜemy określić funkcję   wzorem

Dziedzina funkcji   jest sumą dziedzin wszystkich funkcji ze zbioru 

, podobnie obraz   jest sumą

wszystkich obrazów funkcji z 

. (Krócej moglibyśmy napisać, Ŝe 

.)

Widzimy, Ŝe 

 oraz   jest ograniczeniem górnym łańcucha 

.

Z lematu Kuratowskiego-Zorna dostajemy element maksymalny 

. Niech 

 oraz

. Wtedy 

. Twierdzimy, Ŝe

(a)

 lub 

.

Przypuśćmy, Ŝe nie. Wtedy istnieją elementy 

 i 

. MoŜemy określić wówczas

funkcję 

 rozszerzającą  , kładąc 

. Wtedy 

 i 

,

co przeczy maksymalności  .

Zgodnie z (a) mamy dwa przypadki. Gdy 

, to 

, czyli 

. Gdy 

, to

, więc 

. 

Z aksjomatu wyboru wynika, Ŝe dodawanie i mnoŜenie nieskończonych liczb kardynalnych jest bardzo
łatwe. Mianowicie, gdy 

 lub   jest nieskończone, to

MoŜna to udowodnić przez indukcję pozaskończoną, o której wspomnimy później.

Nawet przy załoŜeniu pewnika wyboru wiele pytań na temat zbiorów pozostaje otwartych.
Najsłynniejszym takim problemem jest hipoteza continuum.

Hipoteza Continuum. KaŜdy nieprzeliczalny podzbiór zbioru liczb rzeczywistych jest
równoliczny z 

.

Hipoteza ta mówi, Ŝe między liczbami 

 i   nie ma Ŝadnej innej liczby kardynalnej. Wiadomo, Ŝe

hipotezy continuum nie moŜna rozstrzygnąć na gruncie teorii mnogości Zermelo-Fraenkla z aksjomatem
wyboru.