Loading...
3 results
Search Results
Now showing 1 - 3 of 3
- The Russell-Prawitz embedding and the atomization of universal instantiationPublication . Espírito Santo, José; Ferreira, GildaGiven the recent interest in the fragment of system F where universal instantiation is restricted to atomic formulas, a fragment nowadays named system Fat, we study directly in system F new conversions whose purpose is to enforce that restriction. We show some benefits of these new atomization conversions: (1) They help achieving strict simulation of proof reduction by means of the Russell-Prawitz embedding of IPC into system F; (2) They are not stronger than a certain “dinaturality” conversion known to generate a consistent equality of proofs; (3) They provide the bridge between the Russell-Prawitz embedding and another translation, due to the authors, of IPC directly into system Fat; (4) They give means for explaining why the Russell-Prawitz translation achieves strict simulation whereas the translation into Fat does not.
- A refined interpretation of intuitionistic logic by means of atomic polymorphismPublication . Espírito Santo, José; Ferreira, GildaWe study an alternative embedding of IPC into atomic system F whose translation of proofs is based, not on instantiation overflow, but instead on the admissibility of the elimination rules for disjunction and absurdity (where these connectives are defined according to the Russell- Prawitz translation). As compared to the embedding based on instantiation overflow, the alternative embedding works equally well at the levels of provability and preservation of proof identity, but it produces shorter derivations and shorter simulations of reduction sequences. Lambda-terms are employed in the technical development so that the algorithmic content is made explicit, both for the alternative and the original embeddings. The investigation of preservation of proof-reduction steps by the alternative embedding enables the analysis of generation of “administrative” redexes. These are the key, on the one hand, to understand the difference between the two embeddings; on the other hand, to understand whether the final word on the embedding of IPC into atomic system F has been said.
- How to avoid the commuting conversions of IPCPublication . Espírito Santo, José; Ferreira, GildaSince the observation in 2006 that it is possible to embed IPC into the atomic polymorphic λ-calculus (a predicative fragment of system F with universal instantiations restricted to atomic formulas) different such embeddings appeared in the literature. All of them comprise the Russell-Prawitz translation of formulas, but have different strategies for the translation of proofs. Although these embeddings preserve proof identity, all fail in delivering preservation of reduction steps. In fact, they translate the commuting conversions of IPC to β-equality, or to other kinds of reduction or equality generated by new principles added to system F. The cause for this is the generation of redexes by the translation itself. In this paper, we present an embedding of IPC into atomic system F, still based on the same translation of formulas, but which maps commuting conversions to syntactic identity, while simulating the other kinds of reduction steps present in IPC by βη-reduction. In this sense the translation achieves a truly commuting-conversion-free image of IPC in atomic system F.