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. ${\displaystyle |S|<|{\mathcal {P}}(S)|}$. Izravna i važna posljedica ovog teorema je ta da ne postoji „najveći kardinalni broj”.^[1]

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

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

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

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

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

Mogu nastupiti dva slučaja:

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

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

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