Ser cuadrado es divertido.

Cómo construir un cubo.

Me refiero a la figura. De hecho, en general, al politopo que generaliza al segmento, al cuadrado, al cubo, al hipercubo, y a todos los n-cubos, con n natural (me faltó nombrar al punto, de dimensión 0?). En general, todos conocemos a los primeros tres... pero, qué es un hipercubo? Cómo definimos a un cubo de más de tres dimensiones? Si los consideramos meros grafos (vértices unidos por aristas, sin considerar la posición de cada vértice), es muy sencillo; veamos que hay un patrón para construirlos:

* Un segmento es la unión de dos puntos por una arista.

* Para tener un cuadrado, debemos tomar dos segmentos A y B. Suponiendo que a1 y a2 son los vértices de A, y b1 y b2 son los vértices de B, al unir por aristas a1 con b1 y a2 con b2 tenemos un cuadrado.

* Para construir un cubo, debemos tener dos cuadrados A y B. Sean a1,a2,a3,a4 los vértices de A y b1,b2,b3,b4 los de B, al unir por aristas a1 con b1, a2 con b2, a3 con b3, a4 con b4 tenemos un cubo.


El patrón es notable en las dimensiones más bajas; podemos generalizarlo y aplicarlo a dimensiones más altas:

* Para construir un (n+1)-cubo ("cubo de dimensión n+1"), tomamos dos n-cubos A y B (dos cubos de una dimensión inmediatamente más baja). Sean a1,a2,...,a2^n los vértices de A y b1,b2,...,b2^n los vértices de B, al unir por aristas a1 con b1, a2 con b2, ... , a2^n con b2^n tenemos un (n+1)-cubo. Para quienes no conozcan la notación, "2^n" significa "dos elevado a la n-ésima potencia"; 2 multiplicado n veces. Simplificado: tomo dos cubos A y B de una dimensión inmediatamente más baja, y ligo con aristas cada vértice de A con exactamente un vértice de B.

Lo que para algunos puede no ser muy claro es que este método asume que un n-cubo tiene 2^n vértices. Pero esta cuestión es muy sencilla de demostrar:

* Claramente, un segmento tiene 2 = 2^1 vértices.
* Un cuadrado está formado por dos segmentos unidos por sus vértices. Cada segmento tiene dos vértices, por lo que tenemos 2 + 2 = 4 = 2^2 vértices.
* Un cuadrado está formado por dos cuadrados unidos por sus vértices. Cada cuadrado tiene cuatro vértices, por lo que tenemos 4 + 4 = 8 = 2^3 vértices.
* Etcétera, para dimensiones más altas.

De hecho, un punto consta de un solo vértice y su dimensión es 0; 1 = 2^0.

La lógica y los cubos.

Alguno diría "qué nexo puede llegar a haber entre un politopo, que es un elemento geométrico, y la lógica?". Otros afirmarían "pfff, por suerte todo se relaciona con la lógica, los cubos no son la excepción". Si bien no estoy seguro de la segunda afirmación (:P) sé que la primera es incorrecta. Inclusive, la correlación puede llegar a ser tan obvia (para nuestras mentes) que pocas veces la notamos.

Una proposición es una declaración que puede ser verdadera o falsa, pero no ambas al mismo tiempo (pues claro). Si es verdadera, se dice que su valor de verdad es verdadero; de lo contrario su valor de verdad es falso. Por ejemplo, "el sol es una estrella" es una proposición cuyo valor de verdad es verdadero, "dos y dos son cinco" es otra cuyo valor es falso. La declaración "qué bonito día!" NO es una proposición. Además, diremos que dos proposiciones son "independientes" si el valor de verdad de una no afecta al de la otra. Por ejemplo, podemos asumir que "yo tengo un gato" y "yo tengo un perro" son independientes, ya que podría no tener ninguno, podría tener uno de ellos, o incluso ambos (poco tiene que ver la propia rivalidad entre perros y gatos). Sin embargo, "hoy es lunes" y "mañana es martes" NO son independientes ya que si la primera es verdadera, la segunda también lo es.

Vamos a imaginar que tenemos una clase de mundo (algo así como una "plantilla") formada por una cantidad n de proposiciones independientes. Cada proposición será p1, p2, p3, ..., pn. Llamaremos a n el grado de la clase. Un mundo será una instancia de esta clase, donde cada proposición toma algún valor de verdad. Para ejemplificar, supongamos que nuestra clase está formada por n = 2 proposiciones, que son las siguientes:

p1: "Javier tiene un gato".
p2: "Javier tiene un perro".

