The Experts below are selected from a list of 237 Experts worldwide ranked by ideXlab platform
Luca Incurvati - One of the best experts on this subject based on the ideXlab platform.
-
Can the Cumulative Hierarchy Be Categorically Characterized
Logique Et Analyse, 2016Co-Authors: Luca IncurvatiAbstract:Mathematical realists have long invoked the categoricity of axiomatizations of arithmetic and analysis to explain how we manage to fix the intended meaning of their respective vocabulary. Can this strategy be extended to set theory? Although traditional wisdom recommends a negative answer to this question, Vann McGee (1997) has offered a proof that purports to show otherwise. I argue that one of the two key assumptions on which the proof rests deprives McGee's result of the significance he and the realist want to attribute to it. I consider two strategies to deal with the problem --- one of which is outlined by McGee himself (2000) --- and argue that both of them fail. I end with some remarks on the prospects for mathematical realism in the light of my discussion.
-
How to be a minimalist about sets
Philosophical Studies, 2012Co-Authors: Luca IncurvatiAbstract:According to the iterative conception of set, sets can be arranged in a Cumulative Hierarchy divided into levels. But why should we think this to be the case? The standard answer in the philosophical literature is that sets are somehow constituted by their members. In the first part of the paper, I present a number of problems for this answer, paying special attention to the view that sets are metaphysically dependent upon their members. In the second part of the paper, I outline a different approach, which circumvents these problems by dispensing with the priority or dependence relation altogether. Along the way, I show how this approach enables the mathematical structuralist to defuse an objection recently raised against her view.
Miguel Pagano - One of the best experts on this subject based on the ideXlab platform.
-
TLCA - A Type-Checking Algorithm for Martin-Löf Type Theory with Subtyping Based on Normalisation by Evaluation
Lecture Notes in Computer Science, 2013Co-Authors: Daniel Fridlender, Miguel PaganoAbstract:We present a core Martin-Lof type theory with subtyping; it has a Cumulative Hierarchy of universes and the contravariant rule for subtyping between dependent product types. We extend to this calculus the normalisation by evaluation technique defined for a variant of MLTT without subtyping. This normalisation function makes the subtyping relation and type-checking decidable. To our knowledge, this is the first time that the normalisation by evaluation technique has been considered in the context of subtypes, which introduce some subtleties in the proof of correctness of NbE; an important result to prove correctness and completeness of type-checking.
Siegfried Gottwald - One of the best experts on this subject based on the ideXlab platform.
-
For the fuzzy set community he is of importance because he developed, parallel to Lotfi Zadeh, in the mid-1960s the idea of generalized sets with degrees of membership, called "mehrwertige Mengen" by Klaua. Klaua gave two versions (5,7) for a cumulat
2015Co-Authors: Siegfried GottwaldAbstract:The German mathematician Dieter Klaua was born July 22, 1930 in Chemnitz and passed away April 14, 2014 in Karlsruhe.He studied mathematics at Leipzig University from 1949 till 1954. As a graduate student, he moved into the logic group of Karl Schroter at Humboldt University in Berlin (East). There he got his PhD degree in 1957 with a thesis [3]on computable analysis, and his habilitation degree in 1959 with a transfinite generalization [4] of the constructions of integers, rationals, and reals.
-
Universes of Fuzzy Sets and Axiomatizations of Fuzzy Set Theory. Part II: Category Theoretic Approaches
Studia Logica, 2006Co-Authors: Siegfried GottwaldAbstract:For classical sets one has with the Cumulative Hierarchy of sets, with axiomatizations like the system ZF, and with the category SET of all sets and mappings standard approaches toward global universes of all sets.
-
Universes of Fuzzy Sets and Axiomatizations of Fuzzy Set Theory. Part II: Category Theoretic Approaches
Studia Logica, 2006Co-Authors: Siegfried GottwaldAbstract:For classical sets one has with the Cumulative Hierarchy of sets, with axiomatizations like the system ZF, and with the category SET of all sets and mappings standard approaches toward global universes of all sets. We discuss here the corresponding situation for fuzzy set theory. Our emphasis will be on various approaches toward (more or less naively formed) universes of fuzzy sets as well as on axiomatizations, and on categories of fuzzy sets. What we give is a (critical) survey of quite a lot of such approaches which have been offered in the last approximately 35 years. Part I was devoted to model based and to axiomatic approaches; the present Part II is devoted to category theoretic approaches.
-
universes of fuzzy sets and axiomatizations of fuzzy set theory part i model based and axiomatic approaches
Studia Logica, 2006Co-Authors: Siegfried GottwaldAbstract:For classical sets one has with the Cumulative Hierarchy of sets, with axiomatizations like the system ZF, and with the category SET of all sets and mappings standard approaches toward global universes of all sets. We discuss here the corresponding situation for fuzzy set theory.Our emphasis will be on various approaches toward (more or less naively formed)universes of fuzzy sets as well as on axiomatizations, and on categories of fuzzy sets. What we give is a (critical)survey of quite a lot of such approaches which have been offered in the last approximately 35 years. The present Part I is devoted to model based and to axiomatic approaches; the forth-coming Part II will be devoted to category theoretic approaches.
-
Universes of Fuzzy Sets and Axiomatizations of Fuzzy Set Theory. Part I: Model-Based and Axiomatic Approaches ∗
Studia Logica, 2006Co-Authors: Siegfried GottwaldAbstract:For classical sets one has with the Cumulative Hierarchy of sets, with axiomatizations like the system ZF, and with the category SET of all sets and mappings standard approaches toward global universes of all sets. We discuss here the corresponding situation for fuzzy set theory.Our emphasis will be on various approaches toward (more or less naively formed)universes of fuzzy sets as well as on axiomatizations, and on categories of fuzzy sets. What we give is a (critical)survey of quite a lot of such approaches which have been offered in the last approximately 35 years. The present Part I is devoted to model based and to axiomatic approaches; the forth-coming Part II will be devoted to category theoretic approaches.
Jean-pierre Jouannaud - One of the best experts on this subject based on the ideXlab platform.
-
Coq without Type Casts: A Complete Proof of Coq Modulo Theory
2017Co-Authors: Jean-pierre Jouannaud, Pierre-yves StrubAbstract:Incorporating extensional equality into a dependent intensional type system such as the Calculus of Constructions provides with stronger type-checking capabilities and makes the proof development closer to intuition. Since strong forms of extensionality lead to undecidable type-checking, a good trade-off is to extend intensional equality with a decidable first-order theory T, as done in CoqMT, which uses matching modulo T for the weak and strong elimination rules, we call these rules T-elimination. So far, type-checking in CoqMT is known to be decidable in presence of a Cumulative Hierarchy of universes and weak T-elimination. Further, it has been shown by Wang with a formal proof in Coq that consistency is preserved in presence of weak and strong elimination rules, which actually implies consistency in presence of weak and strong T-elimination rules since T is already present in the conversion rule of the calculus. We justify here CoqMT's type-checking algorithm by showing strong normalization as well as the Church-Rosser property of β-reductions augmented with CoqMT's weak and strong T-elimination rules. This therefore concludes successfully the meta-theoretical study of CoqMT.
-
LPAR - Coq without Type Casts: A Complete Proof of Coq Modulo Theory
2017Co-Authors: Jean-pierre Jouannaud, Pierre-yves StrubAbstract:Incorporating extensional equality into a dependent intensional type system such as the Calculus of Constructions provides with stronger type-checking capabilities and makes the proof development closer to intuition. Since strong forms of extensionality lead to undecidable type-checking, a good trade-off is to extend intensional equality with a decidable first-order theory T, as done in CoqMT, which uses matching modulo T for the weak and strong elimination rules, we call these rules T-elimination. So far, type-checking in CoqMT is known to be decidable in presence of a Cumulative Hierarchy of universes and weak T-elimination. Further, it has been shown by Wang with a formal proof in Coq that consistency is preserved in presence of weak and strong elimination rules, which actually implies consistency in presence of weak and strong T-elimination rules since T is already present in the conversion rule of the calculus.We justify here CoqMT’s type-checking algorithm by showing strong normalization as well as the Church-Rosser property of β-reductions augmented with CoqMT’s weak and strong T -elimination rules. This therefore concludes successfully the meta-theoretical study of CoqMT.
-
Untyped Confluence In Dependent Type Theories
2017Co-Authors: Ali Assaf, Jean-pierre Jouannaud, Gilles Dowek, Jiaxiang LiuAbstract:We investigate techniques based on van Oostrom's decreasing diagrams that reduce confluence proofs to the checking of critical pairs in the absence of termination properties, which are useful in dependent type calculi to prove confluence on untyped terms. These techniques are applied to a complex example taken from practice: a faithful encoding in an extension of LF with rewrite rules on objects and types, of the calculus of constructions with a Cumulative Hierarchy of predicative universes above Prop. The rules may be first-order or higher-order, plain or modulo, non-linear on the right or on the left. Variables which occur non-linearly in lefthand sides of rules or in equations must take their values in confined types: in our example, the natural numbers. The first-order rules are assumed to be terminating and confluent modulo some theory: in our example, associativity, commutativity and identity. Critical pairs involving higher-order rules must satisfy van Oostrom's decreasing diagram condition with respect to their indexes taken as labels. Our use of decreasing diagrams yields a modular proof of confluence on open terms. Our encoding of the Hierarchy of universes was obtained by using the MAUDE completion tool twisted to fit our needs. The obtained set of rules exploits all the sophistication of our confluence theorem.
-
Untyped Confluence in Dependent Type Theories
2016Co-Authors: Ali Assaf, Jean-pierre Jouannaud, Gilles Dowek, Jiaxiang LiuAbstract:We investigate techniques based on van Oostrom's decreasing diagrams that reduce confluence proofs to the checking of critical pairs in the absence of termination properties, which are useful in dependent type calculi to prove confluence on untyped terms. These techniques are applied to a complex example originating from practice: a faithful encoding, in an extension of LF with rewrite rules on objects and types, of a subset of the calculus of inductive constructions with a Cumulative Hierarchy of predicative universes above Prop. The rules may be first-order or higher-order, plain or modulo, non-linear on the right or on the left. Variables which occur non-linearly in lefthand sides of rules must take their values in confined types: in our example, the natural numbers. The first-order rules are assumed to be terminating and confluent modulo some theory: in our example, associativity, commutativity and identity. Critical pairs involving higher-order rules must satisfy van Oostrom's decreasing diagram condition wrt their indexes taken as labels.
-
Encoding Proofs in Dedukti: the case of Coq proofs
2016Co-Authors: Ali Assaf, Jean-pierre Jouannaud, Gilles Dowek, Jiaxiang LiuAbstract:A main ambition of the Inria project Dedukti is to serve as a common language for representing and type checking proof objects originating from other proof systems. Encoding these proof objects makes heavy use of the rewriting capabilities of LambdaPiModulo, the formal system on which Dedukti is based. So far, the proofs generated by two automatic proof systems, Zenon and iProver, have been encoded, and can therefore be read and checked by Dedukti. But Dedukti goes far beyond this so-called hammering technique of sending goals to automated provers. Proofs from HOL and Matita can be encoded as well. Some Coq’s proofs can be encoded already, when they do not use universe polymorphism. Our ambition here is to close this remaining gap. To this end, we describe a rewrite-based encoding in LambdaPiModulo of the Calculus of Constructions with a Cumulative Hierarchy of predicative universes above Prop, which is confluent on open terms.
Daniel Fridlender - One of the best experts on this subject based on the ideXlab platform.
-
TLCA - A Type-Checking Algorithm for Martin-Löf Type Theory with Subtyping Based on Normalisation by Evaluation
Lecture Notes in Computer Science, 2013Co-Authors: Daniel Fridlender, Miguel PaganoAbstract:We present a core Martin-Lof type theory with subtyping; it has a Cumulative Hierarchy of universes and the contravariant rule for subtyping between dependent product types. We extend to this calculus the normalisation by evaluation technique defined for a variant of MLTT without subtyping. This normalisation function makes the subtyping relation and type-checking decidable. To our knowledge, this is the first time that the normalisation by evaluation technique has been considered in the context of subtypes, which introduce some subtleties in the proof of correctness of NbE; an important result to prove correctness and completeness of type-checking.