Onde está a prova de que Coq + Excluded Middle é consistente

21

Eu já vi (e ouvi) afirmar que é seguro acrescentar o axioma clássico do meio excluído ao Coq, mas não consigo encontrar um documento que apoie essa afirmação. Os artigos que vejo listados no wiki da Coq sobre o meio excluído estão mostrando inconsistência com o conjunto impredicativo.

De fato, parece que Coquand afirma que adicionar Meio Excluído (um habitante de ) é inconsistente para o CoC na seção 4.5.3 de sua descrição (PDF) da metateoria do CoC. No entanto, esta seção é um pouco obscura para mim, então eu posso muito bem interpretá-lo mal.A+¬A

Mark Reitblatt
fonte
6
Esse tipo de coisa deve ser solicitado na lista de correspondência coq.
Andrej Bauer
11
Duh. Por alguma razão, esse local óbvio me passou pela cabeça. Quando você tem um martelo ...
Mark Reitblatt
9
Fico feliz que as pessoas pensam de postagem aqui em primeiro lugar, mesmo para questões teóricas B que não recebem atenção suficiente :)
Suresh Venkat

Respostas:

11

Na verdade, na seção 4.5.3, ele não diz exatamente que a impredicatividade do EM + é inconsistente. Ele diz que, quando você assume, o modelo deve se tornar degeneradamente irrelevante (a interpretação de todos os tipos, exceto Prop, pode ter no máximo um elemento). Andy Pitts descreve um fenômeno semelhante "Tipos de energia não triviais não podem ser subtipos de tipos polimórficos" .

Para versões predicativas da teoria dos tipos, provavelmente é mais fácil fazer apenas a prova de consistência do que procurar no Google - a estratificação do universo fornece tudo o que você precisa para o modelo teórico de conjunto de tipos simples (ou seja, tipos são conjuntos, termos são mapas) para dar certo. Apenas observe que os conjuntos são fechados com somas e produtos indexados e se familiarizam com o axioma da substituição ao interpretar universos. É uma prática acadêmica ruim, é claro, mas ainda vale a pena fazer a prova por si mesmo.

Neel Krishnaswami
fonte
Obrigado. E por Prop impredicative?
Re: Reitblatt
2
2