Demostrando que $\Omega = (\lambda x.xx)(\lambda x.xx)$ no es tipificable en el cálculo simplemente mecanografiado de la lambda

Question

Estoy tratando de demostrar que $\Omega = (\lambda x.xx)(\lambda x.xx)$ es no escribir en el tipo simple cálculo lambda. Sorprendentemente, los diferentes libros de texto y apuntes de clase no contienen dicha prueba, por favor me corrija si estoy equivocado.

La prueba es importante, porque la $\Omega$ no tiene una forma normal y si no se puede escribió luego de la normalización de los teoremas no se aplican.

De el libro de las Pruebas y los Tipos por Girard, Taylor, y Lafont, que he leído:

Si $t$$u$, respectivamente $U \rightarrow V$$U$, luego $t \; u$ es un término de tipo de $V$.

Voy a probar que cualquier lambda plazo de tipo de $x \; x$ no puede ser escrito.

Supongamos que el tipo de la última $x$$T$, entonces el tipo de la ex $x$ debe $T \rightarrow U$.

Eso es imposible, porque $x$ no puede tener dos tipos diferentes.

Esto implica que $\Omega$ es no escribir en el tipo simple cálculo lambda, debido a que contiene una expresión de la forma $x\; x$.

Mis preguntas son:

1. Es mi prueba correcta?
2. Existe una mejor prueba?
3. ¿Existe alguna extensión de cálculo lambda donde $\Omega$ puede ser escrito?

Answer 1

1. Sí.
2. Yo no lo creo. Tienes la esencia de la incompatibilidad.
3. Sí. El ejemplo más notable emplea intersección-tipos que permiten, siguiendo el ejemplo de su elección, asignaciones como $$x\ \ :\ \ T\ \wedge\ T\!\rightarrow\!U$$ y, en consecuencia, $$x x\ \ :\ \ U$$ y $$\lambda x.xx\ \ :\ \ T\!\rightarrow\!U \wedge T\!\rightarrow\!U$$ Más detalles se expresa en un introductive formulario se puede encontrar, entre otros muchos, en el 1998 artículo titulado Intersección Tipos, $\lambda$-modelos, y Bohm Árboles, por M. Dezani-Ciancaglini, E. Giovannetti, y U. De'Liguoro.