Qu'est-ce que

11

Je regarde le calcul des constructions et sa place dans le Lambda Cube .

Si je comprends bien, chaque axe du cube peut être considéré comme ajoutant une autre opération impliquant des types au calcul simplement typé, . Le premier axe ajoute des opérateurs de type à terme, les seconds opérateurs de type à type et le troisième typage dépendant ou opérateurs de type à terme. Le CoC a les trois.λ

Cependant, le CoC introduit un terme et indique que P r o p : T y p e par les règles d'inférence , mais n'est pas utilisé autrement. Je comprends que c'est pour les propositions éponymes, mais les propositions logiques ne sont pas définies en termes de cela.PropProp:Type

Pourriez-vous m'expliquer à quoi sert , où / quand il apparaît, et l'expliquer en termes d'axes du cube (si c'est effectivement possible)?Prop

Michael Rawson
la source

Réponses:

15

Dans la théorie traditionnelle des types de Martin-Löf, il n'y a pas de distinction entre les types et les propositions. Cela passe sous le slogan "propositions en tant que types". Mais il y a parfois des raisons de les distinguer. CoC fait précisément cela.

Prop:Type
Type:PropPropPropType1Type2Type3
Prop:Type1Type1:Type2Type2:Type3
x:AB(x)AB(x)
  1. A:Propx:AB(x):Propx:AB(x):Prop
  2. A:Typeix:AB(x):Propx:AB(x):Prop
  3. A:Propx:AB(x):Typeix:AB(x):Typei
  4. A:Typeix:AB(x):Typejx:AB(x):Typemax(i,j)

Le plus intéressant est la différence entre le deuxième et le quatrième cas. La quatrième règle dit que si est dans le ème univers et est dans le ème univers, alors le produit est dans le -ième univers. Mais la deuxième règle nous dit que n'est pas seulement "un univers de plus en bas", car atterrit dans dès que ne, peu importe la taille est. Ceci est imprédicatif car il nous permet de définir des éléments deAiB(x)jmax(i,j)Propx:AB(x)PropB(x)APropen quantifiant sur lui-même.Prop

Un exemple concret serait versus Le premier produit réside dans , mais le second est dans (et non dans , même si nous quantifions sur un élément de ). En particulier, cela signifie que l'une des valeurs possibles pour est lui-même.

A:Type1AA
A:PropAA
Type2PropType1Type1AA:PropAA
Andrej Bauer
la source