Cantorov teorem je 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".
Teorem tvrdi da je kardinalni broj svakog skupa strogo manji od kardinalnog broja njegova partitivnog skupa, tj.
. Izravna i važna posljedica ovog teorema je ta da ne postoji "najveći kardinalni broj".[1]
Postoje dva slučaja. Naime, skup
može biti prazan ili neprazan.
1. Neka je
prazan skup, odnosno neka je
. Ovo povlači
, čime je teorem u ovom slučaju dokazan.
2. Neka je
neprazan skup, tj. neka je
. Dokažimo da je tada
. Postoji injekcija sa skupa
u
, tj.
. To znači da je zaista
.
Pokažimo sada da je
. Pretpostavimo suprotno, tj. pretpostavimo da je
. Neka je
bijekcija. (Ona postoji jer su prema pretpostavci skupovi
i
iste kardinalnosti.)
Sada slijedi genijalni argument kojega je našao Cantor. Naime, formirajmo skup
Skup
se očito nalazi u
. Budući da je
bijekcija, vrijedi da je
surjekcija, tj.
takav da je
Mogu nastupiti dva slučaja:
1.
, što je kontradikcija.
2.
, što je također kontradikcija.
Iz ovoga slijedi da
nije bijekcija, tj. ne postoji bijekcija sa skupa
u skup
što povlači
, čime je teorem dokazan.