Při konstrukci nezáporných celých čísel jsme měli 2 = {0,1}. Pro libovolnou množinu A je tedy 2A množinou všech zobrazení / : A —>• {0,1}. Dále pro množinu A a pro libovolnou podmnožinu Y C A definujeme charakteristické zobrazení XY '■ ^4 —>- {0,1} podmnožiny Y následovně. Pro libovolné a E A
klademe r .       , ,
II   pokud a 6 r,
Xy(a) - j Q   pokud a ^ y
Nyní jsme připraveni dokázat následující fakt.
Tvrzení. Pro libovolnou množinu A je V (A) = 2A. Důkaz. Zobrazení
ů : V {A) -)> 2A definované pro každou podmnožinu Y C A předpisem
#(Y) = XY
je zřejmě bijekce množiny V (A) na množinu 2A.
Zásadní význam má následující Cantorova věta.
Věta. Pro každou množinu A platí A ^ V(A). Důkaz. Připusťme, že existuje bijekce
Uvažujme množinu
Y = {a£ A \ a(£f(a)}.
Pak ľ C A, čili Y G V (A). Poněvadž / je podle předpokladu bijekce, existuje jediné y E A, pro něž Y = f (y).
Zkoumejme nyní, zda y G Y či nikoliv. Pokud y G Y, pak z definice množiny Y plyne, že y £ f {y), a poněvadž f (y) = Y, znamená to, že y (fc Y, což není možné. Pokud však y (£ Y, pak zase z definice množiny Y plyne, že y G f {y), a poněvadž f (y) = Y, znamená to tentokrát, že y G Y, což opět není možné. To dává spor.
Řekneme, že daná množina A je spočetná, jestliže A je ekvivalentní množině
o; = {0,l,2,3,...}
všech nezáporných celých čísel. Názorně řečeno, množina A je spočetná, je-li možno všechny její prvky očíslovat nezápornými celými čísly, tedy je-li možno všechny prvky množiny A seřadit do nekonečné posloupnosti ao, ai, a2,..., an,... .
Příklad. Množina
N = {1,2,3,...} všech přirozených čísel je spočetná. Skutečně zobrazení
7 : u ->• N
dané předpisem
(VfeGw)(7(Jb) = Jfc + l) je bijekcí množiny uj na množinu N.
Příklad. Množina
Z = {...,-2,-l,0,l,2,...} všech celých čísel je spočetná. Skutečně zobrazení
5 : u -)> 7L
dané předpisem
V    1     Je_li í liché
je bijekcí množiny uj na množinu Z. Názorně předvedeno, znamená to, že jsme seřadili všechna celá čísla do nekonečné posloupnosti 0, —1,1, —2, 2,..., —n, n,... .
Tvrzení. Každá podmnožina Y spočetné množiny A je konečná nebo spočetná.
Důkaz. Poněvadž A je spočetná množina, je možno všechny její prvky seřadit do nekonečné posloupnosti
ao, ai, Gt2,..., an,... .
Není-li podmnožina Y C A konečná, tvoří její prvky v uvedené posloupnosti nekonečnou podposloupnost
kde Íq < i\ < %2 < • • • < in < ■ ■ ■ ■ Poněvadž je možno takto prvky množiny Y očíslovat nezápornými celými čísly, tedy čísly z w, je v tomto případě množina Y spočetná.
Tvrzení. Kartézský součin A x B dvou spočetných množin A, B je spočetná množina.
Důkaz. Poněvadž obě množiny A, B jsou ekvivalentní množině uj všech nezáporných celých čísel, stačí ukázat, že kartézský čtverec o; x o; je spočetná množina. Ovšem
uj x uj = {(&, i) I k, i e oj}.
Pro každou uspořádanou dvojici (k,£) E uj x uj nazvěme výškou této uspořádané dvojice součet k + i. Pak je jasné, že pro každé číslo h E uj existuje právě h + 1 uspořádaných dvojic
(0,/i),(l,/i-l),(2,/i-2),...,(/i-l,l),(/i,0)
výšky h v kartézském čtverci o; x o;. Vypišme nyní podle rostoucí výšky za sebou tímto způsobem všechny uspořádané dvojice z ujxuj. Očíslujeme-li nyní takto seřazené uspořádané dvojice z uj x uj nezápornými celými čísly, tedy čísly z uj, dostaneme tak bijekci množiny uj na množinu ujxuj. Jsou tedy tyto dvě množiny ekvivalentní, takže o; x o; je spočetná množina.
Důsledek. Množina Q všech racionálních čísel je spočetná.
Důkaz. Každé racionální číslo lze jednoznačně zadat ve tvaru |, kde p G Z, q G N a čísla p a q jsou navzájem nesoudělná. Racionální čísla tedy vzájemně jednoznačně odpovídají těm uspořádaným dvojicím (p, q) G 7L x N, které pozůstávají ze vzájemně nesoudělných čísel. Tyto uspořádané dvojice tvoří nekonečnou podmnožinu množiny 7L x N. Množiny Z a N jsou spočetné, takže podle předchozích tvrzení je spočetný také jejich kartézský součin Z x N i každá jeho nekonečná podmnožina. To znamená, že i množina Q všech racionálních čísel je spočetná.
Nekonečná množina, jež není spočetná, se nazývá nespočetná.
Tvrzení. Množina R všech reálných čísel je nespočetná.
Důkaz. Připusťme, že by množina R všech reálných čísel byla spočetná. Tedy by bylo možno všechna reálná čísla seřadit do nekonečné posloupnosti
ro,n,r2, ... ,rn,... .
Každé reálné číslo je možno jediným způsobem zadat jeho dekadickým rozvojem včetně znaménka, vyloučíme-li ty dekadické rozvoje, v nichž se od jistého místa dále vyskytují jen samé cifry 9. Definujme nyní reálné číslo s ležící v intervalu (0,1) jeho dekadickým rozvojem
s = 0, s0sis2 • • • sn ... , kde so, si, S2,..., sn,... jsou cifry zadané následujícím způsobem:
(       ( 1 je-li (i + l)-ní cifra za desetinnou čárkou \ v dekadickém rozvoji čísla r i různá od 1.
(Vi G o;)
2 je-li (i + l)-ní cifra za desetinnou čárkou \       l     v dekadickém rozvoji čísla r i rovna 1. /
Pak je jasné, že číslo s se liší ode všech čísel ro, n, r2,..., rn,... . To je spor s předpokladem, že ro, ri, r i-, ■ ■ ■, rn,... byla všechna reálná čísla. Je tedy množina R všech reálných čísel nespočetná.