Lógica, autorreferencia y teoría de categorías

Traducción automática del original en inglés, todavía sin revisar. Leer el original.

El ensayo anterior siguió el primer motor, la iteración, hasta el final. Una regla aplicada una y otra vez produce puntos fijos, atractores, medidas invariantes, leyes de escala y, al final, los toros invariantes de la teoría KAM, sostenidos o desgarrados por la aritmética de una sola frecuencia. En todo ese recorrido, la aritmética se quedó afuera del sistema. Los enteros contaban retornos. Las fracciones continuas medían la resonancia. Los números eran una regla que poníamos al lado del movimiento para medirlo.

Este ensayo gira la bisagra. Usa la aritmética de la segunda manera: no como una regla puesta al lado del sistema, sino como un lenguaje con el que el sistema habla de sí mismo.

Ese giro es todo el tema. Los mismos enteros que cuentan retornos alrededor de un reloj pueden contar símbolos dentro de una fórmula, porque una fórmula es apenas una cadena finita de símbolos, y una cadena finita se puede empaquetar en un solo número. Una vez que eso es posible, un sistema puede codificar descripciones de sus propios enunciados, reglas y programas, y después actuar sobre esas descripciones. A eso lo llamamos clausura representacional (representational closure), y es el umbral del segundo motor: la autorreferencia (self-reference).

La recompensa es una nueva familia de puntos fijos. No atractores ni toros, sino oraciones de Gödel, programas indecidibles, quines, el combinador Y y tipos recursivos. La pregunta del punto fijo sobrevive intacta al cambio de motor, “¿qué transformación actúa acá, y qué deja invariante?”, aunque la maquinaria que la responde sea completamente nueva. Al final, un único teorema categórico debido a Lawvere va a mostrar que Gödel, Turing, Cantor y Russell son un mismo argumento con cuatro disfraces.

Este es el punto donde la palabra “punto fijo” cambia de nivel. Antes, un punto fijo era un estado que una regla no movía:

$$ f(x^\star)=x^\star. $$

Acá, un punto fijo es un objeto representado que sobrevive a pasar por una regla que opera sobre su propia representación:

$$ \text{object}\simeq\text{transformation}(\text{description of that object}). $$

Por eso la frase reaparece sin ser redundante. El Motor A encontraba puntos fijos repitiendo una regla sobre estados. El Motor B encuentra puntos fijos, o demuestra que son imposibles, dejando que las descripciones actúen sobre sí mismas.

#El vocabulario mínimo

Un sistema formal es un lenguaje regido por reglas para hacer demostraciones. Tiene símbolos, fórmulas, axiomas y reglas de inferencia que convierten fórmulas en otras fórmulas. La aritmética, la teoría del $0$, el sucesor, la suma y la multiplicación, es el sistema formal que nos va a importar, porque es lo bastante fuerte como para volverse sobre sí misma.

Codificar significa representar un tipo de objeto como otro. La codificación en el centro de este ensayo es la numeración de Gödel (Gödel numbering): asignarle un número a cada fórmula y a cada demostración, de modo que los enunciados sobre fórmulas se vuelvan enunciados sobre números. Una vez que la sintaxis está codificada como aritmética, la aritmética puede hablar de sintaxis.

La diagonalización (diagonalization) es la jugada de la autorreferencia, y aparece tantas veces que merece un nombre. Tomás una construcción pensada para recorrer una colección de objetos y le das un objeto armado a partir de ella misma. A veces eso produce un punto fijo útil. A veces produce una contradicción, y la contradicción se convierte en un teorema de imposibilidad. Cantor, Gödel, Turing y Russell son todos esta misma jugada.

La clausura representacional es la condición umbral: el momento en que un sistema puede representar lo suficiente de sus propias expresiones, reglas o mapas como para que la autoaplicación se vuelva posible. Por debajo del umbral, la autorreferencia es un simple juego de palabras informal. Por encima, es matemática.

Una categoría, que aparece cerca del final, es la contabilidad de objetos, flechas entre ellos y una manera de componer flechas. Es el lenguaje en el que todos los teoremas de autorreferencia resultan ser el mismo teorema.

#Los dos motores, otra vez

Un repaso rápido de la arquitectura, porque este ensayo abre la segunda mitad de la serie.

La afirmación nunca fue que todo es el mismo objeto. Es que dos mecanismos obligan una y otra vez a que aparezcan objetos invariantes.

El primero es la iteración: tomás una regla $x\mapsto f(x)$ y la aplicás repetidamente. Eso solo produjo los primeros cuatro ensayos. El sistema no se representa a sí mismo; simplemente se lo hace girar.

El segundo es la autorreferencia: un sistema lo bastante rico como para representar sus propias expresiones, mapas o demostraciones, y después aplicarles transformaciones a esas representaciones. Este es el motor del ensayo actual.

Los dos motores siguen la misma disciplina:

1. elegir un espacio,
2. elegir una transformación,
3. aplicarla repetidamente, o dejar que actúe sobre sus propias representaciones,
4. preguntar qué queda invariante,
5. estudiar si ese invariante es estable, inestable, universal, patológico o expresivo.

Un punto fijo es el invariante más simple, $T(x)=x$. Pero la invariancia también puede significar que un conjunto se mapea dentro de sí mismo, que una distribución conserva su forma al reescalarla, que un toro sobrevive a una perturbación, que una oración habla de su propio código o que un tipo se despliega en una capa más otra copia de sí mismo.

Los dos motores están relacionados pero no son intercambiables, y la diferencia es justamente la representación:

Motor	Acto básico	Umbral	Objetos fijos
Iteración	aplicar una regla otra vez	dinámica repetida no lineal	atractores, conjuntos invariantes, medidas invariantes, leyes de escala
Autorreferencia	aplicar una regla representada a sí misma	suficiente representación interna	oraciones de Gödel, quines, programas recursivos, tipos recursivos

Hay un teorema que está en lo más hondo de la columna de la autorreferencia, y enunciarlo de entrada le da al resto del ensayo un objetivo. Es de Lawvere, y dicho informalmente afirma:

una vez que un sistema puede representar sus propios mapas con suficiente riqueza, los puntos fijos son inevitables.

La contrarrecíproca es igual de importante, y de ahí salen los teoremas de imposibilidad:

si alguna transformación no tiene punto fijo, entonces ningún sistema de representación puede ser tan completo.

Esa sola oración, leída hacia adelante y hacia atrás, es el esqueleto detrás de Cantor, Gödel, Turing y Tarski, cuyo teorema dice que un sistema lo bastante fuerte para la aritmética no puede definir su propia verdad. La negación booleana, “intercambiar verdadero y falso”, no tiene punto fijo. “Hacé lo contrario de lo que diga el decisor” no tiene punto fijo. “Esta oración no es demostrable” es la misma obstrucción escrita en el lenguaje de la demostración. La autorreferencia es generativa cuando el punto fijo relevante existe, y se convierte en un teorema de límite cuando el punto fijo no puede existir. Vamos a ganarnos esa oración como corresponde antes del final.

Una advertencia honesta sobre la frontera entre los motores. Algunos sistemas iterados pueden volverse lo bastante poderosos como para computar, y en ese momento cruzan hacia la representación. La Regla 110, un autómata celular unidimensional con una actualización local trivialmente simple, es lo bastante rica como para simular cualquier cómputo. Así que la línea entre “meramente iterado” y “autorreferencial” no es un muro; la iteración puede trepar hasta la representación. Pero la distinción igual se justifica: el caos no es automáticamente autorreferencia, y la autorreferencia no es automáticamente caos. Mantenerlas separadas es lo que permitió que los primeros cuatro ensayos quedaran limpios.

#Por qué aparece de pronto la lógica

El descubrimiento de Gödel, reducido a una oración, es que cada vez que un sistema formal puede hablar de sus propios enunciados, aparece la autorreferencia, y la autorreferencia fuerza puntos fijos. Llegar ahí requiere ver cómo un sistema habla de sí mismo, que es el truco de la codificación.

#Codificar la sintaxis como números

Recordá qué contiene un sistema formal: símbolos, fórmulas (cadenas de símbolos) y demostraciones (listas de fórmulas). La jugada de Gödel fue darse cuenta de que la aritmética, que obviamente habla de números, puede hacerse hablar también de todo eso, dándole un número a cada cosa.

Hay dos niveles en juego, y ponerles nombre evita confusiones:

1. el lenguaje objeto, donde viven los enunciados aritméticos comunes (“$2+2=4$”),
2. el metalenguaje, donde hablamos de fórmulas, demostraciones y demostrabilidad (“tal cadena es una demostración válida”).

Gödel mostró que una aritmética lo bastante fuerte puede internalizar parte de su propio metalenguaje: puede representar enunciados sobre fórmulas como enunciados sobre números. Esa representación es la numeración de Gödel.

La idea es mucho menos misteriosa si primero la hacés de forma burda. Asignale un número a cada símbolo:

Símbolo	Código
$0$	1
$S$	2
$+$	3
$=$	4
$($	5
$)$	6

Una fórmula es una cadena finita de símbolos, y por lo tanto una lista finita de estos números. Una demostración es una lista finita de fórmulas, y por lo tanto una lista finita de listas de números. El único truco que falta es empaquetar una lista finita de números en un solo número, y hay maneras estándar de hacerlo. Gödel usó la factorización en primos. La lista

$$a_1,a_2,\ldots,a_n$$

se convierte en

$$2^{a_1}3^{a_2}5^{a_3}\cdots p_n^{a_n}.$$

Como todo entero se factoriza en primos de exactamente una manera, la lista original siempre se puede recuperar a partir del producto: leés el exponente de $2$, después el de $3$, después el de $5$, y así. La codificación es reversible, que es la única propiedad que importa. Cualquier cadena de sintaxis se puede guardar dentro de un solo entero, y volver a sacarla.

