Q^c Indecidible

Hace unos años tuve la oportunidad de dar clases de apoyo para ingreso universitario en ingeniería en sistemas. Mi único alumno me consultó por una duda acerca de un ejercicio introductorio de aritmética. La consigna presentaba un conjunto de números reales; el objetivo era asignar cada número a su “conjunto correspondiente”: naturales, enteros, racionales, irracionales, reales o complejos. Claro que la consigna tenía ciertos defectos evidentes: por ejemplo, el número 2 no sólo es natural, sino que también es entero, racional y real. Por lo tanto, no hay “conjunto correspondiente” para el 2. Sin embargo, uno podía asumir que el ejercicio pedía asignar cada valor al conjunto más “pequeño” al que perteneciera. En el caso del 2, sería el conjunto de los naturales.

Además, tenía otro defecto que en ese momento no pude “destapar”. Se presentaba un número con una infinita cantidad de cifras decimales... claro que no todas estaban escritas ya que eso es imposible (¡ja!), pero sí unas 8 ó 9 seguidas de puntos suspensivos a la derecha. No recuerdo el valor, pero supongamos que era “1.23581321...”; le llamaremos x. Mi alumno estaba ansioso por mi respuesta y posterior explicación de por qué x es racional o irracional. Debo aceptar que me mantuvo pensando por un tiempo bastante largo... a simple vista, x NO parece racional ya que estos números (si no tienen una cantidad finita de decimales) suelen mostrar un patrón repetitivo en su parte decimal (periódicos puros); x parece no tenerlo. Sin embargo, es imposible asegurar que x no lo tenga: quizá el período de repetición sea de más de 8 cifras. Podría tener un período de 10 cifras; por ejemplo x =  1.2358132199 2358132199 23... Así, el número sería racional. O podría ser que x sea periódico mixto: por ejemplo x = 1.2358132199777777777... Sencillamente, entre 1.2358132199 y 1.2358132200 hay una infinidad de números reales, algunos racionales y otros no ¿Cómo podría yo saber el tipo de x sin poder acceder a las siguientes cifras decimales? ¿Cómo podría alguien saberlo?

Finalmente, luego de un razonamiento incorrecto, ¡di a mi alumno una respuesta errónea! Al día siguiente le llamé por teléfono para rectificar. De hecho, le dije que en realidad no conocía un método que resuelva el problema general: dado un número real arbitrario, decidir si es racional o irracional. Por unos días estuve imaginando la posibilidad de que el problema sea indecidible: esto significa que no existe un algoritmo que logre resolverlo, dado cualquier real... quizá sí para casos particulares, como raíces de números naturales por ejemplo, pero no para todos los casos. Años después y varias materias universitarias más tarde, en la actualidad, tengo una respuesta al asunto. Veamos...

1. Enumerando pruebas.

¿Qué es una prueba, o demostración de una sentencia w? Sin ahondar en el concepto, se trata de una sucesión de sentencias que parten de un conjunto de premisas (axiomas, postulados o teoremas... en definitiva: sentencias consideradas ciertas o anteriormente probadas verdaderas) y concluyen en w. Es un método que asegura la veracidad de w: o sea, si hay una prueba para w, entonces w “es verdadera” (o w representa una verdad). Esta propiedad se llama “corrección” (en lógica matemática). Sabemos que cada sentencia debe estar escrita en un lenguaje formal; por lo tanto, cada sentencia es una cadena (o conjunto ordenado, o sucesión) finita de símbolos pertenecientes a un alfabeto. Es una clase particular de lo que los lógicos llaman “palabra”. Por ejemplo, la cadena “a+b=c” es una sentencia formada por símbolos “a”, “b”, “c”, “+” y “=”. Una sentencia no debe necesariamente representar una verdad; por ejemplo, la cadena “2+2=5” es una sentencia aún cuando la interpretación natural que le demos a los símbolos “+” y “=” sugiera una mentira.

Para simplificar el razonamiento de la cuestión, vamos a dejar de preocuparnos por la formalidad del lenguaje en que están escritas nuestras sentencias. Aún cuando el español está muy lejos de cualquier formalidad matemática o lógica, la utilización de lenguajes formales requeriría de una introducción demasiado tediosa y probablemente insustancial (bueno, ¡quizá exagero! Pero dejemos ese asunto para próximos artículos). Suponga que tenemos un alfabeto$\Sigma$bien grande formado por TOOOODOS los símbolos humanos que se hayan usado alguna vez en la historia... desde jeroglíficos o caracteres rúnicos, hasta caracteres latinos, signos matemáticos o lógicos... incluso aquellos que suelen no ser considerados caracteres pero aún así símbolos: cruces, estrellas, flechas, formas geométricas y otras pictografías... estados eléctricos, codones genéticos, estados de activación neuronal, etc etc etc. Bueno, sin exagerar... pero en definitiva, si bien son muchos, podríamos enumerarlos (con mucha paciencia... no lo vamos a hacer ahora). Esto significa que podríamos asignar un número natural único a cada carácter, lo que hace a$\Sigma$un conjunto enumerable (o contable).

