Coq pode expressar sua própria metateoria?

7

Estou aprendendo sobre metateoria da linguagem e sistemas de tipos e estou usando coq para formalizar meu estudo. Uma das coisas que eu gostaria de fazer é examinar os sistemas de tipos que incluem tipos dependentes , o que eu entendo estar muito envolvido: poder confiar no coq seria inestimável.

Como esse recurso do sistema de tipos (e outros mais simples) aproxima o poder expressivo do meu sistema estudado do coq, eu me preocupo em encontrar um problema de inicialização que talvez não se revele muito mais tarde. Talvez alguém aqui possa resolver meus medos antes de eu partir.

Coq pode expressar sua própria metateoria? Caso contrário, ele ainda pode expressar sistemas mais simples que incluem formas comuns de digitação dependente?

phs
fonte

Respostas:

3

É possível formalizar a lógica da Coq dentro da Coq, mas apenas subconjuntos da lógica foram formalizados ainda. Contribuições relevantes são CoqInCoq , PTS , PTSATR e PTSF .

Rui Baptista
fonte
É possível formalizar toda a lógica da Coq na Coq, e não apenas um subconjunto (possivelmente um subconjunto grande o suficiente para muitos propósitos práticos)? O que exatamente você inclui em "formalizar a lógica da Coq"?
Gilles 'SO- stop be evil' -
11
Formalizar a lógica de Coq provavelmente significaria formalizar Cálculo de Construções Indutivas. Eu também estaria interessado em quais são os principais obstáculos para formalizar toda a CiC.
bellpeace
11
Penso que a única parte do Coq que ainda não foi formalizada é o mecanismo que introduz definições (co) indutivas e (co) recursivas. Tendo Gödel em mente, deve ser possível provar, por exemplo, que não ter um verificador de positividade pode introduzir inconsistências e que o verificador de positividade está bem implementado. Sem isso, Coq é praticamente apenas ECC, que já foi formalizado, e as definições precisam ser introduzidas como axiomas ou mantidas como hipóteses. Listei apenas algumas formalizações mais fáceis de encontrar.
Rui Baptista