Таран Т.А. Основы дискретной математики
Подождите немного. Документ загружается.
40 41
Ïðîäîëæàÿ ýòî ïîñòðîåíèå, ïîëó÷àåì óáûâàþùóþ ïîñëåäîâà-
òåëüíîñòü ìíîæåñòâ E
0
⊃E
1
⊃E
2
⊃E
3
⊃E
4
⊃ è âçàèìíî îäíî-
çíà÷íîå ñîîòâåòñòâèå f: E
0
→E
2
, ïðè êîòîðîì E
i
îòîáðàæàåòñÿ â
E
i+2
. Ôîðìàëüíî ìîæíî îïèñàòü E
2n
êàê ìíîæåñòâî òåõ ýëåìåíòîâ,
êîòîðûå ïîëó÷àþòñÿ èç ìíîæåñòâà E
0
ïîñëå n-êðàòíîãî ïðèìåíåíèÿ
ôóíêöèè f.
Òàêèì îáðàçîì, ìíîæåñòâî E
0
ìû ðàçáèëè íà íåïåðåñåêàþùèåñÿ
ñëîè A
i
= E
i
\E
i+1
è íà ñåðäöåâèíó A=∩
i
E
i
. Ñëîè A
0
, A
2
, A
4
, ðàâíî-
ìîùíû, òàê êàê ôóíêöèÿ f îñóùåñòâëÿåò âçàèìíî îäíîçíà÷íîå ñîîò-
âåòñòâèå ìåæäó A
0
è A
2
, ìåæäó A
2
è A
4
è ò.ä. Àíàëîãè÷íî, ðàâíîìîù-
íû è ñëîè ñ íå÷åòíûìè íîìåðàìè.
Òåïåðü ìîæíî ëåãêî ïîñòðîèòü âçàèìíî îäíîçíà÷íîå ñîîòâåò-
ñòâèå g ìåæäó E
0
èE
1
.
Ïóñòü x∈ E
0
, òîãäà ñîîòâåòñòâóþùèé åìó ýëåìåíò g(x) ñòðîèòñÿ
òàê: g(x) = f(x) ïðè x∈ A
2k
è g(x) = x ïðè x∈ A
2k+1
èëè x∈ A (êàê
ïîêàçàíî íèæå).
Ýòî äîêàçûâàåò òåîðåìó.
Ñëåäñòâèÿ èç òåîðåìû Êàíòîðà Áåðíøòåéíà:
à) åñëè ñóùåñòâóåò èíúåêöèÿ E→F è íå ñóùåñòâóåò èíúåêöèè
F→E, òî ìíîæåñòâî F èìååò ìîùíîñòü, ñòðîãî áîëüøóþ, ÷åì ìîù-
íîñòü E: card F > card E.
á) åñëè ñóùåñòâóåò èíúåêöèÿ F→E è íå ñóùåñòâóåò èíúåêöèè
E→F, òî ìíîæåñòâî F èìååò ìîùíîñòü, ñòðîãî ìåíüøóþ, ÷åì ìîù-
íîñòü E: card F < card E.
â) åñëè ñóùåñòâóåò áèåêöèÿ èç F â E, òî ìíîæåñòâà F è E ðàâíî-
ìîùíû: card F=card E.
Êëàññ ýêâèâàëåíòíîñòè ðàâíîìîùíûõ ìíîæåñòâ íàçûâàåòñÿ
ìîùíîñòüþ, èëè êàðäèíàëüíûì ÷èñëîì. Êëàññû ýêâèâàëåíòíîñòè
ðàâíîìîùíûõ êîíå÷íûõ ìíîæåñòâ ÿâëÿþòñÿ êîíå÷íûìè êàðäèíàëü-
íûìè ÷èñëàìè. Ýòè ÷èñëà ïî îïðåäåëåíèþ ÿâëÿþòñÿ íàòóðàëüíûìè
÷èñëàìè, ñîîòâåòñòâóþùèìè êîëè÷åñòâó ýëåìåíòîâ â êîíå÷íîì
ìíîæåñòâå. Ìîùíîñòü ïóñòîãî ìíîæåñòâà ðàâíà íóëþ: card∅=0.
Ìîùíîñòü áåñêîíå÷íîãî ìíîæåñòâà íàçûâàåòñÿ òðàíñôèíèòíûì
êàðäèíàëüíûì ÷èñëîì, èëè ïðîñòî òðàíñôèíèòíûì ÷èñëîì. Òàêèì
îáðàçîì, ìíîæåñòâî êàðäèíàëüíûõ ÷èñåë ýòî ôàêòîð-ìíîæåñòâî
ðàâíîìîùíûõ ìíîæåñòâ, êîòîðîå ïðåäñòàâëÿåò ñîáîé îáúåäèíåíèå
ìíîæåñòâà íàòóðàëüíûõ è òðàíñôèíèòíûõ ÷èñåë.
4.3. Ñ÷åòíûå ìíîæåñòâà
Îïðåäåëåíèå 4.2. Ìîùíîñòüþ ñ÷åòíîãî ìíîæåñòâà íàçûâàåòñÿ
ìîùíîñòü ìíîæåñòâà íàòóðàëüíûõ ÷èñåë N. Ñ÷åòíûì íàçûâàåòñÿ
âñÿêîå ìíîæåñòâî X, ðàâíîìîùíîå ìíîæåñòâó N íàòóðàëüíûõ
÷èñåë. Ìîùíîñòü ñ÷åòíîãî ìíîæåñòâà îáîçíà÷àåòñÿ êàðäèíàëü-
íûì òðàíñôèíèòíûì ÷èñëîì
ℵℵ
ℵℵ
ℵ
0
(÷èòàåòñÿ: àëåô-íóëü)
1
.
Ñ÷åòíîñòü ìíîæåñòâà X îçíà÷àåò, ÷òî ñóùåñòâóåò ïî êðàéíåé
ìåðå îäíà áèåêöèÿ èç X íà N (îäíàêî ýòî íå çíà÷èò, ÷òî òàêàÿ
áèåêöèÿ çàäàíà). Èíà÷å ñ÷åòíîå ìíîæåñòâî ìîæíî îïðåäåëèòü êàê
ìíîæåñòâî, ýëåìåíòû êîòîðîãî ìîæíî ðàñïîëîæèòü â âèäå ñïèñêà
(äàæå, åñëè ýòîò ñïèñîê áóäåò áåñêîíå÷íûì). Òîãäà êàæäîìó
ýëåìåíòó ìíîæåñòâà ìîæíî ïîñòàâèòü â ñîîòâåòñòâèå åãî ïîðÿäêî-
âûé íîìåð â ýòîì ñïèñêå, ò.å. ìîæåò áûòü ïîñòðîåíî îòîáðàæåíèå
èç N â X ƒ(n): N→X, ãäå n∈N. Òàêîå îòîáðàæåíèå íàçûâàåòñÿ
íóìåðàöèåé. Î÷åâèäíî, ÷òî çàíóìåðîâàòü ìîæíî ëþáîå êîíå÷íîå
ìíîæåñòâî. Ìíîæåñòâî X êîíå÷íî èëè ñ÷åòíî òîãäà è òîëüêî òîãäà,
êîãäà ñóùåñòâóåò èíúåêöèÿ X â N, èëè, åñëè X≠∅, òîãäà è òîëüêî
òîãäà, êîãäà ñóùåñòâóåò ñþðúåêöèÿ N íà X.
Ïðèìåð. Ìíîæåñòâà âñåõ ÷åòíûõ íàòóðàëüíûõ ÷èñåë X è
ìíîæåñòâî N ðàâíîìîùíû, òàê êàê ñóùåñòâóåò èíúåêöèÿ X → Nè
ñþðúåêöèÿ N→X.
Äîêàæåì ðÿä òåîðåì î ñ÷åòíûõ ìíîæåñòâàõ.
Òåîðåìà 4.2. Ìíîæåñòâî ïîëîæèòåëüíûõ ðàöèîíàëüíûõ ÷èñåë
Q
+
ñ÷åòíî.
Äîêàçàòåëüñòâî. Ëþáîå ðàöèîíàëüíîå ÷èñëî ïðåäñòàâèìî â âèäå
äðîáè m/n, ãäå m, n íàòóðàëüíûå ÷èñëà, n≠0. Çàïèøåì ðàöèîíàëü-
íûå ÷èñëà â âèäå òàáëèöû:
Ïðàâàÿ òàáëèöà çàäàåò íóìåðàöèþ ýëåìåíòîâ ëåâîé òàáëèöû (ñòðåëêè
óêàçûâàþò íàïðàâëåíèå íóìåðàöèè). Òîãäà ìû ìîæåì âûïèñàòü ýëåìåíòû
ëåâîé òàáëèöû (ìíîæåñòâî ðàöèîíàëüíûõ ïîëîæèòåëüíûõ ÷èñåë) â âèäå
ñïèñêà, â êîòîðîì êàæäîìó ýëåìåíòó ñîîòâåòñòâóåò íàòóðàëüíîå ÷èñëî:
1/1 2/1 2/2 1/2 3/1 3/2 3/3 2/3 1/3 4/1 4/2 4/3
↓↓↓↓↓↓↓↓↓↓↓↓
1 2 3 4 5 6 7 8 9 10 11 12
Ìîùíîñòü ìíîæåñòâÃëàâà 4
1
Ìîæíî âñòðåòèòü äðóãîå îáîçíà÷åíèå ìîùíîñòè ñ÷åòíîãî ìíîæåñòâà: cardN=ν.
1/1 2/1 3/1 4/1 1 2 5 10
1/2 2/2 3/2 4/2 4 3 6 11
1/3 2/3 3/3 4/3 9 8 7 12
42 43
Ïîëó÷åííûé ïåðåñ÷åò äîêàçûâàåò ñ÷åòíîñòü ìíîæåñòâà ïîëîæè-
òåëüíûõ ðàöèîíàëüíûõ ÷èñåë.
Ìîæíî çàìåòèòü, ÷òî ðàöèîíàëüíûå ÷èñëà âõîäÿò â ýòîò ïåðåñ÷åò
ñ ïîâòîðåíèÿìè: íàïðèìåð, 1/1=2/2=3/3==1. Îäíàêî,
íåòðóäíî ñîñòàâèòü ýôôåêòèâíóþ ïðîöåäóðó âû÷åðêèâàíèÿ
ïîâòîðÿþùèõñÿ ÷èñåë èç ýòîãî ïåðåñ÷åòà. Ìû ïîêàæåì äàëåå, ÷òî
è áåç âû÷åðêèâàíèÿ ïîâòîðåíèé äîêàçàòåëüñòâî ñ÷åòíîñòè
ìíîæåñòâà Q
+
óæå çàâåðøåíî.
Òåîðåìà 4.3. Ìíîæåñòâî öåëûõ ÷èñåë Z ñ÷åòíî.
Äîêàçàòåëüñòâî. Ïîñòðîèì ñïèñîê:
0112233
↓↓↓↓↓↓↓
0123456
Òîãäà êàæäîìó ÷åòíîìó ÷èñëó ñîîòâåòñòâóåò îòðèöàòåëüíîå
÷èñëî, à êàæäîìó íå÷åòíîìó ïîëîæèòåëüíîå. Ïîñòðîåííàÿ
áèåêöèÿ äîêàçûâàåò òåîðåìó.
Òåîðåìà 4.4. Ìíîæåñòâî âñåõ ðàöèîíàëüíûõ ÷èñåë Q ñ÷åòíî.
Äîêàçàòåëüñòâî àíàëîãè÷íî ïðåäûäóùåìó.
Òåîðåìà 4.5. Ìîùíîñòü ñ÷åòíîãî ìíîæåñòâà
ℵℵ
ℵℵ
ℵ
0
ÿâëÿåòñÿ íàè-
ìåíüøèì òðàíñôèíèòíûì êàðäèíàëüíûì ÷èñëîì. Ýòî îçíà÷àåò,
÷òî âñÿêîå áåñêîíå÷íîå ìíîæåñòâî E èìååò ïî êðàéíåé ìåðå
îäíó ñ÷åòíóþ ÷àñòü (ò.å. ñ÷åòíîå ïîäìíîæåñòâî).
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî äëÿ íåêîòîðîãî áåñêîíå÷-
íîãî ìíîæåñòâà E ñîîòíîøåíèå cardE>
ℵℵ
ℵℵ
ℵ
0
íå âûïîëíÿåòñÿ, ò.å.
cardE≤
ℵℵ
ℵℵ
ℵ
0
. Ýòî îçíà÷àåò, ïî òåîðåìå Áåðíøòåéíà, ÷òî ñóùåñòâóåò
èíúåêöèÿ E→N, ò.å. â N ñóùåñòâóåò áåñêîíå÷íàÿ ÷àñòü P, òàêàÿ,
÷òî ìåæäó E è P ñóùåñòâóåò áèåêöèÿ. Îäíàêî ìåæäó ìíîæåñòâîì
N è åãî áåñêîíå÷íîé ÷àñòüþ P òîæå ñóùåñòâóåò áèåêöèÿ. Îòîáðàæå-
íèå n→x
n
, ãäå x
n
åñòü (n+1)-é â ïîðÿäêå âîçðàñòàíèÿ ýëåìåíò P,
îïðåäåëÿåò áèåêöèþ N íà P. Òîãäà ïîëó÷èì, ÷òî card E=
ℵℵ
ℵℵ
ℵ
0
.
4.4. Êàðäèíàëüíàÿ àðèôìåòèêà
Åñëè ñóùåñòâóåò ñþðúåêöèÿ Å→F, òî ñàrdF ≤ cardE. Äåéñòâè-
òåëüíî, ïðîîáðàç êàæäîé òî÷êè F íå ïóñò, è åñëè â êàæäîì èç
ïðîîáðàçîâ âûáðàòü ïî îäíîìó ýëåìåíòó
1
, òî ïîëó÷èì íåêîòîðóþ
÷àñòü Å, ðàâíîìîùíóþ F. Íàïðèìåð, ôàêòîð-ìíîæåñòâî ìíîæåñòâà
Å ïî íåêîòîðîìó îòíîøåíèþ ýêâèâàëåíòíîñòè âñåãäà èìååò íå
áîëüøóþ ìîùíîñòü, ÷åì ñàìî ìíîæåñòâî Å. Îòñþäà, à òàêæå èç
òåîðåìû 4.5 ñëåäóåò, ÷òî â êëàññå êàðäèíàëüíûõ ÷èñåë ñóùåñòâóåò
îòíîøåíèå ïîðÿäêà: åñëè
α
ÿâëÿåòñÿ êàðäèíàëüíûì ÷èñëîì íåêîòî-
ðîãî ïîäìíîæåñòâà ìíîæåñòâà ìîùíîñòè β, òî α ≤ β.
Íåòðóäíî ïîêàçàòü (äëÿ êîíå÷íûõ ìíîæåñòâ ýòî ïðîñòî, à äëÿ
áåñêîíå÷íûõ ýòî ñëåäóåò èç òåîðåìû Êàíòîðà-Áåðíøòåéíà), ÷òî
ýòî îòíîøåíèå ðåôëåêñèâíî, àíòèñèììåòðè÷íî è òðàíçèòèâíî,
ñëåäîâàòåëüíî, îíî äåéñòâèòåëüíî ÿâëÿåòñÿ îòíîøåíèåì ïîðÿäêà.
Èç òåîðåìû Êàíòîðà-Áåðíøòåéíà ñëåäóåò òàêæå, ÷òî ýòî îòíîøåíèå
ÿâëÿåòñÿ îòíîøåíèåì ëèíåéíîãî ïîðÿäêà, ò.å. ëþáûå äâà êàðäèíàëü-
íûå ÷èñëà ñðàâíèìû.
Íà ìíîæåñòâå êàðäèíàëüíûõ ÷èñåë ìîæíî îïðåäåëèòü îïåðàöèè
ñëîæåíèÿ, óìíîæåíèÿ è âîçâåäåíèÿ â ñòåïåíü.
1. Ñëîæåíèå. Ïóñòü α è β êàðäèíàëüíûå ÷èñëà, à ìíîæåñòâà E
è F èìåþò ñîîòâåòñòâåííî ìîùíîñòè card E=α è card F=β. Òîãäà
α+β ñóììà ìîùíîñòåé E è F, ýòî ìîùíîñòü âñÿêîãî ìíîæåñòâà,
äîïóñêàþùåãî ðàçáèåíèå íà äâà êëàññà ýêâèâàëåíòíîñòè,
ðàâíîìîùíûõ ìíîæåñòâàì Å è F ñîîòâåòñòâåííî. Èíûìè ñëîâàìè,
åñëè ìíîæåñòâà E è F íå ïåðåñåêàþòñÿ, òî ìîùíîñòü èõ îáúåäèíåíèÿ
ðàâíà α+β.
2. Óìíîæåíèå. ×åðåç α⋅β îáîçíà÷àåòñÿ ìîùíîñòü äåêàðòîâîãî
ïðîèçâåäåíèÿ Å×F. Èíûìè ñëîâàìè, ïðîèçâåäåíèå α⋅β ýòî êàðäè-
íàëüíîå ÷èñëî îáúåäèíåíèÿ α íåïåðåñåêàþùèõñÿ ÷àñòåé, êàæäàÿ
èç êîòîðûõ èìååò ìîùíîñòü β.
3. Âîçâåäåíèå â ñòåïåíü. ×åðåç α
β
îáîçíà÷àåòñÿ ìîùíîñòü ìíî-
æåñòâà Å
F
, ò.å. ìîùíîñòü ìíîæåñòâà âñåõ ôóíêöèîíàëüíûõ îòîáðà-
æåíèé èç F â E: card (F→E)=card (E
F
)=card E
card F
.
Òåîðåìà 4.6. Îïåðàöèè, îïðåäåëåííûå íà ìíîæåñòâå êàðäèíàëü-
íûõ ÷èñåë, îáëàäàþò ñëåäóþùèìè ñâîéñòâàìè.
1. Àññîöèàòèâíîñòü è êîììóòàòèâíîñòü ñëîæåíèÿ.
2. Àññîöèàòèâíîñòü è êîììóòàòèâíîñòü óìíîæåíèÿ.
3. Äèñòðèáóòèâíîñòü óìíîæåíèÿ ïî îòíîøåíèþ ê ñëîæåíèþ:
α⋅(β+γ)=α⋅β+α⋅γ.
4. Äëÿ âîçâåäåíèÿ â ñòåïåíü âûïîëíÿþòñÿ ñîîòíîøåíèÿ:
a) (α
β
)⋅(α
γ
)=α
β+γ
,
b) α
γ
β
γ
=(α⋅β)
γ
,
c) ((α)
β
)
γ
= α
b⋅⋅γ
.
Äîêàçàòåëüñòâî ýòèõ ñâîéñòâ îñíîâàíî íà îïðåäåëåíèè è ñâîé-
ñòâàõ îïåðàöèé îáúåäèíåíèÿ, äåêàðòîâà ïðîèçâåäåíèÿ è ôóíêöèî-
íàëüíûõ îòîáðàæåíèé ìíîæåñòâ.
Ìîùíîñòü ìíîæåñòâÃëàâà 4
1
Âûáðàòü ïî îäíîìó ýëåìåíòó â êàæäîì èç êîíå÷íîãî ÷èñëà ìíîæåñòâ íåòðóäíî,
íî ïîäîáíûé âûáîð â ñëó÷àå áåñêîíå÷íîãî ÷èñëà ìíîæåñòâ çàòðóäíèòåëåí.
Ïîñëå ìíîãî÷èñëåííûõ ñïîðîâ â íà÷àëå âåêà âîçìîæíîñòü òàêîãî âûáîðà áûëà
ââåäåíà êàê àêñèîìà òåîðèè ìíîæåñòâ àêñèîìà âûáîðà, èëè àêñèîìà Öåðìåëî.
44 45
 êà÷åñòâå ïðèìåðîâ äîêàæåì ñëåäóþùèå ñâîéñòâà.
