×

On bounded functional interpretations. (English) Zbl 1251.03074

Functional interpretations are powerful tools in mathematical logic with many applications, among them witnessing existential statements. The first class of functional interpretations provided precise witnesses for existential statements. A second class of functional interpretations provided bounds for existential statements by changing the target from precise witnesses to bounds in a last step. A third class of functional interpretations, called bounded functional interpretations, provided also bounds but targeting bounds from the first step.
Paulo Oliva, joined by Gilda Ferreira, has pursued a unification program: to show that different functional interpretations are instances of a parametrized functional interpretation. The first class of unifications took place in the context of the usual intuitionistic logic. A second class of unifications changed the context to classical linear logic. Then a third class of unifications changed the context to intuitionistic linear logic.
This being said, now we can easily describe the article in question: It presents a unification in the context of intuitionistic linear logic of bounded functional interpretations. More extensively, the article:
(1)
presents parametrized functional interpretations of the usual intuitionistic logic and of intuitionistic linear logic;
(2)
shows that the two parametrized functional interpretations are the same modulo embedding one logic in the other;
(3)
proves the soundness theorem / adequacy lemma for the parametrized functional interpretations;
(4)
shows that the parametrized functional interpretations instantiate into three bounded functional interpretations, namely the (simply called) bounded functional interpretation, the bounded modified realizability and the confined modified realizability;
(5)
sheds light on the comparison of the bounded functional interpretations by making clear in the parametrized functional interpretations what they have in common and in what they differ.

MSC:

03F25 Relative consistency and interpretations
03F07 Structure of proofs
03F10 Functionals in proof theory
03F52 Proof-theoretic aspects of linear logic and other substructural logics
Full Text: DOI

References:

[1] Bezem, M., Strongly majorizable functionals of finite type: a model for bar recursion containing discontinuous functionals, The Journal of Symbolic Logic, 50, 652-660 (1985) · Zbl 0578.03030
[2] Diller, J.; Nahm, W., Eine Variant zur Dialectica-interpretation der Heyting Arithmetik endlicher Typen, Archive for Mathematical Logik Grundlagenforsch, 16, 49-66 (1974) · Zbl 0277.02006
[3] Ferreira, F.; Nunes, A., Bounded modified realizability, Journal of Symbolic Logic, 71, 329-346 (2006) · Zbl 1100.03050
[4] Ferreira, F.; Oliva, P., Bounded functional interpretation, Annals of Pure and Applied Logic, 135, 73-112 (2005) · Zbl 1095.03060
[5] Ferreira, F.; Oliva, P., Bounded functional interpretation in feasible analysis, Annals of Pure and Applied Logic, 145, 115-129 (2007) · Zbl 1112.03052
[6] Ferreira, G.; Oliva, P., Functional interpretations of intuitionistic linear logic, (Grädel, E.; Kahle, R., Proceedings of CSL. Proceedings of CSL, LNCS, vol. 5771 (2009), Springer), 3-19 · Zbl 1193.03080
[7] Ferreira, G.; Oliva, P., Confined modified realizability, Mathematical Logic Quarterly, 56, 1, 13-28 (2010) · Zbl 1184.03056
[8] Gödel, K., Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes, Dialectica, 12, 280-287 (1958) · Zbl 0090.01003
[9] Howard, W. A., Hereditarily majorizable functionals of finite type, (Troelstra, A. S., Metamathematical Investigation of Intuitionistic Arithmetic and Analysis. Metamathematical Investigation of Intuitionistic Arithmetic and Analysis, Lecture Notes in Mathematics, vol. 344 (1973), Springer: Springer Berlin), 454-461 · Zbl 0275.02025
[10] Kreisel, G., Interpretation of analysis by means of constructive functionals of finite types, (Heyting, A., Constructivity in Mathematics (1959), North Holland: North Holland Amsterdam), 101-128 · Zbl 0134.01001
[11] Oliva, P., Unifying functional interpretations, Notre Dame Journal of Formal Logic, 47, 2, 263-290 (2006) · Zbl 1113.03052
[12] Oliva, P., Modified realizability interpretation of classical linear logic, (Proc. of the Twenty Second Annual IEEE Symposium on Logic in Computer Science LICS’07 (2007), IEEE Press)
[13] Oliva, P., An analysis of Gödel’s dialectica interpretation via linear logic, dialectica, 62, 2, 269-290 (2008)
[14] Oliva, P., Functional interpretations of linear and intuitionistic logic, Information and Computation, 208, 5, 565-577 (2010) · Zbl 1193.03081
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.