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