¿Es la inducción de ruta constructiva?

17

Estoy leyendo el libro de HoTT y tengo dificultades con la inducción del camino.

Cuando miro el tipo en la sección 1.12.1 :

{ind}_{=_{A}} : \prod_{C : \prod_{x, y : A} (x =_{A} y) \to U} ((\prod_{x : A} C (x, x, {refl}_{x})) \to \prod_{x, y : A} \prod_{p : x =_{A} y} C (x, y, p)),

$\text{ind}_{=_A}:\prod_{C:\prod\limits_{x,y:A}(x=_Ay)\to \mathcal{U}} \left( \left(\prod_{x:A}C(x,x,\text{refl}_x)\right) \to \prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p) \right),$ no tengo problemas para entender lo que eso significa (acabo de escribir el tipo de memoria, para comprobarlo).

Con lo que tengo problemas es con la siguiente declaración:
mi primera impresión fue que esta última expresión nodefinela función resultante pero soloestablece su propiedad.

with the equality {ind}_{=_{A}} (C, c, x, x, {refl}_{x}) :\equiv c (x)

$\text{with the equality}\quad \text{ind}_{=_A}(C,c,x,x,\text{refl}_x):\equiv c(x)$

f : \prod_{x, y : A} \prod_{p : x =_{A} y} C (x, y, p),

$f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$

Esto contrasta con los ejemplos anteriores de los principios de inducción , o - existen ecuaciones definitorias para esos elementos - en realidad sabemos cómo construir la función resultante, dadas las premisas. Lo cual está de acuerdo con la "constructividad" de la teoría de tipos anunciada en todo el capítulo. $\text{ind}_{A\times B}$ $\text{ind}_{A+B}$ $\text{ind}_\mathbb{N}$

Volviendo a , sospechaba que (parece) que no está definido. Afirmar que el elemento simplemente existe parece estar fuera de sintonía con el resto del capítulo. Y, de hecho, la sección 1.12.1 parece enfatizar que mi impresión es incorrecta y de hecho hemos definido $\text{ind}_{=_A}$ $f$

... la función definida por la inducción de ruta de , que además satisface $f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$
$c:\prod_{x:A}C(x,x,\text{refl}_x)$
... $f(x,x,\text{refl}_x):\equiv c(x)$

Eso me deja completamente confundido, pero tengo la sensación de que este punto es muy importante para todos los desarrollos posteriores. Entonces, ¿con cuál de las dos lecturas para debería ir? ¿O, probablemente, me falta alguna sutileza importante y la respuesta es "ninguna"? $\text{ind}_{=_A}$

induction dependent-types homotopy-type-theory Kostya
fuente

Por cierto, esta no es realmente una pregunta específica de HoTT, sino una pregunta más general de "tipos dependientes".

cody

12

Es una ilusión que las reglas de cálculo "definen" o "construyen" los objetos de los que hablan. Usted observó correctamente que la ecuación para no la "define", pero no pudo observar que lo mismo es cierto en otros casos también. Consideremos el principio de inducción para la unidad tipo , que parece particularmente "determinado". De acuerdo con la Sección 1.5 del libro HoTT, tenemos $\mathrm{ind}_{=_A}$ $1$ con la ecuación

{i n d}_{1} : \prod_{C : 1 \to T y p e} C (⋆) \to \prod_{x : 1} P (x)

$\mathrm{ind}_1 : \prod_{C : 1 \to \mathtt{Type}} C(\star) \to \prod_{x : 1} P(x)$

¿Esta "definir" o "constructo"

en el sentido de que no deja ninguna duda en cuanto a lo

"hace"? Por ejemplo, establezca

y

, y considere lo que podríamos decir sobre

{i n d}_{1} (C, c, ⋆) = c .

$\mathrm{ind}_1 (C, c, \star) = c.$

{i n d}_{1}

$\mathrm{ind}_1$

{i n d}_{1}

$\mathrm{ind}_1$

C (x) = N

$C(x) = \mathbb{N}$

a = 42

$a = 42$

para una expresión dada

de tipo

