RUS  ENG
Полная версия
СЕМИНАРЫ

Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
25 апреля 2022 г. 18:30, г. Москва, МИАН (ул. Губкина, 8), ауд. 313 + Контур Толк


A circular version of Gödel's T and its abstraction complexity

Anupam Das

University of Birmingham



Аннотация: Circular and non-wellfounded proofs have become an increasingly popular tool for metalogical treatments of systems with forms of induction and/or recursion. In this work we investigate the expressivity of a variant CT of Gödel's system T where programs are circularly typed, rather than including an explicit recursion combinator. In particular, we examine the abstraction complexity (i.e. type level) of CT, and show that the Gödel primitive recursive functionals may be typed more succinctly with circular derivations, using types precisely one level lower than in T. In fact we give a logical correspondence between the two settings, interpreting the quantifier-free type 1 theory of level n+1 T into that of level n CT and vice-versa.
We also obtain some further results and perspectives on circular 'derivations', namely strong normalisation and confluence, models based on hereditary computable functionals, continuity at type 2, and a translation to terms of T computing the same functional, at all types.

Язык доклада: английский


© МИАН, 2024