Proste zamykania dla typów indukcyjnych ze spacjami funkcyjnymi

Funkcje zbudowane z produktów i sum skończonych mają porządek zamknięcia $\omega$, ładnie wyszczególnione w tym manuskrypcie Francoisa Metayera. tzn. możemy osiągnąć typ indukcyjny$nat := \mu X. 1 + X$ przez iterację funktora $1 + X$, który osiąga swój stały punkt po $\omega$ iteracje.

Ale kiedy pozwolimy na stałe potęgowanie, takie jak w $\mu X. 1 + X + (nat \rightarrow X)$, następnie $\omega$ nie wystarczy.

Szukam wyników obejmujących potęgowanie. Jakie porządki są wystarczające?

Szczególnie docenione byłoby odniesienie, które stanowi dowód, że takie funktory są $\alpha$- ciągłe dla niektórych porządkowych $\alpha$ jak w powyższym manuskrypcie.

Odpowiedź na twoje pytanie zależy od kilku rzeczy, z których najważniejszą jest wielkość przestrzeni funkcji . Wytłumaczę. Definiować

$$O_0 = nat$$ $$O_{n+1} = \mu X.\ 1+X+(O_n\rightarrow X)$$ Jak zauważyłeś w swojej odpowiedzi, każdy $O_n$może być uważany wewnętrznie za$n$-ty zwykły kardynał twojego systemu. W teorii mnogości ten typ danych może być reprezentowany przez rzeczywistą liczbę porządkową i jest odpowiednio ogromny.

Jednak takie konstrukcje mogą zostać dodane do niektórych wersji teorii typów, i powstaje pytanie: jaki porządek jest potrzebny, aby nadać interpretacji zestawu teoretycznej temu konstruktowi? Teraz, jeśli ograniczymy się do konstruktywnej semantyki, naturalną ideą jest próba interpretacji każdego typu przez zbiór „realizatorów” tego typu, który jest podzbiorem zbioru$\lambda$-terms lub równoważnie liczby naturalne $\mathbb{N}$.

W takim przypadku łatwo jest wykazać, że porządek można policzyć dla dowolnego $O_n$, ale ten porządek rośnie bardzo szybko. Jak szybko? Znowu zależy to od ilości swobody, jaką masz, próbując budować funkcje. Teoria budowania takich porządków jest opisana w teorii dużych policzalnych porządków, o których Wikipedia ma zaskakująco wiele do powiedzenia. Zasadniczo łatwo jest wykazać, że omawiane porządki są mniejsze niż Ordinal kościelny-Kleene , chyba że dopuszczasz niekonstruktywne środki budowania funkcji (powiedzmy$Beaver(n)$ która oblicza numer zajętego bobra dla maszyn z $n$ państwa).

Nie mówi to jednak wiele, poza tym, że w teorii konstruktywnej do budowania interpretacji potrzebne są jedynie konstruktywne porządki porządkowe. Jest jednak coś więcej do powiedzenia. Po pierwsze, jest bardzo ładna prezentacja Thierry'ego Coquanda, która opisuje, że przy braku eliminatora dla wszystkich innych typów, ale$nat$, możesz budować $O_1$ Dokładnie $\epsilon_0$ kroki.

Zasadniczo wydaje się, że istnieje zgodność między siłą logiczną teorii typów a wielkością największej liczby porządkowej, którą może reprezentować w ten sposób. Ta korespondencja jest przedmiotem analizy porządkowej , która była badana od późnych lat sześćdziesiątych i jest nadal przedmiotem badań (niektóre niesamowite pytania otwarte). Ostrzeżenie: temat jest równie techniczny, co fascynujący.

Mam nadzieję że to pomoże.

Myślę, że znalazłem odpowiedź, która działa w kategoriach wystarczająco podobnych do Seta. Jest to twierdzenie 3.1.12 w Pierwotnych algebrach i terminalnych węgielach: ankieta przeprowadzona przez Adamka, Miliusa i Mecha.

Odpowiedź jest taka, że ​​jeden porządek nie jest wystarczający dla wszystkich takich funktorów. Stają się dowolnie duże.

Dokładniej dla $F(X) = C_0\times(A_0 \rightarrow X) + C_1\times(A_1 \rightarrow X)\;+\;...\;+\; C_n\times(A_n \rightarrow X)$, odpowiedź jest pierwszą regularną porządkową większą niż wszystkie$A_i$. Mówimy$\alpha$ jest regularny, jeśli dla wszystkich $\beta < \alpha$, wszystko $\beta$-indexed łańcuchy rzędnych < $\alpha$ mieć supremum < $\alpha$. W przybliżeniu,$\alpha$ nie jest osiągalny z mniejszego łańcucha mniejszych porządków.

Kluczowym rezultatem jest to $\alpha$ zwykły porządek, uzasadniony $\alpha$-gałęziające się drzewa mają nieskończoną głębokość < $\alpha$.

Nieformalnie rozumiem to jak każdy $f : A_k \rightarrow F^\alpha(0)$ (to znaczy $f : A_k \rightarrow \bigcup_{i<\alpha} F^i(0)$) "pasuje do" $A_k \rightarrow F^j(0)$ gdzie $j := \mathrm{sup}_{(a:A_k)} \text{``the i such that }f(a) \text{ fits into } F^i(0)"$. Że$j < \alpha$ trzyma się właśnie dlatego $\alpha$ jest regularny i $|A_k| < \alpha$.

Więc $(A_k \rightarrow \bigcup_{i<\alpha}F^i(0)) \subseteq \bigcup_{j<\alpha} (A_k \rightarrow F^j(0))$ dla każdego $k$.

Rozszerzając to na $+$s i $\times$s mamy: $F(F^\alpha(0)) \subseteq \bigcup_{j<\alpha}F(F^j(0)) = \bigcup_{j<\alpha}F^j(0) = F^\alpha(0)$, a więc osiągnął ustalony punkt na $\alpha$.

Jednak nie jest dla mnie jasne, jak uogólnić ten argument poza Setem. Jak bierzemy$A_k$-indexed colimits?