Título: | O QUE É O ESQUELETO DE UMA DEMONSTRAÇÃO | ||||||||||||||||||||||||||||||||
Autor: |
EDUARDO NAHUM OCHS |
||||||||||||||||||||||||||||||||
Colaborador(es): |
NICOLAU CORCAO SALDANHA - Orientador |
||||||||||||||||||||||||||||||||
Catalogação: | 12/MAR/2004 | Língua(s): | PORTUGUÊS - BRASIL |
||||||||||||||||||||||||||||||
Tipo: | TEXTO | Subtipo: | TESE | ||||||||||||||||||||||||||||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||||||||||||||||||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=4645&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=4645&idi=2 |
||||||||||||||||||||||||||||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.4645 | ||||||||||||||||||||||||||||||||
Resumo: | |||||||||||||||||||||||||||||||||
Considere os seguintes dois tipos de transformções em
demonstrações: 1) tornar uma prova mais incompleta,
apagando um lema ou uma construção que sejam parte da prova
e pondo no lugar um aviso dizendo isso é óbvio; 2) pegar um
passo que foi provado por um isso é óbvio, aplicar algum
algoritmo que encontre uma demonstração para esse passo, e
trocar o aviso pela demonstração de verdade. Nós vamos
considerar que a primeira operação vai em direção ao
esqueleto da demonstração, e que ela é como uma projeção;
a segunda operação é um levantamento de um esqueleto para
uma demonstração um pouco mais completa com aquele
esqueleto. Nós só estamos interessados em esqueletos que
possam ser levantados até provas completas usando algum
algoritmo conhecido. Nesta tese descrevemos uma linguagem -
o sistema DNC - que permite provar vários fatos sobre
categorias usando esqueletos. O método para o levantamento
é, a grosso modo, o seguinte: a partir do nome de um termo
em DNC nós podemos obter o seu tipo; por uma espécie de
Isomorfismo de Curry-Howard um tipo desses pode ser visto
como uma preposição numa certa lógica; um algoritmo que
obtenha uma demonstração para essa proposição retorna uma
árvore de demonstração (uma derivação) num certo sistema de
Dedução Natural, e essa árvore pode ser lida como um lambda-
termo do tipo dado - ela dá uma construção natural para um
objeto daquele tipo, e esse objeto muito frequentemente é
exatamente o objeto que esperávamos obter. Derivações em
DNC podem ser traduzidas para derivações num Pure Type
System com Dicionários (PTSD), e derivações em PTSDs podem
ser traduzidas para derivações em Pure Type Systems (PTSs);
daí, questões sobre a teoria da prova de DNC se tornam
questões sobre a teoria da prova de PTSs, que é bastante
bem-conhecida. Não só temos um levantamento de nomes de
termos em DNC para provas completas, mas também temos um
modo formal de levantar diagramas categóricos expressos na
linguagem do DNC para termos em DNC e daí para provas
completas; e se mudamos o dicionário embutido num PTSD
podemos fazer com que o mesmo esqueleto em DNC represente
provas em contextos diferentes; por exemplo, algumas provas
que aparentemente estão sendo feitas sobre a categoria dos
conjuntos podem ser reinterpretados como provas sobre um
topos arbitrário. Usamos essa idéia para apresentar de uma
forma simples - em que os passos óbvios omitidos são óbvios
num sentido muito preciso - a semântica categárica para
alguns PTSs, incluindo PTSs com polimorfismo e tipos
dependentes, e os PTSs para quais as derivações em DNC são
traduzidas.
|
|||||||||||||||||||||||||||||||||
|