Ñâîéñòâî 3. α⋅(β+γ)=α⋅β+α⋅γ.
Äîêàçàòåëüñòâî. Ïóñòü card A = α, card B = β, card C = γ, ãäå
ìíîæåñòâà A, B, C ïîïàðíî íå ïåðåñåêàþòñÿ, è ïóñòü a∈A, b∈B, c∈C.
Ñîîòíîøåíèå 3 âûïîëíÿåòñÿ, åñëè A×(B∪C)∼(A×B)∪(A×C).
Ðàññìîòðèì ýòè ìíîæåñòâà.
Ìíîæåñòâî A × (B ∪ C) ñîñòîèò èç ïàð {<a,b>, <a, c>}, ïðè÷åì
b≠c, òàê êàê B ∩ C = ∅.
Ìíîæåñòâî (A × B) ∪ (A × C) ñîñòîèò èç îáúåäèíåíèÿ ìíîæåñòâ
ïàð {<a, b>} ∪ {<a, c>}, ÷òî ýêâèâàëåíòíî ìíîæåñòâó {<a, b>,
<a,c>}, ãäå b≠c. Êàê âèäèì, ýòè äâà ìíîæåñòâà ñîâïàäàþò.
Ïîêàæåì, ÷òî äèñòðèáóòèâíîñòü ñëîæåíèÿ îòíîñèòåëüíî
óìíîæåíèÿ íå âûïîëíÿåòñÿ, ò.å.
α
+(
β
⋅
γ
)≠(
α
+
β
)⋅(
α
+
γ
).
Äëÿ ýòîãî ïîêàæåì, ÷òî â îáùåì ñëó÷àå îòíîøåíèå ðàâíîìîù-
íîñòè A∪(B×C)∼(A∪B)×(A∪C) íåâûïîëíèìî. Äåéñòâèòåëü-
íî, A∪(B × C) ýòî ìíîæåñòâî, ïîëó÷åííîå îáúåäèíåíèåì
{a}∪{<b, c>}= {a, <b, c>}, ò.å. ýòî ìíîæåñòâî, ñîñòàâëåííîå èç
âñåõ ýëåìåíòîâ ìíîæåñòâà A è ïàð <b, c>, â òî âðåìÿ êàê
(A∪B)×(A ∪ C) = {<a,a>, <b, a>, <a, c>, <b, c>}. Î÷åâèäíî, ÷òî
ýòî ðàçëè÷íûå ìíîæåñòâà.
Èíà÷å ýòî ìîæíî ïîêàçàòü òàê: (A ∪ B) × (A ∪C)=
=((A∪B)×A) ∪ (A ∪ B) × C) = (A×A)∪(B×A)∪(A×C)∪(B×C),
÷òî íå ýêâèâàëåíòíî A ∪ (B × C) =(A × B) ∪ (A × C).
4.5. Îñíîâíûå ñîîòíîøåíèÿ
êàðäèíàëüíîé àðèôìåòèêè
Òåîðåìà 4.7. Äëÿ ëþáîãî êîíå÷íîãî ÷èñëà m ≥ 1 âûïîëíÿþòñÿ
ðàâåíñòâà:
m⋅
ℵℵ
ℵℵ
ℵ
0
=
ℵℵ
ℵℵ
ℵ
0
è
ℵℵ
ℵℵ
ℵ
0
m
=
ℵℵ
ℵℵ
ℵ
0
.
Äîêàçàòåëüñòâî. Âîñïîëüçóåìñÿ ìåòîäîì ìàòåìàòè÷åñêîé
èíäóêöèè. Ïîêàæåì ñíà÷àëà, ÷òî N×N ðàâíîìîùíî N, ò.å.
ℵℵ
ℵℵ
ℵ
0
⋅
ℵℵ
ℵℵ
ℵ
0
=
ℵℵ
ℵℵ
ℵ
0
(áàçèñ èíäóêöèè).
Ýëåìåíòû äåêàðòîâîãî ïðîèçâåäåíèÿ N×N ìîæíî âûïèñàòü â
âèäå òàáëèöû:
Ââåäåì äèàãîíàëüíóþ íóìåðàöèþ. Ïîëó÷èì ïîñëåäîâàòåëüíîñòü
(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), ... . Ýòà ïîñëåäîâàòåëüíîñòü
îïðåäåëÿåò áèåêöèþ N íà N×N. Ñëåäîâàòåëüíî, N ýêâèâàëåíòíî
N×N, ò.å.
ℵℵ
ℵℵ
ℵ
0
⋅
ℵℵ
ℵℵ
ℵ
0
=
ℵℵ
ℵℵ
ℵ
0
2
=
ℵℵ
ℵℵ
ℵ
0
.
Ïðåäïîëîæèì òåïåðü, ÷òî
ℵℵ
ℵℵ
ℵ
0
m1
=
ℵℵ
ℵℵ
ℵ
0
, è ïîêàæåì, ÷òî òîãäà
ℵℵ
ℵℵ
ℵ
0
m
=
ℵℵ
ℵℵ
ℵ
0
.
Ïî ïðåäïîëîæåíèþ èíäóêöèè äåêàðòîâî ïðîèçâåäåíèå N
m1
ñ÷åòíî. Òîãäà, ñîãëàñíî áàçèñó èíäóêöèè, äåêàðòîâî ïðîèçâåäåíèå
äâóõ ñ÷åòíûõ ìíîæåñòâ N
m1
×N = N
m
òàêæå ñ÷åòíî, ò.å.
ℵℵ
ℵℵ
ℵ
0
m
=
ℵℵ
ℵℵ
ℵ
0
.
Ñëåäñòâèå. Îáúåäèíåíèå êîíå÷íîãî èëè ñ÷åòíîãî ìíîæåñòâà
êîíå÷íûõ èëè ñ÷åòíûõ ïîäìíîæåñòâ ìíîæåñòâà Å êîíå÷íî èëè
ñ÷åòíî.
Äîêàçàòåëüñòâî. Ïóñòü I íåêîòîðàÿ ÷àñòü N (I ⊂ N) è A
i
(i∈I) íåêîòîðûå ïîäìíîæåñòâà Å, è äëÿ âñÿêîãî iA
i
≠ ∅ (íî,
åñëè A
i
=∅, òî ýòî íè÷åãî íå ìåíÿåò, òàê êàê åñëè A
i
=∅, òî
îáúåäèíåíèå íå èçìåíèòñÿ). Ïóñòü ƒ
i
ñþðúåêöèÿ N íà A
i
. Òîãäà
îòîáðàæåíèå (i, n) → ƒ
i
(n) áóäåò ñþðúåêöèåé I×N íà
U
Ii
i
A
∈
.
Ïîñêîëüêó I×N ñ÷åòíî, òî
U
Ii
i
A
∈
êîíå÷íî èëè ñ÷åòíî.
Òåïåðü ìîæíî èíà÷å äîêàçàòü, ÷òî ìíîæåñòâî ðàöèîíàëüíûõ
÷èñåë Q ñ÷åòíî. Êàæäîé ïàðå (p, q) (q≠0) ìíîæåñòâà Z×Z ìîæíî
ïîñòàâèòü â ñîîòâåòñòâèå ðàöèîíàëüíîå ÷èñëî p/q. Ýòî îòîáðàæåíèå
ÿâëÿåòñÿ ñþðúåêöèåé ïîäìíîæåñòâà Z×Z íà Q. Çíà÷èò, Q íå áîëåå
÷åì ñ÷åòíî, íî òàê êàê îíî ñîäåðæèò N â êà÷åñòâå ñâîåãî ïîäìíîæå-
ñòâà, òî Q ñ÷åòíî.
Òåîðåìà 4.8. Åñëè A áåñêîíå÷íîå ìíîæåñòâî, à B êîíå÷íî èëè
ñ÷åòíî, òî A∪B∼A (ðàâíîìîùíû), ò.å. card(A∪B)=card(A).
Äîêàçàòåëüñòâî. Ïóñòü A
1
ñ÷åòíîå ïîäìíîæåñòâî ìíîæåñòâà
A. Îáúåäèíåíèå ñ÷åòíîãî è êîíå÷íîãî ìíîæåñòâ ñ÷åòíî, îáúåäèíåíèå
ñ÷åòíûõ ìíîæåñòâ òàêæå ñ÷åòíî, ïîýòîìó A
1
∪B∼A
1
. Ìíîæåñòâî
A∪B íå èçìåíèòñÿ, åñëè èç íåãî âû÷åñòü, à ïîòîì äîáàâèòü
ïîäìíîæåñòâî A
1
. Òîãäà A∪B=(A\A
1
)∪(A
1
∪B). Ïîñêîëüêó
A
1
∪B∼A
1
, òî (A\A
1
)∪(A
1
∪B)∼(A\A
1
)∪A
1
. Íî (A\A
1
)∪A
1
=A,
ñëåäîâàòåëüíî, A∪B∼A, ÷òî è òðåáîâàëîñü äîêàçàòü.
Òåîðåìà 4.9. Åñëè α è β êàðäèíàëüíûå ÷èñëà, òàêèå ÷òî
α
≠0
è β≠0, è åñëè ïî êðàéíåé ìåðå îäíî èç íèõ òðàíñôèíèòíî, òî
ñóììà α+β è ïðîèçâåäåíèå α⋅β ðàâíû íàèáîëüøåìó èç íèõ,
ò.å. α+β=max{α,β}, α⋅β = max{α, β}.
Ìîùíîñòü ìíîæåñòâÃëàâà 4
(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)
46 47
Äîêàçàòåëüñòâî ýòîé òåîðåìû íåïîñðåäñòâåííî ñëåäóåò èç ïðå-
äûäóùåé òåîðåìû. Äåéñòâèòåëüíî, ïîñêîëüêó ìíîæåñòâî êàðäè-
íàëüíûõ ÷èñåë ëèíåéíî óïîðÿäî÷åíî, òî ëèáî α≤β, ëèáî β≤α.
Èç òåîðåìû 4.8 ñëåäóåò, ÷òî ìîùíîñòü îáúåäèíåíèÿ äâóõ áåñêîíå÷-
íûõ ìíîæåñòâ áóäåò îïðåäåëÿòüñÿ áîëüøåé ìîùíîñòüþ. Èç îïðåäå-
ëåíèÿ ïðîèçâåäåíèÿ êàðäèíàëüíûõ ÷èñåë è ïåðâîãî ðàâåíñòâà:
α+β=max{α,β}, ñëåäóåò âûïîëíèìîñòü è âòîðîãî: α⋅β=max{α,β}.
Òåïåðü ìû ìîæåì äîêàçàòü òåîðåìó 4.7 ïîëíîñòüþ.
Äîêàçàòåëüñòâî.
m⋅
ℵℵ
ℵℵ
ℵ
0
=
444344421
ðàç
m
000
...
ℵℵℵ +++
=
ℵℵ
ℵℵ
ℵ
0
(ïî òåîðåìå î ñ÷åòíîñòè îáúåäè-
íåíèÿ ñ÷åòíûõ ìíîæåñòâ);
ℵℵ
ℵℵ
ℵ
0
m
=
4434421
ðàç
m
000
...
ℵℵℵ ⋅⋅⋅
=
ℵℵ
ℵℵ
ℵ
0
(ïî òåîðåìå î ñ÷åòíîñòè äåêàðòîâà
ïðîèçâåäåíèÿ ñ÷åòíûõ ìíîæåñòâ).
Ýòîò æå ðåçóëüòàò ìû ïîëó÷àåì ñîãëàñíî òåîðåìå 4.9: òàê êàê
m≤
ℵℵ
ℵℵ
ℵ
0
, òî m⋅
ℵℵ
ℵℵ
ℵ
0
=
ℵℵ
ℵℵ
ℵ
0
.
Èñïîëüçîâàíèå êàðäèíàëüíîé àðèôìåòèêè ïîçâîëÿåò íàì ëåãêî
äîêàçûâàòü íåêîòîðûå òåîðåìû î ìîùíîñòè ìíîæåñòâ.
Ïðèìåðû.
1. Îïðåäåëèì ìîùíîñòü ìíîæåñòâà âñåõ êîíå÷íûõ ïîñëåäîâàòåëü-
íîñòåé íàòóðàëüíûõ ÷èñåë.
Ðàññìîòðèì, èç ÷åãî ñîñòîèò ýòî ìíîæåñòâî. Ìíîæåñòâî âñåõ îäíî-
ýëåìåíòíûõ ïîñëåäîâàòåëüíîñòåé ýòî ìíîæåñòâî N, âñå äâóõýëå-
ìåíòíûå ïîñëåäîâàòåëüíîñòè îáðàçóþòñÿ äåêàðòîâûì ïðîèçâåäå-
íèåì N×N, òðåõýëåìåíòíûå N
3
, k-ýëåìåíòíûå ïîñëåäîâàòåëüíîñòè
îáðàçîâàíû äåêàðòîâûì ïðîèçâåäåíèåì N
k
è òàê äàëåå. Êàêîå áû
áîëüøîå ÷èñëî k ìû íè âçÿëè, äëÿ íåãî ñóùåñòâóåò ÷èñëî k+1 è,
ñîîòâåòñòâåííî, ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü äëèíîé k+1. Ïî-
ýòîìó ïðîöåññ ïîñòðîåíèÿ ïîñëåäîâàòåëüíîñòåé óõîäèò â áåñêîíå÷-
íîñòü.  ðåçóëüòàòå ìû ïîëó÷àåì, ÷òî ìíîæåñòâî âñåõ êîíå÷íûõ
ïîñëåäîâàòåëüíîñòåé åñòü E=N∪N
2
∪N
3
∪∪N
k
∪, ò.å. ýòî
îáúåäèíåíèå ñ÷åòíîãî ìíîæåñòâà ñ÷åòíûõ ïîäìíîæåñòâ ìíîæåñòâà
E. Ïîñêîëüêó cardN=
ℵℵ
ℵℵ
ℵ
0
, cardN
2
=
ℵℵ
ℵℵ
ℵ
0
2
, , cardN
k
=
ℵℵ
ℵℵ
ℵ
0
k
, òî
ìîùíîñòü ýòîãî ìíîæåñòâà îïðåäåëÿåòñÿ âûðàæåíèåì
cardE=
ℵℵ
ℵℵ
ℵ
0
+
ℵℵ
ℵℵ
ℵ
0
2
+
ℵℵ
ℵℵ
ℵ
0
3
++
ℵℵ
ℵℵ
ℵ
0
k
+ =
ℵℵ
ℵℵ
ℵ
0
.
2. Äëÿ äîêàçàòåëüñòâà ñ÷åòíîñòè íåêîòîðûõ ìíîæåñòâ ìîæíî
èñïîëüçîâàòü ñïîñîá êîäèðîâàíèÿ
1
. Íàèáîëåå ðàñïðîñòðàíåííûì
êîäîì íàòóðàëüíûõ ÷èñåë ÿâëÿåòñÿ äâîè÷íûé êîä: êàæäîìó
íàòóðàëüíîìó ÷èñëó ìîæíî åäèíñòâåííûì îáðàçîì ïîñòàâèòü â
ñîîòâåòñòâèå äâîè÷íîå ÷èñëî. Ñóùåñòâóþò ýôôåêòèâíûå ïðîöåäóðû
ïåðåâîäà ÷èñëà â äâîè÷íûé êîä è îáðàòíî, ïîýòîìó òàêîå ñîîòâåò-
ñòâèå ÿâëÿåòñÿ âçàèìíî îäíîçíà÷íûì. Óñòàíîâèâ òàêîå ñîîòâåòñòâèå,
ìû ïîëó÷àåì, íàïðèìåð, ÷òî áåñêîíå÷íîå ìíîæåñòâî âñåõ êîíå÷íûõ
äâîè÷íûõ ïîñëåäîâàòåëüíîñòåé ñ÷åòíî (íà îñíîâàíèè ïðèìåðà 1).
Äëÿ êîäèðîâàíèÿ ìîæíî èñïîëüçîâàòü íå òîëüêî äâîè÷íóþ, íî
ëþáóþ ñèñòåìó ñ÷èñëåíèÿ ñ îñíîâàíèåì k.
 êà÷åñòâå ïðèìåðà äîêàæåì, ÷òî ìíîæåñòâî âñåõ âåùåñòâåííûõ
àëãåáðàè÷åñêèõ ÷èñåë ñ÷åòíî. Àëãåáðàè÷åñêèå ÷èñëà ýòî äåéñòâè-
òåëüíûå êîðíè àëãåáðàè÷åñêèõ (ïîëèíîìèàëüíûõ) óðàâíåíèé ñ
îäíèì íåèçâåñòíûì ñ öåëûìè êîýôôèöèåíòàìè:
a
0
x
n
+ a
1
x
n1
++a
n1
x + a
n
= 0, (n≥ 1, a
0
≠ 0).
Äîêàçàòåëüñòâî. Äëÿ êàæäîãî àëãåáðàè÷åñêîãî óðàâíåíèÿ
êîëè÷åñòâî åãî äåéñòâèòåëüíûõ êîðíåé êîíå÷íî è íå ïðåâûøàåò
ñòåïåíè óðàâíåíèÿ. Òîãäà, åñëè ìû ñìîæåì ïåðåñ÷èòàòü âñå àëãåáðà-
è÷åñêèå óðàâíåíèÿ, òî ìíîæåñòâî âñåõ àëãåáðàè÷åñêèõ ÷èñåë áóäåò
ïðåäñòàâëÿòü ñîáîé îáúåäèíåíèå ìíîæåñòâ äåéñòâèòåëüíûõ êîðíåé
êàæäîãî óðàâíåíèÿ, ò.å. ýòî áóäåò îáúåäèíåíèå ñ÷åòíîãî ìíîæåñòâà
êîíå÷íûõ ìíîæåñòâ, êîòîðîå ñ÷åòíî. Ñëåäîâàòåëüíî, çàäà÷à ñâîäèòñÿ
ê äîêàçàòåëüñòâó ñ÷åòíîñòè ìíîæåñòâà àëãåáðàè÷åñêèõ óðàâíåíèé.
Àëãåáðàè÷åñêèå óðàâíåíèÿ ñ öåëûìè êîýôôèöèåíòàìè áåç
ïîòåðè îäíîçíà÷íîñòè ìîæíî ïðåäñòàâëÿòü â âèäå ñòðîêè,
çàïèñûâàÿ ïîêàçàòåëè ñòåïåíåé ïîñëå ïåðåìåííîé x, íàïðèìåð:
3x3+6x2+x2=0. Òîãäà óðàâíåíèÿ îêàçûâàþòñÿ êîíå÷íûìè
ïîñëåäîâàòåëüíîñòÿìè, ñîñòàâëåííûìè èç 14 ñèìâîëîâ: 0, 1, 2, 3, 4,
5, 6, 7, 8, 9, x, +, , =. Ïåðâûé ñèìâîë ïîñëåäîâàòåëüíîñòè íå åñòü 0.
Òîãäà ìû ìîæåì ðàññìàòðèâàòü ýòè ïîñëåäîâàòåëüíîñòè êàê ÷èñëà
â ÷åòûðíàäöàòèðè÷íîé ñèñòåìå ñ÷èñëåíèÿ.  ðåçóëüòàòå êàæäîå
óðàâíåíèå, ïðåäñòàâëåííîå êàê ïîñëåäîâàòåëüíîñòü ýòèõ ñèìâîëîâ,
ÿâëÿåòñÿ çàïèñüþ íåêîòîðîãî öåëîãî ïîëîæèòåëüíîãî ÷èñëà â ýòîé
ñèñòåìå ñ÷èñëåíèÿ, ò.å. êîäîì ýòîãî ÷èñëà â ñèñòåìå ñ÷èñëåíèÿ ñ
îñíîâàíèåì 14. Òàêèì îáðàçîì, êàæäîìó àëãåáðàè÷åñêîìó óðàâíå-
íèþ áóäåò ïîñòàâëåíî â ñîîòâåòñòâèå íåêîòîðîå íàòóðàëüíîå ÷èñëî.
Òåì ñàìûì áóäåò ïîñòðîåíî âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå
ìåæäó ìíîæåñòâîì àëãåáðàè÷åñêèõ óðàâíåíèé è ïîäìíîæåñòâîì
íàòóðàëüíûõ ÷èñåë. Èíûìè ñëîâàìè, àëãåáðàè÷åñêèå óðàâíåíèÿ
ìîãóò áûòü ïåðåñ÷èòàíû â ïîðÿäêå âîçðàñòàíèÿ íàòóðàëüíûõ ÷èñåë,
êîäàìè êîòîðûõ îíè ÿâëÿþòñÿ ïðè èíòåðïðåòàöèè âõîäÿùèõ â
óðàâíåíèÿ ñèìâîëîâ êàê öèôð ÷åòûðíàäöàòèðè÷íîé ñèñòåìû
ñ÷èñëåíèÿ. Ïîñòðîåííûé ïåðåñ÷åò äîêàçûâàåò ñ÷åòíîñòü ìíîæåñòâà
àëãåáðàè÷åñêèõ óðàâíåíèé ñ öåëûìè êîýôôèöèåíòàìè. Ñ÷åòíîñòü
Ìîùíîñòü ìíîæåñòâÃëàâà 4
1
 [Êëèíè, 1973] ýòîò ñïîñîá íàçûâàåòñÿ ìåòîäîì öèôð.
