×

The naturality of natural deduction. (English) Zbl 1531.03092

Summary: Developing a suggestion by Russell, Prawitz showed how the usual natural deduction inference rules for disjunction, conjunction and absurdity can be derived using those for implication and the second order quantifier in propositional intuitionistic second order logic \(\mathtt{NI}^2\). It is however well known that the translation does not preserve the relations of identity among derivations induced by the permutative conversions and immediate expansions for the definable connectives, at least when the equational theory of \(\mathtt{NI}^2\) is assumed to consist only of \(\beta \)- and \(\eta \)-equations. On the basis of the categorial interpretation of \(\mathtt{NI}^2\), we introduce a new class of equations expressing what in categorial terms is a naturality condition satisfied by the transformations interpreting \(\mathtt{NI}^2\)-derivations. We show that the Russell-Prawitz translation does preserve identity of proof with respect to the enriched system by highlighting the fact that naturality corresponds to a generalized permutation principle. Finally we sketch how these results could be used to investigate the properties of connectives definable in the framework of higher-level rules.

MSC:

03F03 Proof theory in general (including proof-theoretic semantics)
03B40 Combinatory logic and lambda calculus

References:

[1] Aczel, P., The Russell-Prawitz modality, Mathematical Structures in Computer Science 11: 541-554, 2001. · Zbl 0988.03033 · doi:10.1017/S0960129501003309
[2] Altenkirch, T., P. Dybjer, M. Hoffman, and P. J. Scott, Normalization by evaluation for typed lambda calculus with coproducts, in 16th Annual IEEE Symposium on Logic in Computer Science, Boston, Massachussetts, 2001, pp. 303-310.
[3] Bainbridge, E.S., P. J. Freyd, A. Scedrov, and P. J. Scott, Functorial polymorphism, Theoretical Computer Science 70: 35-64, 1990. · Zbl 0717.18005 · doi:10.1016/0304-3975(90)90151-7
[4] de Lataillade, J., Dinatural terms in System F, in 24th Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, Los Angeles, California, USA, 2009, pp. 267-276.
[5] Ferreira, F., and G. Ferreira, Commuting conversions vs. the standard conversions of the “good” connectives, Studia Logica 92(1): 63-84, 2009. · Zbl 1185.03081 · doi:10.1007/s11225-009-9186-1
[6] Ferreira, F., and G. Ferreira, Atomic polymorphism, Journal of Symbolic Logic 78(1): 260-274, 2013. · Zbl 1279.03035 · doi:10.2178/jsl.7801180
[7] Freyd, P. J., J.-Y. Girard, A. Scedrov, and P. J. Scott, Semantic parametricity in the polymorphic lambda calculus, in LICS ’88., Proceedings of the Third Annual Symposium on Logic in Computer Science, IEEE, 1988, pp. 274-279.
[8] Ghani, \[N., \beta \eta\] βη-equality for coproducts, in TLCA ’95, International Conference on Typed Lambda Calculi and Applications, vol. 902 of Lecture Notes in Computer Science, Springer-Verlag, 1995, pp. 171-185. · Zbl 1063.03513
[9] Girard, J.-Y., Y. Lafont, and P. Taylor, Proof and Types, Cambridge University Press, 1989. · Zbl 0671.68002
[10] Girard, J.-Y., A. Scedrov, and P. J. Scott, Normal forms and cut-free proofs as natural transformations, in Y. Moschovakis, (ed.), Logic from Computer Science, vol. 21 of Mathematical Sciences Research Institute Publications, Springer-Verlag, 1992, pp. 217-241. · Zbl 0753.03024
[11] Lindley, S., Extensional rewriting with sums, in Typed Lambda Calculi and Applications, TLCA 2007, vol. 4583 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2007, pp. 255-271. · Zbl 1215.03026
[12] Prawitz, D., Natural deduction, a proof-theoretical study, Almqvist & Wiskell, 1965. · Zbl 0173.00205
[13] Prawitz, D., Ideas and results in proof theory, in J.E. Fenstad, (ed.), Proceedings of the 2nd Scandinavian Logic Symposium (Oslo), Studies in logic and foundations of mathematics, vol. 63, North-Holland, 1971. · Zbl 0226.02031
[14] Prawitz, D., Proofs and the meaning and completeness of the logical constants, in J. Hintikka, I. Niiniluoto, and E. Saarinen, (eds.), Essays on Mathematical and Philosophical Logic: Proceedings of the Fourth Scandinavian Logic Symposium and the First Soviet-Finnish Logic Conference, Jyväskylä, Finland, June 29-July 6, 1976, Kluwer, Dordrecht, 1979, pp. 25-40. · Zbl 0406.03069
[15] Russell, B., The Principles of Mathematics, George Allen and Unwin Ltd. (2nd edition 1937), 1903.
[16] Schroeder-Heister, P., A natural extension of natural deduction, Journal of Symbolic Logic 49(4): 1284-1300, 1984. · Zbl 0574.03045 · doi:10.2307/2274279
[17] Schroeder-Heister, P., The calculus of higher-level rules, propositional quantification, and the foundational approach to proof-theoretic harmony, Studia Logica 102(6): 1185-1216, 2014. · Zbl 1344.03046 · doi:10.1007/s11225-014-9562-3
[18] Schwichtenberg, H., and A. S. Troelstra, Basic proof theory, Cambridge University Press, 2000. · Zbl 0957.03053
[19] Seely, R. A. G., Weak adjointness in proof theory, in Proceedings of the Durham Conference on Applications of Sheaves, vol. 753 of Springer Lecture Notes in Mathematics, Springer Berlin, 1979, pp. 697-701. · Zbl 0438.18002
[20] Tranchini, L., Proof-theoretic harmony: Towards an intensional account, Synthese, Online first (2016). https://doi.org/10.1007/s11229-016-1200-3. · Zbl 1507.03045
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.