Recientemente, se hizo una encuesta en un foro de internet donde salía un 20% de votantes a IU. Teniendo en cuenta que este partido tiene aproximadamente un 5% de los votos, algo estaba mal en la encuesta.
Para que un sondeo tenga valor, debe realizarse aleatoriamente. Los componentes de aquel foro no eran una muestra insesgada de la población. Por ejemplo, gran parte de la población no participa en los foros (personas mayores, no poseedores de ordenador, quizá personas de bajo nivel cultural). Hay otros aspectos, como la ideología de los moderadores del foro (o del medio de comunicación) donde se hace la encuesta, que también pueden influir.
Por ejemplo, hay sondeos en medios afines a la derecha donde el 98% de la gente coincide con las ideas del PP. Esos sondeos están claramente sesgados. Esos sondeos no valen de nada.En algunos casos, en esos programas, hay un sociólogo, que sabe esto, y se calla, prestándose a una payasada.
Hace 70 años hubo una encuesta en EEUU a 2.000.000 de habitantes en que Franklin Delano Roosevelt salía perdedor. Naturalmente Roosevelt ganó. El elemento que hizo que la encuesta fuera sesgada fue que se hizo por telefono, y no todo el mundo tenía telefono.No importa cómo de grande sea una muestra. Si es sesgada no sirve para nada.
De hecho, una muestra puede ser sesgada aunque sea una muestra infinita. Por ejemplo, si yo escojo como muestra todos los números racionales entre 0 y 1, tengo una muestra infinita. Y en esa muestra no existe un sólo número irracional. Sin embargo ¡existen números irracionales entre 0 y 1!
Esto prueba que no sirve de nada que la muestra tenga un tamaño tan grande como se quiera. Si la muestra está sesgada, los resultados no sirven de nada.
lunes, 5 de marzo de 2007
viernes, 2 de marzo de 2007
El teorema de Gödel (I)
Hofstadter compara el teorema de Gödel a una curiosa idea. Supone un gramófono de alta fidelidad que pueda producir todos los sonidos posibles. El gramófono se llama X y hay un disco que se llama “No puedo ser escuchado por el gramófono X”. Resulta que si se pone ese disco en el gramófono, éste produce unos sonidos que destruyen el propio gramófono. Es posible usar un gramófono de baja fidelidad, que no producirá esos sonidos y no se autodestruirá. Pero entonces ya no será un gramófono que produzca todos los sonidos posibles.
El sistema de Gödel es una parte de la teoría de la computación. Uno de los conceptos fundamentales para entender el tema de la teoría de la computación es lo que los matemáticos llaman conjunto recursivamente enumerable.
¿Qué es un conjunto recursivamente enumerable? Un conjunto A es recursivamente enumerable si la función f(x) :
f(x) = 1 ( si x pertenece a A)
f(x) = indefinido (si x no pertenece a A)
es computable
Que un conjunto sea recursivamente enumerable es equivalente a que el conjunto sea generable por computador. Un conjunto es recursivo, si tanto él como su complemento son recursivamente enumerables.
En muchos casos el concepto de recursivamente enumerable se usa solo para subconjuntos de N (el conjunto de los números naturales). Por ejemplo, los primos son un conjunto recursivo en N. Consideremos otro conjunto, como los números que forman la sucesión de Fibonacci.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…
Los números de Fibonacci consisten en una serie en la que todo número excepto los dos primeros es la suma de los dos precedentes.
1+1=2
1+2=3
2+3=5
3+5= 8
Yo mismo he ideado un programa en Q-Basic que genera la serie de Fibonacci. La serie de Fibonacci es un típico ejemplo de programa sencillo y también un ejemplo de conjunto recursivamente enumerable. De hecho, un conjunto es recursivamente enumerable si puede ser generado por algún programa. En su libro, Hofstadter produce la serie de Fibonacci por lo que él llama una red de transición recursiva. De hecho, la serie de Fibonacci es un programa muy sencillo, que es usado en los lenguajes de programación para aprendices. Consideremos otro programa de Q-Basic . Un programa que produzca la serie de los números primos hasta un número dado, que el usuario debe introducir en el ordenador. Por ejemplo, el conjunto de los números primos es recursivamente enumerable. Pero ¿el conjunto de los números no primos es recursivamente enumerable? Sí, basta con generar un programa que nos dé todo número m, tal que exista un número n (mayor que 1 y menor que m) para el que se cumpla que el resto de m dividido entre n da 0. Cuando sucede a un conjunto que tanto sus elementos como los elementos que no pertenecen a ese conjunto (los primos como los no primos) son generados mediante sus respectivos programas de ordenador, se dice que ese conjunto es recursivo. Se dice también que tanto el conjunto (los primos) como su complementario (los no primos) son recursivamente enumerables. Es decir, que si el conjunto P es recursivamente enumerable y el conjunto complementario de P es, también, recursivamente enumerable, P es recursivo.
Se plantea la interrogante de si todos los conjuntos recursivamente enumerables son, a su vez recursivos. Lo cierto es que no. Existen conjuntos cuyos elementos son generables mediante un programa, pero no tenemos un programa para generar todos y cada uno de los elementos que no pertenecen al conjunto.
Hofstadter supone que tenemos un conjunto I (por ejemplo los primos) y un conjunto O (Por ejemplo, los números compuestos). Juntos I y O abarcan todos los números naturales. El problema es que hay conjuntos en que podemos generar todos los números del conjunto I, pero no hay programa para generar todos los números del conjunto O.
“Es importante fijarse en que, si los miembros del conjunto I fueran generados siempre en orden creciente, podríamos en todo momento caracterizar a O. El problema es que muchos conjuntos r.e. [recursivamente enumerables] son generados a través de métodos
que diseminan los elementos en un orden arbitrario, así que nunca se sabe si un número omitido largo tiempo obtendrá, esperando un poco más, su inclusión”
Si alguien, al tropezar con estas reflexiones, se asombra de que sea posible que tengamos programa para generar un conjunto pero no para generar su complementario, no debe preocuparse, ya que el mismo Hoftadster confiesa su asombro al ver que no todos los complementos de conjuntos recursivamente enumerables eran recursivamente enumerables. Lo compara a una figura, tal que su borde se pudiera discernir, pero no pudiera verse el borde del fondo que hay entorno a la figura.
“Resultó que yo estaba acertado acerca de los primos, pero equivocado en general, lo cual me asombró, y continúa asombrándome todavía hoy”
Por ejemplo, para todo programa, el conjunto de los inputs para los cuales el programa se para es recursivamente enumerable. Pero no es necesariamente recursivo. Por ejemplo, hay muchos programas, que para determinados inputs, se pierden en un bucle infinito.
Gödel supuso que el conjunto de las verdades matemáticas era recursivamente enumerable. y se dispuso a fabricar un sistema lógico (el equivalente de un programa informático) para generar todas las verdades y sólo las verdades de la matemática. Este programa, además, decidiría, dada una proposición matemática, si ésta era verdaera o no.
La idea de Gödel puede parecer, en principio, muy alejada de la de la Biblioteca de Babel, pero, como veremos, tiene algunas semejanzas. (en realidad algo análogo a lo que lo que Gödel se planteaba parece incompatible con la idea que tenemos de la Biblioteca de Babel: se trataría de buscar un procedimiento para discriminar todos los volúmenes de la Biblioteca que dicen verdad). La Biblioteca de Babel no existía en la realidad, pero era un objeto que podíamos imaginar. Del mismo modo, la Biblioteca de Gödel, es decir aquella Biblioteca que contiene todas las verdades de la aritmética es un objeto concebible, ya que Gödel dio las reglas de su codificación. De hecho, para ser más exactos habría que decir que el procedimiento para discriminar cuáles son las verdades en el mundo de la Biblioteca de Gödel es la demostración lógica, que viene a ser una forma restringida y más técnica de la demostración filosófica. La forma de codificar la Biblioteca de Gödel puede parecer alambicada. En primer lugar hay que reducir todas las verdades de la aritmética (en principio, restrinjámoslas a las afirmaciones acerca de números naturales) a fórmulas lógicas. Esto es esencial, ya que si queremos que las verdades de la aritmética sean demostradas hay que reducirlas inevitablemente a fórmulas lógicas. En segundo lugar, Gödel inventa un código por el cual reduce las fórmulas lógicas a números naturales. Tenemos pues tres niveles:
1) En primer lugar todas las verdades aritméticas sobre los números naturales
2) En segundo lugar las fórmulas lógicas que expresan cada una de esas verdades
3) En tercer lugar los números naturales que codifican esas fórmulas lógicas
Aquí encontramos una suerte de autorreflexión, ya que los números naturales sirven para codificar verdades sobre los números naturales. Como veremos, esto dará lugar a una paradoja que será el resultado fundamental de Gödel.
El sistema de Gödel es una parte de la teoría de la computación. Uno de los conceptos fundamentales para entender el tema de la teoría de la computación es lo que los matemáticos llaman conjunto recursivamente enumerable.
¿Qué es un conjunto recursivamente enumerable? Un conjunto A es recursivamente enumerable si la función f(x) :
f(x) = 1 ( si x pertenece a A)
f(x) = indefinido (si x no pertenece a A)
es computable
Que un conjunto sea recursivamente enumerable es equivalente a que el conjunto sea generable por computador. Un conjunto es recursivo, si tanto él como su complemento son recursivamente enumerables.
En muchos casos el concepto de recursivamente enumerable se usa solo para subconjuntos de N (el conjunto de los números naturales). Por ejemplo, los primos son un conjunto recursivo en N. Consideremos otro conjunto, como los números que forman la sucesión de Fibonacci.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…
Los números de Fibonacci consisten en una serie en la que todo número excepto los dos primeros es la suma de los dos precedentes.
1+1=2
1+2=3
2+3=5
3+5= 8
Yo mismo he ideado un programa en Q-Basic que genera la serie de Fibonacci. La serie de Fibonacci es un típico ejemplo de programa sencillo y también un ejemplo de conjunto recursivamente enumerable. De hecho, un conjunto es recursivamente enumerable si puede ser generado por algún programa. En su libro, Hofstadter produce la serie de Fibonacci por lo que él llama una red de transición recursiva. De hecho, la serie de Fibonacci es un programa muy sencillo, que es usado en los lenguajes de programación para aprendices. Consideremos otro programa de Q-Basic . Un programa que produzca la serie de los números primos hasta un número dado, que el usuario debe introducir en el ordenador. Por ejemplo, el conjunto de los números primos es recursivamente enumerable. Pero ¿el conjunto de los números no primos es recursivamente enumerable? Sí, basta con generar un programa que nos dé todo número m, tal que exista un número n (mayor que 1 y menor que m) para el que se cumpla que el resto de m dividido entre n da 0. Cuando sucede a un conjunto que tanto sus elementos como los elementos que no pertenecen a ese conjunto (los primos como los no primos) son generados mediante sus respectivos programas de ordenador, se dice que ese conjunto es recursivo. Se dice también que tanto el conjunto (los primos) como su complementario (los no primos) son recursivamente enumerables. Es decir, que si el conjunto P es recursivamente enumerable y el conjunto complementario de P es, también, recursivamente enumerable, P es recursivo.
Se plantea la interrogante de si todos los conjuntos recursivamente enumerables son, a su vez recursivos. Lo cierto es que no. Existen conjuntos cuyos elementos son generables mediante un programa, pero no tenemos un programa para generar todos y cada uno de los elementos que no pertenecen al conjunto.
Hofstadter supone que tenemos un conjunto I (por ejemplo los primos) y un conjunto O (Por ejemplo, los números compuestos). Juntos I y O abarcan todos los números naturales. El problema es que hay conjuntos en que podemos generar todos los números del conjunto I, pero no hay programa para generar todos los números del conjunto O.
“Es importante fijarse en que, si los miembros del conjunto I fueran generados siempre en orden creciente, podríamos en todo momento caracterizar a O. El problema es que muchos conjuntos r.e. [recursivamente enumerables] son generados a través de métodos
que diseminan los elementos en un orden arbitrario, así que nunca se sabe si un número omitido largo tiempo obtendrá, esperando un poco más, su inclusión”
Si alguien, al tropezar con estas reflexiones, se asombra de que sea posible que tengamos programa para generar un conjunto pero no para generar su complementario, no debe preocuparse, ya que el mismo Hoftadster confiesa su asombro al ver que no todos los complementos de conjuntos recursivamente enumerables eran recursivamente enumerables. Lo compara a una figura, tal que su borde se pudiera discernir, pero no pudiera verse el borde del fondo que hay entorno a la figura.
“Resultó que yo estaba acertado acerca de los primos, pero equivocado en general, lo cual me asombró, y continúa asombrándome todavía hoy”
Por ejemplo, para todo programa, el conjunto de los inputs para los cuales el programa se para es recursivamente enumerable. Pero no es necesariamente recursivo. Por ejemplo, hay muchos programas, que para determinados inputs, se pierden en un bucle infinito.
Gödel supuso que el conjunto de las verdades matemáticas era recursivamente enumerable. y se dispuso a fabricar un sistema lógico (el equivalente de un programa informático) para generar todas las verdades y sólo las verdades de la matemática. Este programa, además, decidiría, dada una proposición matemática, si ésta era verdaera o no.
La idea de Gödel puede parecer, en principio, muy alejada de la de la Biblioteca de Babel, pero, como veremos, tiene algunas semejanzas. (en realidad algo análogo a lo que lo que Gödel se planteaba parece incompatible con la idea que tenemos de la Biblioteca de Babel: se trataría de buscar un procedimiento para discriminar todos los volúmenes de la Biblioteca que dicen verdad). La Biblioteca de Babel no existía en la realidad, pero era un objeto que podíamos imaginar. Del mismo modo, la Biblioteca de Gödel, es decir aquella Biblioteca que contiene todas las verdades de la aritmética es un objeto concebible, ya que Gödel dio las reglas de su codificación. De hecho, para ser más exactos habría que decir que el procedimiento para discriminar cuáles son las verdades en el mundo de la Biblioteca de Gödel es la demostración lógica, que viene a ser una forma restringida y más técnica de la demostración filosófica. La forma de codificar la Biblioteca de Gödel puede parecer alambicada. En primer lugar hay que reducir todas las verdades de la aritmética (en principio, restrinjámoslas a las afirmaciones acerca de números naturales) a fórmulas lógicas. Esto es esencial, ya que si queremos que las verdades de la aritmética sean demostradas hay que reducirlas inevitablemente a fórmulas lógicas. En segundo lugar, Gödel inventa un código por el cual reduce las fórmulas lógicas a números naturales. Tenemos pues tres niveles:
1) En primer lugar todas las verdades aritméticas sobre los números naturales
2) En segundo lugar las fórmulas lógicas que expresan cada una de esas verdades
3) En tercer lugar los números naturales que codifican esas fórmulas lógicas
Aquí encontramos una suerte de autorreflexión, ya que los números naturales sirven para codificar verdades sobre los números naturales. Como veremos, esto dará lugar a una paradoja que será el resultado fundamental de Gödel.
jueves, 1 de marzo de 2007
Las paradojas de la lógica y los ordenadores
Uno de los problemas fundamentales de las matemáticas son las paradojas. Un ejemplo visual de lo que es una paradoja es la llamada paradoja del mapa, citada por Borges en su ensayo “Magias parciales del Quijote”
“Las invenciones de la filosofía no son menos fantásticas que las del arte: Josiah Royce, en el primer volumen de la obra The world and the individual (1899), ha formulado la siguiente: ‘Imaginemos que una porción del suelo de Inglaterra ha sido nivelada perfectamente y que en ella traza un cartógrafo un mapa de Inglaterra. La obra es perfecta; no hay detalle del suelo de Inglaterra, por diminuto que sea, que no esté registrado en el mapa; todo tiene ahí su correspondencia. Este mapa, en tal caso, debe contener un mapa del mapa, que debe contener un mapa del mapa del mapa, y así hasta lo infinito’...”
Un ejemplo literario de paradoja autorreflexiva aparece en la novela Cien años de soledad. Al final de Cien años de soledad de García Márquez, un personaje descifra unas escrituras cuyo contenido es precisamente Cien años de soledad. ¿Cómo la novela Cien años de soledad puede ser un libro que está dentro de la propia novela? Igualmente, el Quijote aparece dentro del Quijote como una novela.
Estas paradojas son formas gráficas de visualizar lo que son las verdaderas paradojas de la matemática.
La mayoría de las paradojas están relacionadas con el tema de la autorreflexión. Se trata de oraciones que, de algún modo, se refieren a sí mismas (del mismo modo que el mapa de Inglaterra contenía un mapa de sí mismo). Una paradoja célebre surge de la siguiente frase:
El número más pequeño que no se puede expresar con menos de 25 símbolos
Pero esta frase define a ese número con menos de 25 símbolos (si una palabra es igual a un símbolo), por lo que se produce, una situación paradójica. Algo parecido sucede con la siguiente frase:
Los números a los que no se hace referencia en esta frase
Efectivamente, si la frase no hace referencia a un número, entonces hace referencia a él. Y si hace referencia a él, entonces no hace referencia a él. Hay otra frase muy curiosa, la siguiente:
Estha fraze tiene tres errores
¿Dónde está el tercer error? Resulta que el tercer error es que el enunciado de la frase dice que la frase tiene tres errores, cuando solo tiene dos. Pero si esto es verdadero, ¡entonces decir que hay tres errores ya no es un error! Por tanto habría dos errores. Un momento ¡pero entonces hay tres errores! Esto no acaba nunca.
Otras paradojas, más al nivel del lenguaje común, pueden ser: Perdonen las disculpas. O la frase ¿Contestará a esta pregunta con un no? (esto me recuerda el chiste del gallego al que le preguntan si es verdad que los gallegos nunca contestan claramente con un sí o un no, y el gallego contesta: “No sé, puede”).
Imaginemos la frase:
Este enunciado no es autorreferente
No existe una forma de que un enunciado explicite el hecho de no ser autorreferente, sin que el enunciado sea autorreferente. De parejo modo, no hay forma de decir que un objeto no existe sin otorgarle una existencia como objeto del lenguaje (pensemos que tenemos símbolos para hablar de cosas que nadie ha visto, como Dios o el conjunto vacío).
El problema de las proposiciones autorreflexivas es que pueden analizarse de dos formas contradictorias. Por ejemplo, véase la proposición “Este enunciado es falso”.
1) Este enunciado Es falso
-----sujeto----------- predicado
Ésta sería una lectura sintáctica (hablando según lo haría un lingüista más que como un lógico). Hasta aquí no hay ningún problema. No es para hacerse ilusiones, ciertamente, ya que esto también es cierto para “Las ideas verdes duermen furiosamente”. Bien, desde el punto de vista sintáctico la frase es correcta. Ahora bien, si hacemos una lectura semántica, nos encontramos con que, la estructura profunda de esta oración sería:
2) “Este enunciado es falso” Es falso
----------sujeto------------------ predicado
Puesto que el enunciado es autorreferente. Si el argumento “Este enunciado es falso” es falso, entonces, por el principio del tercio excluso, no tiene más remedio que ser verdadero. Pero, en cuanto verdadero, no hace otra cosa que afirmar su propia falsedad.
.¿Qué sucede con nuestros amigos los ordenadores? ¿Entienden las paradojas? Pues va a ser que no. Un computador tiene unos transistores, cada uno de los cuales, tiene dos estados, encendido y apagado. No puede ser que un transistor esté, a la vez, encendido y apagado. El computador asigna un valor de verdad a una proposición, 1 ó 0, pero no puede asignarle, a la vez, los dos valores de verdad. Suponiendo que pudiéramos comunicar al computador una paradoja (algo complicado) lo más probable es que éste quedara en un estado en el que se perdería en un bucle infinito.
¿Qué es un bucle infinito? Una analogía se encuentra en el ensayo de Borges “Magias parciales del Quijote”.
“Algo parecido ha obrado el azar en Las Mil y Una Noches. Esta compilación de historias fantásticas duplica y reduplica hasta el vértigo la ramificación de un cuento central en cuentos adventicios, pero no trata de graduar sus realidades, y el efecto (que debió ser muy profundo) es superficial, como una alfombra persa. Es conocida la historia liminar de la serie: el desolado juramento del rey, que cada noche se desposa con una virgen que hace decapitar en el alba, y la resolución de Shahrazad, que lo distrae con fábulas, hasta que encima de los dos han girado mil y una noches y ella le muestra su hijo. La necesidad de copiar mil y un secciones obligó a los copistas de la obra a interpolaciones de todas clases. Ninguna tan perturbadora como la de la noche 602, mágica entre las noches. En esta noche, el rey oye de boca de la reina su propia historia. Oye el principio de la historia, que abarca a todas las demás, y también -de monstruoso modo- a sí misma. ¿Intuye claramente el lector la vasta posibilidad de esa interpolación, el curioso peligro? Que la reina persista y el inmóvil rey oirá para siempre la trunca historia de Las Mil y Una Noches, ahora infinita y circular...”
En un bucle infinito, el ordenador hace lo siguiente: Se encuentra en un proceso que, en un momento dado X, le manda recomenzar el proceso hasta que llega a X donde vuelve a recomenzar el proceso hasta que llega a X...¿tiene esto final? No, naturalmente, salvo que en muchos casos el ordenador nos dice que la memoria ha sido desbordada.
El hecho de que los ordenadores se metan en un bucle infinito cuando aparece una paradoja nos indica que no pueden entenderla. Esto aparece explicitado en famosos descubrimientos matemáticos como el teorema de Gödel o el problema de la parada de las máquinas de Turing.
“Las invenciones de la filosofía no son menos fantásticas que las del arte: Josiah Royce, en el primer volumen de la obra The world and the individual (1899), ha formulado la siguiente: ‘Imaginemos que una porción del suelo de Inglaterra ha sido nivelada perfectamente y que en ella traza un cartógrafo un mapa de Inglaterra. La obra es perfecta; no hay detalle del suelo de Inglaterra, por diminuto que sea, que no esté registrado en el mapa; todo tiene ahí su correspondencia. Este mapa, en tal caso, debe contener un mapa del mapa, que debe contener un mapa del mapa del mapa, y así hasta lo infinito’...”
Un ejemplo literario de paradoja autorreflexiva aparece en la novela Cien años de soledad. Al final de Cien años de soledad de García Márquez, un personaje descifra unas escrituras cuyo contenido es precisamente Cien años de soledad. ¿Cómo la novela Cien años de soledad puede ser un libro que está dentro de la propia novela? Igualmente, el Quijote aparece dentro del Quijote como una novela.
Estas paradojas son formas gráficas de visualizar lo que son las verdaderas paradojas de la matemática.
La mayoría de las paradojas están relacionadas con el tema de la autorreflexión. Se trata de oraciones que, de algún modo, se refieren a sí mismas (del mismo modo que el mapa de Inglaterra contenía un mapa de sí mismo). Una paradoja célebre surge de la siguiente frase:
El número más pequeño que no se puede expresar con menos de 25 símbolos
Pero esta frase define a ese número con menos de 25 símbolos (si una palabra es igual a un símbolo), por lo que se produce, una situación paradójica. Algo parecido sucede con la siguiente frase:
Los números a los que no se hace referencia en esta frase
Efectivamente, si la frase no hace referencia a un número, entonces hace referencia a él. Y si hace referencia a él, entonces no hace referencia a él. Hay otra frase muy curiosa, la siguiente:
Estha fraze tiene tres errores
¿Dónde está el tercer error? Resulta que el tercer error es que el enunciado de la frase dice que la frase tiene tres errores, cuando solo tiene dos. Pero si esto es verdadero, ¡entonces decir que hay tres errores ya no es un error! Por tanto habría dos errores. Un momento ¡pero entonces hay tres errores! Esto no acaba nunca.
Otras paradojas, más al nivel del lenguaje común, pueden ser: Perdonen las disculpas. O la frase ¿Contestará a esta pregunta con un no? (esto me recuerda el chiste del gallego al que le preguntan si es verdad que los gallegos nunca contestan claramente con un sí o un no, y el gallego contesta: “No sé, puede”).
Imaginemos la frase:
Este enunciado no es autorreferente
No existe una forma de que un enunciado explicite el hecho de no ser autorreferente, sin que el enunciado sea autorreferente. De parejo modo, no hay forma de decir que un objeto no existe sin otorgarle una existencia como objeto del lenguaje (pensemos que tenemos símbolos para hablar de cosas que nadie ha visto, como Dios o el conjunto vacío).
El problema de las proposiciones autorreflexivas es que pueden analizarse de dos formas contradictorias. Por ejemplo, véase la proposición “Este enunciado es falso”.
1) Este enunciado Es falso
-----sujeto----------- predicado
Ésta sería una lectura sintáctica (hablando según lo haría un lingüista más que como un lógico). Hasta aquí no hay ningún problema. No es para hacerse ilusiones, ciertamente, ya que esto también es cierto para “Las ideas verdes duermen furiosamente”. Bien, desde el punto de vista sintáctico la frase es correcta. Ahora bien, si hacemos una lectura semántica, nos encontramos con que, la estructura profunda de esta oración sería:
2) “Este enunciado es falso” Es falso
----------sujeto------------------ predicado
Puesto que el enunciado es autorreferente. Si el argumento “Este enunciado es falso” es falso, entonces, por el principio del tercio excluso, no tiene más remedio que ser verdadero. Pero, en cuanto verdadero, no hace otra cosa que afirmar su propia falsedad.
.¿Qué sucede con nuestros amigos los ordenadores? ¿Entienden las paradojas? Pues va a ser que no. Un computador tiene unos transistores, cada uno de los cuales, tiene dos estados, encendido y apagado. No puede ser que un transistor esté, a la vez, encendido y apagado. El computador asigna un valor de verdad a una proposición, 1 ó 0, pero no puede asignarle, a la vez, los dos valores de verdad. Suponiendo que pudiéramos comunicar al computador una paradoja (algo complicado) lo más probable es que éste quedara en un estado en el que se perdería en un bucle infinito.
¿Qué es un bucle infinito? Una analogía se encuentra en el ensayo de Borges “Magias parciales del Quijote”.
“Algo parecido ha obrado el azar en Las Mil y Una Noches. Esta compilación de historias fantásticas duplica y reduplica hasta el vértigo la ramificación de un cuento central en cuentos adventicios, pero no trata de graduar sus realidades, y el efecto (que debió ser muy profundo) es superficial, como una alfombra persa. Es conocida la historia liminar de la serie: el desolado juramento del rey, que cada noche se desposa con una virgen que hace decapitar en el alba, y la resolución de Shahrazad, que lo distrae con fábulas, hasta que encima de los dos han girado mil y una noches y ella le muestra su hijo. La necesidad de copiar mil y un secciones obligó a los copistas de la obra a interpolaciones de todas clases. Ninguna tan perturbadora como la de la noche 602, mágica entre las noches. En esta noche, el rey oye de boca de la reina su propia historia. Oye el principio de la historia, que abarca a todas las demás, y también -de monstruoso modo- a sí misma. ¿Intuye claramente el lector la vasta posibilidad de esa interpolación, el curioso peligro? Que la reina persista y el inmóvil rey oirá para siempre la trunca historia de Las Mil y Una Noches, ahora infinita y circular...”
En un bucle infinito, el ordenador hace lo siguiente: Se encuentra en un proceso que, en un momento dado X, le manda recomenzar el proceso hasta que llega a X donde vuelve a recomenzar el proceso hasta que llega a X...¿tiene esto final? No, naturalmente, salvo que en muchos casos el ordenador nos dice que la memoria ha sido desbordada.
El hecho de que los ordenadores se metan en un bucle infinito cuando aparece una paradoja nos indica que no pueden entenderla. Esto aparece explicitado en famosos descubrimientos matemáticos como el teorema de Gödel o el problema de la parada de las máquinas de Turing.
miércoles, 28 de febrero de 2007
Isomorfismos o el mapa del imperio
Uno de los más bellos cuentos de Borges es “Del rigor de la ciencia”, el famoso cuento en que aparece el mapa del Imperio que es del tamaño del Imperio
“...En aquel Imperio, el Arte de la Cartografía logró tal Perfección que el mapa de una sola Provincia ocupaba toda una Ciudad, y el mapa del Imperio, toda una Provincia. Con el tiempo, esos Mapas Desmesurados no satisficieron y los Colegios de Cartógrafos levantaron un mapa del Imperio, que tenía el tamaño del Imperio y coincidía puntualmente con él. Menos Adictas al Estudio de la Cartografía, las Generaciones Siguientes entendieron que ese dilatado Mapa era Inútil y no sin Impiedad lo entregaron a las Inclemencias del Sol y de los Inviernos. En los desiertos del Oeste perduran despedazadas Ruinas del Mapa, habitadas por Animales y por Mendigos; en todo el país no hay otra reliquia de las Disciplinas Geográficas".
El cuento de Borges tiene paralelos en las matemáticas. Por ejemplo, en el isomorfismo entre dos estructuras.
Cuando descubrimos un isomorfismo entre dos estructuras, lo que sucede es que el estudio de una puede reducirse al de la otra. Hemos descubierto una analogía entre dos estructuras, que dos estructuras son la misma en algún aspecto.
En cierto modo es como si una de las estructuras fuera un mapa de la otra estructura, de forma que todas las ciudades y todas las carreteras entre las ciudades de la estructura A tienen equivalente en la estructura B.
Las estructuras isomórficas son matemáticamente equivalentes, cualquiera que sea la naturaleza de sus elementos. Del conjunto de ellas puede tomarse una cualquiera como modelo.
Los resultados que sobre esta estructura modelo se consignan, son directamente aplicables a cualquier otra estructura isomorfa a ella, sin más que "traducir" la naturaleza de sus elementos y relaciones.
Cuando estudiaba Filosofía, teníamos una asignatura llamada Filosofía y Matemáticas. Yo no me enteraba de nada en esa asignatura, hasta que vimos el concepto de isomorfismo y el de álgebra booleana. La profesora dijo que había una cosa que habíamos estudiado ya que era isomorfa a un álgebra booleana. Yo me di cuenta de que era la lógica proposicional.
A partir de ahí sentí que ya no estaba tan perdido en la asignatura, y además, incluso me empezó a entrar una afición por las matemáticas, cosa que no había tenido nunca.
En cierto modo el pensamiento matemático surge de esa manera, cuando descubrimos analogías entre las cosas nuevas que todavía no conocemos, y las cosas que conocemos bien.
En un lenguaje coloquial, también utilizamos la analogía, que es una especie de isomorfismo. Por ejemplo, llamamos a una constelación el Can, o la Osa Mayor, porque recuerdan a un perro o a una osa. Son a los cielos, lo que los animales a la vida terrestre. “Valdano es el Cicerón del fútbol”. Es decir, Valdano ocupa en el fútbol la misma posición que Cicerón en la filosofía.
En las matemáticas se dan los únicos ejemplos verdaderos de isomorfismo. Así por ejemplo, la lógica proposicional es isomorfa a un álgebra booleana y, al mismo tiempo, el álgebra booleana lo es a un álgebra de conjuntos.
El álgebra booleana es un álgebra especial que opera con sólo dos números, 1 y 0. Sus leyes son diferentes a las del álgebra habitual
La teoría de conjuntos tiene su jerga particular. Por ejemplo, habla de intersección y unión. Por ejemplo, la intersección del conjunto de los negros y el conjunto de los españoles son todos los españoles que son negros. La unión del conjunto de los negros y el conjunto de los españoles son todos los que o bien son españoles o bien son negros (o bien ambas cosas).
El conjunto universal son todos los elementos del universo: en este caso sería todos los hombres y las mujeres, toda la humanidad. El complementario de un conjunto son los elementos que no pertenecen a ese conjunto. Por ejemplo el complementario del conjunto de los españoles son todos los hombres y mujeres que no son españoles. Por último, el conjunto vacío es el que no tiene ningún elemento.
En la proyección del álgebra booleana sobre el álgebra de conjuntos decimos que el 1 es el conjunto universal; y el 0, el conjunto vacío. Se pueden, pues, trasladar conceptos de las leyes del álgebra booleana al álgebra de conjuntos. Así, “a·1= a” significa que la intersección entre el conjunto a y el conjunto universal es el conjunto a. “a·0= 0” significa que la intersección entre el conjunto a y el conjunto vacío es el conjunto vacío. “a+1=1” (ley que no es válida en el álgebra habitual, pero sí en el álgebra booleana, donde no existe un número mayor que 1) quiere decir que la unión del conjunto a y el conjunto universal es el conjunto universal. “a+0=a” quiere decir que la unión de a y el conjunto vacío es a.
(Recuerdo que estuve matriculado una asignatura que trataba sobre isomorfismos, llamada Teoría de Modelos. De forma asombrosa para tratarse de una difícil asignatura de lógica, se había apuntado un montón e gente. La gente que cogía esa asignatura no era de Filosofía. Era gente de otras carreras que cogía la asignatura como de libre elección. Al parecer, había algunos niños y niñas de Pedagogía que creían que esa asignatura enseñaba a ser modelo de pasarela. Que era como una escuela de modelaje).
La idea de isomorfismo se puede trasladar a las ciencias naturales. Así pues, si la ciencia hace predicciones sobre la realidad, es porque debe haber un isomorfismo entre la teoría científica y la realidad.
La apoteosis de la descripción científica sería una copia a escala 1:1 del objeto que se quiere describir, tal como lo ejemplifica Borges. El mejor mapa del imperio sería un mapa del mismo tamaño que el imperio. El mejor modelo del universo sería otro universo exactamente igual que el actual. (Ya Platón decía que la mejor descripción de Cratilo, sería otro Cratilo).
Naturalmente, lo que Borges evidencia es que esto son absurdos. Lo que la ciencia busca, en realidad, son unas ecuaciones que describan con fidelidad una serie limitada de fenómenos no la totalidad de las cosas.
Ian Stewart (¿Juega Dios a los dados?. Barcelona, Crítica, 2001) imagina un computador que calculara todas las variables del universo en un instante, para predecir cual sería el universo en el siguiente instante. Uno de los problemas que se plantea es dónde escribiría el computador los datos, ya que tiene que manejar como mínimo seis variables, la posición y la velocidad, para cada partícula del universo.
Además, el computador debería estar fuera del universo, porque si no, el hecho de hacer el cálculo afectaría al estado del universo, por lo que la computadora se metería en un bucle infinito, pues debería calcular el resultado después de calcular el resultado después de calcular el resultado después de calcular, así ad infinitum.
Una paradoja semejante la propone Hofstadter (The Mind’s I). Supongamos que Aquiles quiere saberlo todo sobre el estado de su cerebro. Lee un libro donde aparece pormenorizadamente el estado neuronal de Aquiles, neurona por neurona y sinapsis por sinapsis. Entonces conoce el estado del cerebro de Aquiles antes de leer el libro. Porque, por el hecho de leerlo, su estado cerebral ha variado.
Naturalmente, lo que se saca como conclusión es que la ciencia hace una simplificación del mundo, un modelo a escala reducida. De ahí las imperfecciones de la ciencia. Pero, también, gracias a ello es que la ciencia resulta manejable.
“...En aquel Imperio, el Arte de la Cartografía logró tal Perfección que el mapa de una sola Provincia ocupaba toda una Ciudad, y el mapa del Imperio, toda una Provincia. Con el tiempo, esos Mapas Desmesurados no satisficieron y los Colegios de Cartógrafos levantaron un mapa del Imperio, que tenía el tamaño del Imperio y coincidía puntualmente con él. Menos Adictas al Estudio de la Cartografía, las Generaciones Siguientes entendieron que ese dilatado Mapa era Inútil y no sin Impiedad lo entregaron a las Inclemencias del Sol y de los Inviernos. En los desiertos del Oeste perduran despedazadas Ruinas del Mapa, habitadas por Animales y por Mendigos; en todo el país no hay otra reliquia de las Disciplinas Geográficas".
El cuento de Borges tiene paralelos en las matemáticas. Por ejemplo, en el isomorfismo entre dos estructuras.
Cuando descubrimos un isomorfismo entre dos estructuras, lo que sucede es que el estudio de una puede reducirse al de la otra. Hemos descubierto una analogía entre dos estructuras, que dos estructuras son la misma en algún aspecto.
En cierto modo es como si una de las estructuras fuera un mapa de la otra estructura, de forma que todas las ciudades y todas las carreteras entre las ciudades de la estructura A tienen equivalente en la estructura B.
Las estructuras isomórficas son matemáticamente equivalentes, cualquiera que sea la naturaleza de sus elementos. Del conjunto de ellas puede tomarse una cualquiera como modelo.
Los resultados que sobre esta estructura modelo se consignan, son directamente aplicables a cualquier otra estructura isomorfa a ella, sin más que "traducir" la naturaleza de sus elementos y relaciones.
Cuando estudiaba Filosofía, teníamos una asignatura llamada Filosofía y Matemáticas. Yo no me enteraba de nada en esa asignatura, hasta que vimos el concepto de isomorfismo y el de álgebra booleana. La profesora dijo que había una cosa que habíamos estudiado ya que era isomorfa a un álgebra booleana. Yo me di cuenta de que era la lógica proposicional.
A partir de ahí sentí que ya no estaba tan perdido en la asignatura, y además, incluso me empezó a entrar una afición por las matemáticas, cosa que no había tenido nunca.
En cierto modo el pensamiento matemático surge de esa manera, cuando descubrimos analogías entre las cosas nuevas que todavía no conocemos, y las cosas que conocemos bien.
En un lenguaje coloquial, también utilizamos la analogía, que es una especie de isomorfismo. Por ejemplo, llamamos a una constelación el Can, o la Osa Mayor, porque recuerdan a un perro o a una osa. Son a los cielos, lo que los animales a la vida terrestre. “Valdano es el Cicerón del fútbol”. Es decir, Valdano ocupa en el fútbol la misma posición que Cicerón en la filosofía.
En las matemáticas se dan los únicos ejemplos verdaderos de isomorfismo. Así por ejemplo, la lógica proposicional es isomorfa a un álgebra booleana y, al mismo tiempo, el álgebra booleana lo es a un álgebra de conjuntos.
El álgebra booleana es un álgebra especial que opera con sólo dos números, 1 y 0. Sus leyes son diferentes a las del álgebra habitual
La teoría de conjuntos tiene su jerga particular. Por ejemplo, habla de intersección y unión. Por ejemplo, la intersección del conjunto de los negros y el conjunto de los españoles son todos los españoles que son negros. La unión del conjunto de los negros y el conjunto de los españoles son todos los que o bien son españoles o bien son negros (o bien ambas cosas).
El conjunto universal son todos los elementos del universo: en este caso sería todos los hombres y las mujeres, toda la humanidad. El complementario de un conjunto son los elementos que no pertenecen a ese conjunto. Por ejemplo el complementario del conjunto de los españoles son todos los hombres y mujeres que no son españoles. Por último, el conjunto vacío es el que no tiene ningún elemento.
En la proyección del álgebra booleana sobre el álgebra de conjuntos decimos que el 1 es el conjunto universal; y el 0, el conjunto vacío. Se pueden, pues, trasladar conceptos de las leyes del álgebra booleana al álgebra de conjuntos. Así, “a·1= a” significa que la intersección entre el conjunto a y el conjunto universal es el conjunto a. “a·0= 0” significa que la intersección entre el conjunto a y el conjunto vacío es el conjunto vacío. “a+1=1” (ley que no es válida en el álgebra habitual, pero sí en el álgebra booleana, donde no existe un número mayor que 1) quiere decir que la unión del conjunto a y el conjunto universal es el conjunto universal. “a+0=a” quiere decir que la unión de a y el conjunto vacío es a.
(Recuerdo que estuve matriculado una asignatura que trataba sobre isomorfismos, llamada Teoría de Modelos. De forma asombrosa para tratarse de una difícil asignatura de lógica, se había apuntado un montón e gente. La gente que cogía esa asignatura no era de Filosofía. Era gente de otras carreras que cogía la asignatura como de libre elección. Al parecer, había algunos niños y niñas de Pedagogía que creían que esa asignatura enseñaba a ser modelo de pasarela. Que era como una escuela de modelaje).
La idea de isomorfismo se puede trasladar a las ciencias naturales. Así pues, si la ciencia hace predicciones sobre la realidad, es porque debe haber un isomorfismo entre la teoría científica y la realidad.
La apoteosis de la descripción científica sería una copia a escala 1:1 del objeto que se quiere describir, tal como lo ejemplifica Borges. El mejor mapa del imperio sería un mapa del mismo tamaño que el imperio. El mejor modelo del universo sería otro universo exactamente igual que el actual. (Ya Platón decía que la mejor descripción de Cratilo, sería otro Cratilo).
Naturalmente, lo que Borges evidencia es que esto son absurdos. Lo que la ciencia busca, en realidad, son unas ecuaciones que describan con fidelidad una serie limitada de fenómenos no la totalidad de las cosas.
Ian Stewart (¿Juega Dios a los dados?. Barcelona, Crítica, 2001) imagina un computador que calculara todas las variables del universo en un instante, para predecir cual sería el universo en el siguiente instante. Uno de los problemas que se plantea es dónde escribiría el computador los datos, ya que tiene que manejar como mínimo seis variables, la posición y la velocidad, para cada partícula del universo.
Además, el computador debería estar fuera del universo, porque si no, el hecho de hacer el cálculo afectaría al estado del universo, por lo que la computadora se metería en un bucle infinito, pues debería calcular el resultado después de calcular el resultado después de calcular el resultado después de calcular, así ad infinitum.
Una paradoja semejante la propone Hofstadter (The Mind’s I). Supongamos que Aquiles quiere saberlo todo sobre el estado de su cerebro. Lee un libro donde aparece pormenorizadamente el estado neuronal de Aquiles, neurona por neurona y sinapsis por sinapsis. Entonces conoce el estado del cerebro de Aquiles antes de leer el libro. Porque, por el hecho de leerlo, su estado cerebral ha variado.
Naturalmente, lo que se saca como conclusión es que la ciencia hace una simplificación del mundo, un modelo a escala reducida. De ahí las imperfecciones de la ciencia. Pero, también, gracias a ello es que la ciencia resulta manejable.
miércoles, 21 de febrero de 2007
Geometría e inducción
Creo que algunas leyes abstractas se pueden explicar de maneras intuitivas, geométricas. Por ejemplo, la propiedad conmutativa de la multiplicación.El resultado 5·3=3·5 se puede ver con el siguiente dibujo:
o o o o o
o o o o o
o o o o o
La propiedad conmutativa consiste en que, al girar este objeto 90º, sigue habiendo igual número de o´s. (Esto se puede mostrar también, por ejemplo, con latas de coca cola).La propiedad de que 1 +3 +5 + 2n-1= n^2 se puede mostrar con la siguiente sucesión de figuras (que se pueden figurar, con latas de coca cola, de manera que formen verdaderos cuadrados):
o
o o
o o
o o o
o o o
o o o
o o o o
o o o o
o o o o
o o o o
Naturalmente que (para probar este resultado) se necesita inducción. Pero eso puede llegar mucho más adelante. Lo esencial es despertar la curiosidad sobre las matemáticas. Las demostraciones pueden llegar en una etapa posterior.
La demostración por inducción funciona de la siguiente mamera
Hay que demostrar que si
1 + 3 +5…+(2n-1) = n^2
entonces
1 + 3 +5…+ n+ (2n+1) = (n+1)^2
Pero, sumando (2n+1) en el primer y segundo miembro de la primera igualdad tenemos que:
1 + 3 +5…+ (2n-1) + (2n+1) = n^2 + (2n +1)
Pero, efectivamente, (n+1)^2 = n ^2 + 2n +1 Por tanto, hemos demostrado que ambas sucesiones son equivalentes para cualquier número natural.
o o o o o
o o o o o
o o o o o
La propiedad conmutativa consiste en que, al girar este objeto 90º, sigue habiendo igual número de o´s. (Esto se puede mostrar también, por ejemplo, con latas de coca cola).La propiedad de que 1 +3 +5 + 2n-1= n^2 se puede mostrar con la siguiente sucesión de figuras (que se pueden figurar, con latas de coca cola, de manera que formen verdaderos cuadrados):
o
o o
o o
o o o
o o o
o o o
o o o o
o o o o
o o o o
o o o o
Naturalmente que (para probar este resultado) se necesita inducción. Pero eso puede llegar mucho más adelante. Lo esencial es despertar la curiosidad sobre las matemáticas. Las demostraciones pueden llegar en una etapa posterior.
La demostración por inducción funciona de la siguiente mamera
Hay que demostrar que si
1 + 3 +5…+(2n-1) = n^2
entonces
1 + 3 +5…+ n+ (2n+1) = (n+1)^2
Pero, sumando (2n+1) en el primer y segundo miembro de la primera igualdad tenemos que:
1 + 3 +5…+ (2n-1) + (2n+1) = n^2 + (2n +1)
Pero, efectivamente, (n+1)^2 = n ^2 + 2n +1 Por tanto, hemos demostrado que ambas sucesiones son equivalentes para cualquier número natural.
sábado, 17 de febrero de 2007
El infinito de Cantor
La teoría de Cantor se basa en la idea de que un conjunto es infinito si puede ponerse en aplicación biyectiva con un subconjunto de sí mismo.
La aplicación biyectiva consiste en hacer corresponder a cada elemento del primer conjunto uno y sólo uno del segundo.
Al 1 corresponde el 2
Al 2 corresponde el 4
Al 3 corresponde el 6
Al 4 corresponde el 8
Esto es una aplicación biyectiva entre los números naturales y los pares
Hay una paradoja acerca de esto. Imagínense un hotel de infinitas habitaciones, en el que todas las habitaciones están ocupadas. Llega alguien al hotel, y no hay habitación para él. El dueño del hotel cambia al huésped de la habitación 1 a la habitación 2, al de de la habitación 2 a la habitación 3, al de de la habitación 3 a la habitación 4. Pregunta: ¿en qué habitación se metería al nuevo huésped? El dueño podría meter en el hotel, incluso, al doble de huéspedes. Cambiaría al huésped de la habitación 1 a la habitación 2, al de de la habitación 2 a la habitación 4, al de de la habitación 3 a la habitación 6…..y así tendría desalojadas la mitad de las habitaciones del hotel, con el objeto de incluir nuevos huéspedes.
Tengamos los números reales entre 0 y 1 ordenados en una tabla, de tal manera que se pueda trazar una aplicación biyectiva entre los naturales y los reales entre 0 y 1.
0,143201
0,121234
0,132114
0,123345
0,124654
0,134766
Imaginemos que esta lista sigue hasta el infinito…Será entonces posible construir un nuevo número real comprendido en el intervalo entre 0 y 1 por el procedimiento de colocar en el lugar de la primera cifra decimal del primer número 1+1 en el lugar de la segunda del segundo número 2+1, en el lugar de la tercera cifra del tercer número 2+1, y así sucesivamente. Pero este número real no sería ya idéntico a ninguno de los incluidos en la tabla, ya que es distinto de cada uno de ellos, por lo menos en una cifra decimal. Veámoslo con números
El número 0,233467... no puede estar en ningún lugar de la lista, porque difiere del primer número en la primera cifra, del segundo en la segunda, del tercero en la tercera, etc. Pero, supongamos que en la lista hemos puesto todos los números reales entre 0 y 1 ¡nuestro nuevo número no estará en la lista! Esto significa que el intervalo de los números reales comprendido entre 0 y 1 es no numerable (es un infinito mayor que el de los números naturales).
Si se tratara de establecer una aplicación biyectiva entre los números naturales y los reales, se agotaría la serie de los números naturales (suponiendo que esto fuera posible, pero no lo es) antes de que se pudiera recorrer en su totalidad el subconjunto de R que comprende tan sólo a los números reales comprendidos entre 0 y 1. Podría suponerse que esto es debido a que, dados dos números reales, por próximos que estén, siempre existe otro entre ellos. Pero esto no es así. El conjunto de los números racionales es un conjunto denso (entre dos números racionales, por muy cerca que estén, siempre se puede encontrar otro). Pero, sin embargo, existe una forma de ordenar el conjunto Q de los racionales de tal manera que pueda establecerse una aplicación biyectiva entre el conjunto de los racionales y el conjunto de los naturales.
1/1
2/1
1/2
1/3
2/2
3/1
4/1
3/2
2/3
1/4
1/5
……..
Esto no sucede con respecto al conjunto de los reales. Como dice Carl Boyer:
“Tanto Galileo como Leibniz habían pensado que la ‘continuidad’ de los puntos de una recta era el resultado de su densidad, es decir, del hecho de que entre dos puntos distintos cualesquiera hay siempre otro. Sin embargo, los números racionales gozan de esta propiedad a pesar de que no forman obviamente un continuo”
No hay que confundir la densidad con la no numerabilidad. Podría pensarse que los números reales no sean muchos más que los racionales, ya que éstos también tienen una expresión decimal infinita. Pero hay que tener en cuenta que los racionales suelen tener expresiones decimales periódicas, es decir más ordenadas que los irracionales (que son la mayoría de los reales, los reales que no son racionales). Así, por ejemplo, la expresión decimal de 1/ 3 es 0,33333... Hay muchas más formas desordenadas que ordenadas (como en el cuento de Borges “La Biblioteca de Babel”, donde aparecen todos los libros posibles mediante variaciones de todas las letras del alfabeto y los libros inteligibles son una minoría) y por eso debe haber más irracionales que racionales. Además, hay que tener en cuenta que un conjunto es enumerable si puede ordenarse uno a uno con el de los números naturales, y esto, que sucede a los racionales (como hemos visto), la prueba de Cantor demuestra que no puede suceder a los reales.
En algún caso se ha sugerido aplicar el método diagonal a los racionales. Tengamos una lista de todos los racionales:
0,12345…
0,23450…
0,01234…
0,54321…
0,23451…
Aquí, nada garantiza que el número diagonal 0,24332 sea racional. Podría ser perfectamente un irracional. Véase el siguiente ejemplo
0,66666
0,33333
0,50000
0,25000
0,77777
Los números de la lista son todos periódicos, y en cambio en la diagonal no es posible discernir ningún tipo de periodicidad.
Claro que si vamos sacando nuevos dígitos podría encontrarse la periodicidad del número diagonal (pero es mucho más probable no encontrarla).
El procedimiento diagonal se puede aplicar a los irracionales, pero no a los racionales. Sucede algo parecido con la demostración de que no existe una enumeración efectiva de las funciones recursivas totales de una variable (que utiliza un método diagonal). Como se sabe, esa prueba no se puede aplicar a las recursivas parciales. Porque para las funciones recursivas parciales no podemos garantizar que la máquina de Turing dé un resultado.
La aplicación biyectiva consiste en hacer corresponder a cada elemento del primer conjunto uno y sólo uno del segundo.
Al 1 corresponde el 2
Al 2 corresponde el 4
Al 3 corresponde el 6
Al 4 corresponde el 8
Esto es una aplicación biyectiva entre los números naturales y los pares
Hay una paradoja acerca de esto. Imagínense un hotel de infinitas habitaciones, en el que todas las habitaciones están ocupadas. Llega alguien al hotel, y no hay habitación para él. El dueño del hotel cambia al huésped de la habitación 1 a la habitación 2, al de de la habitación 2 a la habitación 3, al de de la habitación 3 a la habitación 4. Pregunta: ¿en qué habitación se metería al nuevo huésped? El dueño podría meter en el hotel, incluso, al doble de huéspedes. Cambiaría al huésped de la habitación 1 a la habitación 2, al de de la habitación 2 a la habitación 4, al de de la habitación 3 a la habitación 6…..y así tendría desalojadas la mitad de las habitaciones del hotel, con el objeto de incluir nuevos huéspedes.
Tengamos los números reales entre 0 y 1 ordenados en una tabla, de tal manera que se pueda trazar una aplicación biyectiva entre los naturales y los reales entre 0 y 1.
0,143201
0,121234
0,132114
0,123345
0,124654
0,134766
Imaginemos que esta lista sigue hasta el infinito…Será entonces posible construir un nuevo número real comprendido en el intervalo entre 0 y 1 por el procedimiento de colocar en el lugar de la primera cifra decimal del primer número 1+1 en el lugar de la segunda del segundo número 2+1, en el lugar de la tercera cifra del tercer número 2+1, y así sucesivamente. Pero este número real no sería ya idéntico a ninguno de los incluidos en la tabla, ya que es distinto de cada uno de ellos, por lo menos en una cifra decimal. Veámoslo con números
El número 0,233467... no puede estar en ningún lugar de la lista, porque difiere del primer número en la primera cifra, del segundo en la segunda, del tercero en la tercera, etc. Pero, supongamos que en la lista hemos puesto todos los números reales entre 0 y 1 ¡nuestro nuevo número no estará en la lista! Esto significa que el intervalo de los números reales comprendido entre 0 y 1 es no numerable (es un infinito mayor que el de los números naturales).
Si se tratara de establecer una aplicación biyectiva entre los números naturales y los reales, se agotaría la serie de los números naturales (suponiendo que esto fuera posible, pero no lo es) antes de que se pudiera recorrer en su totalidad el subconjunto de R que comprende tan sólo a los números reales comprendidos entre 0 y 1. Podría suponerse que esto es debido a que, dados dos números reales, por próximos que estén, siempre existe otro entre ellos. Pero esto no es así. El conjunto de los números racionales es un conjunto denso (entre dos números racionales, por muy cerca que estén, siempre se puede encontrar otro). Pero, sin embargo, existe una forma de ordenar el conjunto Q de los racionales de tal manera que pueda establecerse una aplicación biyectiva entre el conjunto de los racionales y el conjunto de los naturales.
1/1
2/1
1/2
1/3
2/2
3/1
4/1
3/2
2/3
1/4
1/5
……..
Esto no sucede con respecto al conjunto de los reales. Como dice Carl Boyer:
“Tanto Galileo como Leibniz habían pensado que la ‘continuidad’ de los puntos de una recta era el resultado de su densidad, es decir, del hecho de que entre dos puntos distintos cualesquiera hay siempre otro. Sin embargo, los números racionales gozan de esta propiedad a pesar de que no forman obviamente un continuo”
No hay que confundir la densidad con la no numerabilidad. Podría pensarse que los números reales no sean muchos más que los racionales, ya que éstos también tienen una expresión decimal infinita. Pero hay que tener en cuenta que los racionales suelen tener expresiones decimales periódicas, es decir más ordenadas que los irracionales (que son la mayoría de los reales, los reales que no son racionales). Así, por ejemplo, la expresión decimal de 1/ 3 es 0,33333... Hay muchas más formas desordenadas que ordenadas (como en el cuento de Borges “La Biblioteca de Babel”, donde aparecen todos los libros posibles mediante variaciones de todas las letras del alfabeto y los libros inteligibles son una minoría) y por eso debe haber más irracionales que racionales. Además, hay que tener en cuenta que un conjunto es enumerable si puede ordenarse uno a uno con el de los números naturales, y esto, que sucede a los racionales (como hemos visto), la prueba de Cantor demuestra que no puede suceder a los reales.
En algún caso se ha sugerido aplicar el método diagonal a los racionales. Tengamos una lista de todos los racionales:
0,12345…
0,23450…
0,01234…
0,54321…
0,23451…
Aquí, nada garantiza que el número diagonal 0,24332 sea racional. Podría ser perfectamente un irracional. Véase el siguiente ejemplo
0,66666
0,33333
0,50000
0,25000
0,77777
Los números de la lista son todos periódicos, y en cambio en la diagonal no es posible discernir ningún tipo de periodicidad.
Claro que si vamos sacando nuevos dígitos podría encontrarse la periodicidad del número diagonal (pero es mucho más probable no encontrarla).
El procedimiento diagonal se puede aplicar a los irracionales, pero no a los racionales. Sucede algo parecido con la demostración de que no existe una enumeración efectiva de las funciones recursivas totales de una variable (que utiliza un método diagonal). Como se sabe, esa prueba no se puede aplicar a las recursivas parciales. Porque para las funciones recursivas parciales no podemos garantizar que la máquina de Turing dé un resultado.
viernes, 16 de febrero de 2007
Sobre "La Biblioteca de Babel"
“La Biblioteca de Babel” es uno de los cuentos más famosos de Borges. Se trata de una biblioteca que contiene el conjunto de todos los libros posibles. Tal como lo expresa el propio Borges:
“Todo: la historia minuciosa del porvenir, las autobiografías de los arcángeles, el catálogo fiel de la Biblioteca, miles y miles de catálogos falsos, la demostración de la falacia de esos catálogos, la demostración de la falacia del catálogo verdadero, el evangelio de Basílides, el comentario de ese evangelio, el comentario del comentario de ese evangelio, la relación verídica de tu muerte, la versión de cada libro a todas las lenguas, las interpolaciones de cada libro en todos los libros”.
Un buen día, se encuentra un libro que tiene dos páginas enteras inteligibles: Su contenido eran “nociones de análisis combinatorio, ilustradas por ejemplos de variaciones con repetición ilimitada”. Precisamente la Biblioteca es un ejemplo de variaciones “con repetición ilimitada” o, simplemente, de variaciones con repetición.
Supongamos que la Biblioteca consta de libros de 500 páginas, cada uno con 2000 letras por página. En total cada libro tendría 1.000.000 de letras. Supongamos que hay 100 signos distintos. En total, el número de libros de la Biblioteca sería 100^1.000.000.
Daniel C. Dennett imagina que la Biblioteca podría ser ordenada alfabéticamente, pero la idea de Borges es que los libros de la Biblioteca estarían ordenados al azar. Aun si los libros estuvieran ordenados por orden alfabético, resultaría, por ejemplo, que "Don Quijote" estaría a una distancia astronómica de "La Regenta" (en realidad "Don Quijote" no estaría en la Biblioteca, pero uniendo quizá 4 ó 5 volúmenes se podría obtener todo el libro). Pero supongamos que "Don Quijote" sólo tuviera 1.000.000 de letras. En este caso habría 100.000.000 de mutantes con un error de una sola letra. Pero imagínense cuantos mutantes habría con una media de 2.000 errores, la mayoría de los cuales serían copias relativamente fieles de "Don Quijote". Si naciéramos en la galaxia "Don Quijote" estaríamos toda la vida viendo tan sólo copias de ese libro.
Pero imaginemos, como quiere Borges, que los libros están distribuidos al azar. En ese caso, en la Biblioteca de Babel es mucho más fácil encontrar un libro sin sentido que un libro escrito con correcta sintaxis y semántica en castellano. Ello se debe a que son muchas más las combinaciones de letras sin ningún significado que las que son correcto castellano. Esto es algo semejante a lo que ocurre con los números irracionales. Como se sabe, los números irracionales tienen una expresión decimal caótica, mientras que la expresión decimal de los racionales es periódica. Pero existen muchos más números con una expresión decimal caótica que con expresión decimal periódica. Ésta es una forma intuitiva de visualizar la mayor cardinalidad de los irracionales (es decir, el hecho de que hay más irracionales que racionales)
Racional: 1,4141414141414141414141414141414141…
Irracional: 1,3457892146807213585423468426847871…
“Todo: la historia minuciosa del porvenir, las autobiografías de los arcángeles, el catálogo fiel de la Biblioteca, miles y miles de catálogos falsos, la demostración de la falacia de esos catálogos, la demostración de la falacia del catálogo verdadero, el evangelio de Basílides, el comentario de ese evangelio, el comentario del comentario de ese evangelio, la relación verídica de tu muerte, la versión de cada libro a todas las lenguas, las interpolaciones de cada libro en todos los libros”.
Un buen día, se encuentra un libro que tiene dos páginas enteras inteligibles: Su contenido eran “nociones de análisis combinatorio, ilustradas por ejemplos de variaciones con repetición ilimitada”. Precisamente la Biblioteca es un ejemplo de variaciones “con repetición ilimitada” o, simplemente, de variaciones con repetición.
Supongamos que la Biblioteca consta de libros de 500 páginas, cada uno con 2000 letras por página. En total cada libro tendría 1.000.000 de letras. Supongamos que hay 100 signos distintos. En total, el número de libros de la Biblioteca sería 100^1.000.000.
Daniel C. Dennett imagina que la Biblioteca podría ser ordenada alfabéticamente, pero la idea de Borges es que los libros de la Biblioteca estarían ordenados al azar. Aun si los libros estuvieran ordenados por orden alfabético, resultaría, por ejemplo, que "Don Quijote" estaría a una distancia astronómica de "La Regenta" (en realidad "Don Quijote" no estaría en la Biblioteca, pero uniendo quizá 4 ó 5 volúmenes se podría obtener todo el libro). Pero supongamos que "Don Quijote" sólo tuviera 1.000.000 de letras. En este caso habría 100.000.000 de mutantes con un error de una sola letra. Pero imagínense cuantos mutantes habría con una media de 2.000 errores, la mayoría de los cuales serían copias relativamente fieles de "Don Quijote". Si naciéramos en la galaxia "Don Quijote" estaríamos toda la vida viendo tan sólo copias de ese libro.
Pero imaginemos, como quiere Borges, que los libros están distribuidos al azar. En ese caso, en la Biblioteca de Babel es mucho más fácil encontrar un libro sin sentido que un libro escrito con correcta sintaxis y semántica en castellano. Ello se debe a que son muchas más las combinaciones de letras sin ningún significado que las que son correcto castellano. Esto es algo semejante a lo que ocurre con los números irracionales. Como se sabe, los números irracionales tienen una expresión decimal caótica, mientras que la expresión decimal de los racionales es periódica. Pero existen muchos más números con una expresión decimal caótica que con expresión decimal periódica. Ésta es una forma intuitiva de visualizar la mayor cardinalidad de los irracionales (es decir, el hecho de que hay más irracionales que racionales)
Racional: 1,4141414141414141414141414141414141…
Irracional: 1,3457892146807213585423468426847871…
Suscribirse a:
Entradas (Atom)