¿Qué es en el cálculo de las construcciones?

11

Estoy mirando el cálculo de construcciones y su lugar en el Cubo Lambda .

Si entiendo correctamente, se puede pensar que cada eje del cubo agrega otra operación que involucra tipos al cálculo de tipo simple, . El primer eje agrega operadores de tipo a término, los segundos operadores de tipo a tipo y el tercer tipo dependiente, u operadores de término a tipo. El CoC tiene los tres.λ

Sin embargo, el CoC introduce un término , y establece que según las reglas de inferencia , pero de lo contrario no se utiliza. Entiendo que es para las proposiciones epónimas, pero las proposiciones lógicas no están definidas en términos de ello.PropProp:Type

¿Podría explicarme para qué sirve , dónde / cuándo aparece, y explicarlo en términos de los ejes del cubo (si es posible hacerlo)?Prop

Michael Rawson
fuente

Respuestas:

15

En la teoría de tipos tradicional de Martin-Löf no hay distinción entre tipos y proposiciones. Esto va bajo el lema "proposiciones como tipos". Pero a veces hay razones para distinguirlos. CoC hace precisamente eso.

Hay muchas variantes de CoC, pero la mayoría tendría pero no . Otra diferencia aparece cuando tenemos infinitos universos tipo y hacemos que impredecible (esto es lo que hace Coq). Concretamente, considere una variante de CoC donde tenemos e infinitos universos tipo , , con La regla de formación para

Prop:Type
Type:PropPropPropType1Type2Type3
Prop:Type1Type1:Type2Type2:Type3
tiene que explicar cómo formar cuando es una proposición o un tipo, y es una proposición o un tipo. Hay cuatro combinaciones: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)

Lo más interesante es la diferencia entre el segundo y el cuarto caso. La cuarta regla dice que si está en el universo -ésimo y está en el universo , entonces el producto está en el universo . Pero la segunda regla nos dice que no es solo "un universo más en la parte inferior", porque aterriza en tan pronto como no, no importa lo grande es. Esto no es predictivo porque nos permite definir elementos deAiB(x)jmax(i,j)Propx:AB(x)PropB(x)APropcuantificando sobre sí.Prop

Un ejemplo concreto sería versus El primer producto vive en , pero el segundo está en (y no en , a pesar de que estamos cuantificando sobre un elemento de ). En particular, esto significa que uno de los valores posibles para es mismo.

A:Type1AA
A:PropAA
Type2PropType1Type1AA:PropAA
Andrej Bauer
fuente