Ahora, consideremos la siguiente pregunta fundamental: sea${\Sigma }^{\text{*}}$el conjunto de todas las sentencias formadas por una cantidad finita de caracteres de$\Sigma$...${\Sigma }^{\text{*}}$= {“2+2=4”, “2+2=5”, “2>1”, “1>2”, “perro=canino”, “gato=felino”, “mañana es viernes”,  “ayer fue domingo”, “yo soy Mickey Mouse”, etc...}... entonces , ¿es${\Sigma }^{\text{*}}$enumerable? Un buen estudiante de computación (digamos) sabe que sí... hay varias formas de enumeración.

1. 1)Por ejemplo, si consideramos que$\Sigma$tiene una cantidad finita M de símbolos, que además$w=w_1\mathrm{...}{w}_n\in {\Sigma }^{\text{*}}$, y que$f(v)\in \mathbb{N}$es un número que asignamos únicamente al símbolo$v\in \Sigma$, entonces w puede codificarse en el valor$F(w)=f(w_1)+f(w_2)(M+1)+f(w_3){(M+1)}^2+\mathrm{...}+f(w_n){(M+1)}^{n-1}\in \mathbb{N}$. Como f(v) > 0,  el valor también codifica el tamaño de la sentencia en cuestión: el grado de F(w) es n-1 ya que$f(v)\ne 0$. 
   
   
2. 2)La numeración de Gödel es otro método que nos permite codificar una palabra en un número natural. 

Ahora supongamos que P es el conjunto de todas las pruebas formadas por sentencias de${\Sigma }^{\text{*}}$. Por ejemplo, la siguiente es una prueba que está en P (recuerde que decidimos olvidar la formalidad):

Sentencia 1 (premisa): “Todos los humanos son mortales”.

Sentencia 2 (premisa): “Sócrates es humano” (o fue humano mejor dicho).

Sentencia 3 (conclusión, por reglas de particularización y modus ponens entre 1 y 2): “Sócrates es mortal”.

¿Es P enumerable? Con un argumento similar a alguno de los que usamos para observar que${\Sigma }^{\text{*}}$lo es, es claro que P es enumerable. O sea que concluimos que podemos asignar un número natural para cada prueba de P, lo que significa que hay a lo sumo tantas pruebas como números naturales.

2. Descontando irracionales.

Otra pregunta a responder es: ¿es Qc (irracionales) enumerable? Cualquiera sabe que$ℝ=\mathbb{Q}\cup {\mathbb{Q}}^c$… ¡o eso creo! Además, cualquier matemático sabe que R (reales) NO es enumerable: lo ha demostrado Cantor en 1981. Un buen “computólogo” sabe que Q es enumerable ya que está formado por elementos que son pares de enteros de la forma p/q (podemos utilizar la numeración de Gödel nuevamente considerando algunos pequeños detalles, o la prueba del mismo Georg Cantor).

Ahora, si suponemos que Qc es enumerable tenemos que$\mathbb{Q}\cup {\mathbb{Q}}^c$también lo es ya que podemos contar sus elementos de la siguiente forma:

1: primer elemento de Q,

2: primer elemento de Qc,

3: segundo elemento de Q,

4: segundo elemento de Qc,

5: tercer elemento de Q,

etc.

Pero$ℝ=\mathbb{Q}\cup {\mathbb{Q}}^c$, por lo que llegamos a un absurdo ya que sabemos que R NO es enumerable. Por lo tanto, debe ser que Qc tampoco es enumerable.

Por otro lado, veamos que hay POR LO MENOS tantos irracionales como naturales. Notemos que toda raíz cuadrada de un número primo es irracional (podemos probarlo utilizando el teorema fundamental de la aritmética) y que el conjunto$\{\sqrt{p}\mathrm{:}p\in \mathbb{N},\text{p primo}\}=\{\sqrt{\mathrm{2,}}\sqrt{\mathrm{3,}}\sqrt{\mathrm{5,}}\mathrm{...}\}\subseteq {\mathbb{Q}}^c$tiene tantos elementos como números naturales (ya que es, valga la redundancia, enumerable). Esto es, podemos considerar la siguiente asignación (a la izquierda de la flecha los irracionales mencionados, y a la derecha todo número natural):