48 49
ìíîæåñòâà àëãåáðàè÷åñêèõ ÷èñåë, êàê óêàçàíî âûøå, ñëåäóåò êàê
ñ÷åòíîñòü îáúåäèíåíèÿ ñ÷åòíîãî ìíîæåñòâà êîíå÷íûõ ìíîæåñòâ.
4.6. Íåñ÷åòíûå ìíîæåñòâà
Òåîðåìà 4.10 (Êàíòîðà). Êàêîâî áû íè áûëî ìíîæåñòâî E,
ìíîæåñòâî åãî ïîäìíîæåñòâ èìååò ìîùíîñòü, ñòðîãî áîëüøóþ
ìîùíîñòè Å.
Ýòà òåîðåìà ïîêàçûâàåò, ÷òî ïîñëåäîâàòåëüíîñòü òðàíñôèíèòíûõ
êàðäèíàëüíûõ ÷èñåë íå îãðàíè÷åííà.
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò ñþðúåêöèÿ ƒ:
E→℘(E), ò.å. ñþðúåêöèÿ ƒ ìíîæåñòâà E íà ìíîæåñòâî åãî ïîäìíî-
æåñòâ ℘(E). Òîãäà äëÿ x∈E ƒ(x) ÿâëÿåòñÿ ýëåìåíòîì ℘(E), ò.å.
íåêîòîðûì ïîäìíîæåñòâîì Å. Îáîçíà÷èì ÷åðåç A ïîäìíîæåñòâî E,
îáðàçîâàííîå èç òàêèõ x∈E, ÷òî x∉ƒ(x). Òàê êàê A∈ ℘(E), òî â
E ñóùåñòâóåò ïî êðàéíåé ìåðå îäèí ýëåìåíò y, òàêîé, ÷òî ƒ(y)=A.
Åñëè y∈ƒ(y)=A, òî, ïî îïðåäåëåíèþ ìíîæåñòâà A, y∉A, ÷òî
íåâîçìîæíî. Åñëè y∉ƒ(y)=A, òî y∈A.  îáîèõ ñëó÷àÿõ ìû ïðè-
õîäèì ê ïðîòèâîðå÷èþ.
Ïîñêîëüêó, îäíàêî, ñóùåñòâóåò èíúåêöèÿ E â ℘(E), à èìåííî,
x→{x}, òî E èìååò ìîùíîñòü, ìåíüøóþ ìîùíîñòè ℘(E), à çíà÷èò,
è ñòðîãî ìåíüøóþ ìîùíîñòè ℘(E).
Òåîðåìà 4.11. Åñëè ìíîæåñòâî E áåñêîíå÷íî, òî ìíîæåñòâî
℘
f
(E) êîíå÷íûõ ïîäìíîæåñòâ E ðàâíîìîùíî ìíîæåñòâó E.
Äîêàçàòåëüñòâî. Îòîáðàæåíèå (x
1
, x
2
, ..., x
n
)→{x
1
, x
2
, ..., x
n
},
ñòàâÿùåå â ñîîòâåòñòâèå êàæäîìó ýëåìåíòó (x
1
, x
2
, ..., x
n
) èç E
n
ïîäìíîæåñòâî E, îáðàçîâàííîå èç ýòèõ ýëåìåíòîâ (íå îáÿçàòåëüíî
ðàçëè÷íûõ), ÿâëÿåòñÿ íåêîòîðîé ñþðúåêöèåé E
n
íà ìíîæåñòâî
℘
n
(E) íåïóñòûõ ïîäìíîæåñòâ E, îáðàçîâàííûõ íå áîëåå ÷åì èç n
ýëåìåíòîâ. Íî òîãäà card℘
n
(E)≤cardE
n
=cardE (òåîðåìà 4.7), è
ïîñêîëüêó card℘
n
(E)≥cardE, òî card℘
n
(E)=cardE. Ïóñòü òåïåðü
ƒ
n
: x→ƒ
n
(x) íåêîòîðàÿ áèåêöèÿ E íà ℘
n
(E). Ïîëîæèì ƒ
0
(x)≠∅
äëÿ âñåõ x∈E. Òîãäà (n,x)→ƒ
n
(x) áóäåò íåêîòîðîé ñþðúåêöèåé
N×E íà ℘
f
(E), à çíà÷èò card℘
f
(E)≤card(N×E)=
ℵℵ
ℵℵ
ℵ
0
⋅cardE=
=cardE (â ñèëó òåîðåìû 4.8, íåðàâåíñòâà
ℵℵ
ℵℵ
ℵ
0
≤cardE è òåîðåìû
4.9). Ïîñêîëüêó îáðàòíîå íåðàâåíñòâî î÷åâèäíî, îêîí÷àòåëüíî
ïîëó÷àåì card℘
f
(E)=cardE.
Çàìå÷àíèå. Õàðàêòåðèñòè÷åñêîé ôóíêöèåé íåêîòîðîãî ïîäìíî-
æåñòâà A ìíîæåñòâà E íàçûâàåòñÿ ôóíêöèÿ ϕ
A
, îïðåäåëåííàÿ
íà E è ïðèíèìàþùàÿ çíà÷åíèÿ â ìíîæåñòâå {0, 1}, òàêàÿ, ÷òî
ϕ
A
(x)=1, åñëè x∈A, è ϕ
A
(x)=0, åñëè x∉A.
Çàäàíèå ýòîé ôóíêöèè îäíîçíà÷íî îïðåäåëÿåò ïîäìíîæåñòâî
(÷àñòü) A ìíîæåñòâà E. Òîãäà êàæäîìó ïîäìíîæåñòâó áóäåò ñîîò-
âåòñòâîâàòü õàðàêòåðèñòè÷åñêèé âåêòîð, ñîñòîÿùèé èç 0 è 1. Íàïðè-
ìåð, åñëè E = {a, b, c}, òî ïîäìíîæåñòâó A = {a, c} áóäåò ñîîòâåò-
ñòâîâàòü âåêòîð ϕ
A
= <1, 0, 1>, ïîäìíîæåñòâó B = {b} âåêòîð
ϕ
B
=<0, 1, 0> è ò.ä.
Õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ ϕ(x)çàäàåò ìíîæåñòâî îòîáðàæå-
íèé ϕ: E→{0, 1}, ò.å. {0, 1}
E
. Òîãäà, íà îñíîâàíèè òåîðåìû 4.11,
ñóùåñòâóåò áèåêöèÿ ìíîæåñòâà-ñòåïåíè ℘(E) ìíîæåñòâà E íà
ìíîæåñòâî îòîáðàæåíèé ϕ: E→{0, 1}. Îòñþäà ñëåäóåò, ÷òî êàðäè-
íàëüíûì ÷èñëîì ìíîæåñòâà ℘(E) ÿâëÿåòñÿ card{0, 1}
E
=2
card E
.
Òåïåðü òåîðåìó Êàíòîðà (4.10) ìîæíî ñôîðìóëèðîâàòü ñëåäóþ-
ùèì îáðàçîì:
Êàêîâî áû íè áûëî êàðäèíàëüíîå ÷èñëî α, 2
α
>α.
 ÷àñòíîñòè, 2
ℵℵ
ℵℵ
ℵ
0
>
ℵℵ
ℵℵ
ℵ
0
. Îòñþäà ñëåäóåò, ÷òî ñóùåñòâóþò íåñ÷åò-
íûå ìíîæåñòâà.
Ìû äîêàçàëè â ïðåäûäóùåì ïàðàãðàôå, ÷òî ìíîæåñòâî âñåõ êî-
íå÷íûõ ïîñëåäîâàòåëüíîñòåé íàòóðàëüíûõ ÷èñåë ñ÷åòíî. Ðàññìîò-
ðèì òåïåðü ìíîæåñòâî âñåõ áåñêîíå÷íûõ ïîñëåäîâàòåëüíîñòåé
íàòóðàëüíûõ ÷èñåë.
Òåîðåìà 4.12. Ìíîæåñòâî âñåõ áåñêîíå÷íûõ ïîñëåäîâàòåëüíî-
ñòåé íàòóðàëüíûõ ÷èñåë íåñ÷åòíî.
Äîêàçàòåëüñòâî (1). Ïðåäïîëîæèì, ÷òî ìíîæåñòâî áåñêîíå÷íûõ
ïîñëåäîâàòåëüíîñòåé íàòóðàëüíûõ ÷èñåë ñ÷åòíî. Òîãäà åãî ìîæíî
çàíóìåðîâàòü, è êàæäàÿ ïîñëåäîâàòåëüíîñòü ïîëó÷èò ñâîé íîìåð.
Áóäåì îáîçíà÷àòü ýòè ïîñëåäîâàòåëüíîñòè S
n
, ãäå n = 1, 2, 3, .
Áóäåì èñïîëüçîâàòü õàðàêòåðèñòè÷åñêóþ ôóíêöèþ ϕ
n
(p), êîòîðàÿ
ïîêàçûâàåò, ïðèíàäëåæèò ëè íåêîòîðîå íàòóðàëüíîå ÷èñëî p ïîñëå-
äîâàòåëüíîñòè S
n
èëè íåò: ϕ
n
(p)=1, åñëè p ∈ S
n
, è ϕ
n
(p)=0, åñëè
p∉S
n
. Òîãäà êàæäîé áåñêîíå÷íîé ïîñëåäîâàòåëüíîñòè íàòóðàëüíûõ
÷èñåë S
n
áóäåò ñîîòâåòñòâîâàòü áåñêîíå÷íûé äâîè÷íûé âåêòîð ϕ
n
è
ìíîæåñòâî ýòèõ âåêòîðîâ, ñîãëàñíî ïðåäïîëîæåíèþ, òàêæå ìîæíî
çàíóìåðîâàòü. Ñîñòàâèì ýòó íóìåðàöèþ è çàïèøåì åå â âèäå
òàáëèöû:
Ýëåìåíòàìè òàáëèöû ÿâëÿþòñÿ ïîñëåäîâàòåëüíîñòè, ñîñòàâëåí-
íûå èç 0 è 1. Íà äèàãîíàëè òàáëèöû òàêæå íàõîäèòñÿ ïîñëåäîâàòåëü-
íîñòü íóëåé è åäèíèö:
Ìîùíîñòü ìíîæåñòâÃëàâà 4
1234k
ϕ
1
ϕ
1
(1) ϕ
1
(2) ϕ
1
(3) ϕ
1
(4) ϕ
1
(k)
ϕ
2
ϕ
2
(1) ϕ
2
(2) ϕ
2
(3) ϕ
2
(4) ϕ
2
(k)
ϕ
3
ϕ
3
(1) ϕ
3
(2) ϕ
3
(3) ϕ
3
(4) ϕ
3
(k)
ϕ
k
ϕ
k
(1) ϕ
k
(2) ϕ
k
(3) ϕ
k
(4) ϕ
k
(k)
50 51
ϕ
d
=ϕ
1
(1), ϕ
2
(2), ϕ
3
(3), , ϕ
k
(k),
Ñîñòàâèì àíòèäèàãîíàëüíóþ ïîñëåäîâàòåëüíîñòü ϕ
d
′ ïî ïðàâèëó:
ϕ
d
′ (1)=1 ϕ
1
(1),
ϕ
d
′ (2)=1 ϕ
2
(2),
ϕ
d
′ (k)=1ϕ
k
(k).
Ýòà ïîñëåäîâàòåëüíîñòü áóäåò îòëè÷àòüñÿ îò ëþáîé ïîñëåäîâà-
òåëüíîñòè â òàáëèöå õîòÿ áû îäíèì äèàãîíàëüíûì ýëåìåíòîì.
Ïðåäïîëîæèì, ÷òî ïîñëåäîâàòåëüíîñòü ϕ
d
′ âñå-òàêè âõîäèò â ïîñòðî-
åííûé ïåðåñ÷åò, äîïóñòèì, ñ íîìåðîì k. Òîãäà ϕ
d
′=ϕ
k
, è, ñîãëàñíî
ïðàâèëó, åå ýëåìåíòû:
ϕ
d
′(1)=ϕ
k
(1)=1ϕ
1
(1),
ϕ
d
′(2)=ϕ
k
(2)=1 ϕ
2
(2),
ϕ
d
′(k)=ϕ
k
(k)=1ϕ
k
(k).
Ïîñëåäíåå íåâîçìîæíî. Ïîëó÷åííîå ïðîòèâîðå÷èå äîêàçûâàåò
òåîðåìó.
Ìû äîêàçàëè, ÷òî ìíîæåñòâî âñåõ áåñêîíå÷íûõ äâîè÷íûõ
ïîñëåäîâàòåëüíîñòåé íåñ÷åòíî. Ñîãëàñíî çàìå÷àíèþ ê òåîðåìå 4.11,
ýòî ìíîæåñòâî åñòü íå ÷òî èíîå, êàê ìíîæåñòâî âñåõ îòîáðàæåíèé
ϕ: N→{0, 1}, ò.å. {0, 1}
N
, è ìîùíîñòü ýòîãî ìíîæåñòâà ðàâíà 2
ℵℵ
ℵℵ
ℵ
0
.
Ïîñêîëüêó êàæäàÿ áåñêîíå÷íàÿ äâîè÷íàÿ ïîñëåäîâàòåëüíîñòü
ÿâëÿåòñÿ õàðàêòåðèñòè÷åñêèì âåêòîðîì áåñêîíå÷íîãî ïîäìíîæåñòâà
íàòóðàëüíûõ ÷èñåë, ò.å., ìåæäó íèìè ñóùåñòâóåò áèåêöèÿ, òî òåì
ñàìûì äîêàçàíà íåñ÷åòíîñòü ìíîæåñòâà âñåõ áåñêîíå÷íûõ ïîñëåäî-
âàòåëüíîñòåé íàòóðàëüíûõ ÷èñåë. Íî ìíîæåñòâî âñåõ áåñêîíå÷íûõ
ïîñëåäîâàòåëüíîñòåé íàòóðàëüíûõ ÷èñåë åñòü íå ÷òî èíîå, êàê
ìíîæåñòâî âñåõ ôóíêöèé, îïðåäåëåííûõ íà N è ïðèíèìàþùèõ
çíà÷åíèÿ â N, ò.å. ìíîæåñòâî âñåõ ôóíêöèîíàëüíûõ îòîáðàæåíèé
ƒ(n): N→N, ò.å. N
N
, ñëåäîâàòåëüíî, ìîùíîñòü ýòîãî ìíîæåñòâà åñòü
ℵℵ
ℵℵ
ℵ
0
ℵℵ
ℵℵ
ℵ
0
. Ïîñêîëüêó ýòè äâà ìíîæåñòâà ðàâíîìîùíû, ìû ïîëó÷àåì,
÷òî
ℵℵ
ℵℵ
ℵ
0
ℵℵ
ℵℵ
ℵ
0
=2
ℵℵ
ℵℵ
ℵ
0
.
Ñ äðóãîé ñòîðîíû, ìíîæåñòâî âñåõ ïîñëåäîâàòåëüíîñòåé íàòó-
ðàëüíûõ ÷èñåë (êàê êîíå÷íûõ, òàê è áåñêîíå÷íûõ) åñòü ìíîæåñòâî
âñåõ ïîäìíîæåñòâ ℘(N) ìíîæåñòâà íàòóðàëüíûõ ÷èñåë, ìîùíîñòü
êîòîðîãî, ñîãëàñíî çàìå÷àíèþ ê òåîðåìå 4.11, ðàâíà 2
ℵℵ
ℵℵ
ℵ
0
. Îòñþäà
ìû ïîëó÷àåì òîò æå ðåçóëüòàò:
ℵℵ
ℵℵ
ℵ
0
ℵℵ
ℵℵ
ℵ
0
=2
ℵℵ
ℵℵ
ℵ
0
.
Ìåòîä äîêàçàòåëüñòâà íåñ÷åòíîñòè ìíîæåñòâà, èñïîëüçîâàííûé
â äàííîé òåîðåìå, íàçûâàåòñÿ äèàãîíàëüíûì ìåòîäîì Êàíòîðà.
Ìû äîêàçàëè íåñ÷åòíîñòü ìíîæåñòâà ℘(N) ñ ïîìîùüþ õàðàêòå-
ðèñòè÷åñêîé ôóíêöèè, óñòàíàâëèâàþùåé âçàèìíî îäíîçíà÷íîå
ñîîòâåòñòâèå ìåæäó ïîñëåäîâàòåëüíîñòÿìè íàòóðàëüíûõ ÷èñåë è
äâîè÷íûìè âåêòîðàìè. Îäíàêî ìû ìîãëè áû ïðèìåíèòü äèàãî-
íàëüíûé ìåòîä íåïîñðåäñòâåííî ê ïîñëåäîâàòåëüíîñòÿì íàòóðàëü-
íûõ ÷èñåë. Äîêàçàòåëüñòâî ñëåäóþùåé òåîðåìû 4.13 åùå ðàç äåìîí-
ñòðèðóåò ïðèìåíåíèå ýòîãî ìåòîäà äëÿ äîêàçàòåëüñòâà íåñ÷åòíîñòè
âñåõ äåéñòâèòåëüíûõ ÷èñåë èç èíòåðâàëà (0, 1), õîòÿ ýòîò ðåçóëüòàò
íåïîñðåäñòâåííî ñëåäóåò èç òåîðåìû 4.12. Êàæäîå äåéñòâèòåëüíîå
÷èñëî èç èíòåðâàëà (0, 1) ìîæíî ðàññìàòðèâàòü êàê áåñêîíå÷íóþ
ïîñëåäîâàòåëüíîñòü íàòóðàëüíûõ ÷èñåë, çàïèñü êîòîðîé íà÷èíàåòñÿ
ñ ñèìâîëîâ 0, Òåì ñàìûì óñòàíàâëèâàåòñÿ âçàèìíî îäíîçíà÷íîå
ñîîòâåòñòâèå ìåæäó ýòèìè äâóìÿ ìíîæåñòâàìè.
Äèàãîíàëüíûé ìåòîä Êàíòîðà èìååò è äðóãóþ ôîðìàëèçàöèþ,
íå èñïîëüçóþùóþ íåïîñðåäñòâåííîãî ïåðåñ÷åòà ýëåìåíòîâ
ìíîæåñòâà. Äëÿ òîãî, ÷òîáû ïîçíàêîìèòüñÿ ñ ýòèì ñïîñîáîì,
ðàññìîòðèì äðóãîå äîêàçàòåëüñòâî íåñ÷åòíîñòè ìíîæåñòâà âñåõ
áåñêîíå÷íûõ ïîñëåäîâàòåëüíîñòåé íàòóðàëüíûõ ÷èñåë.
Äîêàçàòåëüñòâî (2) òåîðåìû 4.12. Ïðåäïîëîæèì, ÷òî ìíîæåñòâî
âñåõ áåñêîíå÷íûõ ïîñëåäîâàòåëüíîñòåé íàòóðàëüíûõ ÷èñåë ñ÷åòíî.
Òîãäà ìîæíî ñîñòàâèòü ñïèñîê L = S
0
, S
1
, , S
k
,, â êîòîðîì êàæäàÿ
ïîñëåäîâàòåëüíîñòü ïîëó÷èò ñâîé íîìåð. Ñîñòàâèì òåïåðü åùå äâå
ïîñëåäîâàòåëüíîñòè U è U′ ñëåäóþùèì îáðàçîì: åñëè i∈S
i
, òî i∈U,
è åñëè i∉S
i
, òî i∈U′. Òàêèì îáðàçîì, â U′ ïîïàäóò âñå òå ÷èñëà
i∈N, êîòîðûå íå âõîäÿò â ïîñëåäîâàòåëüíîñòè S
i
ñ ñîîòâåòñòâó-
þùèì íîìåðîì i. (Íàïðèìåð, åñëè ÷èñëî 3 âõîäèò â ïîñëåäîâàòåëü-
íîñòü S
3
, òî îíî âîéäåò â U, à åñëè íå âõîäèò, òî â U′.) Òîãäà, ïî
ïðåäïîëîæåíèþ, ïîñëåäîâàòåëüíîñòè U è U′ òàêæå äîëæíû âîéòè
â ñïèñîê L ñ íåêîòîðûìè íîìåðàìè. Ïðåäïîëîæèì, ÷òî ïîñëåäîâà-
òåëüíîñòü U′ âõîäèò â ñïèñîê ñ íîìåðîì k: U′ =S
k
. Òîãäà íîìåð
ýòîé ïîñëåäîâàòåëüíîñòè k òîæå äîëæåí âîéòè ëèáî â U, ëèáî â U′.
Îäíàêî, åñëè k∈S
k
, òî k∈U, ñëåäîâàòåëüíî, k∉U′, ò.å. k∉S
k
, à
åñëè k∉S
k
, òî k∈U′, ò.å. k∈S
k
. Ïîëó÷åííîå ïðîòèâîðå÷èå äîêàçû-
âàåò òåîðåìó.
4.7. Ìîùíîñòü êîíòèíóóìà
Òåîðåìà 4.13 (Êàíòîðà). Ìíîæåñòâî äåéñòâèòåëüíûõ ÷èñåë èç
èíòåðâàëà (0, 1) íåñ÷åòíî.
Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà âîñïîëüçóåìñÿ äèàãîíàëü-
íûì ìåòîäîì Êàíòîðà. Áóäåì ïðåäñòàâëÿòü ëþáîå ÷èñëî èç èíòåð-
âàëà (0, 1) â âèäå áåñêîíå÷íîé äåñÿòè÷íîé äðîáè. Êîíå÷íûå äðîáè
òàêæå ïðåäñòàâèìû â òàêîì âèäå, íàïðèìåð, ÷èñëî 0,5 ìîæåò áûòü
ïðåäñòàâëåíî êàê 0,4999999...
Ïðåäïîëîæèì, ÷òî ìíîæåñòâî ýòèõ ÷èñåë ñ÷åòíî. Òîãäà èõ ìîæíî
çàïèñàòü â âèäå ñïèñêà. Ñîñòàâèì ýòîò ñïèñîê è çàïèøåì åãî â
âèäå òàáëèöû, ãäå ïðåäñòàâëåíû äåñÿòè÷íûå ÷àñòè ÷èñåë:
Ìîùíîñòü ìíîæåñòâÃëàâà 4
52 53
Ñîñòàâèì òåïåðü áåñêîíå÷íîå àíòèäèàãîíàëüíîå ÷èñëî b=b
1
b
2
...b
k
...
ïî ïðàâèëó: i-é ðàçðÿä ÷èñëà b
i
ïîëîæèì ðàâíûì 1+a
ii
, åñëè a
ii
≠9
è a
ii
=8 (èëè ëþáîìó äðóãîìó ÷èñëó, îòëè÷íîìó îò 9), åñëè a
ii
=9.
Åñëè ìíîæåñòâî ÷èñåë èç (0, 1) ñ÷åòíî, òî ïîñòðîåííîå ÷èñëî b
äîëæíî âîéòè â ýòîò ñïèñîê ñ êàêèì-ëèáî íîìåðîì, íàïðèìåð, ñ
íîìåðîì k: b =a
k
. Íî òîãäà b
1
=a
k1
=a
11
+1, b
2
= a
k2
=a
22
+1,...,
b
k
=a
kk
= a
kk
+1, ÷òî íåâîçìîæíî. Ñëåäîâàòåëüíî, ìíîæåñòâî äåé-
ñòâèòåëüíûõ ÷èñåë èç èíòåðâàëà (0,1) íåñ÷åòíî.
Îïðåäåëåíèå 4.3. Ìîùíîñòü ìíîæåñòâà (0,1) íàçûâàþò ìîùíîñòüþ
êîíòèíóóìà. Ìîùíîñòü êîíòèíóóìà îáîçíà÷àåòñÿ ñèìâîëîìC.
Ìîùíîñòü êîíòèíóóìà ýòî ìîùíîñòü ìíîæåñòâà äåéñòâè-
òåëüíûõ ÷èñåë R, ò.å. card R=C, èáî ñóùåñòâóåò áèåêöèÿ (0,1)→R,
íàïðèìåð, x→log x/(1x).
Ïðèìåðû.
1. ïðåäûäóùåì ðàçäåëå ìû äîêàçàëè, ÷òî ìíîæåñòâî àëãåáðà-
è÷åñêèõ âåùåñòâåííûõ ÷èñåë ñ÷åòíî. Âåùåñòâåííûå ÷èñëà, íå ÿâ-
ëÿþùèåñÿ àëãåáðàè÷åñêèìè, íàçûâàþòñÿ òðàíñöåíäåíòíûìè.
(Òðàíñöåíäåíòíûìè ÿâëÿþòñÿ ÷èñëà e è π.) Ïîñêîëüêó ìíîæåñòâî
àëãåáðàè÷åñêèõ ÷èñåë ñ÷åòíî, à ìíîæåñòâî âåùåñòâåííûõ ÷èñåë
íåñ÷åòíî, òî ñóùåñòâóþò òðàíñöåíäåíòíûå ÷èñëà è äàæå «áîëüøèí-
ñòâî» âåùåñòâåííûõ ÷èñåë òðàíñöåíäåíòíî.
2. Ìíîæåñòâî âñåõ òî÷åê R
n
ñ ðàöèîíàëüíûìè èëè àëãåáðàè÷åñêèìè
êîîðäèíàòàìè ñ÷åòíî, òàê êàê åãî êàðäèíàëüíîå ÷èñëî ðàâíî
ℵℵ
ℵℵ
ℵ
0
n
=
ℵℵ
ℵℵ
ℵ
0
, à ìíîæåñòâî âñåõ òî÷åê R
n
ñ âåùåñòâåííûìè êîîðäèíàòàìè
íåñ÷åòíî è ðàâíî êîíòèíóóìó.
Òåîðåìà 4.14. Èìåþò ìåñòî ðàâåíñòâà:
m⋅C=
ℵℵ
ℵℵ
ℵ
0
⋅C=C⋅C=C
m
= =C
ℵℵ
ℵℵ
ℵ
0
=C, ãäå m≥1 öåëîå.
Äîêàçàòåëüñòâî. Âñå ýòè êàðäèíàëüíûå ÷èñëà íå áîëüøå C
ℵℵ
ℵℵ
ℵ
0
è
íå ìåíüøå C, ïîýòîìó äîñòàòî÷íî ïîêàçàòü, ÷òî C
ℵℵ
ℵℵ
ℵ
0
=Ñ.
Äåéñòâèòåëüíî, C
ℵℵ
ℵℵ
ℵ
0
= (2
ℵℵ
ℵℵ
ℵ
0
)
ℵℵ
ℵℵ
ℵ
0
=
2
0
2
ℵ
=2
ℵℵ
ℵℵ
ℵ
0
= Ñ.
Îäíàêî, ôàêò: 2
ℵℵ
ℵℵ
ℵ
0
= Ñ òðåáóåò äîêàçàòåëüñòâà.
Åñëè âçÿòü ÷èñëà èç Å = (0, 1), òàêèå, ÷òî â èõ èçîáðàæåíèè
ïðèñóòñòâóþò ÷èñëà 0, 1, 2, , 7, òî ýòî ìíîæåñòâî áóäåò ðàâíîìîùíî
ìíîæåñòâó {0, 1, 2, 3, 4, 5, 6, 7}
N
, ñëåäîâàòåëüíî, åãî ìîùíîñòü ðàâíà
8
ℵℵ
ℵℵ
ℵ
0
. Ñàìî ìíîæåñòâî Å èìååò ìîùíîñòü ≤10
ℵℵ
ℵℵ
ℵ
0
(ìû ïèøåì ≤ èç-çà
äâîÿêîãî äåñÿòè÷íîãî èçîáðàæåíèÿ ÷èñåë). Ïîýòîìó 8
ℵℵ
ℵℵ
ℵ
0
≤cardE≤10
ℵℵ
ℵℵ
ℵ
0
,
îòêóäà 2
ℵℵ
ℵℵ
ℵ
0
≤cardE≤16
ℵℵ
ℵℵ
ℵ
0
=(2
4
)
ℵℵ
ℵℵ
ℵ
0
=2
4
ℵℵ
ℵℵ
ℵ
0
=2
ℵℵ
ℵℵ
ℵ
0
, ñëåäîâàòåëüíî
cardE=2
ℵℵ
ℵℵ
ℵ
0
. Ñ äðóãîé ñòîðîíû, card E =C. Ñëåäîâàòåëüíî, 2
ℵℵ
ℵℵ
ℵ
0
=C.
Ñëåäñòâèå 1. Ìíîæåñòâî êîìïëåêñíûõ ÷èñåë èìååò ìîùíîñòü
êîíòèíóóìà (ïîñêîëüêó îíî ðàâíîìîùíî R
2
: C
2
=C).
Ñëåäñòâèå 2. Ëþáîå âåêòîðíîå ïðîñòðàíñòâî êîíå÷íîãî ÷èñëà
èçìåðåíèé n íàä ïîëåì âåùåñòâåííûõ èëè êîìïëåêñíûõ ÷èñåë èìååò
ìîùíîñòü êîíòèíóóìà.
Ñëåäñòâèå 3. Ìíîæåñòâî âñåõ ïîñëåäîâàòåëüíîñòåé âåùåñòâåí-
íûõ ÷èñåë è ïîñëåäîâàòåëüíîñòåé êîìïëåêñíûõ ÷èñåë èìååò
ìîùíîñòü êîíòèíóóìà, èáî èõ êàðäèíàëüíîå ÷èñëî ðàâíî C
ℵℵ
ℵℵ
ℵ
0
=Ñ.
Ñëåäñòâèå 4. Ìíîæåñòâî Å íåïðåðûâíûõ âåùåñòâåííûõ ôóíêöèé
âåùåñòâåííîé ïåðåìåííîé èìååò ìîùíîñòü êîíòèíóóìà. Êàæäîé òàêîé
ôóíêöèè ìîæíî ïîñòàâèòü â ñîîòâåòñòâèå ïîñëåäîâàòåëüíîñòü
âåùåñòâåííûõ ÷èñåë çíà÷åíèé ôóíêöèè â òî÷êàõ ñ ðàöèîíàëüíûìè
àáñöèññàìè. Ìîæíî ñ÷èòàòü, ÷òî ýòè òî÷êè âçàèìíî îäíîçíà÷íû ñ N,
òàê êàê Q ñ÷åòíî. Ïîñëåäîâàòåëüíîñòü âåùåñòâåííûõ ÷èñåë, ñîîòâåò-
ñòâóþùàÿ íåïðåðûâíîé ôóíêöèè, åå ïîëíîñòüþ îïðåäåëÿåò. Ñëåäîâà-
òåëüíî, ñóùåñòâóåò áèåêöèÿ ìíîæåñòâà íåïðåðûâíûõ ôóíêöèé íà ÷àñòü
ìíîæåñòâà ïîñëåäîâàòåëüíîñòåé âåùåñòâåííûõ ÷èñåë. Çíà÷èò, ýòî
ìíîæåñòâî Å èìååò ìîùíîñòü, íå áîëüøóþ Ñ. À òàê êàê ýòî îòîáðàæå-
íèå, êîòîðîå êàæäîé íåïðåðûâíîé ôóíêöèè ñòàâèò â ñîîòâåòñòâèå åå
çíà÷åíèå â îäíîé òî÷êå, íàïðèìåð, â íà÷àëå êîîðäèíàò, ÿâëÿåòñÿ
ñþðúåêöèåé Å íà R, òî Å èìååò ìîùíîñòü, íå ìåíüøóþ ìîùíîñòè
êîíòèíóóìà. Ñëåäîâàòåëüíî, Å èìååò ìîùíîñòü Ñ.
Ñëåäñòâèå 5. Ìíîæåñòâî âñåõ âåùåñòâåííûõ ôóíêöèé âåùå-
ñòâåííîé ïåðåìåííîé èìååò ìîùíîñòü, ñòðîãî áîëüøóþ ìîùíîñòè
êîíòèíóóìà, èáî åãî ìîùíîñòü ðàâíà Ñ
Ñ
(à åñëè ñî çíà÷åíèÿìè 0 è
1 òî 2
C
), à Ñ
Ñ
= (2
ℵℵ
ℵℵ
ℵ
0
)
C
= 2
ℵℵ
ℵℵ
ℵ
0
C
= 2
Ñ
>Ñ. Òàêèì îáðàçîì, áîëüøèíñòâî
ôóíêöèé èìååò íå ìåíåå îäíîé òî÷êè ðàçðûâà.
4.8. Êîíòèíóóì-ãèïîòåçà
Ïðè èññëåäîâàíèè ìîùíîñòåé áåñêîíå÷íûõ ìíîæåñòâ áûë
óñòàíîâëåí òîò ôàêò, ÷òî ìíîæåñòâî êàðäèíàëüíûõ ÷èñåë ëèíåéíî
óïîðÿäî÷åíî. Ëèíåéíàÿ óïîðÿäî÷åííîñòü îçíà÷àåò, ÷òî äëÿ êàæäîãî
êàðäèíàëüíîãî ÷èñëà ñóùåñòâóåò íåïîñðåäñòâåííî ñëåäóþùåå çà
íèì ÷èñëî.
ℵℵ
ℵℵ
ℵ
0
ÿâëÿåòñÿ íàèìåíüøèì òðàíñôèíèòíûì ÷èñëîì.
Îäíàêî íè÷åãî íå èçâåñòíî î òîì, êàêîå òðàíñôèíèòíîå ÷èñëî ÿâëÿ-
åòñÿ ñëåäóþùèì çà
ℵℵ
ℵℵ
ℵ
0
. Ñóùåñòâóåò ëèøü ïðåäïîëîæåíèå, êîòîðîå
íàçûâàåòñÿ êîíòèíóóì-ãèïîòåçîé.
Ìîùíîñòü ìíîæåñòâÃëàâà 4
123k
a
1
a
11
a
12
a
13
a
1k
a
2
a
21
a
22
a
23
a
2k
a
3
a
31
a
32
a
33
a
3k
a
k
a
k1
a
k2
a
k3
a
kk
54 55
Êîíòèíóóì-ãèïîòåçà. Êàðäèíàëüíîå ÷èñëî 2
ℵℵ
ℵℵ
ℵ
0
íåïîñðåäñòâåííî
ñëåäóåò çà
ℵℵ
ℵℵ
ℵ
0
.
Ýòî îçíà÷àåò, ÷òî
ℵℵ
ℵℵ
ℵ
0
< 2
ℵℵ
ℵℵ
ℵ
0
è ìåæäó íèìè íåò íèêàêîãî äðóãîãî
êàðäèíàëüíîãî ÷èñëà. Ýòîò ôàêò òðåáóåò äîêàçàòåëüñòâà. Ìû íè÷åãî
íå çíàåì î ìíîæåñòâàõ, êîòîðûå íåñ÷åòíû, íî ìåíåå, ÷åì êîíòèíó-
àëüíû, íå çíàåì äàæå, ñóùåñòâóþò ëè òàêèå ìíîæåñòâà. Îòñóòñòâèå
ïðèìåðîâ ïîäîáíûõ ìíîæåñòâ íå ÿâëÿåòñÿ äîêàçàòåëüñòâîì íåâîç-
ìîæíîñòè èõ ñóùåñòâîâàíèÿ, ïîýòîìó óòâåðæäåíèå î íåïîñðåä-
ñòâåííîì ñëåäîâàíèè 2
ℵℵ
ℵℵ
ℵ
0
çà
ℵℵ
ℵℵ
ℵ
0
ÿâëÿåòñÿ ãèïîòåçîé, à íå òåîðåìîé.
Ìîæíî ïîéòè äàëüøå è ñôîðìóëèðîâàòü áîëåå îáùåå óòâåðæäåíèå.
Îáîáùåííàÿ êîíòèíóóì-ãèïîòåçà çàêëþ÷àåòñÿ â ïðåäïîëîæå-
íèè î òîì, ÷òî äëÿ ëþáîãî êàðäèíàëüíîãî ÷èñëà
α
êàðäèíàëüíîå
÷èñëî 2
α
íåïîñðåäñòâåííî ñëåäóåò çà
α
. Îòñþäà ñëåäóåò, ÷òî ïîñëåäî-
âàòåëüíîñòü êàðäèíàëüíûõ ÷èñåë íåîãðàíè÷åííà:
ℵℵ
ℵℵ
ℵ
0
<2
ℵℵ
ℵℵ
ℵ
0
<
0
2
2
ℵ
<
Äåéñòâèòåëüíî, 2
ℵℵ
ℵℵ
ℵ
0
åñòü ìîùíîñòü ìíîæåñòâà-ñòåïåíè ℘(N)
(âìåñòî N ìîæåò áûòü ëþáîå äðóãîå áåñêîíå÷íîå ñ÷åòíîå ìíîæå-
ñòâà). Íî èç ýòîãî ìíîæåñòâà ìîæíî îáðàçîâàòü îïÿòü ìíîæåñòâî
âñåõ åãî ïîäìíîæåñòâ ℘(℘(N)), ìîùíîñòü êîòîðîãî åñòü
0
2
2
ℵ
, è
ýòîò ïðîöåññ ìîæíî ïðîäîëæàòü äî áåñêîíå÷íîñòè. Îòñþäà ñëåäóåò,
÷òî íå ñóùåñòâóåò íàèáîëüøåãî òðàíñôèíèòíîãî ÷èñëà.
Ïîïûòêè äîêàçàòü êîíòèíóóì-ãèïîòåçó â êà÷åñòâå òåîðåìû áûëè
áåçóñïåøíû, à 1963 ã. Ï. Êîýí (ñì. [Êîýí, 1973]) äîêàçàë, ÷òî
êîíòèíóì-ãèïîòåçà íåðàçðåøèìà åå íåâîçìîæíî íè äîêàçàòü, íè
îïðîâåðãíóòü, ìîæíî ëèøü ïðèíÿòü åå èëè ïðîòèâîïîëîæíîå åé
óòâåðæäåíèå â êà÷åñòâå àêñèîìû.
4.9. Ïàðàäîêñû òåîðèè ìíîæåñòâ
Êàíòîðîâñêóþ òåîðèþ ìíîæåñòâ â òîì âèäå, êàê ìû ñ íåé ïîçíà-
êîìèëèñü, íàçûâàþò «íàèâíîé» òåîðèåé ìíîæåñòâ. Êàíòîðîâñêîå
ïîíÿòèå ìíîæåñòâà îòñûëàåò íàñ ê íàøåé èíòóèöèè ïðè ðåøåíèè
âîïðîñà î òîì, êàêèå îáúåêòû ñ÷èòàòü ìíîæåñòâàìè. Ïîïûòêè
ïîñòðîèòü òåîðèþ ìíîæåñòâ íà èíòóèòèâíîé îñíîâå, ïðè êîòîðîé
îòñóòñòâóåò ÷åòêîå ìàòåìàòè÷åñêîå îïðåäåëåíèå ìíîæåñòâà, ïðèâåëè
ê âîçíèêíîâåíèþ ïàðàäîêñîâ.
Îäèí èç ïåðâûõ ïàðàäîêñîâ òåîðèè ìíîæåñòâ áûë îòêðûò ñàìèì
Êàíòîðîì â 1899 ãîäó.
Èç òåîðåìû Êàíòîðà (4.10) ñëåäóåò, ÷òî êàêîâî áû íè áûëî
òðàíñôèíèòíîå ÷èñëî, ñóùåñòâóåò áîëüøåå òðàíñôèíèòíîå ÷èñëî,
è ÷òî íàèáîëüøåãî òðàíñôèíèòíîãî ÷èñëà íå ñóùåñòâóåò. Îäíàêî,
îïðåäåëåíèå ïîíÿòèÿ ìíîæåñòâà íå íàêëàäûâàåò íèêàêèõ îãðàíè÷å-
íèé íà ðàññìàòðèâàåìûå ìíîæåñòâà. Ìîæíî ðàññìîòðåòü óíèâåð-
ñàëüíîå ìíîæåñòâî, ýëåìåíòàìè êîòîðîãî ÿâëÿþòñÿ âñå âîçìîæíûå
ìíîæåñòâà. Î÷åâèäíî, ÷òî òàêîå ìíîæåñòâî âñåõ ìíîæåñòâ ñîäåð-
æèò áîëüøå ýëåìåíòîâ, ÷åì ëþáîå äðóãîå ìíîæåñòâî. Íî åñëè ýòî
òàê, òî êàê òîãäà ìîæåò ñóùåñòâîâàòü òðàíñôèíèòíîå ÷èñëî, áîëüøåå
òðàíñôèíèòíîãî ÷èñëà, êîòîðîå ñîîòâåòñòâóåò ýòîìó ìíîæåñòâó?
Ïàðàäîêñ Áåðòðàíà Ðàññåëà áûë îòêðûò â 1902 ãîäó è ñâÿçàí ñ
îäíèì ëèøü îïðåäåëåíèåì ïîíÿòèÿ ìíîæåñòâà. Ýòè ïàðàäîêñû, à
òàêæå äðóãèå, íàïðèìåð, ïàðàäîêñ Áóðàëè-Ôîðòè (1897 ã.), ñâÿçàí-
íûé ñ òåîðèåé ïîðÿäêîâûõ ÷èñåë, íàçûâàþò ëîãè÷åñêèìè ïàðàäîêñà-
ìè. Äðóãóþ ãðóïïó ïàðàäîêñîâ óñëîâíî íàçûâàþò ñåìàíòè÷åñêèìè.
 1905 ãîäó áûë îòêðûò ïàðàäîêñ Ðèøàðà, êîòîðûé ìîæíî ñôîð-
