A indução de caminho é construtiva?

17

Estou lendo o livro do HoTT e tenho dificuldade em induzir caminhos.

Quando olho para o tipo na secção 1.12.1 :

{ind}_{=_{A}} : \prod_{C : \prod_{x, y : A} (x =_{A} y) \to U} ((\prod_{x : UMA} C (x, x, {refl}_{x})) \to \prod_{x, y : UMA} \prod_{p : x =_{UMA} 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),$ não tenho problema em entender o que isso significa (acabei de escrever o tipo na memória, para verificar isso).

O que eu tenho problema é com a próxima afirmação:

com a igualdade {ind}_{=_{UMA}} (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)$ minha primeira impressão de que esta última expressão nãodefinira função resultante

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

$f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$ mas apenasdeclara sua propriedade.

Isso contrasta com os exemplos anteriores dos princípios de indução $\text{ind}_{A\times B}$ , $\text{ind}_{A+B}$ ou $\text{ind}_\mathbb{N}$ - existem equações definidoras para esses elementos - na verdade, sabemos como construir a função resultante, dadas as premissas. O que está de acordo com a "construtividade" da teoria dos tipos anunciada ao longo do capítulo.

Voltando a , eu suspeitava do fato de que (parece) isso não está definido. Afirmar que o elemento simplesmente existe parecia desafinado com o restante do capítulo. E, de fato, a seção 1.12.1 parece enfatizar que minha impressão está errada e que de fato definimos $\text{ind}_{=_A}$ $f$

... a função definida pela indução de caminho de , além disso, satisfaz $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)$

Isso me deixa totalmente confuso, mas sinto que esse ponto é muito importante para todos os desenvolvimentos futuros. Então, com qual das duas leituras de devo ir? Ou, provavelmente, estou perdendo uma sutileza importante e a resposta é "nenhum"? $\text{ind}_{=_A}$

induction dependent-types homotopy-type-theory Kostya
fonte

A propósito, essa não é realmente uma pergunta específica do HoTT, mas uma questão mais geral de "tipos dependentes".

Cody

12

É uma ilusão que as regras de computação "definam" ou "construam" os objetos sobre os quais falam. Você observou corretamente que a equação para não a "define", mas falhou em observar que o mesmo também acontece em outros casos. Vamos considerar o princípio de indução para o tipo de unidade , que parece particularmente obviamente "determinado". De acordo com o ponto 1.5 do livro Hott temos $\mathrm{ind}_{=_A}$ $1$ com a equação Será que este "definir" ou "construção" no sentido de que ele não deixa dúvida quanto ao que "faz"? Por exemplo, defina e e considere o que poderíamos dizer sobre

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

{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 uma dada expressão

do tipo

. Seu primeiro pensamento pode ser que podemos reduzir isso para

porque "

é o único elemento de

". Mas, para ser bem preciso, a equação para

é aplicável somente se mostrarmos

, que é impossível quando

é uma variável, por exemplo. Podemos tentar mexer fora deste e dizer que estamos interessados apenas em computação com termos fechados, por isso

deve ser fechado.

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

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

e

$e$

1

$1$

42

$42$

⋆

$\star$

1

$1$

{i n d}_{1}

$\mathrm{ind}_1$

e \equiv ⋆

$e \equiv \star$

e

$e$

e

$e$

Não é verdade que todo termo fechado do tipo é julgadamente igual a ? Isso depende de detalhes desagradáveis e provas complicadas de normalização, na verdade. No caso do HoTT, a resposta é "não" porque pode conter instâncias do Axioma da Univalência, e não está claro o que fazer com isso (este é o problema em aberto no HoTT). $e$ $1$ $\star$ $e$

Nós podemos contornar o problema com univalance considerando uma versão da teoria tipo que não têm boas propriedades de modo que cada termo fechado do tipo é judgmentally igual a . Nesse caso, é justo dizer que nós não sabe como calcular com , mas: $1$ $\star$ $\mathrm{ind}_1$

O mesmo vale para o tipo de identidade, porque todo termo fechado de um tipo de identidade será julgadoramente igual a alguns e, portanto, a equação para nos dirá como calcular. $\mathrm{refl}(a)$ $\mathrm{ind}_{=_A}$
Só porque sabemos calcular com termos fechados de um tipo, isso não significa que realmente definimos algo, porque existe mais em um tipo do que em termos fechados , como tentei explicar uma vez.

Por exemplo, a teoria do tipo Martin-Löf (sem os tipos de identidade) pode ser interpretada teoricamente no domínio de forma que contenha dois elementos e , em que corresponda a e à não terminação. Infelizmente, como não há como escrever uma expressão não-terminante na teoria dos tipos, não pode ser nomeado. Consequentemente, a equação para que não nos dizer como calcular em (as duas escolhas óbvias sendo "ansiosamente" e "preguiçosa"). $1$ $\bot$ $\top$ $\top$ $\star$ $\bot$ $\bot$ $\mathrm{ind}_1$ $\bot$

Em termos de engenharia de software, eu diria que temos uma confusão entre especificação e implementação . Os axiomas HoTT para os tipos de identidade são uma especificação . A equação não está nos dizendo como calcular ou como construir , mas sim que no entanto $\mathrm{ind}_{=_C}(C,c,x,x,\mathrm{refl}(x)) \equiv c(x)$ $\mathrm{ind}_{=_C}$ é "implementado", exigimos que ele satisfaça a equação. É uma questão separada se tal pode ser obtido de uma maneira construtiva. $\mathrm{ind}_{=_C}$ $\mathrm{ind}_{=_C}$

Por fim, estou um pouco cansado de como você usa a palavra "construtivo". Parece que você acha que "construtivo" é o mesmo que "definido". Sob essa interpretação, o oráculo Halting é construtivo, porque seu comportamento é definido pelo requisito que lhe impomos (a saber, que ele produz 1 ou 0 de acordo com a parada da máquina). É perfeitamente possível descrever objetos que existem apenas em um ambiente não construtivo. Por outro lado, é perfeitamente possível falar construtivamente sobre propriedades e outras coisas que não podem realmente ser computadas. Aqui está um: a relação definida por $H \subseteq \mathbb{N} \times \{0,1\}$ é construtiva, isto é, não há nada de errado com esta definição de um ponto de vista construtivo. Acontece que, construtivamente, não se pode mostrar que é uma relação total, e seu mapa característico não é fator por

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}$ , portanto, não podemos "calcular" seus valores.