{i n d}_{1} (C, 42, e)

$\mathrm{ind}_1(C, 42, e)$

e

$e$

1

$1$ . Su primer pensamiento podría ser que podemos reducir esto a

porque "

es el único elemento de

". Pero para ser bastante precisos, la ecuación para

es aplicable solo si mostramos

, que es imposible cuando

es una variable, por ejemplo. Podemos tratar de evitar esto y decir que solo estamos interesados en el cálculo con términos cerrados, por lo que

debería estar cerrado.

42

$42$

⋆

$\star$

1

$1$

{i n d}_{1}

$\mathrm{ind}_1$

e \equiv ⋆

$e \equiv \star$

e

$e$

e

$e$

¿No es el caso de que cada término cerrado de tipo es juiciosamente igual a ? Eso depende de detalles desagradables y pruebas complicadas de normalización, en realidad. En el caso de HoTT, la respuesta es "no" porque podría contener instancias del Axioma de Univalencia, y no está claro qué hacer al respecto (este es el problema abierto en HoTT). $e$ $1$ $\star$ $e$

Podemos eludir el problema con univalance considerando una versión de la teoría tipo que no tiene buenas propiedades de manera que cada término cerrado de tipo es igual a judgmentally . En ese caso, es justo decir que sí sabemos cómo calcular con , pero: $1$ $\star$ $\mathrm{ind}_1$

Lo mismo se aplicará al tipo de identidad, ya que cada término cerrado de un tipo de identidad será igual a algunos , y entonces la ecuación para nos dirá cómo calcular. $\mathrm{refl}(a)$ $\mathrm{ind}_{=_A}$
El hecho de que sepamos cómo calcular con términos cerrados de un tipo, no significa que hayamos definido realmente algo porque hay más de un tipo que sus términos cerrados , como intenté explicar una vez.

Por ejemplo, la teoría de tipos de Martin-Löf (sin los tipos de identidad) se puede interpretar teóricamente en el dominio de tal manera que contenga dos elementos y , donde corresponde a y a la no terminación. Por desgracia, dado que no hay forma de escribir una expresión sin terminación en la teoría de tipos, no se puede nombrar . En consecuencia, la ecuación para no no nos dice cómo calcular el (las dos opciones obvias ser "entusiasmo" y "pereza"). $1$ $\bot$ $\top$ $\top$ $\star$ $\bot$ $\bot$ $\mathrm{ind}_1$ $\bot$

En términos de ingeniería de software, diría que tenemos una confusión entre la especificación y la implementación . Los axiomas HoTT para los tipos de identidad son una especificación . La ecuación no nos dice cómo calcular o cómo construir $\mathrm{ind}_{=_C}(C,c,x,x,\mathrm{refl}(x)) \equiv c(x)$ $\mathrm{ind}_{=_C}$ , sino más bien que sin embargo está "implementado", requerimos que satisfaga la ecuación. Es una pregunta separada si tal se puede obtener de manera constructiva. $\mathrm{ind}_{=_C}$ $\mathrm{ind}_{=_C}$

Por último, estoy un poco cansado de cómo usas la palabra "constructivo". Parece que piensas que "constructivo" es lo mismo que "definido". Según esa interpretación, el oráculo de detención es constructivo, porque su comportamiento se define por el requisito que le imponemos (es decir, que genera 1 o 0 según si la máquina dada se detiene). Es perfectamente posible describir objetos que solo existen en un entorno no constructivo. Por el contrario, es perfectamente posible hablar de manera constructiva sobre propiedades y otras cosas que en realidad no se pueden calcular. Aquí hay uno: la relación definida por $H \subseteq \mathbb{N} \times \{0,1\}$ es constructiva, es decir, no hay nada de malo en esta definición desde un punto de vista constructivo. Sucede que de manera constructiva no se puede demostrar que es una relación total, y su mapa característico no factoriza a través de

H (n, d) ⟺ (d = 1 \Rightarrow n -th machine halts) \land (d = 0 \Rightarrow n -th machine diverges)

