Kripke Models for the Second-Order Lambda-Calculus

We define a new class of Kripke structures for the second-order λ-calculus, and investigate the soundness and completeness of some proof systems for proving inequalities (rewrite rules) or equations. The Kripke structures under consideration are equipped with preorders that correspond to an abstract form of reduction, and they are not necessarily extensional. A novelty of our approach is that we define these structures directly as functors A:W→ Preor equipped with certain natural transformations corresponding to application and abstraction (where is a preorder, the set of worlds, and Preor is the category of preorders). We make use of an explicit construction of the exponential of functors in the Cartesian-closed category PreorW, and we also define a kind of exponential ∏Φ(As)s∈Τ to take care of type abstraction. We obtain soundness and completeness theorems that generalize some results of Mitchell and Moggi to the second-order λ-calculus, and to sets of inequalities (rewrite rules).