Cantorov teorem

Cantorov teorem, jedan od temeljnih teorema naivne teorije skupova. Teorem je 1891. dokazao njemački matematičar Georg Cantor u svom radu „Über eine elementare Frage der Mannigfaltigkeitslehre” (njem. O elementarnom pitanju teorije različitosti).

Teorem tvrdi da je kardinalni broj svakog skupa strogo manji od kardinalnog broja njegova partitivnog skupa, tj. $|S|<|{\mathcal {P}}(S)|$. Izravna i važna posljedica ovog teorema je ta da ne postoji „najveći kardinalni broj”.

Dokaz

Postoje dva slučaja. Naime, skup $S$ može biti prazan ili neprazan.

1. Neka je $S$ prazan skup, odnosno neka je $S=\emptyset$. Ovo povlači $|S|=0\implies |S|<|{\mathcal {P}}(S)|=1$, čime je teorem u ovom slučaju dokazan.

2. Neka je $S$ neprazan skup, tj. neka je $S\neq \emptyset$. Dokažimo da je tada $|S|\leq |{\mathcal {P}}(S)|$. Postoji injekcija sa skupa $S$ u ${\mathcal {P}}(S)$, tj. $x\in S,x\mapsto {x}\in {\mathcal {P}}(S)$. To znači da je zaista $|S|\leq |{\mathcal {P}}(S)|$.

Pokažimo sada da je $|S|\neq |{\mathcal {P}}(S)|$. Pretpostavimo suprotno, tj. pretpostavimo da je $|S|=|{\mathcal {P}}(S)|$. Neka je $g:S\rightarrow {\mathcal {P}}(S)$ bijekcija. (Ona postoji jer su prema pretpostavci skupovi $S$ i ${\mathcal {P}}(S)$ iste kardinalnosti.)

Sada slijedi genijalni argument kojega je našao Cantor. Naime, formirajmo skup $Z=\{a\in S|a\not \in g(a)\}.$ Skup $Z\subseteq S$ se očito nalazi u ${\mathcal {P}}(S)$. Budući da je $g$ bijekcija, vrijedi da je $g$ surjekcija, tj. $\exists b\in S$ takav da je $g(b)=Z.$

Mogu nastupiti dva slučaja:

1. $b\in Z\implies b\notin g(b)=Z$, što je kontradikcija.

2. $b\notin Z\implies b\in g(b)=Z$, što je također kontradikcija.

Iz ovoga slijedi da $g$ nije bijekcija, tj. ne postoji bijekcija sa skupa $S$ u skup ${\mathcal {P}}(S)$ što povlači $|S|\neq |{\mathcal {P}}(S)|$, čime je teorem dokazan.