Anuncio

Colapsar
No hay ningún anuncio todavía.

El método diagonal de Cantor

Colapsar
X
 
  • Filtro
  • Hora
  • Mostrar
Borrar todo
nuevos mensajes

  • El método diagonal de Cantor

    El método diagonal de Cantor ha sacudido los cimientos de la matemática en varias ocasiones: con él demostró la no enumerabilidad de los reales (no os asusteis luego explicaré lo que quiero decir), que siempre existía un conjunto mayor que uno dado, y Gödel se ocupó de utilizar este mismo método para demostrar que no existe un computador capaz de resolver los problemas matemáticos.
    Pensareis que algo tan poderoso como el método diagonal es algo complejo, pero no. Siempre he dicho que las grandes ideas son en esencia muy simples.

    Empecemos con un ejemplo sencillito. Consideremos estas tres palabras e intentad formar una cuarta palabra formada también con las letras A y b, diferente de las otras tres:

    ABA
    BBA
    AAB
    ---

    No es algo difícil, por ejemplo BAA, no está en la lista. Bien, pues esto es lo que hace el método diagonal de Cantor, encuentra una palabra que no está en la lista. Veamos cómo: tomemos de la primera palabra la primera letra que es una A. Si tomamos para la nueva palabara una B como primera letra, entonces será diferente de la primera. Como segunda letra tomaremos una diferente de la segunda letra de la segunda palabra, es decir, tomaremos una A. Y con la tercera, por el mismo razonamiento tomaremos una A. Así obtenemos la palabra BAA, que será diferente a las otras tres.
    Ya habréis visto por qué se le llama método diagonal: nos movemos a lo largo de la diagonal del listado tomando elementos diferentes a los de la diagonal, de esa manera nos aseguramos de que la nueva palabra es diferente a todas las de la lista.

    Este método de diagonalización se puede generalizar al caso de una lista infinita. Ya que estamos podemos decir que cualquier conjunto que podamos colocar en forma de lista se denomina numerable. Ejemplo de esto son los números naturales, los números pares, los enteros, los número cuadrados...pero NO los reales. Este es uno de los grandes resultados de Cantor, los reales no son numerables, lo cual implica que en esencia hay muchos más números reales que números naturales. Este resultado implica que hay varios tipos de infinito, algo sorprendente para el sentido común.

    Para demostrar esto colocó los números reales entre 0 y 1 en una lista numerada. Algo así:

    0 .[1]2 7 0 3 5 7 3 5...
    0 . 0[4]7 2 6 8 4 2 1...
    0 . 3 3[1]3 3 3 3 3 3...
    0 . 6 8 4[5]3 4 8 7 2...
    0 . 2 5 0 0[9]4 0 6 7...
    0 . 6 6 6 6 6[2]6 6 6...
    0 . 5 4 7 9 2 5[6]6 9...
    0 . 2 4 7 8 4 7 3[5]5...

    Si de la diagonal tomamos elementos diferentes a los que están entre corchetes obtendremos un número real diferente a los dados en al lista, pero esto es contradictorio, pues obviamente el número así obtenido es real...cómo es esto posible? Pues es posible porque hemos partido de un supuesto erróneo, el creer que los números reales se pueden colocar en una lista enumerada.

    El argumento diagonal de Cantor también se utiliza para probar que dado un conjunto C cualquiera, el conjunto de sus subconjuntos (también llamado conjunto de las partes, P(C)) tiene siempre mayor cardinal (más elementos) que el conjunto dado C. Esto demuestra entre otras cosas que no podemos nunca considerar un conjunto de todos los conjuntos pues el conjunto de sus partes sería mayor. Este resultado no resultó sorprendente a una mente como la de Cantor y ni siquiera lo publicó en su obra magna en 1890. Fue Russell quien se dio cuenta de la relevancia de tal resultado y el que le llevó a su famosa paradoja. Fue tal el impacto que tardó un año en escribir a sus maestros para comunicarles la noticia. Frege, que ya tenía la gran obra de su vida a punto de acabar, tuvo que tirarla a la basura pues fallaba en sus fundamentos. La reacción de Frege fue de placer intelectual sin caer en la frustración personal o la descalificación personal. El llamado axioma de comprehensión tuvo que eliminarse, pues es el que daba pie a este tipo de contradicciones, de esto ya se estaba encargando Ernst Zermelo por su cuenta, ajeno a estos descubrimientos, y es que en esa época no había Internet....ufff, ya me estoy yendo a otro tema...mejor me piro
    ciao

  • #2
    Re: El método diagonal de Cantor

    Buén tema, y buena exposición, felicidades. De todas formas, yo como siempre me voy por los cerros de úveda, para comentarte algo de lo que hablamos un día, contigo y con jubari, y para ponerte una demostración que he encontrado y que me encanta . De hecho algo tiene que ver con el proceso en diagonal osea que ...
    Ese día en cuestión nos preguntabamos que si teniamos una cantidad de conjuntos infinita y numerable, y cada uno de los conjuntos a su vez era infinito y numerable, su reunión era numerable?
    Usando el procedimiento en diagonal de cantor se demuestra que así es, es más, se demuestra sin usar el axioma de elección, por lo tanto la demostración es constructiva.
    Lo que quiero exponer aquí es otra demostración constructiva que se me ha ocurrido sin usar el proceso en diagonal a ver que te parece.
    Bién vamos a numerar cada uno de nuestros conjuntos, de la forma A1, A2, A3 etc.....como la cantidad de conjuntos es numerable, podemos hacerlo. Así mismo vamos a suponer todos los conjuntos disjuntos, lo que no quita generalidad a la demostración, ya que siempre podemos forzar las cosas para que sea así. Así cualquier elemento de la reunión de dichos conjuntos será de la forma A(n,m ) en donde n representa el conjunto en cuestión y m el orden de dicho elemento en el conjunto.
    Es obvio que existe una aplicación inyectiva de N en el conjunto reunión, sirva por ejemplo la biyección de N con cualquiera de los conjuntos de la reunión.
    Ahora se trata de demostrar que existe una aplicación inyectiva desde el conjunto reunión hasta N, lo que por el teorema de Cantor-Bernstein implicará, que existe una biyección entre ambos.
    Hemos dicho que cada elemento del conjunto reunión podía expresarse en la forma A(n,m) siendo n y m naturales
    Pues la aplicación en cuestión, la podemos encontrar usando números primos, a saber, A(n,m)------->2^n*3^m.
    Que te parece?
    PS: Dicho sea de paso, el proceso puede extenderse para demostrar que el producto cartesiano de una cantidad finita de conjuntos numerables es también numerable.

    Comentario


    • #3
      Re: El método diagonal de Cantor

      [FONT=Verdana]Hola a todos[/FONT]

      [FONT=Verdana]El intercambio de opiniones siempre ha sido un modo fructífero de transmisión de las inquietudes, de las experiencias y de los éxitos y fracasos de las personas. Hoy en día, cuando no cabe la posibilidad de charlar y debatir cara a cara, utilizamos el correo electrónico, los mensajes cortos y los foros de la web. Pero cuando aún no se habían inventado estos medios, se utilizaba la correspondencia epistolar (¿os acordáis?).[/FONT]

      [FONT=Verdana]R. Dedekind y G. Cantor, tras entablar amistad después de conocerse en Suiza allá por el año 1872, empezaron a cartearse con cierta asiduidad. Como no podía ser de otro modo, cada una de estas cartas está plagada de cuestiones matemáticas interesantísimas. Es precisamente en una de las primeras cartas donde Cantor invita a Dedekind a buscar una solución al siguiente problema: ¿Se puede o no se puede establecer una correspondencia biunívoca entre los números reales y los naturales? [/FONT]

      [FONT=Verdana]Por aquel entonces Cantor ya había encontrado que los naturales podían ponerse en correspondencia biunívoca con los enteros. La demostración es bien sencilla: basta con reordenar los números enteros en la forma 0, 1, -1, 2, -2, ..., y contarlos en el orden establecido. También había demostrado que los números racionales pueden ponerse en correspondencia biunívoca con los naturales. La demostración es similar a la anterior: [/FONT][FONT=Verdana]dispónganse los racionales en una tabla de la forma[/FONT]

      [FONT=Wingdings 3]"[/FONT]1/1[FONT=Wingdings 3]"[/FONT]2/1 3/1[FONT=Wingdings 3]"[/FONT]4/1 ...
       [FONT=Wingdings 3]'[/FONT] [FONT=Wingdings 3]&[/FONT] [FONT=Wingdings 3]'[/FONT]   
      1/2 2/2 3/2 ...  
      [FONT=Wingdings 3]$[/FONT][FONT=Wingdings 3]&[/FONT] [FONT=Wingdings 3]'[/FONT]     
      1/3 2/3 ...    
       [FONT=Wingdings 3]'[/FONT]       
      1/4 ...      
      [FONT=Wingdings 3]$[/FONT][FONT=Wingdings 3]&[/FONT]       
      1/5 ...      
      ...        


      [FONT=Verdana]y cuéntense siguiendo la flecha.[/FONT]

      [FONT=Verdana]Dedekind no pudo encontrar una solución al problema que le proponía su amigo Cantor, pero demostró (y así se lo comunicó por carta a Cantor), que entre el conjunto de los números algebraicos y el de los naturales sí es posible establecer tal correspondencia biunívoca. La demostración tampoco es complicada:[/FONT]

      [FONT=Verdana]Sea la ecuación general , con entero. Definimos el índice de la ecuación mediante [/FONT][FONT=Symbol][FONT=Symbol]½[/FONT][/FONT][FONT=Verdana][/FONT][FONT=Symbol][FONT=Symbol]½[/FONT][/FONT][FONT=Verdana] + ... +[/FONT][FONT=Symbol][FONT=Symbol]½[/FONT][/FONT][FONT=Verdana][/FONT][FONT=Symbol][FONT=Symbol]½[/FONT][/FONT][FONT=Verdana] + [/FONT][FONT=Symbol][FONT=Symbol]½[/FONT][/FONT][FONT=Verdana][/FONT][FONT=Symbol][FONT=Symbol]½[/FONT][/FONT][FONT=Verdana]+ n[/FONT][FONT=Verdana]. Hay una única ecuación de índice 2, a saber: x = 0. Hay 4 ecuaciones de índice 3, a saber, 2x = 0; x + 1 = 0; x – 1 = 0; x^2= 0; cuyas raíces son 0, 1 y –1. Para cada índice hay un número finito de ecuaciones posibles y por lo tanto, un número finito de posibles raíces reales. Por lo tanto, ordenándolas adecuadamente pueden contarse.[/FONT]

      [FONT=Verdana]La solución final al problema la encontró finalmente Cantor en 1873: los números reales no pueden ponerse en correspondencia biunívoca con los naturales. La demostración la hizo pública un año después en Mathematische Annalen, (Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen, 1874). Pero no fue hasta 1890 que Cantor encontró una segunda demostración del problema, mucho más simple que la primera, de la que nos da noticia NuezMoscada en su post.[/FONT]

      [FONT=Verdana]Lo que es importante de este hallazgo es que con él Cantor pone de manifiesto la existencia de al menos dos infinitos distintos. Más aún, siendo el conjunto de los números algebraicos denumerable (tal como demostró Dedekind), Cantor concluyó con su descubrimiento que son los números trascendentes los que confieren al conjunto de los reales su potencia. La conjetura propuesta por Liouville en 1851 (Joseph Liouville demostró en 1851 que existen irracionales, a los que llamó números trascendentes, que no son raíz de ninguna ecuación algebraica, aisló una clase particular de dichos números -números de Liouville- y conjeturó que en cualquier intervalo hay un número infinito de ellos), había quedado resuelta.[/FONT]

      Saludos

      Comentario


      • #4
        Re: El método diagonal de Cantor

        Mi agradecimiento, por tan buena explicación!

        Comentario


        • #5
          Re: El método diagonal de Cantor

          espero me responda alguien, es muy interesante el tema y pues yo alguna ves recuerdo haber oido que usando el metodo de diagonalizacion de cantor se prueba que los numeros reales son completos, es decir que toda sucesion de Cauchy de nuemeros reales es convergente, se da una sucesion de cauchy arbitraria y usando el metodo de diagonalizacion se haya el limite (numero real al que converje dicha sucesion) pero buscando no he encontrado nada jaja!!, por otro lado, en la prueba de la completes de los numeros reales pues se usan sucesiones de cauchy formada por clases de equivalencia de sucesiones de Cauchy de numeros racionales y pues por esa misma construccion todo numero real es una de esas clases y por tanto cada real es punto limite de una sucesion (considerando al real como el limite de algun un representante de dicha clase de equivalencia) pero me quedo la duda de como se prueba la otra implicacion, es decir, toda sucesion de cauchy es convergente, bueno ps un saludo.

          Comentario

          Contenido relacionado

          Colapsar

          Trabajando...
          X