Ahora la consecuencia. Una vez que las fórmulas y las demostraciones son números, las propiedades de la sintaxis se vuelven propiedades de números. “Esta cadena es una fórmula bien formada” se vuelve una propiedad aritmética de un entero. “Esta lista de fórmulas es una demostración válida de aquella fórmula” se vuelve una relación aritmética entre dos enteros. Concretamente, escribí

$$\operatorname{Proof}(p,g)$$

para decir “el número $p$ codifica una demostración de la fórmula cuyo código es $g$”. Parece un enunciado sobre demostraciones, pero después de la codificación es una relación aritmética común, verificable con aritmética. Y entonces la propia demostrabilidad (provability) se vuelve aritmética:

$$\operatorname{Provable}(g)\equiv \exists p,\operatorname{Proof}(p,g),$$

que se lee “existe algún número $p$ que codifica una demostración de $g$”. Este es el giro crucial. La demostrabilidad suena a una noción que vive en el metalenguaje, afuera del sistema. Después de la numeración de Gödel, el sistema puede expresarla internamente. La aritmética puede hablar de lo que la aritmética puede demostrar.

#La diagonal, en su forma más cruda

Antes de la oración de Gödel, mirá la jugada que tiene debajo sin nada de lógica encima. Supongamos que alguien afirma haber listado todas las propiedades de sí/no de los números naturales, una propiedad por fila:

	0	1	2	3	…
$P_0$	1	0	1	1	…
$P_1$	0	0	1	0	…
$P_2$	1	1	1	0	…
$P_3$	0	1	0	0	…

Ahora armá una propiedad nueva $D$ recorriendo la diagonal y dando vuelta cada entrada:

$$D(n)=1-P_n(n).$$

Por construcción, $D$ difiere de $P_0$ en la entrada $0$, de $P_1$ en la entrada $1$, de $P_2$ en la entrada $2$, y así a lo largo de toda la lista. Entonces $D$ difiere de cada fila en al menos un lugar, lo que significa que $D$ nunca estuvo en la lista. La pretensión de haber listado todas las propiedades falla. Ese es el argumento diagonal de Cantor, y es la semilla de todo lo que hay en este ensayo: tomás el objeto indexado por $n$, preguntás qué dice sobre $n$, y después transformás esa respuesta. La diagonalización es el lugar donde la representación (indexar objetos por $n$) se encuentra con la autoaplicación (preguntarle al objeto $n$ sobre $n$).

#La oración de Gödel como punto fijo

La construcción de Gödel es una versión más rica de esa inversión. El motor técnico es el lema diagonal (diagonal lemma), que dice, a grandes rasgos, que para cualquier propiedad de códigos $\varphi(x)$ que puedas escribir, hay una oración $G$ que afirma esa propiedad de su propio código:

$$G \leftrightarrow \varphi(\ulcorner G\urcorner).$$

Los corchetes de esquina $\ulcorner G\urcorner$ significan “el número de código de la oración $G$”. Así que el lema diagonal es una fábrica de puntos fijos: le das cualquier propiedad de códigos, y te devuelve una oración que es verdadera exactamente cuando esa propiedad se cumple de sí misma. La oración $G$ es un punto fijo de la operación “tomar un código, armar un enunciado sobre ese código”.

Ahora alimentá la fábrica con la única propiedad que hace estallar todo. Sea

$$\varphi(x)=\text{``the sentence coded by }x\text{ is not provable.‘’}$$

es decir, “la oración codificada por $x$ no es demostrable”. El lema diagonal te devuelve una oración $G$ con

$$G \leftrightarrow \text{``}G\text{ is not provable.‘’}$$

Esa es la oración de Gödel: un enunciado que afirma, en efecto, no soy demostrable en este sistema. Si el sistema pudiera demostrarla, el sistema demostraría una falsedad; si el sistema es correcto, o sea, si solo demuestra enunciados verdaderos, no puede demostrar $G$, así que $G$ es verdadera pero indemostrable. El sistema es incompleto, no por un hueco que mejores axiomas podrían llenar, sino porque su propia capacidad de autorreferencia fabricó una oración verdadera que no puede alcanzar.

El mismo esqueleto diagonal aparece en todo el tema cambiando la propiedad $\varphi$:

• Gödel le da “no demostrable” y obtiene una verdad indemostrable.
• Turing le da “el programa que se detiene acá no se detiene” y obtiene la indecidibilidad del problema de la parada (halting problem).
• Un quine le da la operación de imprimirse a sí mismo y obtiene un programa que muestra su propio código fuente.

La entrada de Turing condensa una construcción que vale la pena ver una vez. Supongamos que un programa $H$ pudiera decidir la parada: dado cualquier programa $p$ y una entrada $x$, responde si $p$ termina deteniéndose cuando se ejecuta con $x$. Armá un programa contrera $D$ que, al recibir el código de un programa $p$, le pregunta a $H$ qué hace $p$ cuando se le da su propio código, y después hace lo contrario: $D$ entra en un loop infinito donde $H$ predice que se detiene, y se detiene donde $H$ predice un loop. Ahora corré $D$ sobre su propio código. Si $H$ dice que se detiene, entra en loop; si $H$ dice que entra en loop, se detiene. De cualquier forma $H$ se equivoca, así que no puede existir tal $H$. El problema de la parada es indecidible, y la demostración es la inversión de Cantor con “se detiene sobre sí mismo” en lugar de “está en la lista”.

#De la lógica al código que corre: quines y el combinador Y

La versión lógica intimida; la versión de programación es amigable, y es el mismo punto fijo. Un quine es un programa $q$ que imprime su propio código fuente. Escribiendo $\operatorname{eval}$ para “correr el programa”, un quine cumple

$$\operatorname{eval}(q)=q.$$

Es literalmente un punto fijo del proceso de correr e imprimir. El truco es exactamente el del lema diagonal: el programa guarda una representación de sí mismo como datos, y después usa esos datos para reconstruirse. Acá está toda la idea en tres líneas de Python, lo bastante cortas para leerlas:

template = 'template = {!r}\nprint(template.format(template))'
print(template.format(template))

El string template es una descripción del programa. La última línea inserta esa descripción dentro de sí misma e imprime el resultado, que es el propio código fuente del programa. No pasa nada místico. El programa puede referirse a sí mismo porque puede guardar una representación de sí mismo y volver a pasar esa representación por su propia regla. Esa es la clausura representacional hecha lo bastante chica como para ejecutarla.

El teorema de recursión de Kleene es el enunciado general detrás de los quines: para cualquier transformación computable que quieras aplicarles a los programas, hay un programa que obtiene su propia descripción y la pasa por esa transformación. Siempre se puede hacer que los programas conozcan su propio código.

#Simulación: juguete del punto fijo diagonal

Abrí esta simulación en Explorar →

El punto fijo más famoso de toda la programación es el combinador Y (Y combinator), que vive en el cálculo lambda, el lenguaje mínimo de las funciones. Cumple

$$Yf=f(Yf).$$

Mirá eso un segundo: $Yf$ no cambia cuando le aplicás $f$ una vez más. Es una ecuación de punto fijo genuina, pero para funciones en lugar de números. Su propósito es hacer posible la recursión sin nombrar nunca una función. Normalmente una definición recursiva dice “definí esta función en términos de sí misma”, lo que parece requerir que la función ya tenga un nombre al cual referirse. El combinador Y disuelve esa circularidad aparente en un punto fijo explícito: arma la autorreferencia a partir de pura aplicación de funciones. Es el hermano computacional del lema diagonal y, como vamos a ver, el hermano en teoría de tipos de los tipos recursivos.

#La misma jugada, cinco veces

Así que la diagonalización reaparece una y otra vez porque es una sola idea estructural, no cinco coincidencias:

1. Cantor diagonaliza contra listas de números reales.
2. Gödel diagonaliza contra la demostrabilidad.
3. Turing diagonaliza contra los decisores de parada.
4. Los quines diagonalizan contra la separación entre código fuente y salida.
5. Lawvere, enseguida, abstrae la diagonal misma.

La forma común es siempre la misma: un sistema lo bastante rico como para codificar sus propios elementos, y una transformación que se puede volver sobre esa codificación.

Acá está el diccionario entre este ensayo y el motor de iteración de los anteriores. En dinámica, aplicás repetidamente una función a un estado, $x\mapsto f(x)$. En lógica, codificás un enunciado como número y armás un enunciado nuevo sobre ese número, $n\mapsto\varphi(\ulcorner n\urcorner)$. El paso diagonal vuelve a meter el código del enunciado construido en la construcción, que es autoaplicación, el análogo lógico de la iteración.

Dinámica	Lógica
estado $x$	oración/código $g$
regla $f$	plantilla de fórmula $\varphi(x)$
iterar $f(x)$	sustituir un código en una fórmula
punto fijo $f(x^\star)=x^\star$	oración autorreferencial $G\leftrightarrow\varphi(\ulcorner G\urcorner)$
estabilidad o inestabilidad	consistencia, incompletitud, indecidibilidad

Dominio distinto, misma estructura. Un sistema tiene suficiente poder expresivo interno como para volver una regla sobre sus propios objetos, y una vez que lo hace, aparecen puntos fijos. En dinámica son atractores y ciclos. En lógica son oraciones autorreferenciales. En computación son programas que se refieren a su propio código fuente.

La décima lección:

La autorreferencia genera puntos fijos en la lógica igual que la iteración genera puntos fijos en la dinámica.

El puente de la teoría de números a la lógica es la codificación. La teoría de números te da objetos aritméticos; Gödel muestra que esos objetos pueden codificar sintaxis; una vez que la sintaxis está codificada, los enunciados pueden apuntarse a sí mismos a través de sus propios códigos. Antes de Gödel, la aritmética parece una materia sobre números. Después de Gödel, la aritmética también es un medio en el que un sistema formal representa su propia gramática, un espejo en el que puede ver sus propias oraciones.

