Igualdade de provas decidíveis?

Quero saber se a decidibilidade da igualdade de duas provas decidíveis da mesma proposição pode ser comprovada sem axiomas adicionais em Cálculo de construções indutivas.

Especificamente, quero saber se isso é verdade sem axiomas adicionais no Coq.

\forall P : Prop, P \lor \neg P \Rightarrow (\forall p_{1} : P, \forall p_{2} : P, {p_{1} = p_{2}} \lor {p_{1} \neq p_{2}})

$\forall P: \texttt{Prop}, P \vee \neg P \Rightarrow (\forall p_1 : P, \forall p_2: P, \{p_1 = p_2\} \vee \{p_1 \neq p_2\})$

Obrigado!

Editado para corrigir o erro: Edite 2 para tornar Propmais explícito

coq constructive-mathematics calculus-of-constructions Adam Barak
fonte

O que você escreveu não faz sentido. Se é uma proposição, então é uma prova e você não pode formar . Você quis dizer que sua hipótese é vez de , ou seja, " é decidível"?

P

$P$

p : P

$p : P$

p \lor \neg p

$p \lor \lnot p$

P \lor \neg P

$P \lor \lnot P$

p \lor \neg p

$p \lor \lnot p$

P

$P$

Andrej Bauer

Desculpe, eu quis dizer a hipótese " é decidível", ou seja,

P

$P$

P \lor \neg P

$P \vee \neg P$

Adam Barak

Considere como , e a declaração é falsa, pois você pode habitar facilmente com , e a equivalência de funções é obviamente indecidível. Existem outras condições em você tem em mente?

P

$P$

N \to N

$\mathbb{N} \to \mathbb{N}$

(N \to N) \lor \neg (N \to N)

$(\mathbb{N} \to \mathbb{N}) \vee \lnot(\mathbb{N} \to \mathbb{N})$

i n l (λ x . x)

$\mathsf{inl}(\lambda x.\;x)$

P

$P$

Neel Krishnaswami

P deve ser uma proposição. (Na verdade, no meu desenvolvimento, eu já uso a extensionalidade funcional, de modo que a declaração ainda pode ser válida para mim, mas vamos ignorar a extensionalidade funcional / proposicional por enquanto).

11134 Adam Barak

A extensionalidade da função não implica que a equivalência da função seja decidível ... E a resposta de Neel resolve o caso geral: se P é um tipo infinito (habitado) (que inclui alguns tipos de proposições se nenhum axioma extra for incluído), a implicação falhará a espera por .

P \to P

$P\rightarrow P$

C4:

Como Neel aponta, se você trabalha sob as "proposições são tipos", pode facilmente criar um tipo cuja igualdade não possa ser mostrada decidível (mas é claro que é consistente assumir que todos os tipos têm igualdade decidível), como . $\mathbb{N} \to \mathbb{N}$

Se entendermos "proposição" como um tipo de tipo mais restrito, a resposta dependerá do que exatamente queremos dizer. Se você está trabalhando no cálculo de construções de um Proptipo, ainda não pode mostrar que proposições decidíveis têm igualdade decidível. Isso ocorre porque, no cálculo das construções, é consistente equiparar-se Propa um universo de tipo relevante para prova, portanto, pelo que você sabe, Proppode conter algo como . Isso também implica que você não pode provar seu teorema para a noção de Coq de . $\mathbb{N} \to \mathbb{N}$ Prop

Mas, em qualquer caso, a melhor resposta vem da teoria dos tipos de homotopia. Uma proposição é um tipo que satisfaz Ou seja, uma proposição tem no máximo um elemento (como deveria se fosse para ser entendido como um valor de verdade irrelevante para a prova). Nesse caso, a resposta é obviamente positiva, porque a definição de proposição implica imediatamente que sua igualdade é decidível. $P$

\forall x, y : P . x = y .

$\forall x, y : P \,.\, x = y.$

Estou curioso para saber o que você quer dizer com "proposição".

Andrej Bauer
fonte

Como você teria dentro ? Obrigado!

N \to N

$\mathbb{N} \rightarrow \mathbb{N}$ Prop

Adam Barak

Não há nada no cálculo da construção que impeça , existe?

P r o p = T y p e

$\mathtt{Prop} = \mathtt{Type}$

Andrej Bauer

A confusão aqui é sobre o que se entende por "sistema coq". Se for "o cálculo das construções", então . Se o "Cálculo de construções indutivas com 1 universo impredicativo" mais preciso, então não sentido sem as anotações no nível do universo. Até onde eu sei, é um axioma consistente (embora inconsistente com o EM por motivos sutis).

P r o p = S e t = T y p e

$\mathtt{Prop=Set=Type}$

T y p e

$\mathtt{Type}$

T y p e_{1} = P r o p

$\mathtt{Type_1=Prop}$

Cody

Claro, temos que um índice em . O ponto para @AdamBarak entender é o seguinte: como não leva a nenhuma contradição no Coq, podemos mostrar que algo não pode ser feito no Coq, mostrando que isso levaria a uma contradição se também tivéssemos .

T y p e

$\mathtt{Type}$

P r o p = {T y p e}_{1}

$\mathtt{Prop} = \mathtt{Type}_1$

P r o p = {T y p e}_{1}

$\mathtt{Prop} = \mathtt{Type}_1$

Andrej Bauer

Ainda não está certo, porque em Coq não podemos mostrar que a equivalência funcional é indecidível. A afirmação "igualdade em é decidível" é o que Martin Escardo chama de tabu construtivo: não pode ser provado nem refutado no Coq. Portanto, o argumento correto é: se então é uma proposição e a declaração "igualdade em é decidível "não é comprovável. (Considerando que você disse: e a declaração "igualdade em é decidível" é falsa).

N \to N

$\mathbb{N} \to \mathbb{N}$

P r o p = {T y p e}_{1}

$\mathtt{Prop} = \mathtt{Type}_1$

N \to N

$\mathbb{N} \to \mathbb{N}$

N \to N

$\mathbb{N} \to \mathbb{N}$

N \to N

$\mathbb{N} \to \mathbb{N}$

Andrej Bauer 12/12

Igualdade de provas decidíveis?

Respostas: