Versión infinita del teorema de Ramsey
Comentábamos hace unos días que el Teorema de Ramsey en su versión inicial es finitista: no hace mención alguna de conjuntos infinitos. SIn elbargo existe una versión infinita del mismo, cuyo enunciado podría ser el siguiente:
Dado un conjunto infinito numerable A, si coloreamos todos sus subconjuntos de k elementos con r colores, entonces existe un subjonjunto B infinito tal que todos sus subconjuntos de k elementos llevan el mismo color.
En el lenguaje de los grafos ( lo cual, recordemos, sólo es posible cuando los subconjuntos son de tamaño k=2), tendríamos:
Si en un grafo completo infinito numerable coloreamos sus aristas con r colores, necesariamente tendremos un subgrafo monocromático de tamaño infinito.
Lo realmente extraordinario es que este teorema nos facilita una demostración inmediata del famoso Teorema de Bolzano .
Este teorema dice que Toda sucesión infinita de números reales contiene una subsucesión infinita que es monótona (creciente o decreciente)
La demostración es interesantísima por su simplicidad:
Sea A tal sucesión infinita de reales. Coloreemos todos sus subconjuntos de tres elementos {a,b,c}con cuatro colores, dependiendo de la disposición de los tres números que forman el subconjunto:
Color 1: si los tres elementos forman una secuencia creciente
Color 2: si el central es el mayor de los tres
Color 3: si el central es el menor de los tres
Color 4: si los tres elementos forman una secuencia decreciente.
No hay más posibilidades, de forma que nos bastan cuatro colores para asignar un color a cada uno de los subconjuntos de tamaño tres de la sucesión.
Pues bien: la versión infinita de Ramsey nos garantiza la existencia de un subconjunto infinito de A tal que todos sus subconjuntos de tres elementos son del mismo color. Es evidente que ese color sólo puede ser el 1 ó el 4, que corresponderían a la subsucesión creciente o decreciente del teorema de Bolzano.
Creo sinceramente que quien no se sorprenda con esta demostración, es que no ha entendido nada; o tiene la sensibilidad matemática de un celentéreo.
Dado un conjunto infinito numerable A, si coloreamos todos sus subconjuntos de k elementos con r colores, entonces existe un subjonjunto B infinito tal que todos sus subconjuntos de k elementos llevan el mismo color.
En el lenguaje de los grafos ( lo cual, recordemos, sólo es posible cuando los subconjuntos son de tamaño k=2), tendríamos:
Si en un grafo completo infinito numerable coloreamos sus aristas con r colores, necesariamente tendremos un subgrafo monocromático de tamaño infinito.
Lo realmente extraordinario es que este teorema nos facilita una demostración inmediata del famoso Teorema de Bolzano .
Este teorema dice que Toda sucesión infinita de números reales contiene una subsucesión infinita que es monótona (creciente o decreciente)
La demostración es interesantísima por su simplicidad:
Sea A tal sucesión infinita de reales. Coloreemos todos sus subconjuntos de tres elementos {a,b,c}con cuatro colores, dependiendo de la disposición de los tres números que forman el subconjunto:
Color 1: si los tres elementos forman una secuencia creciente
Color 2: si el central es el mayor de los tres
Color 3: si el central es el menor de los tres
Color 4: si los tres elementos forman una secuencia decreciente.
No hay más posibilidades, de forma que nos bastan cuatro colores para asignar un color a cada uno de los subconjuntos de tamaño tres de la sucesión.
Pues bien: la versión infinita de Ramsey nos garantiza la existencia de un subconjunto infinito de A tal que todos sus subconjuntos de tres elementos son del mismo color. Es evidente que ese color sólo puede ser el 1 ó el 4, que corresponderían a la subsucesión creciente o decreciente del teorema de Bolzano.
Creo sinceramente que quien no se sorprenda con esta demostración, es que no ha entendido nada; o tiene la sensibilidad matemática de un celentéreo.
10 comentarios
Yazu -
Porque la explicación hipersimplificada de la teoría de Ramsey dice "El desorden completo es imposible" entonces la disposición de los decimales de un número irracional debería tener un orden.
EDWIN -
Giselle -
Saludos
Giselle
xor and -
Caigo por aqui de casualidad, googleando informacion sobre el teorema de Ramsey (accesible para mortales no matemáticos como yo). Mi inquietud o confusión es: es aplicable en algo el teorema de Ramsey a los numeros primos ? - Me explico: si en un conjunto suficienteme grande de numeros primos (cercano al infinito) se puede hallar una sucesion racional ( con racional quiero decir que cumplan alguna condicion común )
Ricardo -
yandhery -
Tio Petros -
Una demostración del teorema de Ramsey la tienes en el excelente documento PDF siguiente:
mipagina.cantv.net/jhnieto1/tc.pdf
En las páginas 86-88 se desarrolla la demostración que pides.
Dicha demostración se apoya en el llamado principio de Dirichlet (conocido vulgarmente como "el principio del palomar"), y se desarrolla en varias fases: se demuestra para r=1, como un corolario del principio arriba citado, luego para casos más complicados, por inducción. Creo que es una demostración difícil (para mi lo es). Un saludo.
Anónimo -
Un saludo
Tio Petros -
En caso contrario, no tendría sentido las cuatro diferenciaciones que hemos hecho para asignar los cuatro colores.
La omisión es mía, el mérito de explicarlo, tuyo.
Un saludo.
pepe -
Un saludo