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:C:x,y:A(x=Ay)U((x:UMAC(x,x,reflx))x,y:UMAp:x=UMAyC(x,y,p)),
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 igualdadeind=UMA(C,c,x,x,reflx): ≡c(x)
minha primeira impressão de que esta última expressão nãodefinira função resultante
f:x,y:UMAp:x=UMAyC(x,y,p),
mas apenasdeclara sua propriedade.

Isso contrasta com os exemplos anteriores dos princípios de indução indUMA×B , indA+B ou indN - 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 f 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 definimosind=Af

... a função definida pela indução de caminho de c : x : A C ( x , x , refl x ) , além disso, satisfaz f ( x , x , refl x )f:x,y:Ap:x=AyC(x,y,p),
c:x:AC(x,x,reflx)
...f(x,x,reflx):≡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"? ind=A

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

Respostas:

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 1 , que parece particularmente obviamente "determinado". De acordo com o ponto 1.5 do livro Hott temos i n d 1 : Π C : 1 T y p e C ( ) Π x : 1 Pind=A1 com a equação i n d 1 ( C , c , ) = c . Será que este "definir" ou "construção" i n d 1 no sentido de que ele não deixa dúvida quanto ao que i n d 1 "faz"? Por exemplo, defina C ( x ) = N e a = 42 e considere o que poderíamos dizer sobre i n d 1 ( C , 42 ,

ind1:C:1TypeC()x:1P(x)
ind1(C,c,)=c.
ind1ind1C(x)=Na=42 para uma dada expressão e do tipo 1 . Seu primeiro pensamento pode ser que podemos reduzir isso para 42 porque " é o único elemento de 1 ". Mas, para ser bem preciso, a equação para i n d 1 é aplicável somente se mostrarmos e , que é impossível quando e é uma variável, por exemplo. Podemos tentar mexer fora deste e dizer que estamos interessados apenas em computação com termos fechados, por isso e deve ser fechado.
ind1(C,42,e)
e1421ind1eee

Não é verdade que todo termo fechado do tipo 1 é 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 e 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).e1e

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 i n d 1 , mas:1ind1

  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 i n d = A nos dirá como calcular.refl(a)ind=A

  2. 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 i n d 1 que não nos dizer como calcular em (as duas escolhas óbvias sendo "ansiosamente" e "preguiçosa").1ind1

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 i n d = C , mas sim que no entanto eu nind=C(C,c,x,x,refl(x))c(x)ind=C é "implementado", exigimos que ele satisfaça a equação. É uma questão separada se tal i n d = C pode ser obtido de uma maneira construtiva.ind=Cind=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 ( n , d )HN×{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 H é uma relação total, e seu mapa característico χ H : N × { 0 , 1 } P r o p não é fator por b o o l

H(n,d)(d=1n-th machine halts)(d=0n-th machine diverges)
HχH:N×{0,1}Propbool, 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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

fA:x,y:Ap:x=AyC(x,y,p)
x,y:Ap:x=AyAx,y
refla:a=Aa, for any a:A
preflaa:Ax=a=yC(x,x,reflx)x:A
baseC:x:AC(x,x,reflx)
CfA
fA(x,y,p):=baseC(x,x,p)
.

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

Espero que ajude!


eEE

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
refl
3

A×BA×B

pair : ABA×B
f A×Bpair

pairf:A×BCAB

f:ABC
fA×B
(ABC)(A×BC)
indA×B

f pumaEur(uma,b)ff

f(pumaEur(uma,b)) : = f uma b
EundUMA×B f pumaEur(uma,b) : = f uma b
=

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

  1. Eund

  2. Eund


=UMAx,y:UMAp:x=yCpx=y refeu(z)z

f:Πx,y:A,x=yC
f:Πz:A,C
refl(z)C

ff

f z z refl(z):=f z

A×B=A

cody
fonte