Hasta el infinito y mas allá…

¿Qué hay en común entre Cantor, Gödel y Turing? Al menos dos cosas, y la primera de ellas es que los tres intentaron expandir los límites de las matemáticas.

Cantor, por ejemplo, quería contar hasta el infinito. Esta es una tarea muy difícil: todos los que lo han intentado, se cansan antes de concluir! Pero lo que Cantor percibió fue que, aunque es difícil contar hasta el infinito directamente, se podía hacer indirectamente, desde que se conociese el significado real de “contar” algo.

¿Qué significa, por ejemplo, que tiene cuatro manzanas? En la interpretación de Cantor, esto significa que puede crear una biyección de su conjunto de manzanas con un subconjunto de los números naturales, como se muestra a continuación:

De esta manera, si creó una biyección de su conjunto con el conjunto de los cuatro primeros naturales, entonces efectivamente contó su conjunto y concluyó que tiene cuatro elementos. El truco de Cantor fue percibir que se podía extender ese concepto, y crear biyecciones con todos los naturales, en lugar de sólo algún subconjunto. Lo cual lleva a resultados que son muy poco intuitivos!

Por ejemplo, con respecto al conjunto de los números pares. La intuición de un principiante es que ese conjunto tiene la mitad de los elementos de los naturales. Lo cual no es verdad, porque puede construir una biyección entre los dos:

Para cada natural tiene un par correspondiente, para cada par tiene un natural. Por el razonamiento del Cantor, entonces estos dos conjuntos tienen el mismo número de elementos, lo que también muestra que, al menos cuando está tratando con el infinito, la parte puede ser igual al todo.

Más tarde, Cantor también mostró que los números racionales son del mismo tamaño que los naturales. Quién quisiera repetir la demostración original, puede intentar hacer el problema CANTON de SPOJ, que pide que cree una biyección. Una forma alternativa es utilizar una construcción inventada por Gödel: cada racional p/q, se asocia el natural, ​\( 2^p3^q \)​ , y para transformar el natural devuelta en un racional, se utiliza la factorización única que El teorema fundamental de la aritmética asegura.

Cuando un conjunto tiene el mismo tamaño que el de los naturales, se dice que tiene cardinalidad aleph-cero, o, lo que es un conjunto numerable. Pero, ¿todos los conjuntos infinitos son contables? ¡No! Cantor también mostró que el conjunto de los números reales es mayor que cualquier conjunto contable dado utilizando un método llamado argumento diagonal. Es decir, los números reales son un tipo de infinito mayor que el infinito de los naturales!

Ahora bien, si los racionales son contables, y los reales no lo son, está claro que los culpables que un infinito sea más grande que otros son los irracionales. Pero, ¿qué irracionales? Hay varios tipos de ellos también. Por ejemplo, algunos irracionales pueden ser construidos como raíces de polinomios de coeficientes enteros (se dice que estos son irracionales algebraicos). Un ejemplo es el número áureo, que es la mayor raíz del polinomio ​\( x^2-x-1 \)

Sin embargo, los irracionales algebraicos son contables también. Basta con utilizar el mismo truco de Gödel, esta vez asociando cada coeficiente del polinomio a un exponente de un número primo. Un polinomio como ​\( x^2+2x+1 \)​, por ejemplo, se escribiría entonces como ​\( 2^13^25^1 \)

Ahora, si los irracionales algebraicos son contables, entonces lo que convierte a los reales en más grande que los naturales son los irracionales no algebraicos (o trascendentales). Pero incluso entre estos hay varios tipos. El número Pi, por ejemplo: no se puede construir como una raíz de un polinomio, pero puede acercarse a ella con un algoritmo de computadora, con tanta precisión como lo desee. Los números que se pueden aproximar por medio de algoritmos, se dice que son números computables.

Sorprendentemente, los irracionales computables son contables también. La manera simple de visualizar esto es de la siguiente manera: si existe un algoritmo que aproxima el número, entonces ese algoritmo puede ser implementado en un lenguaje cualquiera (como nos garantiza la tesis Church-Turing). Ahora, imagine que creó un binario que implementó este algoritmo, y ese binario tiene X bytes. Si hace un hexdump del binario y lo imprime, tendrá en frente un número hexadecimal de 2X dígitos (que es un número natural grande, pero aún así un natural).

Pero si los irracionales computables son contables, ¿quiénes son los no contables? ¿Existen números que no pueden ser calculados por algoritmos? La respuesta es sí, y uno de estos números es la constante de Chaitin. La construcción de la constante es curiosa. Hemos visto que, a cada algoritmo posible, existe un natural asociado. Calcule la sumatoria siguiente: para cada algoritmo existente (cuyo natural asociado es n), si el algoritmo se detiene, se agrega 2-n, pero no suma nada. Ahora, esta suma no puede ser calculada por un algoritmo, debido a que el teorema de Turing garantiza que no se puede construir un algoritmo que detecte si otro algoritmo se detiene. La constante de Chaitin, entonces, es un número no computable.

Pero los irracionales no computables todavía no son el secreto del infinito real. Pues no conseguimos construir un algoritmo que se acerce a la constante de Chaitin, pero en el párrafo anterior he podido describir exactamente de lo que trata la constante. Los números que puedo describir son los números definibles, y (sorpresa), también son contables. El argumento es aún más simple, si puedo escribir un archivo de texto que contiene la descripción del número, el hexdump de ese archivo también va a asociar la descripción a un número natural.

Entonces, los números que hacen al infinito de los reales ser más grandes que el infinito de los naturales son los números que no podemos construir, no podemos aproximar y no podemos describir, o sea, ni pensar en ellos!

Si a esta altura su cabeza dio tilt, entonces déjeme concluir cuál es la segunda cosa en común entre Cantor, Gödel y Turing: los tres quedaron locos. De hecho, Cantor creía que era un mensajero de Dios, y terminó la vida en un hospicio. Gödel se quedó paranoico con comida contaminada, y sólo comía lo que su mujer le preparaba (cuando la mujer se enfermó y se internó en un hospital, literalmente murió de hambre). Y Turing quedó tan deprimido que se mató, comiendo una manzana envenenada.

Hay quien dice que existe una relación causal entre estudiar el infinito y quedarse loco. Si usted es tal, eh, hubiese sido mejor que no leyera este post 🙂

Leave a Reply

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert