Elementary Proof of Strong Normalization for Atomic F

• Autorzy: Fernando Ferreira , Gilda Ferreira
• Języki publikacji: EN

Abstrakty

EN

We give an elementary proof (in the sense that it is formalizable in Peano arithmetic) of the strong normalization of the atomic polymorphic calculus Fat (a predicative restriction of Girard’s system F).

Słowa kluczowe

EN

Predicative polymorphism; strong normalization; elementary proofs; lambda-calculus

• Wydawca: Wydawnictwo Uniwersytetu Łódzkiego
• Czasopismo: Bulletin of the Section of Logic
• Rocznik: 2016
• Tom: 45
• Numer: 1

Daty

wydano

2016-03-30

Twórcy

autor

Fernando Ferreira

• Universidade de Lisboa, Faculdade de Ciências, Departamento de Matemática

autor

Gilda Ferreira

• Universidade Lusófona de Humanidades e Tecnologias, Departamento de Matemática

Bibliografia

• [1] T. Altenkirch and T. Coquand, A finitary subsystem of the polymorphic λ-calculus, Proceedings of the 5th International Conference on Typed Lambda Calculi and Applications (TLCA 2001), Lecture Notes in Computer Science 2044 (2001), pp. 22–28.
• A. Beckmann, Exact bounds for lenghts of reductions in typed λ-calculus, The Journal of Symbolic Logic 66(3) (2001), pp. 1277–1285.
• F. Ferreira, A simple proof of Parsons’ theorem, Notre Dame Journal of Formal Logic 46 (2005), pp. 83–91.
• F. Ferreira, Comments on predicative logic, Journal of Philosophical Logic 35 (2006), pp. 1–8.
• F. Ferreira and G. Ferreira, Atomic polymorphism, The Journal of Symbolic Logic 78 (2013), pp. 260–274.
• F. Ferreira and G. Ferreira, The faithfulness of Fat : a proof-theoretic proof, Studia Logica 103(6) (2015), pp. 1303–1311.
• J.-Y. Girard, Y. Lafont and P. Taylor, Proofs and Types, Cambridge University Press (1989).
• F. Joachimski and R. Matthes, Short proofs of normalization for the simplytyped lambda-calculus, permutative conversions and Gödel’s T, Archive for Mathematical Logic 42 (2003), pp. 59–87.
• H. Schwichtenberg, An upper bound for reduction sequences in the typed λ-calculus, Archive for Mathematical Logic 30 (1991), pp. 405–408.
• W. Tait, Intentional interpretations of functionals of finite type I, The Journal of Symbolic Logic 32 (1967), pp. 198–212.
• W. Tait, Finitism, Journal of Philosophy 78 (1981), pp. 524–546.
• A. S. Troelstra and H. Schwichtenberg, Basic Proof Theory, Cambridge University Press (1996).
• A. S. Troelstra and D. van Dalen, Constructivism in Mathematics. An Introduction, volume 1, North Holland, Amsterdam (1988).
• J. van de Pol, Two different strong normalization proofs? Computability versus functionals of finite type, Proceedings of the Second International Workshop on Higher-Order Algebra, Logic and Term Rewriting (HOA’95), Lecture Notes in Computer Science 1074 (1996), pp. 201–220.
• F. van Raamsdonk and P. Severi, On normalization, Technical report CSR9545, Centrum voor Wiskunde en Informatica, Amsterdam (1995).

Identyfikatory

DOI

10.18778/0138-0680.45.1.01