#Por qué aparece la teoría de categorías

Una vez que viste caer puntos fijos de las contracciones de Banach, las oraciones de Gödel, las máquinas de Turing, los fractales, la renormalización, los lenguajes de programación y los tipos recursivos, se forma una pregunta natural:

¿Cuál es el marco más general en el que los puntos fijos tienen que existir?

Para eso sirve acá la teoría de categorías (category theory). No es abstracción por deporte; es la búsqueda de los supuestos más chicos que todavía fuerzan un punto fijo.

No te hace falta un curso de teoría de categorías para lo que sigue. El único hábito que hay que tomar prestado es este: cuando los objetos se vuelven demasiado distintos, compará las flechas. Un mapa dinámico, un programa, una traducción de demostraciones y un constructor de tipos no son el mismo tipo de cosa, pero cada uno es una transformación que se puede componer con otra transformación.

#La teoría de categorías justa y necesaria

Una categoría es una estructura deliberadamente austera:

1. objetos,
2. flechas entre objetos,
3. una manera de componer flechas.

Eso es todo. En la categoría de conjuntos, los objetos son conjuntos y las flechas son funciones. En una categoría de tipos, los objetos son tipos y las flechas son programas. En una categoría de espacios, los objetos son espacios y las flechas son mapas que preservan la estructura. El truco de la teoría de categorías es estudiar una materia por sus flechas en lugar de por aquello de lo que están hechos sus objetos: no “qué hay adentro de este objeto” sino “qué se mapea hacia él, hacia qué se mapea él, y cómo se componen esos mapas”.

Ese punto de vista encaja acá porque cada ensayo de esta serie trató sobre una transformación que actúa sobre un espacio:

Objeto del ensayo	Transformación
estado	mapa dinámico
conjunto	operador de Hutchinson
distribución	renormalización / coarse-graining
vector de frecuencias	ecuación de conjugación perturbativa
código de oración	plantilla de fórmula
programa	evaluación
tipo	funtor

La teoría de categorías se queda con la transformación y olvida deliberadamente el material. Olvidar suena a pérdida, pero es lo que deja ver el esqueleto: si dejás de preguntar de qué están hechos los objetos y te quedás solo con cómo se componen los mapas, las partes de los argumentos de punto fijo que en realidad eran iguales se vuelven visiblemente iguales.

La única operación que una categoría exige es la composición. Si

$$A\xrightarrow{f}B\xrightarrow{g}C,$$

entonces hay una flecha compuesta

$$A\xrightarrow{g\circ f}C.$$

Eso ya alcanza para modelar pipelines, dinámica, ejecución de programas, traducción de demostraciones y cambios de coordenadas, porque cada una de esas cosas es “hacé una cosa, después hacé la siguiente”.

#Los funtores y los puntos fijos que son estructuras de datos

Un funtor (functor) es un mapa entre categorías que preserva esta estructura. Para un programador, el modelo mental más limpio es un constructor de tipos que además sabe mapear funciones. Tomá

$$F(X)=1+A\times X.$$

Leé el lado derecho como una elección: o bien el único caso vacío (el $1$), o bien un par formado por un $A$ y un $X$ (el $A\times X$). Si $A$ es el tipo de los elementos, entonces $X$ es el lugar reservado para “el resto de la lista”. Esa es exactamente la forma de una lista: una lista está vacía, o es un elemento de tipo $A$ seguido de otra lista. El funtor $F$ captura “una capa de lista”.

Un álgebra para un funtor $F$ es un objeto $X$ junto con una manera de colapsar una capa $F(X)$ de vuelta en $X$:

$$F(X)\to X.$$

Para listas, eso significa: dado “vacío” o “un elemento más una lista”, producir una lista. Un tipo de datos inductivo es el álgebra inicial de ese tipo, donde inicial significa que toda otra álgebra recibe exactamente un mapa que respeta la estructura desde ella; es la manera que tiene la categoría de decir “la más chica, sin nada extra agregado”. El álgebra inicial (initial algebra) es un punto fijo del funtor. El tipo de las listas finitas, escrito $\mu F$, cumple

$$\mu F \cong 1 + A\times \mu F,$$

que es la ecuación “una lista está vacía, o es un elemento de $A$ emparejado con otra lista”, ahora leída como una ecuación de punto fijo para tipos. El símbolo $\cong$ significa que los dos lados son el mismo tipo salvo un cambio de etiquetas.

#Simulación: despliegue de un tipo recursivo

Abrí esta simulación en Explorar →