Entonces, pregunto: cuántos mundos de esta clase podría haber? Respuesta: cuatro mundos.

Mundo número 1: p1 y p2 son falsos; o sea, Javier no tiene ni gato ni perro.
Mundo número 2: p1 es verdadero y p2 es falso; o sea, Javier tiene gato pero no tiene perro.
Mundo número 3: p1 es falso pero p2 es verdadero; Javier no tiene gato pero sí perro.
Mundo número 4: p1 y p2 son verdaderos; Javier tiene ambos.

En definitiva, es muy fácil enumerar los mundos para cada clase. Simplemente probamos todas las posibilidades, asignando verdadero o falso a las proposiciones. Entonces, en general, si tenemos una clase de mundo de grado n (con n proposiciones), cuántas instancias habrá? La respuesta es 2^n y el razonamiento es sencillo:

* Si n = 1, nuestra clase sólo está formada por una proposición; sea p1. Por ende, hay 2 = 2^1 mundos: en uno p1 es falso, en el otro p1 es verdadero.

* Si n = 2, la clase está hecha de dos proposiciones; sean p1 y p2. Notemos que si tomamos p1 podemos crear otra clase de grado 1; sea A. De la misma forma, podemos tomar p2 y crear otra clase de grado 1; sea B. Entonces, cualquier mundo de la clase está conformado por dos mundos, uno de A y otro de B. Cuántos mundos hay para A? Ya conocemos la respuesta por el punto anterior: 2. Y para B? Respuesta: también 2. Entonces cuántos mundos tenemos? 2*2 = 2^2 = 4.

* Si n = 3, la clase está hecha de tres proposiciones; sean p1,p2,p3. Con un razonamiento análogo al anterior, un mundo de nuestra clase está formado por tres mundos de clases de grado 1; sean A,B,C. Cuántos mundos hay para A? Ya conocemos la respuesta por el primer punto: 2. Lo mismo para B y C: 2 mundos. Entonces cuántos mundos tenemos? 2*2*2 = 2^3 = 8.

* Etcétera para grados más altos.

Se ve la relación entre clases y cubos? O entre mundos y vértices de un cubo? Notemos que dadas una clase de grado n y un n-cubo, podemos asignar un mundo a cada vértice del cubo... y viceversa: podemos asignar un vértice a cada mundo! Pero uno podría considerar esta correspondencia bastante trivial... más adelante mostraré que no es así.

Los conjuntos, la lógica y los cubos.

Pensemos en números naturales (son 0,1,2,3,4,5,... en adelante). De hecho, pensemos en conjuntos finitos de número naturales... son colecciones de números naturales, como por ejemplo {1,2,3}, o {1,3,5}, o {10}, o el conjunto vacío {} (es un conjunto con cero números naturales). Me gustan estos conjuntos ya que me gustan estos números... parecen ser "más reales que algunos reales"... esto me recuerda a una cita del matemático y lógico alemán Leopold Kronecker: "Dios sólo hizo a los naturales, todo lo demás es obra del hombre". En fin... Una "parte" de un conjunto X es un subconjunto de X. Por ejemplo, si X = {1,2,3}, entonces {2,3} es una parte de X, pero {3,5} NO es ya que 5 no está en la lista 1,2,3. Además, el conjunto vacío {} es parte de cualquier conjunto, y un conjunto siempre es parte de sí mismo. Representaremos a la colección de partes de un conjunto S como P(S). Pregunta: cuántas partes tiene X? O sea, cuántos elementos tiene P({1,2,3})? Contemos:

* Primero el conjunto vacío, 1.
* Contemos las partes de cardinal 1, {1}, {2}, {3}, son 3.
* Contemos las partes de cardinal 2, {1,2}, {1,3}, {2,3}, son 3.
* Contemos las partes de cardinal 3, {1,2, 3}, sólo 1.

En total: 1 + 3 + 3 + 1 = 2^3 = 8. Se observa la idea del planteo?

En general, supongamos que tenemos un conjunto finito S = {x1, x2, x3, ..., xn} cuyo cardinal es n (tiene n elementos). Cuántas partes tiene S? Respuesta: 2^n. La prueba es análoga a las anteriores, que demuestran que la cantidad de vértices de un cubo o la cantidad de mundos de una clase es una potencia de dos... se mantiene la naturaleza de recursividad, o de inducción...

