Minimalna specyfikacja teorii typów Martina-Löfa

Czytam formalną prezentację teorii typów Martina-Löfsa (załącznik do książki HoTT ). Autorzy wprowadzić hierarchię światów, a oraz -types jak liczb naturalnych (indukcyjnie przez , a ). W końcu dodają także wyższe typy indukcyjne. $\Pi, \Sigma,+, {\bf 0}, {\bf 1}$ $W$ $\mathbb N$ $0$ $succ$

Ale potem zastanawiam się, dlaczego konieczne jest wykonanie w specyfikacji teorii. Czy i oraz algebraiczne typy danych, w inkarnacji posiadania typów , nie wystarczą, aby je skonfigurować? Np. Z początkowym podejściem do algebry . (Lub przynajmniej po przejściu z MLTT do HoTT mają typy indukcyjne - w końcu liczby całkowite pojawiają się jako grupa homotopii okręgu typu w teorii). $\mathbb N$ ${\bf 1}$ $+$ $W$ $\mathbb Z$ $\mathbb S$

Czy może ma to związek z naszą potrzebą prymitywnej rekurencji od samego początku, która jest zdefiniowana obok w prezentacji? Jest to pomysł, który mam, ponieważ nie do końca wiem, jak „definicja jest zdefiniowana” w tym frameworku lub jak formalnie rozszerza się język. Mogę dodać, że zdaję sobie sprawę, że przynajmniej nieformalne pojęcie liczb i „większe” jest używane już przy definiowaniu hierarchii wszechświatów. $\mathbb N$

W przypadku, gdy można oszczędzić a specyfikacja nie jest po prostu minimalna, czy są jeszcze inne przedmioty, które można w zasadzie upuścić? Np. Mogłem sobie wyobrazić a potem pochodzące z kombinacji , ale nie byłem w stanie tego zrobić. $\mathbb N$ $\bf 2$ $+$ $\Pi, \Sigma, {\bf 0}, {\bf 1}$

type-theory

— Nikolaj-K
źródło

Celem systemu opisanego w dodatku do książki HoTT jest przedstawienie czegoś, co odpowiada temu, z czego korzysta książka. Książka ma na celu edukację. Dlatego złym pomysłem byłoby robienie wszystkiego w minimalistyczny sposób. Na przykład wprowadzamy osobno, ponieważ instruktażowe jest sprawdzenie, jak działają konstrukcje indukcyjne w znanym przypadku. $\mathbb{N}$

Masz całkowitą rację, aby przeskoczyć typy indukcyjne z ogólnych typów , potrzebujesz tylko i . Natychmiast dostajesz jako i dostajesz od i . Gdy to zrobisz, otrzymasz wszystkie skończone sumy . W tym momencie łatwo jest wykonać zwykłe algebraiczne typy danych. $W$ $0$ $2$ $1$ $0 \to 0$ $+$ $2$ $\Sigma$ $1 + 1 + \cdots + 1$

Jeśli upuścisz , więc zaczniesz od , , i , nie możesz odzyskać ponieważ każdy tworzony typ będzie zamieszkały. $0$ $\Pi$ $\Sigma$ $1$ $2$ $0$

Załóżmy, że masz tylko , , i . Nie możesz zrobić ponieważ możesz pokazać, że każda zbudowana konstrukcja daje ci lub . W rzeczywistości nie można tworzyć interesujących rodzin zależnych. Większy rodziny rodzaju, który jest zamknięty pod , , i , ale nie zawierają jest -types (propozycji). $\Pi$ $\Sigma$ $0$ $1$ $2$ $0$ $1$ $\Pi$ $\Sigma$ $0$ $1$ $2$ $(-1)$

— Andrej Bauer
źródło

OK, dziękuję za odpowiedź. Przypuszczam, że

jest możliwe w tych ramach, ponieważ

jest możliwe według definicji

. Chociaż ta funkcja

który nigdy nie podejmie dyskusji, jest niezręczny.

1 \equiv (0 \to 0)

${\bf 1}\equiv({\bf 0}\to {\bf 0})$

(λ x . x) : (0 \to 0)

$(\lambda x.x):({\bf 0}\to {\bf 0})$

Π

$\Pi$

λ x . x

$\lambda x.x$

— Nikolaj-K,

Przydałoby się dodać, że typy

przedstawiają pewne techniczne zastrzeżenia w teorii celowej: patrz np. Równość obserwacyjna, teraz! . Niektóre (wszystkie?) Z nich są nieobecne, gdy obecny jest aksjomat Univalence.

W

$W$

— cody

Dzisiaj znów myślałem o tym pytaniu. Właściwie, kiedy mówimy o MLTT lub HOTT, mamy równość dla wszystkich typów, tak sądzę, więc możemy otrzymać

, prawda?

0

${\bf 0}$

1 =_{U} 2

${\bf 1}=_U{\bf 2}$

— Nikolaj-K

Można dostać

tamtędy, ale należy pamiętać, że

odnosi się do uniwersum

. I tak zdefiniowane

żyje niezręcznie w następnym wszechświecie.

0

$0$

1 =_{U} 2

$1 =_U 2$

U

$U$

0

$0$

— Andrej Bauer,

Jestem zdezorientowany przez „Jeśli spadniesz

, więc zaczniesz od

, to nie możesz odzyskać

ponieważ każdy typ, który stworzysz, będzie zamieszkały”. Ponieważ możliwe jest konstruowanie pustych typów w czystym rachunku różniczkowym konstrukcji, który ma tylko

0

$0$

Π

$\Pi$

Σ

$\Sigma$

1

$1$

2

$2$

0

$0$

Π

$\Pi$

— user833970,