¿Cuál es la paradoja de Girard?

Answer 1

“Paradoja de Girard” es el nombre que generalmente se le da a cualquier formalización del argumento de la paradoja de Russell en un sistema de tipo polimórfico.

En la paradoja de Russell, la inconsistencia de la existencia de un conjunto [matemática] U [/ matemática] de todos los conjuntos se deriva de hecho de la propiedad más específica [matemática] \ matemática {P} (U) \ subseteq U [/ matemática], que tal conjunto [matemática] U [/ matemática] tendría. De hecho, suponga que tiene un conjunto [math] U [/ math] tal que [math] \ mathcal {P} (U) \ subseteq U [/ math]. Puede definir el “conjunto” de Russell [matemáticas] \ Delta: = \ {a \ en U: a \ not \ in a \} [/ math]. Luego, como [math] \ Delta \ in \ mathcal {P} (U) \ subseteq U [/ math], puede preguntar si [math] \ Delta \ in \ Delta [/ math], obteniendo la famosa equivalencia paradójica [ math] \ Delta \ in \ Delta [/ math] iff [math] \ Delta \ not \ in \ Delta [/ math]. Esto también se conoce como la prueba del teorema de Cantor, es decir, del hecho de que no hay una suposición de un conjunto [matemática] U [/ matemática] a [matemática] \ matemática {P} (U) [/ matemática]. Multa. Hasta ahora, esta es la cultura popular.

Ahora, el argumento anterior se puede formalizar en cualquier sistema de tipos que tenga la regla de mecanografía [matemáticas] Tipo: Tipo [/ matemáticas] y también tipos de polimorfismo (la capacidad de definir objetos que dependen de tipos, es decir, objetos de tipo [matemáticas] Tipo \ Tipo de flecha derecha [/ math]). Por ” formalizado” me refiero a encontrar términos del sistema que imiten todos los pasos del argumento de Russell anterior.
Como [math] Type: Type [/ math], para cualquier [math] U: Type [/ math] se puede definir [math] U \ rightarrow Type: Type. [/ Math]
La idea inicial de Girard es utilizar ese tipo [math] U \ rightarrow [/ math] como algo así como un “powertype” [math] \ mathcal {P} (U). [/ Math] Diría que [math] \ mathcal {P} (U) [/ math] debería ser algo así como [math] U \ rightarrow Bool [/ math] (intuitivamente, el conjunto / tipo de funciones características). Bueno, aquí se usa Tipo en sí en lugar de Bool . A partir de ahora, configuro [math] \ mathcal {P} (U): = U \ rightarrow Type [/ math].
Uno encuentra los términos [math] elem: \ mathcal {P} (U) \ rightarrow U [/ math] ( elemX intuitivamente dice “pensemos el subconjunto X de U como un elemento de U “) y el subconjunto [math]: U \ rightarrow \ mathcal {P} (U) [/ math] (el subconjunto a intuitivamente dice “pensemos que el elemento a de U como un subconjunto de U “) lo hace capaz de formalizar el conjunto [math] \ Delta [/ math ] de la paradoja de Russell: ya sea como el término [matemáticas] \ Delta: = elem (\ lambda x: U. \ neg (subconjunto x) x): U [/ matemáticas] si uno quiere verlo como un elemento de U , o como
[math] subset \ Delta: \ mathcal {P} (U) [/ math] si uno quiere usarlo como un subconjunto de U.
Al final, es posible encontrar un término [matemático] R: subconjunto (\ Delta) \ Delta \ leftrightarrow \ neg subconjunto (\ Delta) \ Delta [/ math]. No sé exactamente cómo (¡esa es la parte difícil de la cosa, y nunca leí una prueba completa de esto!), Pero la hipótesis de tener tipos de polimorfismo es necesaria para que aparezca R. De la existencia de R se obtiene que todo es tipificable en dicho sistema.

Girard hizo esto en su tesis de doctorado publicada en 1970, para demostrar la inconsistencia de la primera versión de la teoría del tipo intuicionista de Martin-Löf, que apareció en 1968, creo. ¡De hecho, la cosa es más complicada que eso! Martin-Löf no puso la regla [matemáticas] Tipo: Tipo [/ matemáticas] en su sistema del ’68, porque entendió que podía inyectar alguna forma de contradicción similar a Russell en la lógica. Eso es bastante intuitivo, de hecho. Entonces él dio lo que llamaríamos ahora la regla (no peligrosa) [matemáticas] Tipo: Tipo [/ matemáticas]. Sin embargo, dejó que su sistema tuviera “tipos de polimorfismo”, lo mismo que los tipos de polimorfismo, pero a un nivel superior. Bueno, lo que Girard demostró en su tesis es, de hecho, que incluso con este tipo de polimorfismo se puede formalizar la paradoja de Russell.

Answer 2

El problema está relacionado con la paradoja de Russel, pero se aborda en el texto que usted indica (vea mi cita, a continuación).

He reformulado la paradoja de R. para usuarios de lenguaje común. Por lo general, requiere una breve discusión para dejar en claro, pero cualquiera que quiera jugar con este pequeño juguete notará rápidamente que tiene cualidades peculiares que no se agotan fácilmente con solo descubrirlo uno mismo.

Considere que “Esta declaración es una mentira”. Tiene una estructura peculiar en el sentido de que, por su contenido, “se promueve” al orden de las declaraciones de contenedor mediante las cuales normalmente se interpretaría, lo que interfiere con cualquier interpretación posible. .

Esto se puede afirmar … como una declaración que debe entrar en conflicto consigo misma para ser declarada.

“Ninguna declaración se promoverá al orden de las declaraciones o proposiciones por las cuales se interpretaría”.

La declaración anterior hace lo que prohíbe.

Esto está algo bien explicado en el texto fuente de la siguiente manera:

“Las ocurrencias de tipo se anotan con información adicional, comentarios internos. Estas anotaciones tienen que ver con el secreto detrás de Type: realmente representa una jerarquía infinita de tipos. El tipo de Conjunto es Tipo (0), el tipo de Tipo (0) es Tipo (1), el tipo de Tipo (1) es Tipo (2), y así sucesivamente. Así es como evitamos la paradoja “Tipo: Tipo”. Como conveniencia, la jerarquía del universo impulsa la variedad de subtipos de Coq. Cualquier término cuyo tipo es Tipo en el nivel i también se describe automáticamente por Tipo en el nivel j cuando j> i “.