1. Morten H. Sørensen & Paweł Urzyczyn (2010). A Syntactic Embedding of Predicate Logic Into Second-Order Propositional Logic. Notre Dame Journal of Formal Logic 51 (4):457-473.
    We give a syntactic translation from first-order intuitionistic predicate logic into second-order intuitionistic propositional logic IPC2. The translation covers the full set of logical connectives ∧, ∨, →, ⊥, ∀, and ∃, extending our previous work, which studied the significantly simpler case of the universal-implicational fragment of predicate logic. As corollaries of our approach, we obtain simple proofs of nondefinability of ∃ from the propositional connectives and nondefinability of ∀ from ∃ in the second-order intuitionistic propositional logic. We also show (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  2. Morten Heine Sørensen & Paweł Urzyczyn (2008). Strong Cut-Elimination in Sequent Calculus Using Klop's L-Translation and Perpetual Reductions. Journal of Symbolic Logic 73 (3):919 - 932.
    There is a simple technique, due to Dragalin, for proving strong cut-elimination for intuitionistic sequent calculus, but the technique is constrained to certain choices of reduction rules, preventing equally natural alternatives. We consider such a natural, alternative set of reduction rules and show that the classical technique is inapplicable. Instead we develop another approach combining two of our favorite tools—Klop's l-translation and perpetual reductions. These tools are of independent interest and have proved useful in a variety of settings; it is (...)
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  3. Morten Heine Sørensen (2007). Lectures on the Curry-Howard Isomorphism. Elsevier.
    The Curry-Howard isomorphism states an amazing correspondence between systems of formal logic as encountered in proof theory and computational calculi as found in type theory. For instance, minimal propositional logic corresponds to simply typed lambda-calculus, first-order logic corresponds to dependent types, second-order logic corresponds to polymorphic types, sequent calculus is related to explicit substitution, etc. The isomorphism has many aspects, even at the syntactic level: formulas correspond to types, proofs correspond to terms, provability corresponds to inhabitation, proof normalization corresponds to (...)
    Direct download  
     
    My bibliography  
     
    Export citation