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

Ser Humano

"Ser humano" y "ser algún humano" parecen predicados similares, pero haré notar las grandes diferencias. Por empezar, en la primera frase, la palabra "humano" es un adjetivo, pero en la segunda es un sustantivo. Por qué? Porque en la primera ocurrencia de "humano" subyace un conjunto de características (humanas) y en la última una colección de seres vivos.

Claramente, si bien se escribe siempre igual, la palabra tiene dos definiciones bien distintas. A la primera, de "ser humano", "tener características humanas", "ser de tipo humano", la llamaremos "tipo humano"; a la segunda "grupo humano". Supongamos que yo quiero saber si Javier es de tipo humano ( :D )... suponiendo que sabemos de antemano qué es SER un humano, ya que conocemos las propiedades que hacen a uno; sólo bastaría con ver que Javier cumple con todas las condiciones para demostrar la sentencia... si encuentro que Javier NO cumple con alguna de ellas, el predicado se valúa en falso. Por otro lado, la pregunta "es Javier algún humano?" (del grupo) hace referencia a otro tipo de análisis. Para saber si tal cosa es cierta, debería ejecutarse un experimento: suponiendo que yo puedo analizar a toda la raza y a cada uno de sus integrantes, bastaría con encontrar a Javier entre la población para demostrar la sentencia... si no puedo encontrar a Javier, entonces el predicado para este caso es falso.

Qué ocurre en el párrafo anterior?

1)

Como tipo: para el primer análisis, uno "arranca" suponiendo que el juicio es VERDADERO hasta que se pruebe lo contrario. Sin embargo, si la cantidad de características a chequear es muy grande, probar la sentencia se vuelve una tarea impráctica (hasta quizá imposible) aunque la idea sea claramente falsable.

Como grupo: en el segundo análisis, uno arranca asumiendo que el juicio es FALSO, hasta que se encuentre a Javier. Como el número de personas en el mundo (hoy en 2011) es de aproximadamente 7 mil millones de individuos, la refutación se vuelve impráctica (ya que hay que analizar a miles de millones para mantener el juicio en falso). Claro que hay grupos con infinitos elementos (imaginar infinitas personas), por lo que en esos casos una refutación es imposible; sin embargo bastaría con un solo Javier para mostrar la veracidad de la sentencia.

2)

Como tipo: la primera definición es análoga a un teoría del humano. Así, un modelo es un humano si cumple con todos los axiomas (atributos) de la teoría. Se trata de constructos, de abstracciones, de razonamientos e inferencias...

Como grupo: la segunda tiene que ver con la realidad, con los hechos, con lo empírico: aquí a la verdad hay que encontrarla en vez de deducirla.

3)

Como tipo: uno conoce A PRIORI lo que es "ser humano" (conocemos las cualidades que lo definen, más o menos), pero NO ocurre lo mismo con Javier: Javier sólo puede ser conocido a posteriori; o sea, luego de observar todas sus propiedades.

Como grupo: aquí ocurre lo contrario. Sabemos quién es Javier, conocemos sus atributos a priori, lo que nos permite buscar entre todos los miembros del grupo "Humano": si alguno de ellos tiene exactamente los mismos rasgos que Javier, entonces debe tratarse de él (asumimos que Javier es una entidad; es único). Sin embargo, sólo podemos conocer al grupo humano A POSTERIORI una vez que conocemos a todos sus integrantes.

4)
Como tipo: ya que no conocemos a priori a Javier, debemos hacer una observación completa de la persona para probar que se trata de un ser humano. O sea, la finalidad es saber si Javier es humano o no.
Como grupo: ya sabemos quién es Javier porque lo observamos anteriormente o tenemos conciencia de sus características de alguna otra forma. Ahora sólo basta con encontrarlo entre todas las personas: el objetivo es hallar a Javier entre la multitud... se trata de saber si existe una persona con ciertos rasgos.

5)
Como tipo: se trata de un conjunto de propiedades, pero las propiedades también son tipos. Por lo tanto, un tipo es una colección de tipos, preferentemente más "sencillos"... luego explicaré a lo que me refiero con "sencillo".
Como grupo: se trata de un conjunto de objetos de cualquier tipo (valga la redundancia). Un grupo mismo puede ser visto como un objeto también.

Y qué tiene de asombroso todo esto? Que ambos, los tipos y los grupos, son conjuntos. Ambos, de alguna manera, parecen complementarse. Y en el lenguaje tradicional de la lógica que vemos los que estudiamos ciencia o ingeniería, "x es algún humano" o "x es humano" puede escribirse como "Humano(x)", donde x es un término que representa a un objeto y Humano una fórmula (predicado o relación unaria)... también puede escribirse "x ∈
Humano". Aunque quizá la primera notación sea más adecuada para los tipos, y la segunda para los grupos.

Conjuntos normales y singulares:

En 1901, el filósofo y matemático británico Bertrand Russell hizo una distinción entre dos clases de conjuntos, a los que llamó "normales" y "singulares". Un conjunto es normal si NO pertenece a sí mismo; o sea, no es elemento de sí mismo. Un conjunto es singular si no es normal (o sea, las nociones de "normal" y "singular" son lógicamente contrarias). Por ejemplo, el conjunto T = {"perro", "gato", 1, 2, 3} es normal, pero S = {"perro", "gato", S} es singular. Estas definiciones le permitieron al filósofo demostrar que hay una contradicción en la teoría original de conjuntos, formulada por Georg Cantor y Gottlob Frege... se trata de la "paradoja de Russell", y la muestro a continuación:


Sean:

• N la colección de todos los conjuntos normales; 
• S la colección de todos los conjuntos singulares.

Qué tal si nos preguntamos "es N normal?":

• Supongamos que sí. En este caso, como N es la colección de todos los normales, N debe ser un elemento de N... pero esto es absurdo ya que eso haría que N fuera singular.
• Debe ser entonces que N es singular. Entonces, N es elemento de S. Como N y S son complementarios, N NO pertenece a N. Absurdo, ya que esto haría que N fuera normal.

No quedan dudas que se trata de una inconsistencia en la teoría tradicional de conjuntos. Cómo se puede solucionar?

Ahora que tipos y grupos son distintos...

Una solución es limitarse a aquellos tipos y grupos que podemos definir (no es posible con todos; ver "definable set" en las referencias). Qué procesos podemos utilizar para definir unos y otros? Una forma segura de evitar paradojas es la siguiente:

• Los tipos pueden ser definidos por "comprensión". Notemos que los atributos también son tipos; por lo tanto, cada tipo puede ser una lista de tipos más "simples"... estos deben estar definidos con anterioridad, para evitar crear "tipos singulares" y ciclos (y por ende, evitando paradojas de Russell). Entonces, sea X el tipo formado por X1, X2 y X3, con X1, X2 y X3 definidos antes que X; para chequear que x es X debería ocurrir que x es X1, que x es X2 y que x es X3. Por ejemplo, el tipo "Humano" podría estar formado por "Mamífero", "Bípedo", "Depredador", "Autoconciente", etc...

• Los grupos pueden ser definidos por "extensión". Un grupo es un conjunto de elementos. Por ejemplo, el grupo "Humano" será el conjunto formado por "Juan X", "María Y", "Fernanda R", "Bruno O", "Javier G", etc. Hay que tener cuidado de no crear "grupos singulares" y circularidades al estilo Russell ya que sabemos que pueden traer problemas.

Finalmente, comento algunas cosas...

Al principio, antes de hacer este detallado examen ( :P ), pensé que la diferencia entre las dos nociones tenía que ver con la distinción entre "juicio analítico" y "juicio sintético" (Kant, "Crítica de la Razón Pura")... consideré a la sentencia "Javier es Humano" como una especie de juicio analítico, y a "Javier es algún Humano" como un juicio sintético. Sin embargo, podemos notar que "Javier es Humano" no es analítico ya que las palabras "Javier" y "Humano" no determinan por sí solas todas las características de la persona y de los humanos, respectivamente... no son atómicas. "Javier" es sólo una etiqueta para un conjunto más amplio de información; lo mismo pasa con "Humano". Por lo tanto, la sentencia "Javier es Humano" es SINTÉTICA A PRIORI... luego me di cuenta que el primer juicio es a priori, y el segundo a posteriori, y es esa la naturaleza de la diferencia entre ambos.


Además, en la primera versión de este artículo sostuve que el problema de la paradoja de Russell radicaba en que la teoría original de conjuntos no hace distinción entre los tipos y los grupos. Sin embargo, hoy sé que estaba equivocado: luego consideré que mi propuesta (solución) era rebuscada, poco práctica y hasta quizá incorrecta, así que la descarté en esta nueva publicación. Para hacer notar la gran brecha entre lo teórico y lo empírico, me dediqué a encontrar nuevas diferencias entre ambos mundos: a priori (tipos) y a posteriori (grupos).

El tema da para mucho análisis, así que no se trata del último artículo... pronto veremos que hay una amplia relación entre la brecha "a priori" y "a posteriori", y la disparidad entre lo "computable" y lo "incomputable"... pasando por los bucles extraños de Hofstadter (Gödel, Escher, Bach) y las autorreferencias...

Más datos:

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

http://es.wikipedia.org/wiki/Paradoja_de_Russell#La_paradoja_en_t.C3.A9rminos_de_conjuntos

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

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

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

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_tipos
http://en.wikipedia.org/wiki/Definable_set

http://es.wikipedia.org/wiki/Distinci%C3%B3n_anal%C3%ADtico-sint%C3%A9tico

http://es.wikipedia.org/wiki/Cr%C3%ADtica_de_la_raz%C3%B3n_pura

http://es.wikipedia.org/wiki/Juicios_sint%C3%A9ticos_a_priori

http://es.wikipedia.org/wiki/Bucle_extra%C3%B1o

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

http://es.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach