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.