In a previous paper we investigated the extraction of proof-theoretic properties of natural deduction derivations from their impredicative translation into System F. Our key idea was to introduce an extended equational theory for System F codifying at a syntactic level some properties found in parametric models of polymorphic type theory. A different approach to extract proof-theoretic properties of natural deduction derivations was proposed in a recent series of papers on the basis of an embedding of intuitionistic propositional logic into a (...) predicative fragment of System F, called atomic System F. In this paper we show that this approach finds a general explanation within our equational study of second-order natural deduction, and a clear semantic justification in terms of parametricity. (shrink)

In the present paper we discuss a recent suggestion of Schroeder-Heister concerning the possibility of defining an intensional notion of harmony using isomorphism in second-order propositional logic. The latter is not an absolute notion, but its definition is relative to the choice of criteria for identity of proofs. In the paper, it is argued that in order to attain a satisfactory account of harmony, one has to consider a notion of identity stronger than the usual one (based on β- and (...) η-conversions) that the authors have investigated in recent work. (shrink)

This special issue on general proof theory collects papers resulting from the conference on general proof theory held in November 2015 in Tübingen.

The investigations on higher-order type theories and on the related notion of parametric polymorphism constitute the technical counterpart of the old foundational problem of the circularity of second and higher-order logic. However, the epistemological significance of such investigations has not received much attention in the contemporary foundational debate.We discuss Girard’s normalization proof for second order type theory or System F and compare it with two faulty consistency arguments: the one given by Frege for the logical system of the Grundgesetze and (...) the one given by Martin-Löf for the intuitionistic type theory with a type of all types.The comparison suggests that the question of the circularity of second order logic cannot be reduced to Russell’s and Poincaré’s 1906 “vicious circle” diagnosis. Rather, it reveals a bunch of mathematical and logical ideas hidden behind the hazardous idea of impredicative quantification, constituting a vast domain for foundational research. (shrink)

Given the recent interest in the fragment of system $\mathbf{F}$ where universal instantiation is restricted to atomic formulas, a fragment nowadays named system ${\mathbf{F}}_{\textbf{at}}$, we study directly in system $\mathbf{F}$ new conversions whose purpose is to enforce that restriction. We show some benefits of these new atomization conversions: they help achieving strict simulation of proof reduction by means of the Russell–Prawitz embedding of $\textbf{IPC}$ into system $\mathbf{F}$, they are not stronger than a certain ‘dinaturality’ conversion known to generate a consistent (...) equality of proofs, they provide the bridge between the Russell–Prawitz embedding and another translation, due to the authors, of $\textbf{IPC}$ directly into system ${\mathbf{F}}_{\textbf{at}}$ and they give means for explaining why the Russell–Prawitz translation achieves strict simulation whereas the translation into ${\mathbf{F}}_{\textbf{at}}$ does not. (shrink)