Hola,
Me ha preguntado por privado
Eparoh sobre teorías de tipos, pensando en formalización de teoremas con Lean. Cómo puede ser de interés para más gente, copio a continuación lo que le contesté en privado.
El problema es que explicar teoría de tipos dependientes es un poco largo, tendría que hacer un hilo como los de Carlos, y no tengo el tiempo suficiente para ello. Pero te puedo explicar muy resumidamente las ideas básicas, aunque si ya has jugado con Lean creo que más o menos ya las debes tener.
Las teorías de tipos (dependientes) son una fundamentación para las matemáticas alternativas a las teorías de conjuntos. En teorías de conjuntos tipo ZFC hay dos capas: primero hay una capa lógica (lógica de primer orden) y encima tienes la teoría axiomática de conjuntos como ZFC. En teorías de tipos solamente hay una capa: la lógica y la "teoría de conjuntos" quedan mezcladas. Así pues, en teorías de tipos todo lo que hay son tipos y términos, y (a diferencia de lo que ocurre en teoría de conjuntos donde todo es un conjunto) un término siempre tiene un tipo asociado. Que el término \( a \) tiene tipo \( A \) se suele denotar por \( a:A \). Además hay operaciones que permiten formar nuevos tipos a partir de los que ya teníamos. Por ejemplo, dados dos tipos $$A,B$$ tenemos un tipo implicación $$A \to B$$, un tipo producto $$A \times B$$, un tipo coproducto $$A \sqcup B$$, etc. Junto con cada uno de estos tipos hay reglas de introducción y de eliminación de términos, así como de computación (que dicen qué pasa cuando aplicamos una regla de introducción seguida de una de eliminación).
Hay varias familias de teorías de tipos. La más sencilla es la teoría de tipos simple, y vamos a empezar con esa porque es suficiente para ver la conexión con la teoría de la demostración.
Por ejemplo, para $$A \times B$$, la regla de introducción sería "si $$a:A$$ y $$b:B$$ entonces $$(a,b):A \times B$$". Aquí la notación $$(a,b)$$ no es algo definido en términos más simples como en teoría de conjuntos, sino que es un nuevo símbolo primitivo (que se llama un constructor). De manera análoga, tenemos dos reglas de eliminación: "si $$u:A \times B$$ entonces $$pr_1(u):A$$ y $$pr_2(u):B$$. Y finalmente, las reglas de computación nos dicen $$pr_1(a,b) \equiv a : A$$ y $$pr_2(a,b) \equiv b : B$$. Aquí el símbolo $$\equiv$$ es un símbolo primitivo que se llama "igualdad definicional" (a veces en inglés también "judgmental equality") y quiere decir que los términos a ambos lados son iguales por definición. A efectos prácticos, puedes intercambiar uno por otro siempre que quieras.
Análogamente, podemos dar reglas por ejemplo para $$A \to B$$. Aquí la regla de introducción sería "dados $$a:A, b:B$$, entonces $$\lambda a.b : A \to B$$", la de eliminación "dados $$f:A \to B$$, $$a:A$$ entonces $$f(a):B$$", y la de computación $$(\lambda a.b)(a) \equiv b : B$$.
De forma parecida, podríamos dar reglas para otras operaciones de tipos. Lo importante ahora es que podemos pensar estos tipos de dos formas distintas: una como si los tipos fueran conjuntos y sus términos como si fueran sus elementos, y la otra como si los tipos fueran proposiciones de las de lógica proposicional y sus términos fueran demostraciones.
Con la primera interpretación, $$A\times B$$ se interpreta como el producto cartesiano de $$A$$ y $$B$$, y $$A \to B$$ como el conjunto de las funciones de $$A$$ en $$B$$. Con la segunda interpretación, $$A \times B$$ se interpreta como la proposición $$A \wedge B$$ y $$A \to B$$ como la implicación (donde aquí $$A,B$$ los pensamos como variables proposicionales).
Si te fijas bien, las reglas de introducción y eliminación que hemos dado para $$\times$$ y $$\to$$ son exactamente las reglas de introducción y eliminación para la lógica proposicional en un cálculo de
deducción natural. Por ejemplo, la regla de eliminación para $$\to$$ es exactamente modus ponens: si tenemos $$f:A\to B$$ (una demostración de $$A \to B$$) y tenemos $$a:A$$ (una demostración de $$A$$), obtenemos una demostración $$f(a)$$ de $$B$$. Y los términos codifican exactamente las reglas que usamos en la demostración de una proposición. Esto se ve mejor con un ejemplo más complejo.
Por ejemplo, vamos a demostrar $$A \times (A \to B) \to B$$.
Primero, si pensamos de forma puramente lógica (en deducción natural), podríamos proceder como sigue. Para ver $$A \wedge (A \to B) \to B$$ basta con suponer $$A \wedge (A \to B)$$ y probar $$B$$. Pero si tenemos $$A \wedge (A \to B)$$, tenemos $$A$$ y tenemos $$A \to B$$ y por modus ponens obtenemos $$B$$, luego hemos acabado.
Ahora la versión de teoría de tipos. Si a partir de un término $$u : A \times (A \to B)$$ somos capaces de obtener un término $$b(u): B$$ (aquí la notación $$b(u)$$ denota que el término puede contener $$u$$ como variable libre) entonces por introducción de $$\to$$ obtendríamos que $$\lambda u. b(u) : A \times (A \to B) \to B$$ y ya estaríamos. Por lo tanto, basta con obtener un término de tipo $$B$$ a partir de uno de tipo $$A \times (A \to B)$$. Pero esto es relativamente sencillo: si $$u:A \times (A \to B)$$ entonces $$pr_1(u) : A$$ y $$pr_2(u):A \to B$$. Y una vez tenemos un término de tipo $$A \to B$$ y otro de tipo $$A$$ podemos aplicar eliminación de $$\to$$ (modus ponens) para obtener $$pr_2(u)(pr_1(u)):B$$. Poniendo todo junto, hemos encontrado un término en $$A \times (A \to B) \to B$$: en efecto, $$\lambda u. pr_2(u)(pr_1(u)) : A \times (A \to B) \to B$$.
Lo importante aquí es darse cuenta de que la segunda demostración es una copia de la primera, pero donde vamos "anotando" los pasos en los términos que vamos construyendo. Por lo tanto, el término final codifica la demostración entera. Así pues, hemos visto en un ejemplo la llamada correspondencia de Curry-Howard: hay una correspondencia entre tipos y proposiciones, y entre términos y demostraciones (en deducción natural).
Además hay otra correspondencia más: cada término de un tipo se puede interpretar como un programa. Por ejemplo, podemos interpretar los términos de $$A \to B$$ como procedimientos para a partir de un objeto de tipo $$A$$ obtener un objeto de tipo $$B$$. Veamos esto con el ejemplo anterior. Hemos construido el término $$\lambda u. pr_2(u)(pr_1(u)) : A \times (A \to B) \to B$$. Supongamos ahora que \( A=B=\Bbb Z \), el tipo de los enteros (podemos pensar en el tipo int de un lenguaje de programación). Imaginemos que tenemos un entero \( n \) y una función \( \Bbb Z \to \Bbb Z \), por ejemplo, \( f = \lambda n. n^2 \) (la función que a cada \( n \) entero le asigna su cuadrado). El término interpretado como un programa nos computa, a partir del par \( (n,f) \), el valor \( f(n) \). Y lo importante es que todo esto se sigue de las reglas de la teoría de tipos (en particular, de las de computación). Veámoslo con el ejemplo: $$\lambda u. pr_2(u)(pr_1(u))(n,f) \equiv pr_2(n,f)(pr_1(n,f)) \equiv f(n) \equiv (\lambda n.n^2)(n) \equiv n^2$$. Aquí hemos usado en la primera igualdad la regla de computación de $$\to$$, en la segunda las reglas de computación de $$\times$$, en la tercera la definición de $$f$$ y en la cuarta la regla de computación de $$\to$$.
Esto debería dar una idea de la "trinidad computacional": programas = tipos = lógica. No obstante, hay un pero. Aunque no he dado la versión completa de la teoría de tipos, la lógica proposicional que se obtiene no es la lógica clásica, sino la intuicionista (no es demostrable el tercio excluso \( A \vee \neg A \) o la regla de doble negación \( \neg \neg A \to A \)). Esto es debido a que no es posible dar una interpretación computacional de esas reglas, con lo que se "rompe" la trinidad de más arriba. No obstante, Lean usa estos principios clásicos sin problemas. La cuestión es que los puedes imponer como axiomas en la teoría de tipos, es decir, puedes usar un axioma (o esquema axiomático) que diga "para cualquier tipo $$A$$ existe un término en $$A \vee \neg A$$" y usar este término siempre que lo necesites en medio de una demostración. Pero este término no se puede obtener a partir de las reglas para $$\vee$$ y $$\neg$$ (que de hecho se define como $$\neg A:=A \to 0$$ donde $$0$$ es el tipo "vacío", que no tiene ningún término).
Una vez visto todo esto, por supuesto, la lógica proposicional se queda muy corta para hacer matemáticas. Por eso es necesario pasar a teorías de tipos más complicadas llamadas teorías de tipos dependientes. Aquí la diferencia es que los tipos pueden depender de términos de otros tipos. Por ejemplo, podrías definir un tipo $$Seq(n)$$ dependiente de un término $$n:\Bbb N$$, cuyos términos se interpretan como sucesiones finitas de longitud $$n$$. Y se suplementan las operaciones de tipos "proposicionales" de las que hablaba antes con otras nuevas (productos dependientes y sumas dependientes) que desde una interpretación lógica se pueden interpretar como cuantificadores universales y existenciales. Además, se añaden formas de definir nuevos tipos a partir de antiguos por recursión, llamados tipos inductivos. Con estos ingredientes básicamente se puede formalizar toda la matemática. Y con una versión adecuada de la correspondencia de Curry-Howard que he descrito antes, se puede ver cada término como codificando una demostración de una cierta fórmula en lógica de primer orden (o en una teoría de conjuntos, más o menos).
Espero que esto te dé aunque sea una ligera idea de por dónde van los tiros. Para aprender esto mejor con todos los detalles, puedes echar por ejemplo un vistazo a la primera parte de
este libro. Puedes ignorar el capítulo sobre la igualdad, porque el libro es de Homotopy Type Theory (HoTT) y ahí la igualdad funciona de forma distinta que en la teoría de tipos de Lean. Básicamente, la igualdad en HoTT en intensional, lo que quiere decir que se pueden tener términos distintos en un tipo igualdad (dicho de otra manera, dos objetos pueden ser iguales de formas esencialmente diferentes), lo que lleva a una interpretación homotópica de la teoría de tipos en la que los tipos se interpretan como espacios (tipos de homotopía) y los términos como puntos del espacio. Pero en Lean la igualdad es extensional: se fuerza a que si dos objetos son iguales, lo son de una sola manera, con lo cual los tipos se comportan de forma mucho más parecida a los conjuntos.
Otro tema: ¿por qué teoría de tipos en lugar de teoría de conjuntos para demostraciones asistidas por ordenador? Básicamente dos respuestas. La primera, la teoría de tipos está mucho más cerca de la práctica matemática habitual que la teoría de conjuntos. El hecho de que cada término pertenezca a un único tipo hace que si bien la sintaxis de la teoría sea bastante más compleja que la de teoría de conjuntos, no se permita expresar cosas "sin sentido" como por ejemplo \( \Bbb R^2 \in 5 \), que sí tienen sentido en teoría de conjuntos. Esto simplifica las comprobaciones y hace que el lenguaje sea de más "alto nivel" que en teoría de conjuntos. Por otro lado, el hecho de tener un sistema de tipos hace que las demostraciones sean comprobables por ordenador de manera sencilla y se puedan detectar los errores (de manera análoga a como un lenguaje de programación tipado usual detecta errores en tiempo de compilación).
Finalmente, sobre la relación entre la teoría de tipos de Lean y ZFC. Probablemente las haya, pero yo no conozco ninguna comparación directa del estilo "toda traducción de una sentencia de ZFC (o alguna extensión suya) es demostrable en teoría de tipos (tiene un término) y viceversa". Primero habría que aclarar qué es una traducción de manera formal, aunque en la práctica es bastante obvio cómo traducir entre ZFC y tipos. Quizás es un poco menos obvio el tema de las demostraciones porque las reglas en teoría de tipos suelen corresponder a teoremas de ZFC (por ejemplo, para el tipo de los naturales una de las reglas es el teorema de recursión), pero aún así debería ser evidente. Otro tema es cómo de fuerte es el sistema de tipos de Lean comparado con ZFC. En este
paper, además de dar una descripción formal de la teoría de tipos que implementa Lean exactamente, se prueba que la teoría de tipos de Lean es equiconsistente con ZFC + existen \( \omega \) cardinales inaccesibles. Esto quiere decir que, esencialmente, se puede formalizar lo mismo que en ZFC más algunas cuestiones de teoría de categorías que usan universos de Grothendieck.
Puf, al final me ha quedado larguísimo el mensaje, y eso que apenas he rascado la teoría de tipos dependiente propiamente dicha. Espero que se entienda algo y te sirva de algo, aunque sea el par de referencias que te he puesto.