Logiczne reakcje na system impredykatywny w predykatywnej metateorii

14

Relacje logiczne dla języków impredykatywnych, takich jak System F, wydają się krytycznie opierać na impredykatywności logiki otoczenia. W szczególności interpretacja typu forall zostanie zdefiniowana w kategoriach wszystkich relacji typowanych. W systemie impredykatywnym (jak CiC / Coq) jest w porządku, ale wydaje się to niemożliwe w systemie predykcyjnym (jak Agda).

Jak można to zrobić? Na przykład, jak udowodniłbyś normalizację dla Systemu F w Agdzie? Czy musisz budować własny impredykacyjny wszechświat?

Max nowy
źródło

Odpowiedzi:

14

Zasadniczo to, co zwykle nazywamy argumentem relacji logicznych, nie jest tak naprawdę powiązane z impredykatywnością: główną ideą jest po prostu interpretacja terminów w jakiejś abstrakcyjnej algebrze i reprezentowanie typów jako ( n -aryjna) relacja R A n .ZAnRZAn

λ

P.ZA2)

Jednak pouczające jest ustalenie, gdzie dokładnie dowody popełniają błąd w Agdzie. Rzeczywiście ma to miejsce, gdy próbujesz zdefiniować interpretację relacji logicznych impredykatywnej kwantyfikacji. Interpretacja nieprzywierających łączników (w tym kwantyfikacja „zależna”) jest koszerna w teorii takiej jak Agda.

cody
źródło
1
Łał, naprawdę? Nie możesz udowodnić, że System F normalizuje się w Agdzie? Czy masz na to powód?
Max New
2
@ MaxNew: Trudno jest znaleźć cytat. Najbliższe, jakie mogę znaleźć, to Siła niektórych teorii typu Martina-Löfa, która zdecydowanie rozwiązuje kwestię teorii predykatywnej z jednym wszechświatem i pewnego rodzaju indukcją. Ale Agda ma przerażającą rekurencję indukcyjną, co czyni ją znacznie potężniejszą.
cody
1
Powinienem jednak dodać, że w niektórych przypadkach rekurencja indukcyjna jest słabsza niż impredykatywna kwantyfikacja, jak to dobrze wyjaśniono tutaj: fplab.bitbucket.org/posts/2012-12-06-induction-recursion.html
cody
1
@cody Niestety, link już nie działa. Czy możesz ponownie znaleźć tę treść? Czy znasz nowe publikacje z zakresu formalizacji impredykatywności?
Łukasz Lew