Teoria do tipo intuicionista “mínima”?

18

Estou surpreso que as pessoas continuem adicionando novos tipos nas teorias de tipos, mas ninguém parece mencionar uma teoria mínima (ou não a consigo encontrar). Eu pensei que os matemáticos amam coisas mínimas, não amam?

Se bem entendi, em uma teoria de tipos com impredicative Prop, a abstração λ e os tipos suff são suficientes. Ao dizer o suficiente, quero dizer que poderia ser usado como lógica intuicionista. Outros tipos podem ser definidos da seguinte maneira:

=defΠα:Prop.α¬A=defAAB=defΠC:Prop.(ABC)CAB=defΠC:Prop.(AC)(BC)Cx:S(P(x))=defΠα:Prop.(Πx:S.Pxα)α

Minha primeira pergunta é: eles ( λ, Π) são realmente suficientes? Minha segunda pergunta é: o que precisamos minimamente se não tivermos um impredicative Prop, como no MLTT? No MLTT, Church / Scott / qualquer codificação não funciona.

Editar: relacionado

盛安安
fonte
2
O que seria um tipo "mínimo"? que propriedades teria, na sua opinião?
Raphael
Ser capaz de provar o que Coq pode provar? Eu admito que não têm uma resposta clara em minha mente D:
盛安安
Mas ouvi dizer que Coq adicionou polimorfismo no universo, para o qual o sistema mínimo que propus obviamente não funciona. Que tal "Ser capaz de provar o que o MLTT (no sentido normal) pode provar."? Eu pensei que tipos W podem ser simulados? Embora eu não tenha pensado nisso em geral.
盛安安
Espere, parece que com impredicative Propnem precisamos de igualdade.
盛安安

Respostas:

12

Para elaborar os esclarecimentos de gallais, uma teoria de tipos com Prop impredicativo e tipos dependentes pode ser vista como um subsistema do cálculo de construções, tipicamente próximo à teoria de tipos de Church . A relação entre a teoria de tipos da Igreja e o CdC não é tão simples, mas foi explorada, principalmente pelo excelente artigo de Geuvers .

Para a maioria dos propósitos, porém, os sistemas podem ser vistos como equivalentes. Então, de fato, você pode conviver com muito pouco, especialmente se você não estiver interessado em lógica clássica, a única coisa que você realmente precisa é de um axioma do infinito : não é possível no CoC que qualquer tipo tenha mais de um elemento! Mas com apenas um axioma expressando que algum tipo é infinito, digamos um tipo de números naturais com o princípio de indução e o axioma , você pode ir muito longe: a maioria da matemática de graduação pode ser formalizada nesse sistema (tipo, é difícil fazer algumas coisas sem o meio excluído).01

Sem Prop impredicative, você precisa de um pouco mais de trabalho. Conforme observado nos comentários, um sistema extensional (um sistema com extensionalidade funcional na relação de igualdade) pode obter com apenas e Π -Tipos, B O O G , os vazios e unidade tipos e , e W-tipos. No cenário intensional, isso não é possível: você precisa de muito mais indutivos. Note-se que para construir W-tipos úteis, você precisa ser capaz de construir tipos por eliminação sobre B o o l assim:ΣΠBoolBool

if b then  else 

Para fazer meta-matemática, você provavelmente precisará de pelo menos um universo (por exemplo, para construir um modelo de aritmética de Heyting).

Tudo isso parece muito, e é tentador procurar um sistema mais simples que não tenha a impredicatividade louca do CoC, mas ainda é relativamente fácil de escrever em algumas regras. Uma tentativa recente para fazê-lo é o sistemaΠΣ descrito por Altenkirch et al . Não é totalmente satisfatório, pois a verificação de positividade necessária para consistência não faz parte do sistema "como está". A meta-teoria ainda precisa ser desenvolvida também.

Uma visão geral útil é o artigo A ZF é um hack? de Freek Wiedijk, que na verdade compara os números reais em todos esses sistemas (número de regras e axiomas).

cody
fonte
Σ
Na verdade não, acredito que você precisa assumi-las também. Meu erro.
Cody
11

O problema com as codificações da Igreja é que você não pode obter princípios de indução para seus tipos, o que significa que eles são praticamente inúteis quando se trata de provar declarações sobre eles.

Em termos de minimalidade do sistema, um caminho mencionado nos comentários é usar contêineres e tipos (W / M), no entanto, eles são bastante extensivos para que não seja realmente conveniente trabalhar em sistemas como Coq ou Agda.

ΠΣμν

μν

Gallais
fonte