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.

La cardinalitat del conjunt {x, y, z}, és tres, mentre que hi ha vuit elements en el seu conjunt potència (3 < 2³ = 8), aquí ordenats per inclusió.

Per a conjunts finits, el teorema de Cantor es pot comprovar simplement enumerant els diferents subconjunts. Comptant el conjunt buit com a subconjunt, un conjunt amb ${\displaystyle n}$ elements té un total de ${\displaystyle 2^{n}}$ subconjunts, i el teorema és vàlid perquè ${\displaystyle 2^{n}>n}$ per tot ${\displaystyle n}$ natural.

El descobriment de Cantor és molt més significatiu com a argument aplicable a qualsevol conjunt, i demostra que el teorema és cert també per conjunts infinits. Com a conseqüència, la cardinalitat dels nombres reals, que és la mateixa que la del conjunt potència dels enters, és estrictametn més gran que la cardinalitat del enters; vegi's cardinalitat del continu per més detalls.

El teorema du el nom de Georg Cantor, que el va formular i demostrar per primer cop a finals del segle XIX. El teorema de Cantor té conseqüències immediates i importants en el camp de la filosofia de les matemàtiques. Per exemple, prenent iterativament el conjunt potència d'un conjunt infinit i aplicant el teorema de Cantor, s'obté una jerarquia infinita de cardinals, cadascun dels qual és estrictament superior que el que el precedeix. En conseqüència, el teorema implica que no existeix un nombre cardinal màxim (col·loquialment, "no hi ha un infinit màxim").

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'${\displaystyle \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:

