Ordenales de cierre para tipos inductivos con espacios funcionales.

Los functores construidos a partir de productos finitos y sumas tienen cierre ordinal , que se detalla muy bien en este manuscrito de Francois Metayer. es decir, podemos alcanzar el tipo inductivo iterando el functor , que alcanza su punto fijo después de las iteraciones .$\omega$$nat := \mu X. 1 + X$$1 + X$$\omega$

Pero una vez que permitimos la exponenciación constante, como en , entonces no es suficiente.$\mu X. 1 + X + (nat \rightarrow X)$$\omega$

Estoy buscando resultados que incluyan exponenciación. ¿Qué tipo de ordinales son suficientes?

Especialmente apreciada sería una referencia que presenta una prueba de que tales functores son continuos para algún ordinal como en el manuscrito anterior.$\alpha$$\alpha$

La respuesta a su pregunta depende de varias cosas, la más importante de las cuales es el tamaño de sus espacios de funciones . Lo explicaré. Definir Como se anotó en su respuesta, cada puede considerarse internamente para ser el -ésimo cardenal regular de su sistema. En la teoría de conjuntos, este tipo de datos puede representarse mediante un ordinal real y es apropiadamente enorme.O n + 1 = μ X . 1 + X + ( O n → X ) O n

$$O_0 = nat$$ $$O_{n+1} = \mu X.\ 1+X+(O_n\rightarrow X)$$ $O_n$$n$

Sin embargo, tales construcciones pueden agregarse a alguna versión de la teoría de tipos, y la pregunta es: ¿qué ordinal se necesita para dar una interpretación teórica de conjuntos a esta construcción? Ahora, si nos limitamos a la semántica constructiva , una idea natural es tratar de interpretar cada tipo por el conjunto de "realizadores" de este tipo, que es un subconjunto del conjunto de -terms, o equivalentemente, los números naturales .$\lambda$$\mathbb{N}$

En este caso, es fácil demostrar que el ordinal es contable para cualquier , pero que este ordinal crece muy rápidamente. ¿Cuan rápido? Nuevamente, esto depende de la cantidad de libertad que tenga cuando intente construir funciones. La teoría para construir tales ordinales se describe en la teoría de los ordinales contables grandes, de la cual Wikipedia tiene, sorprendentemente, mucho que decir. En general, es fácil mostrar que los ordinales en cuestión son más pequeños que el ordinal de Church-Kleene , a menos que permita medios no constructivos para construir funciones (digamos que calcula el número de castores ocupados para máquinas con estados). B e a v e r ( n ) $O_n$$Beaver(n)$$n$

Sin embargo, esto no dice mucho, excepto que en una teoría constructiva, solo se requieren ordinales constructivos para construir interpretaciones. Sin embargo, hay un poco más que decir. Primero, hay una muy buena presentación de Thierry Coquand que detalla que, en ausencia de un eliminador para todos los demás tipos, excepto$nat$ , puede construir en exactamente pasos.ϵ $O_1$$\epsilon_0$

En general, parece haber una correspondencia entre la fuerza lógica de una teoría de tipos y el tamaño del ordinal más grande que puede representar de esta manera. Esta correspondencia es el tema del Análisis Ordinal , que se ha estudiado ampliamente desde finales de los años sesenta, y todavía se está estudiando hoy (con algunas preguntas abiertas sorprendentes). Advertencia, sin embargo: el tema es tan técnico como fascinante.

Espero que esto ayude.

Creo que he encontrado una respuesta que funciona en categorías lo suficientemente similares a Set. Es el teorema 3.1.12 en Álgebras iniciales y coalgebras terminales: una encuesta realizada por Adamek, Milius y Moss.

La respuesta es que ningún ordinal es suficiente para todos esos functores. Se vuelven arbitrariamente grandes.

Más precisamente, para , la respuesta es el primer ordinal regular más grande que todos los . Decimos que es regular si para todas , todas las cadenas de ordinales indexadas con < tienen un supremum < . Aproximadamente, no es accesible desde una cadena más pequeña de ordinales más pequeños.$F(X) = C_0\times(A_0 \rightarrow X) + C_1\times(A_1 \rightarrow X)\;+\;...\;+\; C_n\times(A_n \rightarrow X)$$A_i$$\alpha$$\beta < \alpha$$\beta$$\alpha$$\alpha$$\alpha$

El resultado clave es que para un ordinal regular, los árboles bien ramificados tienen una profundidad transfinita < .$\alpha$$\alpha$$\alpha$

Informalmente, entiendo que cualquier (es decir, ) "encaja en" donde . Eso es precisamente porque es regular y .f : A k → ⋃ i < α F i ( 0 ) A k → F j ( 0 $f : A_k \rightarrow F^\alpha(0)$$f : A_k \rightarrow \bigcup_{i<\alpha} F^i(0)$$A_k \rightarrow F^j(0)$$j := \mathrm{sup}_{(a:A_k)} \text{``the i such that }f(a) \text{ fits into } F^i(0)"$$j < \alpha$$\alpha$$|A_k| < \alpha$

Entonces para cada .$(A_k \rightarrow \bigcup_{i<\alpha}F^i(0)) \subseteq \bigcup_{j<\alpha} (A_k \rightarrow F^j(0))$$k$

Entonces, extendiendo esto a través de sy s, tenemos: , y así se alcanza el punto fijo en .× F ( F α ( 0 ) ) ⊆ ⋃ j < α F ( F j ( 0 ) ) = ⋃ j < α F j ( 0 ) = F α ( 0 ) $+$$\times$$F(F^\alpha(0)) \subseteq \bigcup_{j<\alpha}F(F^j(0)) = \bigcup_{j<\alpha}F^j(0) = F^\alpha(0)$$\alpha$

Sin embargo, no tengo muy claro cómo generalizar este argumento más allá de Set. ¿Cómo tomamos indexados con A_k?$A_k$