$\begin{array}{c}\sqrt{2}\to \mathrm{0,}\\ \sqrt{3}\to \mathrm{1,}\\ \sqrt{5}\to \mathrm{2,}\\ \sqrt{7}\to \mathrm{3,}\\ \mathit{etc}\mathrm{...}\end{array}$

Por lo tanto, el cardinal de Qc (que es un número “transfinito”) es mayor o igual al de N (también transfinito).

3. Numerales que no encajan.

En el punto 1 vimos que P es enumerable, en el punto 2 que Qc  no lo es. Asimismo, descubrimos la cardinalidad de cada conjunto. Además, veamos que NO puede ser que #P = #Qc ya que en ese caso Qc sería contable. Esto nos lleva a pensar que Qc  es “más grande” que P; o sea que #P < #Qc.

Volviendo a las sentencias, piense en el conjunto$S=\{\text{"x es irracional"}\in {\Sigma }^{\text{*}}\mathrm{:}x\in ℝ,\text{"x es irracional"}\text{tiene una prueba en}P\}$. O sea, el conjunto formado por todas las sentencias que representan el hecho de que un x real es irracional. Notemos que como$S\subseteq {\Sigma }^{\text{*}}$, S es contable, por lo que #S = #P = #N (S es infinito). ¿Por qué utilizo la palabra “representan”? Porque una sentencia verdadera NO es lo mismo que una verdad (o un hecho); la primera es de carácter sintáctico mientras que la segunda es de naturaleza semántica.

Para diferenciar mejor entre una sentencia verdadera y una verdad, piense en el conjunto definido como$T=\{\text{"x es irracional"}\text{como hecho}\mathrm{:}x\in ℝ\}$. O sea, T como el conjunto de verdades o hechos que tienen que ver con que x es irracional, para cualquier x real. Sencillamente, T es el conjunto de verdades de la forma “x es irracional”. Obviamente #T = #Qc ya que hay tantas verdades de la forma “x es irracional” como números irracionales. Observemos que T NO está conformado por “palabras”, pero S sí lo está.

Finalmente, ya no queda salida e inevitablemente caemos en la cruda realidad!: #S = #P < #Qc = #T, lo que significa que, excepto para algunos x en particular, existen verdades de la forma “x es irracional” que NO pueden demostrarse. ¿Pero por qué no? Porque como #P < #T, ¡no hay una cantidad suficiente de pruebas en P para verdades en T!

4. Conclusión.

No siempre es posible decidir si un número real es irracional, incluso cuando de verdad lo sea. Por lo tanto, dado un irracional con esas características, tampoco es posible probar que es racional ya que tal cosa no es verdadera. En definitiva, el problema es indecidible. Eso hace que no exista método alguno, ya sea con un algoritmo, con un programa de computadora o un procedimiento formal que funcione en todos los casos (para todo x real). Es que ningún sistema conocido parece ser lo suficientemente expresivo como para trabajar con todo Q: ¡los irracionales escapan al alcance de cualquier “sistema enumerable”! Por ejemplo, los ordenadores son máquinas finitas que sólo pueden hacer cálculos de valores almacenados en registros finitos o memoria finita.

Una pregunta a contestar en próximos artículos es: ¿qué números reales NO padecen de estas trabas? Otra eterna pregunta es: ¿un cerebro humano sufre de las mismas limitaciones que un ordenador?... muchos creemos que sí: todos los humanos tenemos una cantidad finita de neuronas y conexiones sinápticas; es muy probable que el conjunto de estados capaces de ser generados por un cerebro también sea finito, aún cuando inimaginablemente grande. Para mi es una clara evidencia de las limitaciones de la abstracción humana.

Más info:

http://es.wikipedia.org/wiki/Número_racional

http://es.wikipedia.org/wiki/Problema_indecidible

http://en.wikipedia.org/wiki/Soundness

http://es.wikipedia.org/wiki/Lenguaje_formal

http://es.wikipedia.org/wiki/S%C3%ADmbolo

http://es.wikipedia.org/wiki/Conjunto_enumerable

http://es.wikipedia.org/wiki/Numeraci%C3%B3n_de_G%C3%B6del

http://es.wikipedia.org/wiki/Diagonalizaci%C3%B3n_de_Cantor

http://es.wikipedia.org/wiki/Teorema_fundamental_de_la_aritm%C3%A9tica

http://es.wikipedia.org/wiki/N%C3%BAmero_transfinito

Real o imaginario?

Kurt Gödel