${\displaystyle 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:

1. Donat que f és sobrejectiva, llavors existeix ${\displaystyle a\in A:B=f(a)}$ donat que B és un subconjunt d'A.
2. Ara tractarem de veure si ${\displaystyle a\in B}$ o bé ${\displaystyle 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ó.
3. 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.

Quan A és numerable

Examini's ara la demostració en el cas particular en què ${\displaystyle A}$ és un conjunt numerable. Sense pèrdua de generalitat, es pot prendre ${\displaystyle A=\mathbb {N} =\{1,2,3,\ldots \}}$, el conjunt dels nombres naturals.

Suposi's que ${\displaystyle \mathbb {N} }$ és equipotent amb el seu conjunt de les parts ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$. Una mostra d'exemples d'elements de ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ és:

${\displaystyle {\mathcal {P}}(\mathbb {N} )=\{\varnothing ,\{1,2\},\{1,2,3\},\{4\},\{1,5\},\{3,4,6\},\{2,4,6,\dots \},\dots \}.}$

En efecte, ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ conté subconjunts infinits de ${\displaystyle \mathbb {N} }$, per exemple, el conjunt de tots els nombres parells positius ${\displaystyle \{2,4,6,\ldots \}=\{2k:k\in \mathbb {N} \}}$, juntament amb el conjunt buit ${\displaystyle \varnothing }$.

Ara que es té una idea de com són els elements de ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$, per tal de mostrar que aquests conjunts infinits són equipotents, l'objectiu és emparellar cadascun dels elements de ${\displaystyle \mathbb {N} }$ amb cada element de ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$. En altres paraules, s'intenta emparellar cada element de ${\displaystyle \mathbb {N} }$ amb un element del conjunt infinit ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$, de tal manera que cap element de cada conjunt infinit no quedi sense parella. És a dir:

${\displaystyle \mathbb {N} {\begin{Bmatrix}1&\longleftrightarrow &\{4,5\}\\2&\longleftrightarrow &\{1,2,3\}\\3&\longleftrightarrow &\{4,5,6\}\\4&\longleftrightarrow &\{1,3,5\}\\\vdots &\vdots &\vdots \end{Bmatrix}}{\mathcal {P}}(\mathbb {N} ).}$

Donat tal emparellament, alguns nombres naturals són emparallets amb subconjunts que contenen el nombre natural en sí. Per exemple, en l'exemple de més amunt, el nombre 2 és emparellat amb el subconjunt {1, 2, 3}, que conté el 2 com a membre. Aquests nombres s'anomenaran egoistes. La resta de nombres naturals són emparellats amb subconjunts que no es contenen a si mateixos. Per exemple, en el cas anterior el nombre 1 és emparellat amb el subconjunt {4, 5}, que no conté el nombre 1. Aquests nombres rebran el nom de no-egoistes. De manera similar, els nombres 3 i 4 són no-egoistes.

Utilitzant aquest principi, es construeix un conjunt especial de nombres naturals. Aquest conjunt proporcionarà la contradicció que es busca. Sigui ${\displaystyle B}$ el conjunt de tots els nombre naturals no-egoistes. Per definició, el conjunt de les parts ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ conté tots els conjunts de nombres naturals, i per tant conté aquest conjunt ${\displaystyle B}$ com a element. Si la funció que mapeja elements d'un conjunt a un altre és bijectiva, ${\displaystyle B}$ ha de ser emparellat amb un cert nombre natural, que s'anomenarà ${\displaystyle b}$. Tanmateix, això és un problema. Si ${\displaystyle b}$ és en ${\displaystyle B}$, llavors ${\displaystyle b}$ és egoista perquè es troba en el conjunt corresponent, cosa que contradiu la definició de ${\displaystyle B}$. Si ${\displaystyle b}$ no es troba en ${\displaystyle B}$, llavors és no-egoista però en canvi hauria de ser membre de ${\displaystyle B}$. Per tant, tal element ${\displaystyle b}$ emparellat amb ${\displaystyle B}$ no pot existir.

Com que no hi ha cap nombre natural que pugui estar emparellat amb ${\displaystyle B}$, s'ha acontradit la suposició original, que hi ha una bijecció entre ${\displaystyle \mathbb {N} }$ i ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$.

Noti's que el conjunt ${\displaystyle B}$ pot ser buit. Això voldria dir que tot nombre natural ${\displaystyle x}$ està emparellat amb un subconjunt de nombres naturals que conté ${\displaystyle x}$. Llavors, tot nombre està emparellat amb un conjunt no buit i no hi ha cap nombre que estigui emparellat amb el conjunt buit. Però el conjunt buit és un membre de ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$, així doncs l'aplicaicó tampoc no cobreix enterament ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$.

A través d'aquesta demostració per contradicció, s'ha demostrat que la cardinalitat de ${\displaystyle \mathbb {N} }$ i ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ no poden ser iguals. També se sap que la cardinalitat de ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ no pot ser menor a la cardinalitat de ${\displaystyle \mathbb {N} }$ ja que ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ conté tots els singletons, per definició, i aquests singletons formen una "còpia" de ${\displaystyle \mathbb {N} }$ dins de ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$. Per tant, només queda una possibilitat, que és que la cardinalitat de ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ sigui estrictament més gran que la cardinalitat de ${\displaystyle \mathbb {N} }$, demostrant el teorema de Cantor

Paradoxes relacionades

El teorema de Cantor i la seva demostració estan estretament relacionades amb dues paradoxes de la teoria de conjunts.

La paradoxa de Cantor és la contradicció consqüència del teorema de Cantor i de l'assumpció que hi ha conjunt que conté tots els conjunts, el conjunt universal ${\displaystyle V}$. Per tal de distingir aquesta paradoxa de la següent, de què es parla més endavant, cal notar quina és la contradicció. Seguint el teorema de Cantor, ${\displaystyle |{\mathcal {P}}(X)|>|X|}$ per qualsevol conjunt ${\displaystyle X}$. D'altra banda, tots els elements de ${\displaystyle {\mathcal {P}}(V)}$ són conjunts, i per tant estan continguts en ${\displaystyle V}$, per tant ${\displaystyle |{\mathcal {P}}(V)|\leq |V|}$.^[1]

Es pot derivar una altra paradoxa de la demostració del teorema de Cantor exemplificant la funció f amb la funció identitat; cosa que torna el conjunt diagonal de Cantor en el que s'anomena sovint conjunt de Russell d'un conjunt donat A:^[1]

${\displaystyle R_{A}=\left\{\,x\in A:x\not \in x\,\right\}.}$

S'aplica la demostració del teorema de Cantor directament per demostrar que si s'assumeix l'existència del conjunt de tots els conjunts U, llavors considerar el seu conjunt de Russell R_U dóna lloc a la contradicció:

${\displaystyle R_{U}\in R_{U}\iff R_{U}\notin R_{U}.}$

Aquest argument rep el nom de la paradoxa de Russell.^[1] Com a subtilesa, la versió de la paradoxa de Russell presentada aquí és de fet el teorema de Zermelo;^[2] es pot concloure a partir de la contradicció obtinguda que s'ha de rebutjar la hipòtesi que R_U∈U, per tant demostrant la no existència d'un conjunt que contingui tots els conjunts. Això és així perquè s'ha usat la comprensió restringida (tal com apareix en la ZFC) en la definició de R_A més amunt, que alhora implica que

${\displaystyle R_{U}\in R_{U}\iff (R_{U}\in U\wedge R_{U}\notin R_{U}).}$

Si s'hagués utilitzat la comprensió no restringida (com en el sistema de Frege, per exemple) definint el conjunt de Russell simlpement com ${\displaystyle R=\left\{\,x:x\not \in x\,\right\}}$, llavors el sistema d'axiomes mateix hagués implicat la contradicció, sense la necessitat de cap més hipòtesi.^[2]

Malgrat les similiritats sintàctiques entre el conjunt de Russell (en qualsevol de les seves variants) i el conjunt diagonal de Cantor, Alonzo Church va emfasitxar que la paradoxa de Russell és independent de tota consideració de la cardinalitat i de les seves nocions subjacents, com la correspondència u-a-u.^[3]

Història

Cantor va donar bàsicament aquesta demostració en un article publicat l'any 1891 sota el títol "Über eine elementare Frage der Mannigfaltigkeitslehre",^[4] en què també va aparèixer per primer cop l'argument diagonal per la innumerabilitat dels nombres reals (tot i que Cantor ja havia demostrat que els nombres reals són incomptables utilitzant altres mètodes). La versió d'aquest argument en l'article estava expressat en termes de funció característiques en un conjunt, i no mitjançant subconjunts d'un conjunt.^[5] Va demostrar que si f és una funció definida en X els valors de la qual són funcions de 2 valors en X, quan la funció de de 2 valors G(x) = 1 − f(x)(x) no és en la imatge de f.

Bertrand Russell té una demostració molt similar en el seu llibre Principles of Mathematics (1903, secció 348), en què demostra que hi ha més funcions proposicionals que objectes. Ernst Zermelo té un teorema (que anomena "teorema de Cantor") que és idèntic a l'expressió de més amunt en l'article que es va convertir en els fonaments de la teoria moderna de conjunts ("Untersuchungen über die Grundlagen der Mengenlehre I"), publicat l'any 1908.

Generalizations

El teorema del punt fix Lawvere proporciona una àmplia generalització del teorema de Cantor a tota categoria amb productes finits de la següent manera:^[6] sigui ${\displaystyle {\mathcal {C}}}$ tal categoria, i sigui ${\displaystyle 1}$ un objecte terminal en ${\displaystyle {\mathcal {C}}}$. Suposi's que ${\displaystyle Y}$ és un objecte en ${\displaystyle {\mathcal {C}}}$ i que existeix un endomorfisme ${\displaystyle \alpha :Y\to Y}$ que no té cap punt fix; és a dir, que hi ha un morfisme ${\displaystyle y:1\to Y}$ que satisfà ${\displaystyle \alpha \circ y=y}$. Llavors no hi ha cap objecte ${\displaystyle T}$ de ${\displaystyle {\mathcal {C}}}$ tal que un morfisme ${\displaystyle f:T\times T\to Y}$ pugui parametritzat tots els morfismes ${\displaystyle T\to Y}$. En altres paraules, per tot objecte ${\displaystyle T}$ i tot morfisme ${\displaystyle f:T\times T\to Y}$, intentar escriure les funcions ${\displaystyle T\to Y}$ com a mapes de la forma ${\displaystyle f(-,x):T\to Y}$ ha de deixar fora com a mínim una funció ${\displaystyle T\to Y}$.

Vegeu també

• Teorema de Schröder-Bernstein