Adendo: O título da sua pergunta é "A indução de caminho é construtiva?" Depois de esclarecer a diferença entre "construtivo" e "definido", podemos responder à pergunta. Sim, a indução de caminho é conhecida por ser construtiva em certos casos:

Se restringirmos a teoria de tipos sem Univalência, para que possamos mostrar forte normalização, a indução de caminho e tudo o mais é construtivo, porque existem algoritmos que executam o procedimento de normalização.
Existem modelos de realizabilidade da teoria dos tipos, que explicam como todo termo fechado na teoria dos tipos corresponde a uma máquina de Turing. No entanto, esses modelos satisfazem o Axiom K de Streicher, que descarta a univalência.
Há uma tradução da teoria dos tipos (novamente sem univalência) na teoria dos conjuntos construtivos CZF. Mais uma vez, isso valida o axioma K. de Streicher.
Existe um modelo grupóide dentro dos modelos de realização que nos permite interpretar a teoria dos tipos sem o K. de Streicher. Este é um trabalho preliminar de Steve Awodey e de mim.

Nós realmente precisamos resolver o status construtivo da Univalência.

Andrej Bauer
fonte

Eu acredito que esta resposta é agora (parcialmente) fora da data

WorldSEnder

De fato, nesse meio tempo, a teoria do tipo cúbico deu uma resposta positiva: existe um modelo construtivo da teoria do tipo Univalente.

Andrej Bauer

7

Eu não sou uma pessoa do HoTT, mas jogarei meus dois 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)$

x, y : A

$x,y : A$

p : x =_{A} y

$p : x =_A y$

A

$A$

x, y

$x,y$

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

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

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

$p \equiv \mathsf{refl}_a$

a : A

$a : A$

x = a = y

$x=a=y$

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

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

x : A

$x : A$

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)$

C

$C$

f_{A}

$f_A$

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

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

Livrar-se dos subscritos leva à definição indutiva geral.

Espero que ajude!

$e$ $E$ $E$

Musa Al-hassy
fonte

1

Talvez você possa entender um pouco, ou pelo menos se preocupar com suas intuições atuais, consultando math.andrej.com/2013/08/28/the-elements-of-an-inductive-type onde tento explicar por que é prejudicial pensar que os termos fechados de um tipo são tudo o que existe para um tipo.

Andrej Bauer 30/07

2

r e f l

$\mathsf{refl}$

3

$A\times B$ $A\times B$

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

$\mathrm{pair}\ :\ A\rightarrow B\rightarrow A\times B$

f

$f$

A \times B

$A\times B$ $\mathrm{pair}$

$\mathrm{pair}$ $f:A\times B\rightarrow C$ $A$ $B$

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

$f':A\rightarrow B\rightarrow C$

f

$f$

A \times B

$A\times B$

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

$(A\rightarrow B\rightarrow C)\rightarrow(A\times B\rightarrow C)$

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

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

$f$ $\mathrm{pair}(a,b)$ $f$ $f'$

f (p uma Eu r (uma, b)) : = f^{'} uma b

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

{Eu n d}_{UMA \times B} f^{'} p uma Eu r (uma, b) : = f^{'} uma b

$\mathrm{ind}_{A\times B}\ f'\ \mathrm{pair}(a,b)\ :=\ f'\ a\ b$

=

$=$

Então você vê que a definição de um eliminador para o tipo indutivo com determinados construtores vem em duas etapas:

$\mathrm{ind}$
$\mathrm{ind}$

$=_A$ $x,y:A$ $p:x=y$ $C$ $p$ $x=y$ $\mathrm{refl}(z)$ $z$

f : Π x, y : A, x = y \to C

$f:\Pi x, y:A, x=y\rightarrow C$

f^{'} : Π z : A, C

$f':\Pi z:A, C$

r e f l (z)

$\mathrm{refl}(z)$

C

$C$

$f$ $f'$

f z z r e f l (z) := f^{'} z

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

$A\times B$ $=_A$

cody
fonte

A indução de caminho é construtiva?

Respostas: