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|<|𝒫(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=\mathrm{\varnothing }$. Ovo povlači $|S|=0⟹|S|<|𝒫(S)|=1$, čime je teorem u ovom slučaju dokazan.

2. Neka je $S$ neprazan skup, tj. neka je $S\ne \mathrm{\varnothing }$. Dokažimo da je tada $|S|\le |𝒫(S)|$. Postoji injekcija sa skupa $S$ u $𝒫(S)$, tj. $x\in S,x\mapsto x\in 𝒫(S)$. To znači da je zaista $|S|\le |𝒫(S)|$.

Pokažimo sada da je $|S|\ne |𝒫(S)|$. Pretpostavimo suprotno, tj. pretpostavimo da je $|S|=|𝒫(S)|$. Neka je $g:S\to 𝒫(S)$ bijekcija. (Ona postoji jer su prema pretpostavci skupovi $S$ i $𝒫(S)$ iste kardinalnosti.)

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

Mogu nastupiti dva slučaja:

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

2. $b\notin Z⟹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 $𝒫(S)$ što povlači $|S|\ne |𝒫(S)|$, čime je teorem dokazan.