195 research outputs found
Impredicative Encodings of Inductive and Coinductive Types
No full textIn impredicative type theory (System F, also known as λ2), it is possible to define inductive data types, such as natural numbers and lists. It is also possible to define coinductive data types such as streams. They work well in the sense that their (co)recursion principles obey the expected computation rules (the β-rules). Unfortunately, they do not yield a (co)induction principle [Herman Geuvers, 2001; Ivar Rummelhoff, 2004], because the necessary uniqueness principles are missing (the η-rules). Awodey, Frey, and Speight [Steve Awodey et al., 2018] used an extension of the Calculus of Constructions [Thierry Coquand and Gérard P. Huet, 1988] (λ C) with Σ-types, identity-types, and functional extensionality to define System F style inductive types with an induction principle, by encoding them as a well-chosen subtype, making them initial algebras.
In this paper, we extend their results to coinductive data types, and we detail the example of the stream data type with the desired coinduction principle (also called bisimulation). To do that, we first define quotient types (with the desired η-rules) and we also need a stronger form of the definable existential types. We also show that we can use the original method by Awodey, Frey and Speight for general inductive types by defining W-types with an induction principle. The dual approach for streams can be extended to M-types, the generic notion of coinductive types, and the dual of W-types
Front Matter, Table of Contents, Preface, Conference Organization
No full textFront Matter, Table of Contents, Preface, Conference Organizatio
RELATING APARTNESS AND BISIMULATION
No full textContains fulltext :
235962.pdf (Publisher’s version ) (Open Access
Classical Natural Deduction from Truth Tables
No full textIn earlier articles we have introduced truth table natural deduction which allows one to extract natural deduction rules for a propositional logic connective from its truth table definition. This works for both intuitionistic logic and classical logic. We have studied the proof theory of the intuitionistic rules in detail, giving rise to a general Kripke semantics and general proof term calculus with reduction rules that are strongly normalizing. In the present paper we study the classical rules and give a term interpretation to classical deductions with reduction rules. As a variation we define a multi-conclusion variant of the natural deduction rules as it simplifies the study of proof term reduction. We show that the reduction is normalizing and gives rise to the sub-formula property. We also compare the logical strength of the classical rules with the intuitionistic ones and we show that if one non-monotone connective is classical, then all connectives become classical
Proof Terms for Generalized Natural Deduction
No full textIn previous work it has been shown how to generate natural deduction rules for propositional connectives from truth tables, both for classical and constructive logic. The present paper extends this for the constructive case with proof-terms, thereby extending the Curry-Howard isomorphism to these new connectives. A general notion of conversion of proofs is defined, both as a conversion of derivations and as a reduction of proof-terms. It is shown how the well-known rules for natural deduction (Gentzen, Prawitz) and general elimination rules (Schroeder-Heister, von Plato, and others), and their proof conversions can be found as instances. As an illustration of the power of the method, we give constructive rules for the nand logical operator (also called Sheffer stroke).
As usual, conversions come in two flavours: either a detour conversion arising from a detour convertibility, where an introduction rule is immediately followed by an elimination rule, or a permutation conversion arising from an permutation convertibility, an elimination rule nested inside another elimination rule. In this paper, both are defined for the general setting, as conversions of derivations and as reductions of proof-terms. The properties of these are studied as proof-term reductions. As one of the main contributions it is proved that detour conversion is strongly normalizing and permutation conversion is strongly normalizing: no matter how one reduces, the process eventually terminates. Furthermore, the combination of the two conversions is shown to be weakly normalizing: one can always reduce away all convertibilities
Characteristics of de Bruijn's early proof checker Automath
No full textThe `mathematical language' Automath, conceived by N.G. de Bruijn in 1968,
was the first theorem prover actually working and was used for checking many
specimina of mathematical content. Its goals and syntactic ideas inspired Th.
Coquand and G. Huet to develop the calculus of constructions, CC, which was one
of the first widely used interactive theorem provers and forms the basis for
the widely used Coq system. The original syntax of Automath is not easy to
grasp. Yet, it is essentially based on a derivation system that is similar to
the Calculus of Constructions (`CC'). The relation between the Automath syntax
and CC has not yet been sufficiently described, although there are many
references in the type theory community to Automath. In this paper we focus on
the backgrounds and on some uncommon aspects of the syntax of Automath. We
expose the fundamental aspects of a `generic' Automath system, encapsulating
the most common versions of Automath. We present this generic Automath system
in a modern syntactic frame. The obtained system makes use of {\lambda}D, a
direct extension of CC with definitions
Deduction Graphs with Universal Quantification
No full textAbstractDeduction Graphs are meant to generalise both Gentzen-Prawitz style natural deductions and Fitch style flag deductions. They have the structure of acyclic directed graphs with boxes. In [Herman Geuvers and Iris Loeb. Natural Deduction via Graphs: Formal Definition and Computation Rules. Mathematical Structures in Computer Science (Special Issue on Theory and Applications of Term Graph Rewriting), Volume 17(03):485–526, 2007.] we have investigated the deduction graphs for minimal proposition logic. This paper studies the extension with first-order universal quantification, showing the robustness of the concept of deduction graphs
Iteration and primitive recursion in categorical terms
No full textContains fulltext :
34575.pdf ( ) (Open Access
Computer-ondersteund redeneren : de boekhouder steunt de denker
No full textBewijsassistenten moeten ervoor zorgen dat complexe softwaresystemen correct werken. Geen eenvoudige klus, zegt Herman Geuvers, die vandaag zijn inaugurele rede houdt. Het is nog vrijwel onmogelijk formele wiskunde tussen verschillende bewijsassistenten uit te wisselen
- …