Como existe una cantidad finita de partes, estas también pueden ser enumeradas. Vamos a usar una numeración bastante estándar, un algoritmo sencillo... para asignar un número a una parte T de S, empezamos asignando el valor 0 una variable r. Luego, recorremos todos los elementos de S, que son x1, ..., xn. Si i es tal que xi pertenece a T, le sumamos 2^i a r. Hago esto para todos los elementos xi de S. Finalmente, r será el número asignado a T. Por ejemplo, supongamos que S = {0,1,2} y T = {1,2}:

* Empezamos haciendo r = 0.
* x0 = 0 pertenece a S; pero está en T? NO, dejo r como está.
* x1 = 1 pertenece a S; pero está en T? SÍ, sumo 2^1 = 2 a r. r = 2.
* x2 = 2 pertenece a S; pero está en T? SÍ, sumo 2^2 = 4 a r. r = 6.

Resultado final: {2,3} tiene asignado el número r = 6. En general para este ejemplo tenemos 2^3 = 8 partes que se enumeran de la siguiente forma:

{} -> 0
{0} -> 1
{1} -> 2
{0, 1} -> 3
{2} -> 4
{0, 2} -> 5
{1, 2} -> 6
{0, 1, 2} -> 7

Se ve la relación entre conjuntos finitos de naturales, los cubos y las clases? Todo esto significa que dados un conjunto finito de cardinal n y un n-cubo, podemos asociar una parte a cada vértice del cubo... y podemos asociar un vértice a cada parte... y una parte a cada mundo... y un mundo a cada parte! Y aún más: podemos enumerar cada vértice, mundo o parte! En definitiva, existe la siguiente correlación:

Cubo........... Clase......... Conjunto finito
Vértice........ Mundo...... Parte (con su número natural asignado)
Dimensión... Grado....... Cardinal

Pero uno podría seguir creyendo que esta correspondencia es algo banal.

Vértices en el espacio.

No voy a profundizar en lo que es un espacio vectorial; sólo explicaré de forma sencilla qué es un vector: puede ser imaginado como un punto o vértice dentro de un espacio. En muchas ocasiones, quienes utilizamos el álgebra, nos enfrentamos a la tarea de trabajar con espacios de dimensión finita. Estos son, por ejemplo, los espacios unidimensionales, bidimensionales, tridimensionales (como lo es nuestro espacio físico), o tetradimensionales... en general, n-dimensionales, siendo n un número natural. En este artículo sólo mencionaremos espacios de dimensión finita.

Estos espacios son conjuntos de vectores (o vértices, o puntos); cada vector  ocupa un lugar distinto del espacio. Por lo tanto, si elegimos un punto de referencia, podemos concluir que cada vector tiene una posición. Esa posición puede ser representada mediante una lista (o tupla) de coordenadas, que son valores (en general numéricos) que codifican la posición del vector a lo largo de algún eje o dimensión.

Por ejemplo, supongamos que tenemos un espacio tridimensional V, formado por todos los vectores cuyas coordenadas son triplas de números enteros. Además, llamémosle "x" a la primera dimensión de V, "y" a la segunda, "z" a la tercera. Las siguientes son coordenadas de algunos vértices de V:

(1, 2, 3),
en este caso, la posición de nuestro punto a lo largo del eje x es 1, a lo largo del eje y es 2, para el eje z es 3.

(-1, 2, 3)
en este otro, la posición de nuestro punto a lo largo del eje x es -1, a lo largo del eje y es 2, para el eje z es 3. Notemos que este vector NO es el mismo que el anterior... su posición NO es la misma: que la coordenada x sea positiva o negativa significa que el punto está de un lado o del otro con respecto al plano formado por los ejes y, z.

(2, -3, 5)
este último caso representa al vector x=2, y=-3, z=5.

Notemos que, como NO puede haber dos puntos distintos en la misma posición, las coordenadas de un vector lo representan unívocamente. Por lo tanto, diremos que un vector es igual a su tupla de coordenadas. Por ejemplo, el vector (1,2,3) es el vector cuya posición es (1,2,3).

Para cerrar este apartado, observemos que un espacio de dimensión finita puede ser infinito. Por ejemplo, el espacio tridimensional conformado por "todas" las triplas de enteros es de dimensión finita (3); sin embargo hay una cantidad infinita de triplas de enteros. En los siguientes apartados, sólo nos concentraremos en espacios "totalmente" finitos.

Códigos lineales binarios.

Un código lineal binario (o para nosotros, simplemente "código") es un espacio vectorial finito (por ende, también de dimensión finita), constituido por tuplas de valores en {0, 1}. A cada vector se le llama palabra. Representaremos con Z(2,n) al código lineal binario de n dimensiones formado por todas las tuplas de valores {0, 1} y de longitud n.

