Czy w książce Hott większość redaktorów jest zbędna? A jeśli tak, to dlaczego?

W rozdziale 1 i załączniku A książki Hott przedstawiono kilka rodzin typów pierwotnych (typy wszechświatów, typy funkcji zależnych, typy par zależnych, typy koproduktów, typy puste, typy jednostek, typy liczb naturalnych i typy tożsamości), aby stworzyć podstawę dla teorii typów homotopii.

Wydaje się jednak, że biorąc pod uwagę typy wszechświata i typy funkcji zależnych, można skonstruować wszystkie inne typy „prymitywne”. Na przykład typ Pusty można zamiast tego zdefiniować jako

ΠT:U.T

Zakładam, że inne typy mogą być również skonstruowane podobnie jak w czystym CC , (tj. Po prostu wyprowadzić typ z indukcyjnej części definicji).

Wiele z tych typów zostało wyraźnie zwolnionych przez typy indukcyjne / W, które zostały wprowadzone w rozdziałach 5 i 6. Jednak typy indukcyjne / W wydają się być opcjonalną częścią teorii, ponieważ istnieją otwarte pytania dotyczące ich interakcji z HoTT (w przynajmniej w momencie ukazania się książki).

Jestem bardzo zdezorientowany, dlaczego te dodatkowe typy są przedstawiane jako prymitywne. Moją intuicją jest to, że podstawowa teoria powinna być jak najmniejsza, a redefiniowanie zbędnego typu pustego jako prymitywnego w teorii wydaje się bardzo arbitralne.

Czy dokonano tego wyboru?

z jakichś metateoretycznych powodów, których nie jestem świadomy?
z powodów historycznych, aby teoria typów wyglądała jak teorie typu przeszłego (które niekoniecznie próbowały być fundamentalne)?
za „użyteczność” interfejsów komputerowych?
dla jakiejś korzyści w poszukiwaniu dowodów, której nie jestem świadomy?

Podobne do: Minimalna specyfikacja teorii typów Martina-Löfa , /cs/82810/reducing-products-in-hott-to-church-scott-encodings/82891#82891

type-theory dependent-type homotopy-type-theory

— użytkownik833970
źródło

Są zbędne, ale nie tak, jak sugerujesz. Powinieneś zadać sobie pytanie, do czego służy „minimalizm fundamentów”? Czy zależy nam na celu?

— Andrej Bauer

Zakładam, że praca techniczna jest minimalna zgodnie z konwencją, gdzie rzeczy nie muszą być minimalne, jeśli są najwyraźniej wygodne lub wyraźnie zaznaczono inaczej. Książka przestrzega tego nawet w innych miejscach, na przykład gdy definiuje typy obcięcia (zdefiniowane przez reguły, ale wyraźnie nie minimalne). Na przykład, gdybym widział naty zdefiniowane w kategoriach 0,1,10, następcę i operację zasilania, byłbym zdezorientowany, ale mógłbym przynajmniej zrozumieć, dlaczego jest to notarialnie wygodne. Hott jest o wiele bardziej złożonym obszarem nauki i chcę wiedzieć, czy brakuje mi czegoś oczywistego.

— user833970,

Byłbym bardzo zainteresowany, aby dowiedzieć się, w jaki sposób mogą być szkodliwe. Czy powinienem zadać nowe pytanie?

— user833970,

@AndrejBauer Chciałbym wiedzieć, dlaczego byłyby również szkodliwe. Moje rozumowanie, by sądzić, że podstawowy język powinien być minimalny, jest uzasadnieniem brzytwy okazjonalnej, jest to nieuzasadniona dodatkowa złożoność. Po co się tam zatrzymywać? Dlaczego nie dodać także list, ciągów, par, potrójników, wektorów? To wydaje się arbitralne wybory, co je uzasadnia? Edycja: Właśnie zauważyłem, że to pytanie ma odpowiedzi; ale zostawiam ten komentarz tutaj, aby przypomnieć sobie, dlaczego też mnie to interesuje.

— MaiaVictor,

Napiszę post na blogu.

— Andrej Bauer,

Odpowiedzi:

Pozwól mi wyjaśnić, dlaczego sugerowane kodowanie pustego typu nie działa. Musimy jasno określać poziomy wszechświata i nie zamiatać ich pod dywan.

Kiedy ludzie mówią „pusty typ”, mogą oznaczać jedną z dwóch rzeczy:

Pojedynczego typu , który jest pusty w odniesieniu do wszystkich typów. Taki typ ma zasadę eliminacji: dla każdej rodziny typów istnieje mapa $E$ $n$ $A : E \to U_n$ $e_{n,A} : E \to A$ .
Rodzina typów , po jednym dla każdego poziomu wszechświata , tak że jest „pustym typem ”. Taki typ musi spełniać , oczywiście, a także: dla każdego typu rodziny , jest mapa . $E_k$ $k$ $E_k$ $U_k$ $E_k : U_k$ $A : E_{k} \to U_k$ $e_{k,A} : E_{k} \to A$

Bez żadnych zastrzeżeń, kiedy ludzie mówią „pusty typ”, oczekują pierwszego znaczenia powyżej.

Jak możemy uzyskać ? Pierwsza próba może być czymś w rodzaju $E$ ale właśnie taki zamiatanie pod dywan powoduje zamieszanie. Musimy zapisać wyraźne poziomy wszechświata. Jeśli napiszemy coś w rodzaju

mi = Π (T. : U) . T.

$E = \Pi (T : U) \,.\, T$

wtedy otrzymujemy sekwencję typów

, po jednym dla każdego poziomu

. Możemy mieć nadzieję, że ta sekwencja jest pustym typem w powyższym znaczeniu, ale tak nie jest, ponieważ

jest w

ale powinno być w

{mi}_{k} = Π (T. : U_{k}) . T.

$E_k = \Pi (T : U_k) \,.\, T$

E_{0}, E_{1}, E_{2}, \dots

$E_0, E_1, E_2, \ldots$

k

$k$

E_{k}

$E_k$

U_{k + 1}

$U_{k+1}$

U_{k}

$U_k$

Kolejna próba to ale teraz musisz wyjaśnić, czympowinno być„ ”. Możesz pokusić się o stwierdzenie, że istnieje typ poziomów wszechświata, a więc

E = Π n . Π (T : U_{n}) . T

$E = \Pi n \,.\,\Pi (T : U_{n}) \,.\, T$

Π n

$\Pi n$

L

$L$

Wpadłeś teraz w pułapkę, bo zapytam: w jakim wszechświecieżyje

? I w którym wszechświat ma

E = Π (n : L) . Π (T : U_{n}) . T

$E = \Pi (n : L) \,.\,\Pi (T : U_{n}) \,.\, T$

E

$E$

L

$L$ żyje ? To nie zadziała.

$U$ $B : U \to U$ $\Pi (X : U) B(X)$ $U$ $U$ $\Pi (X : U) X$ $U$ i będzie miał oczekiwany eliminator. Ale wciąż nie jesteśmy skończeni, ponieważ teraz musimy martwić się równaniami eliminatora, jak zauważył Neel.

Wszechświaty impredykatywne mogą być ustawione. Jednak słynne twierdzenie Thierry'ego Coquanda (jeśli się nie mylę) pokazuje, że posiadanie dwóch impredykatywnych wszechświatów, jednego zawartego w drugim, prowadzi do sprzeczności.

Morał tej historii jest taki: po prostu aksjatyzuj pusty typ bezpośrednio i przestań kodować rzeczy.

— Andrej Bauer
źródło

To przekonujące uzasadnienie do aksjatyzacji pustego typu, ale nadal jestem ciekawy uzasadnienia do aksjatyzacji tych wszystkich cięższych rzeczy.

— MaiaVictor,

@MaiaVictor: w przeciwieństwie do czego?

— Andrej Bauer,

Przepraszam? Mam na myśli, że jesteś przekonująco uzasadniony, dlaczego warto aksjatyzować w szczególności pusty typ. Ale OP zapytał także o inne rzeczy: „typy wszechświata, typy funkcji zależnych, typy par zależnych, typy koproduktów, typy puste, typy jednostek, typy liczb naturalnych i typy tożsamości” (które, jak zakładam, są również prymitywami w systemie zaproponowanym na Książka HoTT). (Oczywiście nie proszę cię o uzasadnienie tego wszystkiego, tylko

— okazuję

1 = \prod_{X : U} (X \to X)

$\mathbb{1} = \prod_{X : U} (X \to X)$

@IngoBlechschmidt ciekawi, jakie rodzaje problemów! Dobrze mi to wygląda ...

— MaiaVictor

Zadajesz kilka pytań, które są podobne, ale różne.

Dlaczego książka HoTT nie używa kodowań kościelnych dla typów danych?

Kodowanie kościelne nie działa w teorii typów Martina-Löfa z dwóch powodów.

$n$ $k < n$

Po drugie, nawet jeśli zdefiniowałeś typy danych, takie jak liczby naturalne w kodowaniu kościelnym, aby wykonać dowody z tymi typami, potrzebujesz zasad indukcyjnych, aby udowodnić pewne rzeczy na ich temat. Aby wyprowadzić zasady indukcji dla kodowań kościelnych, musisz użyć argumentu opartego na parametryczności Reynoldsa, a pytanie, jak internalizować zasady parametryczności do teorii typów, wciąż nie jest w pełni rozstrzygnięte. (Najnowszym stanem techniki jest Nuyts, Vezzosi i Devriese's ICFP 2017 Paper Parametric Quantifiers for Dependent Type Theory - zauważ, że jest to dużo po napisaniu książki HoTT!)
Następnie pytasz, dlaczego podstawa nie jest minimalna. Jest to w rzeczywistości jedna z charakterystycznych cech socjologicznych podstaw teoretycznych typu - teoretycy typu uważają, że posiadanie małego zestawu reguł jest techniczną wygodą, bez większego znaczenia fundamentalnego. O wiele ważniejsze jest posiadanie odpowiedniego zestawu reguł niż najmniejszego zestawu reguł.

Opracowujemy teorie typów, które mają być stosowane przez matematyków i programistów, i bardzo, bardzo ważne jest, aby dowody wykonane w ramach teorii typów były tymi, które matematyki i programiści uważają za wykonane we właściwy sposób. Wynika to z tego, że argumenty, które matematycy zwykle uważają za posiadające dobry styl, są zazwyczaj ustrukturyzowane przy użyciu kluczowych zasad algebraicznych i geometrycznych w dziedzinie badań. Jeśli musisz korzystać ze skomplikowanych kodowań, wiele struktur jest traconych lub zasłanianych.

Dlatego nawet teoretyczne prezentacje klasycznej logiki zdań niezmiennie dają wszystkie logiczne połączenia, mimo że formalnie jest to równoważne logice z tylko NAND. Jasne, wszystkie łączniki boolowskie mogą być kodowane za pomocą NAND, ale to kodowanie zaciemnia strukturę logiki.

— Neel Krishnaswami
źródło

Dzięki za tę odpowiedź! Będę musiał przeczytać ten artykuł (i twój) i może to mieć większy sens. Ale myślałem, że hierarchia wszechświata została zaprojektowana tak, aby wyglądała, jakbyś mogła robić predykcyjne rzeczy: na przykład (λA: U.λa: Aa) (ΠA: UA → A) zaprowadziłby się do (λA: Un + 1.λa: Aa) (ΠA: Un.A → A). Myślę, że nie jest to dziwny wybór redakcyjny, żeby tego nie wyjaśniać, każda książka logiczna, którą znam, wskazuje na kilka bardziej minimalnych kodowań, takich jak CNF, DNF, NAND i tak dalej. I każdy, kto jest przyzwyczajony do ustalania teorii, oczekuje „naturalnego” kodowania Natsa, aby zademonstrować teorię. Ale to mogą być tylko moje klasyczne uprzedzenia.

— user833970,

to powinno być „impredicative” w moim ostatnim komentarzu

— user833970,

\prod (T : U_{n}) . T

$\prod (T : U_n) . T$

U_{n}

$U_n$

U_{n + 1}

$U_{n+1}$

U_{n}

$U_n$

Być może coś nie rozumiem o hierarchiach wszechświata. Pomyślałem, że nigdy nie obchodzi nas, w którym konkretnym Wszechświecie jest dany typ, tylko że numery wszechświata można przypisać, gdy chcemy zweryfikować dowód. Technicznie ΠT: UT jest rodziną typów indeksowanych przez wszechświaty. Podobnie jak tożsamość polimorficzna jest rodziną typów indeksowaną przez wszechświaty. Ale czy nie mamy tego samego problemu z tożsamością polimorficzną? Byłbym bardzo wdzięczny, gdybyś mógł rozwinąć ostatnie 2 zdania, nie sądzę, że rozumiem.

— user833970,

Kiedy mówisz, że nie ma właściwych właściwości eliminacyjnych, masz na myśli, że po naprawieniu wszechświata istnieją typy w wyższych wszechświatach, których nie można bezpośrednio zsyntetyzować za pomocą terminu ΠT: Un.T?

— user833970,