Teorema de Cantor

El teorema de Cantor és un resultat formalitzable en la teoria de conjunts de Zermelo-Fränkel, que afirma el següent:

El conjunt potència de qualsevol conjunt A té una cardinalitat estrictament més gran que la cardinalitat del propi A.

Discussió

El teorema de Cantor és obvi per a conjunts finits: si un conjunt finit té n elements llavors el conjunt de parts d'aquest conjunt té 2ⁿ elements. El fet que sigui vàlid per tot conjunt infinit no és del tot intuïtiu, però permet establir diversos resultats interessants:

Existeix una infinitat de cardinals transfinits, el que significa que en realitat existeixen molts tipus d'infinits (de fet una infinitat) cada un més gran que l'anterior. Aquest resultat a priori és molt poc intuïtiu, però terriblement important en la fonamentació de les matemàtiques.
No existeix cap manera d'enumerar tots els subconjunts d' $\mathbb {N}$ .

Per il·lustrar la validesa d'aquest teorema per conjunts infinits es reprodueix a continuació una demostració.

Demostració

Considerem una funció qualsevol f d'A en el conjunt de parts d'A, llavors demostrar el teorema de Cantor requereix provar que f no és suprajectiva (exhaustiva). I per provar que f no és sobrejectiva només cal trobar un subconjunt d'A que no sigui la imatge de cap element d'A a través de f. Cantor considerà un conjunt particular B definit com:

B=\left\{\,x\in A:x\not \in f(x)\,\right\}.

I va provar que aquest subconjunt no pot ser la imatge de cap element d'A. L'argument que va construir Cantor es pot reducció a l'absurd pressuposant de partida que f si és sobrejectiva, i llavors l'argument va com segueix:

Donat que f és sobrejectiva, llavors existeix $a\in A:B=f(a)$ donat que B és un subconjunt d'A.
Ara tractarem de veure si $a\in B$ o bé $a\notin B$ . Suposem en primer lloc que a pertany a B, llavors per la definició de B es té que a no pertany, el que és contradictori. Per altre costat si suponem que a no pertany a B, llavors per la definició de B, a ha de ser un element de B el que torna a ser una contradicció.
Per tant arribem al cas que si existeix un a la imatge del qual sigui el conjunt B llavors irremissiblement arribem a una contradicció, per tant l'única sortida és suposar que dit a no existeix i per tant f no pot ser sobrejectiva, com volíem demostrar.

Referències

Paul Halmos, Naive set theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.