A sound pure type system with ranks as sorts and Type-in-Type
En palabras de los autores
We present a dependently typed pure type system that contains a circular axiom for a certain sort and is nonetheless strongly normalizing. Girard's paradox is avoided because our sorts are not closed under a -former: function types are placed in sorts according to their rank. Turns out that this system has a unique set of characteristics: it has similar normalization behaviour as STLC (so complexity of normalization is TOWER-complete) while at the same time allowing non-uniform representation of arbitrary elementary recursive functions; furthermore, it has a nontrivial set-theoretical model in ZF+GCH and allows to carry out nontrivial proof developments. Base normalization proof is surprisingly simple (modulo general metatheoretical properties of pure type systems) and has been fully formalized in vanilla Rocq (formerly Coq) without additional axioms.
Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 28 pages, 3 figures, supplementary material to be found at http://github.com/TurtlePU/pts-rk