Por ejemplo, las palabras (1,0,1), (0,0,1), (0,1,0), (0,0,0) pertenecen a Z(2,3), ya que son vectores de tres coordenadas {0, 1}. De hecho:

Z(2,3) = {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}.

Pudimos enumerar las palabras de Z(2,3) ya que el espacio tiene una cantidad determinada de elementos. En general, cuántas palabras hay en un código Z(2,n)? Respuesta: como siempre, 2^n. La prueba es muy sencilla: ya que Z(2,n) tiene TODAS las palabras de longitud n, una palabra w de Z(2,n) podría contener 0 ó 1 en cualquiera de sus coordenadas. O sea, podemos asignarle a w el 0 en la primera posición, o tal vez el 1; el 0 en la segunda, o quizá el 1; etc. En definitiva: podemos asignar uno de dos valores a cada coordenada. Eso nos da una cantidad 2*2*2*...*2 [n veces] = 2^n de combinaciones... por ende, 2^n palabras.

Cuando hablamos de conjuntos finitos en un apartado anterior, aprendimos que el conjunto de las partes de {0, 1, 2} (P({0,1,2})) tiene 2^3 = 8 elementos. Existirá una correlación entre P({0,1,2}) y Z(2,3)? Claro que sí: podemos asignar exactamente una palabra de Z(2,3) a cada parte de P({0,1,2}), de la siguiente manera:

sea w = (w0, w1, w2) una palabra de Z(2,3). Elegimos una parte X de P({0,1,2}) tal que X contenga 0 si y sólo si w0 = 1, que contenga 1 siempre y cuando w1 = 1 y que tenga a 2 si y sólo si w2 = 1. A esa parte X le asignamos w. Para ilustrar, damos las asignaciones de cada parte:

{} -> (0, 0, 0)
{0} -> (1, 0, 0)
{1} -> (0, 1, 0)
{2} -> (0, 0, 1)
{0, 1} -> (1, 1, 0)
{0, 2} -> (1, 0, 1)
{1, 2} -> (0, 1, 1)
{1, 2, 3} -> (1, 1, 1)

Pero, como cada parte tiene un número natural asignado, podemos asociar un número natural con cada palabra!:

  {} <-> (0, 0, 0) <-> 0
{0} <-> (1, 0, 0) <-> 1
{1} <-> (0, 1, 0) <-> 2
{2} <-> (0, 0, 1) <-> 4
{0, 1} <-> (1, 1, 0) <-> 3
{0, 2} <-> (1, 0, 1) <-> 5
{1, 2} <-> (0, 1, 1) <-> 6
{1, 2, 3} <-> (1, 1, 1) <-> 7

De hecho, para quienes conocen de la materia, las palabras y su número asociado son representaciones del mismo valor, sólo que una en binario (base 2) y la otra en decimal (base 10), respectivamente.

Estas cualidades no sólo se cumplen para n = 3, sino que para cualquier n natural! Por ende, tenemos la siguiente correlación:

Cubo........... Clase......... Conjunto finito......... Código
Vértice........ Mundo...... Parte......................... Palabra
Dimensión... Grado....... Cardinal................... Dimensión (del código)

Finalizando este artículo...

En definitiva, la tabla anterior resume íntimos paralelismos entre estructuras aparentemente distintas. Quizá en diversos ambientes sea conveniente considerar que cubos, clases, conjuntos finitos y códigos son "la misma cosa".

Por otro lado, ya que este artículo se me ha hecho algo extenso, dejaré los temas de distancia de Hamming, coloreo de grafos y ciclos de Hamilton para el futuro. Hay mucho más por descubrir detrás de la inocente traza de un discreto cubo.

Más info:
http://es.wikipedia.org/wiki/Politopo
http://es.wikipedia.org/wiki/Hipercubo
http://es.wikipedia.org/wiki/Grafo
http://es.wikipedia.org/wiki/Proposici%C3%B3n
http://es.wikipedia.org/wiki/N%C3%BAmero_natural
http://es.wikipedia.org/wiki/Leopold_Kronecker
http://es.wikipedia.org/wiki/Conjunto_enumerable
http://es.wikipedia.org/wiki/Recursividad
http://es.wikipedia.org/wiki/Inducci%C3%B3n_matem%C3%A1tica
http://es.wikipedia.org/wiki/Algoritmo
http://es.wikipedia.org/wiki/Espacio_vectorial
http://es.wikipedia.org/wiki/V%C3%A9rtice_%28geometr%C3%ADa%29
http://en.wikipedia.org/wiki/Linear_code
http://es.wikipedia.org/wiki/Base_%28aritm%C3%A9tica%29

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