ìóëèðîâàòü ñëåäóþùèì îáðàçîì. Ðàññìîòðèì êîíå÷íûé àëôàâèò,
ñîñòîÿùèé èç 33 áóêâ ðóññêîãî àëôàâèòà è äâóõ ðàçäåëèòåëüíûõ
ñèìâîëîâ: ïðîáåëà è çàïÿòîé. Áóäåì ïîíèìàòü ïîä «ôðàçîé» êîíå÷-
íóþ ïîñëåäîâàòåëüíîñòü áóêâ, âêëþ÷àþùóþ ïðîáåë èëè çàïÿòóþ â
ñåðåäèíå ïîñëåäîâàòåëüíîñòè â êà÷åñòâå ðàçäåëèòåëåé. Êàæäóþ òàêóþ
ïîñëåäîâàòåëüíîñòü ìîæíî ðàññìàòðèâàòü êàê ÷èñëî â 35-ðè÷íîé
ñèñòåìå ñ÷èñëåíèÿ. Íåêîòîðûå òàêèå ôðàçû ÿâëÿþòñÿ îïèñàíèÿìè
îäíîìåñòíûõ àðèôìåòè÷åñêèõ ôóíêöèé íà åñòåñòâåííîì ÿçûêå,
íàïðèìåð, «à â êâàäðàòå», «ìîäóëü êîðíÿ êâàäðàòíîãî èç à». Èç
ìíîæåñòâà âñåõ ïîñëåäîâàòåëüíîñòåé âû÷åðêíåì ôðàçû, íå
ÿâëÿþùèåñÿ îïèñàíèÿìè ôóíêöèé.  ðåçóëüòàòå ìû ìîæåì ïîëó÷èòü
ïîñëåäîâàòåëüíîñòü P
0
, P
1
, P
2
, âñåõ òàêèõ îïèñàíèé. Îáîçíà÷èì
ôóíêöèè, îïèñûâàåìûå ýòèìè ôðàçàìè, ÷åðåç f
0
(a), f
1
(a), f
2
(a), .
Ðàññìîòðèì òåïåðü ôðàçó P, îïèñûâàþùóþ ôóíêöèþ f(a)=f
a
(a)+1:
«Ôóíêöèÿ, çíà÷åíèå êîòîðîé äëÿ ëþáîãî àðãóìåíòà a, ÿâëÿþùåãîñÿ
íàòóðàëüíûì ÷èñëîì, ðàâíî óâåëè÷åííîìó íà åäèíèöó çíà÷åíèþ äëÿ
ýòîãî æå àðãóìåíòà òîé ôóíêöèè, êîòîðàÿ îïðåäåëÿåòñÿ ôðàçîé,
ñîîòâåòñòâóþùåé â ïåðåñ÷åòå P
0
, P
1
, P
2
, ýòîìó íàòóðàëüíîìó ÷èñëó».
Ýòà ôðàçà òîæå îïèñûâàåò àðèôìåòè÷åñêóþ ôóíêöèþ, ñëåäîâàòåëü-
íî, P âõîäèò â ïåðåñ÷åò P
0
, P
1
, P
2
, ñ íåêîòîðûì íîìåðîì, íàïðèìåð,
k. Òîãäà f(a)=f
k
(a). Ïîäñòàâëÿÿ k âìåñòî a, ïîëó÷èì f(k)=f
k
(k),
îäíàêî, ïî îïðåäåëåíèþ ýòîé ôóíêöèè, f(k)=f
k
(k)+1, ÷òî íåâîçìîæíî.
Ýòîò ïàðàäîêñ ñâÿçàí ñ òåì, ÷òî ìíîæåñòâî ôðàç äàííîãî ÿçûêà ÿâëÿåòñÿ
ñ÷åòíî-áåñêîíå÷íûì, è, ñëåäîâàòåëüíî, ìíîæåñòâî îïðåäåëåííûõ âûøå
ôóíêöèé òàêæå ÿâëÿåòñÿ ñ÷åòíî-áåñêîíå÷íûì, â òî âðåìÿ, êàê ìíîæåñòâî
âñåõ àðèôìåòè÷åñêèõ ôóíêöèé íåñ÷åòíî (ñì. òåîðåìó 4.12).
Ïîõîæèé ïàðàäîêñ ïðåäëîæèë Áåððè. Ðàññìîòðèì âûðàæåíèå:
«Íàèìåíüøåå íàòóðàëüíîå ÷èñëî, êîòîðîå íåëüçÿ íàçâàòü ïîñðåäñòâîì
ìåíüøå, ÷åì òðèäöàòè òðåõ ñëîãîâ». Ýòî âûðàæåíèå íàçûâàåò íåêîòîðîå
íàòóðàëüíîå ÷èñëî. Òîãäà, ñîãëàñíî ýòîìó îïðåäåëåíèþ, ýòî ÷èñëî
íåëüçÿ íàçâàòü ïîñðåäñòâîì ìåíåå, ÷åì 33 ñëîãîâ. Íî äàííîå âûðàæåíèå
îïðåäåëÿåò ýòî ÷èñëî, ïðè÷åì ñ ïîìîùüþ ðîâíî 32 ñëîãîâ!
Ìîùíîñòü ìíîæåñòâÃëàâà 4
56 57
Ýòè ïàðàäîêñû ðîäñòâåííû èçâåñòíûì åùå â äðåâíîñòè ñåìàíòè-
÷åñêèì ïàðàäîêñàì. Äðåâíåãðå÷åñêîìó ôèëîñîôó ñ îñòðîâà Êðèò
Ýïèìåíèäó (VI äî í.ý.) ïðèïèñûâàåòñÿ âûñêàçûâàíèå: «Âñå êðèòÿ-
íå ëæåöû». Ó÷èòûâàÿ, ÷òî ñàì Ýïèìåíèä ÿâëÿåòñÿ êðèòÿíèíîì,
íåâîçìîæíî ñêàçàòü, èñòèííî ýòî óòâåðæäåíèå èëè ëîæíî. Äðóãîé
ôèëîñîô, Ýâáóëèä (VI äî í.ý.), òîò æå ïàðàäîêñ ñôîðìóëèðîâàë
òàêèì îáðàçîì: «Òî, ÷òî ÿ ñåé÷àñ ãîâîðþ, ëîæü» («ß ëãó»). Ýòîò
ïàðàäîêñ èçâåñòåí êàê ïàðàäîêñ «ëæåöà», äëÿ êîòîðîãî ñóùåñòâóåò
ìíîæåñòâî ìîäèôèêàöèé.
 äðåâíåé «äèëåììå êðîêîäèëà» êðîêîäèë óêðàë ðåáåíêà, íî
îáåùàë âåðíóòü åãî îòöó, åñëè òîò óãàäàåò, âåðíåò ëè åìó êðîêîäèë
ðåáåíêà. Íåðàçðåøèìàÿ äèëåììà âñòàåò ïåðåä êðîêîäèëîì, åñëè
îòåö ñêàæåò åìó, ÷òî îí íå âåðíåò ðåáåíêà.
Ìèññèîíåð, ïîïàâøèé ê ëþäîåäàì, ìîæåò ïðîèçíåñòè êàêóþ-íèáóäü
ôðàçó, è, åñëè îíà îêàæåòñÿ èñòèííîé, òî åãî ñâàðÿò, à åñëè ëîæíîé, òî
çàæàðÿò. ×òî äîëæåí ñêàçàòü ìèññèîíåð, ÷òîáû îñòàòüñÿ æèâûì?
Îòêðûòèå ïàðàäîêñîâ â êàíòîðîâñêîé òåîðèè ìíîæåñòâ ñòàâèëî
ïîä ñîìíåíèå ïîñëåäíèå äîñòèæåíèÿ â îáëàñòè ìàòåìàòèêè è ïðèâå-
ëî ê êðèçèñó îñíîâ ìàòåìàòèêè
1
. Ê ýòîìó âðåìåíè áîëüøèíñòâî
ðàçäåëîâ ìàòåìàòèêè óæå èñïîëüçîâàëè òåîðåòèêî-ìíîæåñòâåííûå
ïîíÿòèÿ. Òåîðèÿ ìíîæåñòâ ëåãëà â îñíîâó íîâîé íàóêè ôîðìàëü-
íîé (ìàòåìàòè÷åñêîé) ëîãèêè, êîòîðàÿ â êîíöå XIX-ãî íà÷àëå
XX-ãî âåêà áóðíî ðàçâèâàëàñü. Îïóáëèêîâàííûå â 1879 1903 ã.ã.
ðàáîòû íåìåöêîãî ó÷åíîãî Ãîòëèáà Ôðåãå è èññëåäîâàíèÿ èòàëüÿí-
ñêîãî ìàòåìàòèêà Ïåàíî ïîëîæèëè íà÷àëî íîâûì íàïðàâëåíèÿì â
ìàòåìàòè÷åñêîé ëîãèêå. Ïåàíî õîòåë ïîñòðîèòü ìàòåìàòèêó íà áàçå
ëîãè÷åñêîãî èñ÷èñëåíèÿ, à Ôðåãå ðàáîòàë íàä ëîãè÷åñêèì îáîñíîâà-
íèåì ìàòåìàòè÷åñêîé íàóêè. Ïåðâàÿ ÷àñòü åãî òðóäà «Îñíîâàíèÿ
àðèôìåòèêè» ïîÿâèëàñü â 1903ã., è â ýòî æå âðåìÿ ïðîèçîøëî
îäíî èç ñàìûõ òðàãè÷åñêèõ ñîáûòèé â èñòîðèè ìàòåìàòèêè. Áåðòðàí
Ðàññåë ñîîáùèë î ñâîåì ïàðàäîêñå Ôðåãå, êîòîðûé ïåðåä ýòèì
òîëüêî ÷òî çàêîí÷èë ïîñëåäíèé òîì ñâîåãî ãðîìàäíîãî òðàêòàòà ïî
îñíîâàíèÿì àðèôìåòèêè. Â êîíöå âòîðîãî òîìà Ôðåãå ïîäòâåðäèë
ïîëó÷åíèå ýòîãî ñîîáùåíèÿ: «Çàêîí÷èâ ñâîé òðóä, ó÷åíûé îáíàðó-
æèâàåò íåñîñòîÿòåëüíîñòü èñõîäíûõ ïîçèöèé âðÿä ëè ìîæíî
ïðèäóìàòü ÷òî-íèáóäü áîëåå íåæåëàòåëüíîå. Èìåííî â ýòîì ïîëîæå-
íèè îêàçàëñÿ ÿ ïîñëå ïîëó÷åíèÿ ïèñüìà ìèñòåðà Áåðòðàíà Ðàññåëà,
êîãäà ðóêîïèñü áûëà ïî÷òè ãîòîâà ê íàáîðó.» Ýòèìè ñëîâàìè Ôðåãå
çàêîí÷èë ñâîé äâåíàäöàòèëåòíèé òðóä.
Ïîñêîëüêó òåîðèÿ ìíîæåñòâ áûëà ïîëîæåíà â îñíîâó ìàòåìàòè-
êè, îáíàðóæåííûå ïàðàäîêñû ïîñòàâèëè ïîä ñîìíåíèå äîñòîâåð-
íîñòü âñåé ìàòåìàòè÷åñêîé íàóêè â öåëîì. Âûõîä èç ýòîãî êðèçèñà
áûë äëèòåëüíûì è òðóäíûì.
Ïðè âíèìàòåëüíîì ðàññìîòðåíèè ëîãè÷åñêèõ ïàðàäîêñîâ òåîðèè
ìíîæåñòâ ìîæíî çàìåòèòü, ÷òî îíè èìåþò ðÿä îáùèõ ñâîéñòâ,
ñâÿçàííûõ ñ ñàìèì îïðåäåëåíèåì ìíîæåñòâà. Âî-ïåðâûõ, îíè
äîïóñêàþò ñóùåñòâîâàíèå «ñëèøêîì áîëüøèõ» ìíîæåñòâ, òàêèõ
êàê «ìíîæåñòâî âñåõ ìíîæåñòâ» â ïàðàäîêñå Êàíòîðà; âî-âòîðûõ,
îíè äîïóñêàþò èìïðåäèêàòèâíûå îïðåäåëåíèÿ ìíîæåñòâ, ò.å. òàêèå
îïðåäåëåíèÿ, â êîòîðûõ ôèãóðèðóåò êàêîå-òî ìíîæåñòâî S è ýëåìåíò
x èç S, îïðåäåëåíèå êîòîðîãî çàâèñèò îò S. Òàêèå îïðåäåëåíèÿ
ÿâëÿþòñÿ â èçâåñòíîì ñìûñëå êðóãîâûìè: îïðåäåëÿåìîå ïîíÿòèå
çàâèñèò ñàìî îò ñåáÿ. Ìîæíî áûëî áû çàïðåòèòü èñïîëüçîâàíèå
òàêèõ îïðåäåëåíèé, îäíàêî èñêëþ÷èòü èõ ïîëíîñòüþ èç ìàòåìàòèêè
íåëüçÿ. Ïðèìåðîì òàêîãî îïðåäåëåíèÿ ÿâëÿåòñÿ îïðåäåëåíèå òî÷íîé
âåðõíåé ãðàíè óïîðÿäî÷åííîãî ìíîæåñòâà ýòî íàèìåíüøèé ýëåìåíò
ìíîæåñòâà âñåõ âåðõíèõ ãðàíåé äàííîãî ìíîæåñòâà.
4.10. Ïðåîäîëåíèå ïàðàäîêñîâ
Äëÿ âûõîäà èç ñîçäàâøåãîñÿ ïîëîæåíèÿ áûëî ïðåäëîæåíî ïî-
ñòðîèòü ñòðîãîå àêñèîìàòè÷åñêîå îïðåäåëåíèå ïîíÿòèÿ ìíîæåñòâà
è îãðàíè÷èòüñÿ ðàññìîòðåíèåì ìíîæåñòâ, óäîâëåòâîðÿþùèõ ýòèì
àêñèîìàì. Ýòè àêñèîìû ñôîðìóëèðîâàíû òàê, ÷òî èç íèõ íå âûâîäè-
Ìîùíîñòü ìíîæåñòâÃëàâà 4
1
Èñòîðèÿ ìàòåìàòèêè óæå çíàëà ïîäîáíûå êðèçèñû. Ïåðâûé êðèçèñ îñíîâ
ìàòåìàòèêè ïðîèçîøåë â V âåêå äî í.ý. Îí áûë âûçâàí íåîæèäàííûì îòêðûòè-
åì: îêàçàëîñü, ÷òî íå âñå îäíîðîäíûå ãåîìåòðè÷åñêèå âåëè÷èíû ñîèçìåðèìû
äðóã ñ äðóãîì. Áûëî, íàïðèìåð, ïîêàçàíî, ÷òî äèàãîíàëü êâàäðàòà íå ñîèçìåðè-
ìà ñ åãî ñòîðîíîé. Ýòî íàíåñëî ãðîìàäíûé óùåðá ó÷åíèþ Ïèôàãîðà î âåëè÷è-
íàõ, êîòîðîå ïîëàãàëîñü íà ñîèçìåðèìîñòü îäíîðîäíûõ ãåîìåòðè÷åñêèõ âåëè-
÷èí. Ïèôàãîðîâà òåîðèÿ áûëà îòáðîøåíà êàê íåîáîñíîâàííàÿ. Ïåðâûé êðèçèñ
ïðåîäîëåâàëñÿ íåëåãêî. Êîíåö êðèçèñà îòíîñèòñÿ ê 370 ã. äî í.ý. è ñâÿçàí ñ
èìåíåì âûäàþùåãîñÿ ìàòåìàòèêà Åâäîêëà ïîñòðîåííàÿ èì òåîðèÿ âåëè÷èí
è ó÷åíèå î íåñîèçìåðèìîñòÿõ â îñíîâíîì ñîâïàäàåò ñ ñîâðåìåííîé òåîðèåé
èððàöèíàëüíûõ ÷èñåë, ïîñòðîåííîé Ðèõàðäîì Äåäåêèíäîì â 1872 ã. Ýòîò
êðèçèñ ñûãðàë âûäàþùóþñÿ ðîëü â ñòàíîâëåíèè ìàòåìàòè÷åñêîãî ìåòîäà.
Îòêðûòèÿ Íüþòîíà è Ëåéáíèöà, çàðîæäåíèå àíàëèçà â êîíöå XVII â. ïðèâåëî
êî âòîðîìó êðèçèñó îñíîâ ìàòåìàòèêè. Ïîñëåäîâàòåëè Íüþòîíà è Ëåéáíèöà,
óâëå÷åííûå îãðîìíûìè ïðàêòè÷åñêèìè âîçìîæíîñòÿìè è ñèëîé ñâîåãî ìåòîäà,
ìàëî çàáîòèëèñü î ïðî÷íîñòè ôóíäàìåíòà, íà êîòîðîì áûë ïîñòðîåí àíàëèç,
òàê ÷òî íå äîêàçàòåëüñòâà ãàðàíòèðîâàëè ïðàâèëüíîñòü ðåçóëüòàòîâ, à íàîáîðîò,
ñïðàâåäëèâîñòü ðåçóëüòàòîâ äàâàëà óâåðåííîñòü â ïðàâèëüíîñòè äîêàçàòåëüñòâ.
Ñ òå÷åíèåì âðåìåíè ïàðàäîêñû è ïðîòèâîðå÷èÿ âîçíèêàëè âñå â áîëüøåì
êîëè÷åñòâå, ïîêà êðèçèñ îñíîâ ìàòåìàòèêè íå ñòàë äëÿ âñåõ î÷åâèäíîé ðåàëüíî-
ñòüþ. Íàêîíåö, â íà÷àëå XIX â. Êîøè îòáðîñèë òóìàííóþ òåîðèþ áåñêîíå÷íî
ìàëûõ è çàìåíèë åå ñòðîãîé òåîðèåé ïðåäåëîâ. Âñëåä çà íèì Âåéåðøòðàññ
îñóùåñòâèë òàê íàçûâàåìóþ àðèôìåòèçàöèþ àíàëèçà, è âòîðîé êðèçèñ îñíîâ
ìàòåìàòèêè áûë ïðåîäîëåí.
58 59
ìû èçâåñòíûå ïàðàäîêñû è, â òî æå âðåìÿ, îíè äîñòàòî÷íû äëÿ
âûâîäà îñíîâíûõ ïðåäëîæåíèé êëàññè÷åñêîé ìàòåìàòèêè, â òîì
÷èñëå è àáñòðàêòíîé òåîðèè ìíîæåñòâ. Òàêàÿ ñèñòåìà àêñèîì áûëà
ïðåäëîæåíà 1908 ã. Öåðìåëî, à çàòåì óñîâåðøåíñòâîâàííà Ôðåíêå-
ëåì, Ñêîëåìîì, ôîí Íåéìàíîì, Áåðíàéñîì.  êà÷åñòâå ïðèìåðà
íèæå ïðèâîäèòñÿ îäíà èç íàèáîëåå èçâåñòíûõ àêñèîìàòè÷åñêèõ
ñèñòåì ñèñòåìà àêñèîì ÖåðìåëîÔðåíêåëÿ (ñì. [Êëèíè, 1973]).
Ñèñòåìà àêñèîì Öåðìåëî-Ôðåíêåëÿ.
1. Àêñèîìà îáúåìíîñòè.
Äâà ìíîæåñòâà A è B ðàâíû, åñëè è òîëüêî åñëè îíè ñîñòîÿò èç
îäíèõ è òåõ æå ýëåìåíòîâ: A = B ≡ (A ⊆ B & B ⊆ A).
2. Àêñèîìà âûäåëåíèÿ.
Äëÿ ëþáîãî ìíîæåñòâà A è ïðåäèêàòà P(x), òàêîãî, ÷òî äëÿ ëþáî-
ãî x ∈A P(x) ëèáî èñòèííî, ëèáî ëîæíî, ñóùåñòâóåò ìíîæåñòâî
X= {x | x ∈ A & P(x)}, ñîñòîÿùåå â òî÷íîñòè èç òåõ ýëåìåíòîâ A,
äëÿ êîòîðûõ P(x) èñòèííî.
3. Àêñèîìà ïàðû.
Åñëè a è b ðàçëè÷íûå îáúåêòû, òî ñóùåñòâóåò ìíîæåñòâî {a,b},
ñîñòîÿùåå â òî÷íîñòè èç a è b.
4. Àêñèîìà îáúåäèíåíèÿ.
Äëÿ ëþáîãî ìíîæåñòâà ìíîæåñòâ A ñóùåñòâóåò îáúåäèíåíèå
âñåõ ìíîæåñòâ, ñîñòîÿùåå â òî÷íîñòè èç âñåõ ýëåìåíòîâ, êîòîðûå
ïðèíàäëåæàò ýëåìåíòàì ìíîæåñòâà A.
5. Àêñèîìà áåñêîíå÷íîñòè.
Ñóùåñòâóåò ïî êðàéíåé ìåðå îäíî áåñêîíå÷íîå ìíîæåñòâî
ìíîæåñòâî íàòóðàëüíûõ ÷èñåë {0, 1, 2, ...}.
6. Àêñèîìà ìíîæåñòâà-ñòåïåíè.
Äëÿ ëþáîãî ìíîæåñòâà A ñóùåñòâóåò ìíîæåñòâî 2
A
âñåõ ïîä-
ìíîæåñòâ A.
7. Àêñèîìà âûáîðà.
Äëÿ ëþáîãî íåïóñòîãî ìíîæåñòâà S ïîïàðíî íåïåðåñåêàþùèõñÿ
ìíîæåñòâ ñóùåñòâóåò íåêîòîðîå ìíîæåñòâî A, ñîäåðæàùåå â
êà÷åñòâå ñâîèõ ýëåìåíòîâ ðîâíî ïî îäíîìó ýëåìåíòó èç êàæäîãî
ýëåìåíòà ìíîæåñòâà S.
8. Àêñèîìà ïîäñòàíîâêè.
Äëÿ êàæäîãî ìíîæåñòâà A è îäíîçíà÷íîé ôóíêöèè ƒ, îïðåäåëåí-
íîé íà A, ñóùåñòâóåò ìíîæåñòâî, ñîäåðæàùåå â òî÷íîñòè îáúåêòû
ƒ(x) äëÿ x ∈ A.
Ñèñòåìà àêñèîì òåîðèè ìíîæåñòâ îãðàíè÷èâàåò ìíîæåñòâî
îáúåêòîâ, êîòîðûå ìîæíî ñ÷èòàòü ìíîæåñòâàìè. Òàê, èíòóèòèâíûé
ïðèíöèï àáñòðàêöèè, ñîãëàñíî êîòîðîìó äëÿ ëþáîãî ñâîéñòâà P(x)
ñóùåñòâóåò ñîîòâåòñòâóþùåå ìíîæåñòâî âñåõ ýëåìåíòîâ x, îáëàäàþ-
ùèõ ýòèì ñâîéñòâîì, çàìåíåí áîëåå ñòðîãîé àêñèîìîé âûäåëåíèÿ,
òðåáóþùåé îïðåäåëåííîñòè ïðåäèêàòà P(x) îí äîëæåí áûòü ëèáî
èñòèíåí, ëèáî ëîæåí. Òîãäà ïàðàäîêñ Ðàññåëà äîêàçûâàåò, ÷òî íå
ñóùåñòâóåò ìíîæåñòâà âñåõ ìíîæåñòâ, êîòîðûå íå ïðèíàäëåæàò ñà-
ìèì ñåáå â êà÷åñòâå ýëåìåíòà. Ïàðàäîêñ Êàíòîðà ïîêàçûâàåò, ÷òî
íå ñóùåñòâóåò óíèâåðñàëüíîãî ìíîæåñòâà ìíîæåñòâà âñåõ
ìíîæåñòâ.
 íåêîòîðûõ äðóãèõ ñèñòåìàõ àêñèîì òåîðèè ìíîæåñòâ, íàïðè-
ìåð, â ñèñòåìå øäåëÿ (ñì. [Ìåíäåëüñîí, 1976]), âñå ñîâîêóïíîñòè
îáúåêòîâ äåëÿòñÿ íà äâà âèäà: ìíîæåñòâà è êëàññû. Âñå ìíîæåñòâà
ìîãóò âõîäèòü êàê ýëåìåíòû â äðóãèå ñîâîêóïíîñòè, êàê âî ìíîæå-
ñòâà, òàê è â êëàññû. Êëàññû ìîãóò áûòü èëè íå áûòü ìíîæåñòâàìè.
Êëàññû, êîòîðûå íå ÿâëÿþòñÿ ìíîæåñòâàìè, íàçûâàþòñÿ ñîáñòâåí-
íûìè êëàññàìè. Ñîâîêóïíîñòü âñåõ ìíîæåñòâ îáðàçóåò êëàññ. Ïàðà-
äîêñ Êàíòîðà óñòðàíÿåòñÿ òåì îáñòîÿòåëüñòâîì, ÷òî ýòîò êëàññ óæå
íå ÿâëÿåòñÿ ìíîæåñòâîì, îí ÿâëÿåòñÿ ñîáñòâåííûì êëàññîì.
Àíàëîãè÷íî óñòðàíÿåòñÿ è ïàðàäîêñ Ðàññåëà: èç ñèñòåìû àêñèîì
âûâîäèìî ïðåäëîæåíèå î òîì, ÷òî ñîâîêóïíîñòü, îïðåäåëåííàÿ
òàêèì îáðàçîì, ÷òî îíà ñîäåðæèò âñå ìíîæåñòâà, íå ÿâëÿþùèåñÿ
ýëåìåíòàìè ñàìèõ ñåáÿ, íå ÿâëÿåòñÿ ìíîæåñòâîì, îíà ÿâëÿåòñÿ
ñîáñòâåííûì êëàññîì.
Íå âñå, îäíàêî, îáñòîÿëî ãëàäêî ñ àêñèîìàòè÷åñêîé òåîðèåé
ìíîæåñòâ. Àêñèîìà âûáîðà, ââåäåííàÿ Öåðìåëî, ÿâèëàñü ïðåäìåòîì
ìíîãî÷èñëåííûõ èññëåäîâàíèé è ñïîðîâ, ñóòü êîòîðûõ ñâîäèëàñü
ê âîïðîñó, ïðèíèìàòü èëè íå ïðèíèìàòü åå â êà÷åñòâå äîïóùåíèÿ,
êîòîðîå ìîæíî áåç ïðîòèâîðå÷èé ïðèñîåäèíèòü ê äðóãèì àêñèîìàì
òåîðèè ìíîæåñòâ, ïðè óñëîâèè, ÷òî ýòè àêñèîìû íåïðîòèâîðå÷èâû.
 1963 ãîäó Êîýí ïîêàçàë, ÷òî ìîæíî áåç ïðîòèâîðå÷èÿ ïðèñîåäè-
íèòü ê àêñèîìàòèêå òåîðèè ìíîæåñòâ è îòðèöàíèå àêñèîìû âûáîðà.
Îäíàêî èç àêñèîìû âûáîðà Öåðìåëî ñëåäóþò íåêîòîðûå
âûçûâàþùèå ñîìíåíèÿ âûâîäû.  ÷àñòíîñòè, èç íåå ñëåäóåò, ÷òî
ëþáîå ìíîæåñòâî ìîæíî âïîëíå óïîðÿäî÷èòü. Ïîÿñíèì, ÷òî âïîëíå
óïîðÿäî÷åííîå ìíîæåñòâî ýòî ëèíåéíî óïîðÿäî÷åííîå ìíîæåñòâî,
ò.å. öåïü, â êîòîðîì êàæäîå íåïóñòîå ïîäìíîæåñòâî èìååò íàèìåíü-
øèé ýëåìåíò. Ëþáàÿ êîíå÷íàÿ öåïü âïîëíå óïîðÿäî÷åíà, íàïðèìåð,
êîíå÷íîå ïîäìíîæåñòâî íàòóðàëüíûõ ÷èñåë. Ìíîæåñòâî íàòóðàëü-
íûõ ÷èñåë N âïîëíå óïîðÿäî÷åíî îòíîøåíèåì «ìåíüøå»: îíî èìååò
íàèìåíüøèé ýëåìåíò, ÿâëÿåòñÿ öåïüþ è ëþáîå åãî ïîäìíîæåñòâî
òàêæå âïîëíå óïîðÿäî÷åíî. Îòíîøåíèå «ìåíüøå» íà ìíîæåñòâå
Ìîùíîñòü ìíîæåñòâÃëàâà 4