$H(n,d) \iff (d = 1 \Rightarrow \text{$n$-th machine halts}) \land (d = 0 \Rightarrow \text{$n$-th machine diverges})$

H

$H$

χ_{H} : N \times {0, 1} \to P r o p

$\chi_H : \mathbb{N} \times \{0,1\} \to \mathsf{Prop}$

b o o l

$\mathtt{bool}$ , por lo que no podemos "calcular" sus valores.

Anexo: El título de su pregunta es "¿Es la inducción de ruta constructiva?" Después de haber aclarado la diferencia entre "constructivo" y "definido", podemos responder la pregunta. Sí, se sabe que la inducción de ruta es constructiva en ciertos casos:

Si nos limitamos a la teoría de tipos sin Univalencia para que podamos mostrar una fuerte normalización, entonces la inducción de ruta y todo lo demás es constructivo porque hay algoritmos que realizan el procedimiento de normalización.
Existen modelos de realizabilidad de la teoría de tipos, que explican cómo cada término cerrado en la teoría de tipos corresponde a una máquina de Turing. Sin embargo, estos modelos satisfacen el Axioma K de Streicher, que descarta la Univalencia.
Hay una traducción de la teoría de tipos (nuevamente sin Univalencia) a la teoría de conjuntos constructiva CZF. Una vez más, esto valida el axioma K. de Streicher.
Hay un modelo de grupo dentro de los modelos de realizabilidad que nos permite interpretar la teoría de tipos sin Streicher's K. Este es un trabajo preliminar de Steve Awodey y yo.

Realmente necesitamos resolver el estado constructivo de la Univalencia.

Andrej Bauer
fuente

Creo que esta respuesta está ahora (parcialmente) desactualizada

WorldSEnder

De hecho, mientras tanto, la teoría del tipo cúbico dio una respuesta positiva: hay un modelo constructivo de la teoría del tipo univalente.

Andrej Bauer el

7

No soy una persona de HoTT, pero arrojaré mis dos centavos.

f_{A} : \prod_{x, y : A} \prod_{p : x =_{A} y} C (x, y, p)

$f_A : \prod_{x,y : A}\prod_{p : x =_A y} C(x,y,p)$ How would we do this? Well, suppose we're given any

x, y : A

$x,y : A$ and a proof of their equality

p : x =_{A} y

$p : x =_A y$ . Since I know nothing about the arbitrary type

A

$A$ , I know nothing about the `structure' of

x, y

$x,y$ . However, I know something about the specific equality type: it has a single constructor,

{r e f l}_{a} : a =_{A} a, for any a : A

$\mathsf{refl}_a : a =_A a, \text{ for any } a : A$ Hence,

p \equiv {r e f l}_{a}

$p \equiv \mathsf{refl}_a$ for some

a : A

$a : A$ , but this would force

x = a = y

$x=a=y$ . Hence, if we had an element of

C (x, x, {r e f l}_{x})

$C(x,x,\mathsf{refl}_x)$ for any

x : A

$x : A$ ; ie if we had a function

b a s e_{C} : \prod_{x : A} C (x, x, {r e f l}_{x})

$base_C : \prod_{x:A}C(x,x,\mathsf{refl}_x)$ (for our specific

C

$C$ ), then our function

f_{A}

$f_A$ can be defined as follows:

f_{A} (x, y, p) := b a s e_{C} (x, x, p)

$f_A(x,y,p) := base_C(x,x,p)$ .

Getting rid of the subscripts leads to the general inductive definition.

Hope that helps!

PS. I'm no HoTT guy, so I'm assuming `Axiom K'. More precisely, I'm assuming that an element $e$ of type $E$ must be the result of repeated applications of constructor of $E$ . Hasta donde sé, HoTT, probablemente el capítulo 2 en adelante, desecha esta noción ... y eso no tiene absolutamente ningún sentido para mí.

Musa Al-hassy
fuente

1

Quizás pueda entenderlo, o al menos preocuparse por sus intuiciones actuales al consultar math.andrej.com/2013/08/28/the-elements-of-an-inductive-type donde trato de explicar por qué Es perjudicial pensar que los términos cerrados de un tipo son todo lo que hay para un tipo.