La notación $\mu F$ significa “el menor punto fijo de $F$”, y “menor” está haciendo un trabajo real. Es la historia del punto fijo en la teoría del orden del primer ensayo, que vuelve en forma de tipos. Knaster y Tarski demostraron que los mapas monótonos sobre retículos completos tienen un menor y un mayor punto fijo; Kleene mostró que, bajo los supuestos de continuidad adecuados, el menor se puede construir empezando desde abajo e iterando hacia arriba. Un tipo recursivo se construye de la misma manera: empezás sin valores, aplicás el patrón del constructor, lo aplicás otra vez, y te quedás con la menor solución estable.

Para las listas, la construcción hacia arriba es concreta y vale la pena verla:

$X_0$ no contiene ninguna lista. $X_1$ contiene solo la lista vacía. $X_2$ agrega las listas de un elemento. $X_3$ agrega las listas de longitud a lo sumo dos. Iterando para siempre, la unión de todas las etapas es el menor punto fijo: exactamente las listas finitas, y nada infinito. Por eso importa “menor”. La misma ecuación $X\cong 1+A\times X$ también tiene soluciones más grandes si permitís objetos infinitos o circulares; el tipo lista inductivo elige deliberadamente la más chica, lo que mantiene finita cada lista. Es el “iterar hacia arriba desde el fondo” de Kleene en otra categoría, y es la misma imagen de convergencia desde abajo que la de una contracción asentándose en su punto fijo en el primer ensayo.

El patrón ya es lo bastante familiar como para ponerlo en una tabla:

Antes	Versión en categorías / tipos
número $x$	tipo $X$
función $f(x)$	funtor $F(X)$
punto fijo $x^\star=f(x^\star)$	tipo recursivo $\mu F\cong F(\mu F)$
la iteración construye convergencia	los constructores construyen datos finitos

#Coálgebras: la misma idea, corriendo para siempre

Hay una historia dual para el comportamiento infinito. Una coálgebra (coalgebra) tiene la flecha dada vuelta:

$$X\to F(X).$$

En lugar de colapsar una capa en un objeto, despliega un objeto en una capa observable más un estado siguiente. Los streams son el ejemplo limpio. Un stream infinito de valores,

$$a_0,a_1,a_2,\ldots,$$

se describe con el funtor $F(X)=A\times X$ (“un valor de cabeza, más el resto”), y un stream es un valor de la coálgebra terminal, donde terminal significa que toda otra coálgebra se mapea en ella de manera única, la manera que tiene la categoría de decir “la más grande”,

$$\nu F \cong A\times \nu F,$$

que se lee “un stream es un elemento de cabeza de tipo $A$ junto con otro stream”. A diferencia de una lista, no hay caso vacío que lo detenga. Se despliega para siempre.

La distinción práctica es simple. Un álgebra construye datos finitos consumiendo una capa a la vez. Una coálgebra observa un sistema en marcha exponiendo una capa y un estado siguiente. Las listas son algebraicas; los streams, los autómatas y las máquinas de estados son coalgebraicos.

Entonces la división álgebra/coálgebra refleja una distinción que la serie ya rondó antes: la construcción inductiva arma objetos finitos a partir de casos base, mientras que la observación coinductiva describe procesos en marcha observados a lo largo del tiempo. Las dos son puntos fijos de funtores, $\mu F$ y $\nu F$, el menor y el mayor. Y la forma coalgebraica, $\text{state}\to\text{observation plus next state}$ (estado hacia observación más estado siguiente), es exactamente un sistema dinámico: autómatas, sistemas de transición, procesos infinitos y lazos de retroalimentación encajan todos en ella. La teoría de categorías resulta ser el lenguaje en el que los datos recursivos y la dinámica en marcha son dos lecturas de una misma idea de punto fijo, y por eso puede ubicarse en la costura entre la lógica de este ensayo y los sistemas vivos y de mercado de los dos siguientes.

#El teorema de Lawvere: la diagonal desnuda

Ahora podemos enunciar el resultado al que apuntaba todo el ensayo. El teorema del punto fijo de Lawvere (Lawvere’s fixed-point theorem) abstrae el argumento diagonal en pura teoría de categorías: bajo condiciones adecuadas, si una categoría contiene suficiente autodescripción, los puntos fijos se siguen. Por eso una sola familia de teoremas toca a la vez a Gödel, Turing, Cantor, Russell y la recursión en programas.

El esqueleto que aísla tiene cuatro pasos:

1. los objetos pueden representar mapas,
2. los mapas representados se pueden evaluar,
3. la evaluación se puede diagonalizar,
4. la diagonalización fuerza un punto fijo.

En un lenguaje menos comprimido: si un sistema puede nombrar cada operación sobre sí mismo, entonces a una de esas operaciones nombradas se le puede dar su propio nombre. Esa autoaplicación es la jugada diagonal. El teorema de Lawvere dice que, bajo los supuestos estructurales correctos, esta jugada fuerza un punto fijo.

Una formulación informal: si toda función $A\to B$ puede representarse con algún elemento de $A$, entonces todo mapa $B\to B$ tiene un punto fijo. Dejame ganármelo con ropa de teoría de conjuntos, despacio, porque la demostración es solo el argumento diagonal sin la decoración.

Supongamos que hay un mapa sobreyectivo

$$\phi:A\to B^A,$$

donde $B^A$ significa “las funciones de $A$ en $B$”. Sobreyectivo significa que cada una de esas funciones aparece como $\phi(a)$ para algún $a$; esta es la hipótesis de “suficiente autodescripción”, que $A$ es lo bastante rico como para nombrar todas las funciones $A\to B$. Ahora tomá cualquier mapa $\alpha:B\to B$ y definí una función nueva

$$g(a)=\alpha(\phi(a)(a)).$$

Leé $\phi(a)(a)$ así: tomá la función nombrada por $a$, y dale el propio $a$, la jugada diagonal. Después aplicá $\alpha$. Como $g$ es una función $A\to B$, y $\phi$ nombra todas esas funciones, tenemos $g=\phi(a_0)$ para algún $a_0$ en particular. Evaluá todo en ese $a_0$:

$$\phi(a_0)(a_0)=g(a_0)=\alpha(\phi(a_0)(a_0)).$$

Entonces el valor $b=\phi(a_0)(a_0)$ cumple $b=\alpha(b)$. Es un punto fijo de $\alpha$. No supusimos que $\alpha$ tuviera uno; la riqueza de $\phi$ lo fabricó.

Ahora corré la implicación hacia atrás, y los teoremas de imposibilidad salen gratis. Tomá $B={0,1}$ y sea $\alpha$ la negación booleana, que, como es sabido, no tiene punto fijo (intercambiás $0$ y $1$ y nada se queda quieto). El teorema de Lawvere entonces prohíbe la hipótesis: no puede haber una sobreyección $A\to{0,1}^A$. Ese es el teorema de Cantor, que ningún conjunto se mapea sobreyectivamente en su propio conjunto potencia. Gödel, Turing y Russell son la misma jugada con un $B$ más rico y un $\alpha$ distinto sin punto fijo: negar la demostrabilidad, invertir el decisor de parada, negar la pertenencia. La versión de Russell merece una oración, ya que el ensayo todavía no la construyó: formá el conjunto de todos los conjuntos que no se contienen a sí mismos, y preguntá si se contiene a sí mismo. Cada respuesta fuerza la otra. Esa es la diagonal con la pertenencia como propiedad invertida, y es la razón por la que hubo que reconstruir la teoría ingenua de conjuntos. Un solo teorema, leído hacia adelante para los puntos fijos positivos y hacia atrás para los resultados de imposibilidad.

#Simulación: diagrama de Lawvere

Abrí esta simulación en Explorar →

El paralelo con Gödel es exacto una vez que los alineás:

Demostración de Lawvere	Demostración de Gödel
el elemento $a$ representa una función	el número $g$ representa una fórmula
evaluar $\phi(a)(a)$	sustituir el código de una fórmula en sí misma
aplicar $\alpha:B\to B$	negar la demostrabilidad o transformar una propiedad
la sobreyectividad/representación da un punto fijo	el lema diagonal da $G\leftrightarrow\varphi(\ulcorner G\urcorner)$

Gödel no usó teoría de categorías a escondidas; históricamente no podría haberlo hecho. Lo que agrega la teoría de categorías llega después y desde otra dirección: aísla la forma de su argumento y muestra que nunca se trató realmente de fórmulas, máquinas o conjuntos. Se trataba de una configuración estructural: objetos que representan flechas, flechas que se componen, y una diagonal que vuelve a meter la representación en la evaluación.

La undécima lección:

La teoría de categorías es el lenguaje general de las estructuras de punto fijo que se repiten.

El puente de la lógica a la teoría de categorías es olvidar el sustrato. Gödel habla de fórmulas, Turing de máquinas, los lenguajes de programación de tipos recursivos, la dinámica de mapas iterados, la renormalización de operadores, la probabilidad de distribuciones invariantes de escala. La teoría de categorías pregunta qué queda una vez que borrás el material local y te quedás solo con las flechas. Eso es abstracción como compresión, no como decoración: si la misma forma de demostración aparece en lógica, computación y teoría de conjuntos, entonces quizás la demostración nunca se trató de ninguno de sus contenidos particulares. Según el contexto, el punto fijo que fuerza aparece como una oración de Gödel, un programa indecidible, una definición recursiva, una paradoja, un álgebra inicial o una coálgebra terminal. Lo común es el esqueleto.

#El arco teórico está completo

Ya vimos los puntos fijos como límites de la iteración, los atractores de la dinámica, los conjuntos invariantes del caos, las leyes de escala de las distribuciones, las restricciones de pequeños divisores de la aritmética y los puntos fijos diagonales de la lógica y la computación. Los dos motores quedaron expuestos: la iteración, que hace girar una regla hasta que algo invariante sobrevive, y la autorreferencia, que deja que un sistema actúe sobre su propia descripción hasta que un punto fijo se vuelve inevitable.

Este es el lugar para decir exactamente por qué los dos motores riman, y exactamente por qué no son lo mismo. Un atractor de Hutchinson contiene copias a escala de sí mismo porque una regla contractiva sobre conjuntos compactos cumple $K=\mathcal{H}(K)$. Una oración de Gödel contiene una afirmación sobre su propio código porque la aritmética puede codificar sintaxis y volver a meter ese código en una plantilla de fórmula. Los dos producen una regresión infinita a partir de una ecuación de punto fijo: copias dentro de copias del lado geométrico, descripciones de descripciones del lado lógico. Pero los teoremas son distintos. El atractor de Hutchinson no se refiere a sí mismo; el sistema de funciones iteradas no describe nada. La oración de Gödel no estira, ni pliega, ni contrae un espacio métrico. La escalera los conecta porque los dos son fenómenos de punto fijo, no porque en secreto sean el mismo objeto.

Queda una transición por hacer con cuidado, y es el paso del pizarrón al mundo.

La autorreferencia formal ocurre cuando un sistema contiene una descripción de una de sus propias expresiones y puede volver a meter esa descripción en sus reglas. Los sistemas vivos y los mercados no son sistemas formales, pero tienen los mismos tres ingredientes estructurales: una descripción interna, un intérprete para ella y retroalimentación del intérprete hacia el estado futuro del sistema.

Sistema	Descripción interna	Intérprete	Retroalimentación
Lógica	código de Gödel de una oración	reglas de demostración	enunciados de demostrabilidad
Programa	código fuente	evaluador/compilador	ejecución y recursión
Célula	genoma	maquinaria celular	desarrollo y reproducción
Mercado	modelo, precio, estrategia	traders y capital	órdenes que cambian precios

Esta tabla es el puente de la autorreferencia formal al mundo vivido. Una célula no es un teorema, y un mercado no es un término lambda. Pero cada uno contiene descripciones que participan en la misma dinámica que describen. Por eso los últimos dos ensayos no son apéndices abrochados a un repaso de matemática. Son donde los dos motores corren juntos a la vista:

El Motor A aporta la estructura de atractores. Los cuerpos se mantienen dentro de estados viables; los mercados se mueven entre regímenes.

El Motor B aporta el lazo representacional. Los genomas ayudan a construir los organismos que llevan genomas; los modelos de mercado ayudan a crear los precios que actualizan los modelos de mercado.

Los dos ensayos finales aplican este esqueleto a los dos sistemas autorreferenciales dentro de los cuales realmente vivimos: la biología y los mercados.

#Lecturas recomendadas

Sobre lógica, computación y autorreferencia:

1. Kurt Gödel, On formally undecidable propositions of Principia Mathematica and related systems (1931). El paper de la incompletitud, donde la autorreferencia se convierte por primera vez en un teorema.
2. Alan Turing, On computable numbers, with an application to the Entscheidungsproblem (1936). El problema de la parada y la idea moderna de computación.
3. Alfred Tarski, The concept of truth in formalized languages (1936). Indefinibilidad: un sistema lo bastante fuerte para la aritmética no puede definir su propia verdad.
4. Douglas Hofstadter, Gödel, Escher, Bach. No es la fuente más formal, pero sigue siendo una de las mejores maneras de sentir por qué importa la autorreferencia.
5. Raymond Smullyan, Gödel’s Incompleteness Theorems. Un camino lógico más amable hacia la diagonalización.
6. Haskell Curry y Robert Feys, Combinatory Logic. Una fuente clásica sobre los combinadores de punto fijo.
7. Henk Barendregt, The Lambda Calculus. La referencia estándar sobre el cálculo lambda y el combinador Y.

Sobre teoría de categorías y la forma general de los puntos fijos:

1. F. William Lawvere, Diagonal arguments and cartesian closed categories (1969). La abstracción categórica de la diagonalización que unifica a Gödel, Turing y Cantor.
2. Joachim Lambek, A fixpoint theorem for complete categories (1968). El origen de la visión algebraica de los tipos recursivos.
3. Steve Awodey, Category Theory. Una introducción moderna y limpia.
4. Benjamin Pierce, Basic Category Theory for Computer Scientists. Corto, práctico y bueno para programadores.
5. Bart Jacobs, Introduction to Coalgebra. Un camino desde las coálgebras hasta los sistemas basados en estados y el comportamiento infinito.
6. Alfred Tarski, A lattice-theoretical fixpoint theorem and its applications (1955). El teorema de punto fijo de la teoría del orden detrás de muchas construcciones de menor y mayor punto fijo.
7. Stephen Kleene, Introduction to Metamathematics. Una fuente clásica sobre computabilidad y menores puntos fijos iterativos.
8. L. E. J. Brouwer, Uber Abbildung von Mannigfaltigkeiten (1911), y Shizuo Kakutani, A generalization of Brouwer’s fixed point theorem (1941). Los teoremas de punto fijo topológico y de valores en conjuntos detrás de los argumentos de equilibrio.