Teorema de Cantor

Archiu:Hasse diagram of powerset of 3.svg

La cardinalidad del conjunt {x, i, z}, és tres, i en el seu conjunt potencia hi ha huit elements (3 < 2³ = 8), ací ordenats per mig d'inclusió.

La teorema de Cantor, de Georg Cantor,^[1] és un resultat formalisable en la teoria de conjunts de Zermelo-Fränkel, que afirma lo següent:

Para conjunts finitos, es pot vore que la teorema de Cantor és verdader per mig d'una simple enumeració del número de subconjunts. Contant el conjunt buit com un subconjunt, un conjunt en $n$ elements té un total de $2^{n}$ subconjunts, i la teorema es complix perque $2^{n} > n$ per a tots els sancers no negatius.

Molt més significatiu és el descobriment de Cantor d'un argument que és aplicable a qualsevol conjunt i mostra que la teorema també es complix para conjunts infinits. En conseqüència, la cardinalidad dels número real, que és la mateixa que la del conjunt potencia dels sancers, és estrictament major que la cardinalidad dels sancers.

La teorema du el nom del matemàtic alemà Georg Cantor, qui ho va plantejar i va demostrar per primera volta a fins de el XIX. La teorema de Cantor va tindre conseqüències immediates i importants per a la filosofia de les matemàtiques. Per eixemple, prenent iterativamente el conjunt potencia d'un conjunt infinit i aplicant la teorema de Cantor, obtenim una jerarquia infinita de cardinals infinits, cada u estrictament major que l'anterior. En conseqüència, la teorema implica que no hi ha un número cardinal més gran (coloquialmente, "no hi ha un infinit més gran").

Discussió

La teorema de Cantor és obvi per a conjunts finitos: si un conjunt finito té n elements llavors el conjunt de parts d'eixe conjunt té 2ⁿ elements. El fet de que siga vàlit para tot conjunt infinit no és del tot intuïtiu, pero permet establir varis resultats interessants:

Existix una infinitat de cardinals transfinitos, la qual cosa significa que en realitat existixen molts tipos d'infinit (de fet una infinitat) cada u major que l'anterior. Este resultat a priori és molt poc intuïtiu, pero tremendament important en la fundamentación de les matemàtiques.
No existix cap manera d'enumerar tots els subconjunts de $ℕ$ .

Per a ilustrar la validea d'esta teorema per a conjunts infinits es reproduïx a continuació una demostració.

Demostració

Siga $A$ un conjunt arbitrari, i considerem una funció $f : A \to 𝒫 (A)$ arbitrària, a on $𝒫 (A)$ és el conjunt potencia de $A$ . Volem vore que esta funció no és sobreyectiva, i per a això necessitem trobar un subconjunt de $A$ que no siga l'image de cap element de $A$ a través de $f$ . Cantor va considerar un subconjunt particular $B$ definit de la següent manera:

B = {x \in A : x \in̸ f (x)} .

Vejam que $B$ no pot ser l'image de cap element de $A$ . L'argument que va construir Cantor és per reducció a l'absurt presuponent que existix $a \in A$ tal que $B = f (a)$ , ya que $B$ és un subconjunt de $A$ . Ara podem distinguir dos casos:

Si $a \in B$ , llavors per la definició de $B$ es té que $a \notin B$ , la qual cosa és contradictori.
Si $a \notin B$ , llavors per la definició de $B$ es té que $a \in B$ , la qual cosa és contradictori.

En abdós casos apleguem a una contradicció, per tant no existix dita $a$ i llavors $f$ (que és una funció qualsevol) no és sobreyectiva, com volíem demostrar.

Quan A és un infinit numerable

Si s'examina la demostració per al cas específic quan $A$ és un infinit numerable. Sense pèrdua de generalitat, es pot prendre $A = N = Plantilla:Mset$ , el conjunt dels número natural.

Si se supon que N és equinumeroso en la seua conjunt potencia 𝒫(N). S'analisa una mostra de l'aspecte de 𝒫(N):

𝒫 (ℕ) = {\emptyset, {1, 2}, {1, 2, 3}, {4}, {1, 5}, {3, 4, 6}, {2, 4, 6, \dots}, \dots} .

𝒫(N) conté infinits subconjunts de N, o siga el conjunt de tots els número par {2, 4, 6,...}, ademés del conjunt buit.

Ara que tenim una idea de cóm són els elements de 𝒫(N), anem a intentar emparellar cada element de N en cada element de 𝒫(N) per a demostrar que estos conjunts infinits són equinuméricos. En atres paraules, intentarem emparellar cada element de N en un element del conjunt infinit 𝒫(N), de manera que cap element de cap dels dos conjunts infinits quede sense emparellar. Este intent d'emparellar elements es voria aixina:

ℕ {\begin{matrix} 1 & ⟷ & {4, 5} \\ 2 & ⟷ & {1, 2, 3} \\ 3 & ⟷ & {4, 5, 6} \\ 4 & ⟷ & {1, 3, 5} \\ ⋮ & ⋮ & ⋮ \end{matrix}} 𝒫 (ℕ) .

Donat este emparejamiento, alguns número natural s'emparellen en subconjunts que contenen el mateix número. Per eixemple, en el nostre eixemple el número 2 està emparellat en el subconjunt {1, 2, 3}, que conté el 2 com a membre. Cridem a estos números egoistes. Atres número natural estan emparellats en subconjunts que no els contenen. Per eixemple, en el nostre eixemple el número 1 està emparellat en el subconjunt {4, 5}, que no conté el número 1. Cridem a estos números no egoistes. De la mateixa manera, el 3 i el 4 són no egoistes.

Usant esta idea, construïm un conjunt especial d'número natural. Este conjunt proporcionarà la contradicció que busquem. Siga B el conjunt de tots els número natural no egoistes. Per definició, el conjunt de potències 𝒫(N) conté tots els conjunts d'número natural, i per tant conté este conjunt B com a element. Si el mapage és biyectivo, B deu ser emparellat en algun número natural, digam b. No obstant, açò causa un problema. Si b està en B, llavors b és egoista perque està en el conjunt corresponent, lo que contradiu la definició de B. Si b no està en B, llavors no és egoista i en canvi deuria ser membre de B. Per lo tant, no pot existir cap element b que mapee a B.

Com no hi ha cap número natural que puga ser emparellat en B, hem contradit la nostra suposició original, de que hi ha una biyección entre N i 𝒫(N).

Note's que el conjunt B pot estar buit. Açò significaria que cada número natural x mapea a un subconjunt d'número natural que conté a x. Llavors, cada número correspon a un conjunt no buit i cap número correspon al conjunt buit. Pero el conjunt buit és un membre de 𝒫(N), per lo que el mapage encara no cobrix 𝒫(N).

Per mig d'esta demostració per contradicció hem demostrat que la cardinalidadés de N i 𝒫(N) no poden ser iguals. També sabem que la cardinalidad de 𝒫(N) no pot ser menor que la cardinalidad de N perque 𝒫(N) conté tots els singletons, per definició, i estos singletons formen una "còpia" de N dins de 𝒫(N). Per tant, només queda una possibilitat, i és que la cardinalidad de 𝒫(N) siga estrictament major que la cardinalidad de N, demostrant la teorema de Cantor.

Paradoxes relacionades

La teorema de Cantor i la seua demostració estan estretament relacionats en dos paradoxes de la teoria de conjunts.

La paradoxa de Cantor és el nom que rep una contradicció que es deriva de la teorema de Cantor junt en la suposició de que existix un conjunt que conté a tots els conjunts, el conjunt universal. $V$ . Per a distinguir esta paradoxa de l'atra que es tracta més avall, és important notar la naturalea d'esta contradicció. Segons la teorema de Cantor $| 𝒫 (X) | > | X |$ para tot conjunt $X$ . Per una atra part, tots els elements de $𝒫 (V)$ són conjunts, i per lo tant estan continguts en $V$ , per lo tant $| 𝒫 (V) | \leq | V |$ .^[2]

Una atra paradoxa pot derivar-se de la demostració de la teorema de Cantor instanciando la funció f en la funció identitat; açò convertix el conjunt diagonal de Cantor en lo que a voltes es diu el conjunt de Russell d'un conjunt donat A:^[2]

R_{A} = {x \in A : x \in̸ x} .

La demostració de la teorema de Cantor s'adapta directament per a mostrar que suponent que existix un conjunt de tots els conjunts O, llavors considerant el seu conjunt Russell R _O s'aplega a la contradicció:

R_{U} \in R_{U} ⟺ R_{U} \notin R_{U} .

Esta argumentació es denomina la paradoxa de Russell.^[2] És de notar que la versió de la paradoxa de Russell que hem presentat ací és en realitat una teorema de Zermelo;^[3] es pot concloure a partir de la contradicció obtinguda que devem rebujar l'hipòtesis que R_O∈O, refutando aixina l'existència d'un conjunt que conté tots els conjunts.

Açò és possible perque hem usat comprensió restringida (com es mostra en ZFC) en la definició de R_A anterior, lo que a la seua volta implica que

R_{U} \in R_{U} ⟺ (R_{U} \in U \land R_{U} \notin R_{U}) .

Si s'haguera utilisat la comprensió irrestricta (com per eixemple en el sistema de Frege) per a definir el conjunt de Russell simplement com $R = {x : x \in̸ x}$ , llavors el sistema d'axioma mateix haguera implicat la contracicción, sense necessitat de recórrer a atres hipòtesis.^[3]

Hipòtesis del continu

Existix un atre método per a demostrar que no existix un cardinal major: el número de Hartogs de qualsevol conjunt té una cardinalidad estrictament major que la del conjunt inicial. Quan el conjunt de partida és el dels número natural N, la coincidència entre estos dos métodos és l'hipòtesis de continuïtat deguda al mateix Cantor. Més precisament, vàrem mostrar que el conjunt d'ordinals contables com a màxim també té un cardinal estrictament major que el de N (resultat per Cantor). La hipòtesis del continu és llavors que este cardinal és el de totes les parts de N.

Aplicacions

La teorema de Cantor s'utilisa en la demostració del Teorema de categories de Baire.

Història

Cantor va demostrar este resultat en 1891, per al conjunt de funcions característiques de N (el conjunt dels número entero naturals), i després per al conjunt de funcions característiques de l'interval dels número real entre 0 i 1. Va afirmar, no obstant, que el resultat podia generalisar-se a qualsevol conjunt, lo que el seu método permetia sense ambigüitats.

Zermelo va enunciar (i va demostrar) este resultat, que va denominar teorema de Cantor (en alemà Satz von Cantor) en el seu artícul de 1908,^[4] el primer en presentar una axiomatisació de la teoria de conjunts.

Bertrand Russell té una prova molt similar en Principia Mathematica (1903, secció 348),^[5] a on mostra que hi ha més funcions proposicionals que objectes. "Supongam que una correlació de tots els objectes i algunes funcions proposicionals han segut afectades, i que phi-x és el correlato de x. Llavors "no-phi-x(x)", és dir, "phi-x no se sosté de x" és una funció proposicional no continguda en esta correlació; perque és verdadera o falsa de x segons phi-x siga falsa o verdadera de x, i per lo tant diferix de phi-x per a cada valor de x". Russell atribuïx l'idea d'esta prova a Cantor.

Vore també

Referències

↑ Georg Cantor «Über eine elementare Frage der Mannigfaltigskeitslehre» (Sobre una qüestió elemental de la teoria de la multiplicitat), Jahresber. der DMV, vol. 1, 1891, p. 75-78 (url [archiu]), arreplegat en Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, editat per E. Zermelo, 1932.
↑ ^2,0 ^2,1 ^2,2 Abhijit Dasgupta (2013). Set Theory: With an Introduction to Real Point Sets. Springer Science & Business Mija. pp. 362–363. ISBN 978-1-4614-8854-5.
↑ ^3,0 ^3,1 Heinz-Dieter Ebbinghaus (2007). Ernst Zermelo: An Approach to His Life and Work, Springer Science & Business Mija, pp. 86–87. ISBN 978-3-540-49553-6.
↑ (alemà) Ernst Zermelo, « Untersuchungen über die Grundlagen der Mengenlehre. I », en Mathematische Annalen, vol. 65, 1908, p. 261-281, traducció en anglés en Jean van Heijenoort, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, Harvard Univ. Press, 1967 ISBN 978-0-67432449-7, p. 199-215.
↑ «The Principles of Mathematics (1903)» (en anglés). Consultat el 4 d'octubre de 2022.

Bibliografia

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.

Enllaços externs

Cantor's Theorem en MathWorld. (anglés)

Referències

Este artícul conté una traducció derivada de «Teorema de Cantor» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Georg Cantor «Über eine elementare Frage der Mannigfaltigskeitslehre» (Sobre una qüestió elemental de la teoria de la multiplicitat), Jahresber. der DMV, vol. 1, 1891, p. 75-78 (url [archiu]), arreplegat en Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, editat per E. Zermelo, 1932.

[Dasgupta2013-2] 2,0 ^2,1 ^2,2 Abhijit Dasgupta (2013). Set Theory: With an Introduction to Real Point Sets. Springer Science & Business Mija. pp. 362–363. ISBN 978-1-4614-8854-5.

[Ebbinghaus2007-3] 3,0 ^3,1 Heinz-Dieter Ebbinghaus (2007). Ernst Zermelo: An Approach to His Life and Work, Springer Science & Business Mija, pp. 86–87. ISBN 978-3-540-49553-6.

[4] (alemà) Ernst Zermelo, « Untersuchungen über die Grundlagen der Mengenlehre. I », en Mathematische Annalen, vol. 65, 1908, p. 261-281, traducció en anglés en Jean van Heijenoort, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, Harvard Univ. Press, 1967 ISBN 978-0-67432449-7, p. 199-215.

[5] «The Principles of Mathematics (1903)» (en anglés). Consultat el 4 d'octubre de 2022.

[1]

[2]

[3]

[4]

[5]