Andrej Bauer

2

By the way, you need not asssume Axiom K. For your answer to make sense, you need to know that every closed term of an identity type normalizes to

r e f l

$\mathsf{refl}$ . This has nothing to do with Axiom K, as such a normalization property does not prove axiom K, nor does it follow from axiom K.

Andrej Bauer

3

Soy un tipo aficionado de HoTT, así que intentaré complementar la ya excelente respuesta de Moisés. Déjame tomar el tipo $A\times B$ as an example. The basic principle of constructive type theory, as outlined by Martin-Löf, is that *every element of $A\times B$ is described as being in the image of the constructor:

p a i r : A \to B \to A \times B

$\mathrm{pair}\ :\ A\rightarrow B\rightarrow A\times B$ This philosophy allows us to define elimination: to build a function

f

$f$ out of

A \times B

$A\times B$ , it suffices to describe its action on the image of $\mathrm{pair}$ .

But since $\mathrm{pair}$ is a constructor (and so is in particular injective), this means exactly that to build a function $f:A\times B\rightarrow C$ , it suffices to describe it's action on a pair of elements in $A$ and $B$ , so

f^{'} : A \to B \to C

$f':A\rightarrow B\rightarrow C$ is sufficient to describe such an

f

$f$ . In conclusion, there is a canonical way to define functions out of

A \times B

$A\times B$ , and this can be encapsulated in the type

(A \to B \to C) \to (A \times B \to C)

$(A\rightarrow B\rightarrow C)\rightarrow(A\times B\rightarrow C)$ but this is exactly the type of

{i n d}_{A \times B}

$\mathrm{ind}_{A\times B}$ .

But this is only half of the story: what happens if this newly constructed $f$ is applied to a given $\mathrm{pair}(a,b)$ ? Well then $f$ should agree with its defining function $f'$ , i.e.

F (pag un yo r (un, si)) : = F^{'} un si

$f(\mathrm{pair}(a,b))\ :=\ f'\ a\ b$ es decir

{yo norte re}_{UN \times si} F^{'} pag un yo r (un, si) : = F^{'} un si

$\mathrm{ind}_{A\times B}\ f'\ \mathrm{pair}(a,b)\ :=\ f'\ a\ b$ y esto debería tener definición (o computacionalmente ), lo que significa que los dos deberían ser completamente intercambiables en todas las situaciones (que es muy diferente de la

=

$=$ en HoTT).

Entonces verá que la definición de un eliminador para el tipo inductivo con constructores dados viene en 2 pasos:

Un principio de existencia , que describe el tipo de $\mathrm{ind}$ .
a coherence principle which defines the computational behavior of $\mathrm{ind}$ . In category theory, this would correspond to uniqueness of the eliminator in some sense.

Let me argue that this is the same for the $=_A$ type. We want to build, given $x,y:A$ and $p:x=y$ , an element of $C$ (we're forgetting the dependencies for simplification). To do that, we need to assume that $p$ was built using a constructor for the type $x=y$ , which can only be $\mathrm{refl}(z)$ for some $z$ . This means that to give a function

F : Π X, y : UN, X = y \to C

$f:\Pi x, y:A, x=y\rightarrow C$ es suficiente para dar una función

F^{'} : Π z : UN, C

$f':\Pi z:A, C$ que se define para

r e f l (z)

$\mathrm{refl}(z)$ (de nuevo, olvidando las dependencias en

C

$C$ )

Ahora, ¿qué dice el principio de coherencia? Bueno, simplemente que si se aplica a un constructor conocido, $f$ debería comportarse como $f'$ , lo que significa

F z z r mi F l (z) : = F^{'} z

$f\ z\ z\ \mathrm{refl}(z):= f'\ z$

¡Pero eso es exactamente lo que tienes arriba! El mismo principio que nos dio la existencia y coherencia para el eliminador de $A\times B$ nos da la existencia y coherencia para el eliminador de $=_A$ .

cody
fuente

¿Es la inducción de ruta constructiva?

Respuestas: