Dans le livre Hott, la plupart des types de types sont-ils redondants? Et si oui, pourquoi?

Dans le chapitre 1 et l'annexe A du livre Hott , plusieurs familles de types primitifs sont présentées (types d'univers, types de fonctions dépendantes, types de paires dépendantes, types de coproduits, type vide, type d'unité, type de nombre naturel et types d'identité) pour former la base pour la théorie des types d'homotopie.

Cependant, il semble que, compte tenu des types d'univers et des types de fonctions dépendants, vous pouvez construire tous ces autres types "primitifs". Par exemple, le type Empty pourrait à la place être défini comme

ΠT:U.T

Je suppose que les autres types pourraient également être construits de manière similaire à la façon dont ils sont en CC pur , (c'est-à-dire simplement dériver le type de la partie inductive de la définition).

Beaucoup de ces types sont explicitement rendus redondants par les types inductifs / W qui sont introduits dans les chapitres 5 et 6. Mais les types inductifs / W semblent être une partie facultative de la théorie car il y a des questions ouvertes sur la façon dont ils interagissent avec HoTT (à au moins au moment où le livre est sorti).

Je suis donc très confus quant à la raison pour laquelle ces types supplémentaires sont présentés comme primitifs. Mon intuition est qu'une théorie fondamentale devrait être aussi minimale que possible, et redéfinir un type vide redondant comme primitif dans la théorie semble très arbitraire.

Ce choix a-t-il été fait

pour quelques raisons métathéoriques que je ne connais pas?
pour des raisons historiques, faire ressembler la théorie des types à des théories de type passées (qui n'essayaient pas nécessairement d'être fondamentales)?
pour "l'utilisabilité" des interfaces informatiques?
pour un avantage dans la recherche de preuves que je ne connais pas?

Similaire à: Spécification minimale de la théorie des types de Martin-Löf , /cs/82810/reducing-products-in-hott-to-church-scott-encodings/82891#82891

type-theory dependent-type homotopy-type-theory user833970
la source

Ils sont redondants, mais pas comme vous le suggérez. Vous devriez vous demander à quoi sert la «minimalité de fondation»? Et nous soucions-nous du but?

Andrej Bauer

Je suppose que le travail technique est minime par convention, où les choses n'ont pas besoin d'être minimes si cela est évidemment pratique ou explicitement indiqué autrement. Le livre y adhère même à d'autres endroits, comme lorsqu'il définit des types de troncature (définis par des règles, mais explicitement non minimaux). Par exemple, si je voyais les nats définis en termes de 0,1,10, le successeur et l'opération de puissance, je serais confus, mais je pourrais au moins voir pourquoi c'est pratique sur le plan de la notation. Hott est un domaine d'étude beaucoup plus complexe et je veux savoir si je manque quelque chose d'évident.

user833970

Je serais très intéressé à savoir comment ils peuvent être nocifs. Dois-je poser une nouvelle question à ce sujet?

user833970

@AndrejBauer J'aimerais aussi savoir pourquoi ils seraient nuisibles. Mon raisonnement pour croire que le langage fondamental devrait être minimal est le raisonnement derrière le rasoir d'Occam, c'est une complexité supplémentaire injustifiée. Pourquoi s'arrêter là? Pourquoi ne pas ajouter également des listes, des chaînes, des paires, des triplets, des vecteurs? Ces choix semblent arbitraires, qu'est-ce qui les justifie? Edit: Je viens de remarquer que cette question a des réponses; mais je vais laisser ce commentaire ici juste pour noter pourquoi je serais aussi intéressé par cela.

MaiaVictor

J'écrirai un article de blog.

Andrej Bauer

Réponses:

Permettez-moi d'expliquer pourquoi l'encodage suggéré du type vide ne fonctionne pas. Nous devons être explicites sur les niveaux de l'univers et ne pas les balayer sous le tapis.

Quand les gens disent "le type vide", cela peut signifier deux choses:

Un seul type qui est vide par rapport à tous les types. Un tel type a la règle d'élimination: pour chaque et le type de famille , il y a une carte . $E$ $n$ $A : E \to U_n$ $e_{n,A} : E \to A$
Une famille de types , un pour chaque niveau d'univers , tels que est "le type vide de ". Un tel type doit satisfaire , évidemment, et aussi: pour chaque type de famille , il y a une carte . $E_k$ $k$ $E_k$ $U_k$ $E_k : U_k$ $A : E_{k} \to U_k$ $e_{k,A} : E_{k} \to A$

Sans aucune réserve, lorsque les gens disent "type vide", ils attendent la première signification ci-dessus.

Comment pouvons-nous obtenir ? Un premier essai pourrait être quelque chose comme $E$ mais c'est précisément le genre de balayage sous le tapis qui crée la confusion. Nous devons noter les niveaux universels explicites. Si nous écrivons quelque chose comme

E = Π (T : U) . T

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

on obtient alors une suite de types

, un pour chaque niveau

. On peut espérer que cette séquence est du type vide dans le sens ci-dessus, mais ce n'est pas le cas, car

est dans

mais il est supposé être dans

E_{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$

Un autre essai est mais maintenant vous devez expliquer ce que " " est censé être. Vous pourriez être tenté de dire qu'il existe un type de niveaux universels, et donc

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

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

Π n

$\Pi n$

L

$L$

Vous êtes maintenant tombé dans un piège, car je vais vous demander: dans quel univers

vit-il? Et dans quel univers

vit-il? Ça ne va pas marcher.

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

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

E

$E$

L

$L$

$U$ $B : U \to U$ $\Pi (X : U) B(X)$ $U$ $U$ $\Pi (X : U) X$ $U$

Des univers imprédicatifs peuvent être arrangés. Cependant, un célèbre théorème de Thierry Coquand (si je ne me trompe pas), montre qu'avoir deux univers imprédicatifs, l'un contenu dans l'autre, conduit à une contradiction.

La morale de l'histoire est la suivante: axiomatisez directement le type vide et arrêtez de coder les choses.

Andrej Bauer
la source

C'est un raisonnement convaincant pour axiomatiser le type vide, mais je suis toujours curieux du raisonnement pour axiomatiser toutes ces choses plus lourdes.

MaiaVictor

@MaiaVictor: par opposition à quoi?

Andrej Bauer

Pardon? Je veux juste dire que vous avez justifié de manière convaincante pourquoi c'est une bonne idée d'axiomatiser le type vide en particulier. Mais OP a également posé des questions sur d'autres choses: "types d'univers, types de fonctions dépendantes, types de paires dépendantes, types de coproduits, type vide, type d'unité, type de nombre naturel et types d'identité" (qui je suppose sont également des primitives sur le système proposé sur le Livre HoTT). (Je ne vous demande évidemment pas de justifier tout cela, je manifeste simplement mon intérêt.)

MaiaVictor

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

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

@IngoBlechschmidt curieux de savoir quels types de problèmes! Ça me semble bien ...

MaiaVictor

Vous posez plusieurs questions similaires mais distinctes.

Pourquoi le livre HoTT n'utilise-t-il pas les encodages Church pour les types de données?

Les codages d'église ne fonctionnent pas dans la théorie de type Martin-Löf, pour deux raisons.

$n$ $k < n$

Deuxièmement, même si vous avez défini des types de données comme les nombres naturels avec des codages Church, pour faire des preuves avec ces types, vous avez besoin de principes d'induction pour prouver les choses à leur sujet. Pour dériver les principes d'induction des encodages de Church, vous devez utiliser un argument basé sur la paramétricité de Reynolds, et la question de savoir comment intérioriser les principes de paramétricité dans la théorie des types n'est toujours pas entièrement résolue. (L'état de l'art est Nuyts, Vezzosi et Devriese's ICFP 2017 paper Parametric Quantifiers for Dependent Type Theory - notez que c'est bien après l'écriture du livre HoTT!)
Ensuite, vous demandez pourquoi la fondation n'est pas minimale. C'est en fait l'une des caractéristiques sociologiques distinctives des fondements de la théorie des types - les théoriciens des types considèrent avoir un petit ensemble de règles comme une commodité technique, sans grande signification fondamentale. Il est de loin, beaucoup plus important d'avoir le bon ensemble de règles, plutôt que le plus petit ensemble de règles.

Nous développons des théories de types à utiliser par les mathématiciens et les programmeurs, et il est très, très important que les preuves faites dans la théorie des types soient celles que les mathématiciens et les programmeurs considèrent comme étant faites de la bonne manière. En effet, les arguments que les mathématiciens considèrent généralement comme ayant un bon style sont généralement structurés en utilisant les principes algébriques et géométriques clés du domaine d'étude. Si vous devez utiliser des encodages complexes, une grande partie de la structure est perdue ou obscurcie.

C'est pourquoi même les présentations théoriques de type de la logique classique propositionnelle donnent invariablement tous les connecteurs logiques, même si elles sont formellement équivalentes à une logique avec juste NAND. Bien sûr, tous les connecteurs booléens peuvent être encodés avec NAND, mais cet encodage obscurcit la structure de la logique.

Neel Krishnaswami
la source

Merci pour cette réponse! Je devrai lire ce document (et le vôtre) et cela pourrait avoir plus de sens. Mais, je pensais que la hiérarchie de l'univers avait été conçue pour donner l'impression que vous pouvez faire des choses prédicatives: par exemple (λA: U.λa: Aa) (ΠA: UA → A) serait désuet vers (λA: Un + 1.λa: Aa) (ΠA: Un.A → A). Je pense que c'est un choix éditorial étrange de ne pas expliquer cela, chaque livre de logique que je connais souligne plusieurs encodages plus minimaux comme CNF, DNF, NAND et ainsi de suite. Et quiconque est habitué à définir la théorie attend un encodage "naturel" des Nats, pour démontrer la théorie. Mais c'est peut-être juste mes préjugés classiques.

user833970

cela devrait être "imprédicatif" dans mon dernier commentaire

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$

Peut-être que je me méprends sur les hiérarchies des univers. Je pensais que nous ne nous soucions jamais de l'Univers spécifique dans lequel un type se trouve, seulement que les numéros d'univers peuvent être attribués lorsque nous voulons vérifier une preuve. Donc techniquement ΠT: UT est une famille de types indexés sur des univers. Tout comme l'identité polymorphe est une famille de types indexés sur des univers. Mais n'avons-nous pas le même problème avec l'identité polymorphe? J'apprécierais vraiment si vous pouviez développer les 2 dernières phrases, je ne pense pas comprendre.

user833970

Quand vous dites qu'il n'a pas les bonnes propriétés d'élimination, voulez-vous dire qu'une fois l'univers fixé, il existe des types dans les univers supérieurs qui ne peuvent pas être directement synthétisés par un terme de ΠT: Un.T?

user833970