Algunos de los que estamos dentro del círculo de las matemáticas o de la computación, y otros dentro de otros ambientes, sabemos que en ciertas teorías de la lógica (tradicional) hay sentencias que son verdaderas pero no se pueden probar. Este descubrimiento se le atribuye, entre otras personas, a Kurt Gödel (1906 - 1978), quien en el año 1930 demostró sus Teoremas de Incompletitud; quizá el trabajo más conocido de Gödel y uno de los más significativos (si no el más) de la historia de las matemáticas.

Sin muchas vueltas, propongo imaginar una analogía entre la lógica y la "esencia" de todo aquello que es observable. Lo último tiene que ver con los objetos de estudio de las ciencias fácticas...

1) En la lógica, una sentencia puede ser verdadera o puede ser falsa.
Análogamente, en la naturaleza, una idea u objeto puede ser real o imaginario, puede existir o no.

2) En la lógica, "probar" o demostrar la veracidad de una sentencia es encontrar una prueba formal que asevere que tal sentencia es verdadera. Una prueba es similar a un algoritmo; es una sucesión de pasos que permiten resolver el problema: "es una sentencia verdadera?" Claro que si demostramos tal fórmula no quedan dudas de que es cierta.

En la naturaleza, decimos que algo es real cuando lo observamos. Es decir, si encontramos una forma de medir x, ya sea directamente con alguno de nuestros sentidos o por medio de instrumentos (como lo hace la ciencia), queda claro que x es real. A veces la ciencia suele generalizar usando la inducción, pero no viene al caso: si yo observo que un vaso cae de una mesa y se rompe, es claro que resultado "vaso roto" es real (a menos que sea mental y seriamente insano, jeje).

3) En la lógica, "refutar" una sentencia es probar que su opuesta es verdadera. Es el único método que existe para demostrar que tal fórmula es falsa: la ausencia de pruebas no hace a la idea incierta.

Análogamente, en la naturaleza, si observamos un fenómeno opuesto a x, queda por sentado que x NO es real. Por ejemplo, es claro que si veo a mi vecino caminando por la calle (y otros vecinos lo ven, asegurando que no estoy de la cabeza :P), definitivamente NO se encuentra en su casa; y eso es muy real.

4) Finalmente, llegamos al punto más interesante. En la lógica, recordando lo que está escrito en la introducción de este artículo, algunas sentencias son verdaderas, pero no se pueden probar (ni refutar, claro, ya que así serían falsas). Un caso es el de la sentencia "esto no se puede probar"; para más información, recomiendo leer la sección "esbozo de prueba para el primer teorema" en la referencia a "teoremas de incompletitud". Esto significa que NO existe una sucesión de pasos que resuelvan el problema de afirmar que la fórmula sea cierta... aún cuando sea una gran verdad.
Este es un (gran) problema de la lógica, una clara limitación... para algunos incómoda, desagradable; para otros como para mi, apasionante por sus implicaciones.

Análogamente, no sería tan descabellado pensar que haya fenómenos naturales REALES que NO se puedan observar. Después de todo, observar x es encontrar una forma de medir x. Que no seamos capaces de hallar tal método de medición, o incluso que no exista no significa que x sea imaginario o irreal.

Teniendo muy en cuenta esta analogía como un posible isomorfismo ( :P ), opino que es tiempo de echar un ojo al método científico OTRA VEZ, que está tan asociado a la observación. Además, algunas conjeturas sugestivas se consideran "no falsables" por el simple hecho de tratar sucesos no observables, con lo que automáticamente son etiquetadas con desprecio como "pseudociencia".

Qué tal si buscamos otro procedimiento para examinar la realidad? Recién el siglo pasado nos topamos con la llamada "revolución indeterminista", que nos dio una gran lección que aprendimos a medias. Quizá sea momento de volver a la metafísica y de recordar sus fines; no nos olvidemos de la filosofía. Pero tomemos la cuestión con pinzas... no vaya a ser que regresemos a la fe, ahora que sabemos que es una excusa conveniente para algunos pocos.

Mucha más info interesante, accediendo por los siguientes vínculos:

http://es.wikipedia.org/wiki/Falsacionismo
http://es.wikipedia.org/wiki/Kurt_Gödel
http://es.wikipedia.org/wiki/Teorema_de_incompletitud
http://es.wikipedia.org/wiki/Razonamiento_inductivo
http://es.wikipedia.org/wiki/Ciencias_f%C3%A1cticas
http://es.wikipedia.org/wiki/Metaf%C3%ADsica
http://sociedadytecnologiaculnocg8.wordpress.com/revolucion-cientifica/revolucion-indeterminista/

El tema da para muchos posts...

Javier Alejandro Gallo, Córdoba, Argentina, 25 de Julio de 2011.