The Experts below are selected from a list of 551079 Experts worldwide ranked by ideXlab platform
Daniel R Licata - One of the best experts on this subject based on the ideXlab platform.
-
internal universes in models of homotopy Type Theory
arXiv: Logic in Computer Science, 2018Co-Authors: Daniel R Licata, Ian Orton, Andrew M Pitts, Bas SpittersAbstract:We begin by recalling the essentially global character of universes in various models of homotopy Type Theory, which prevents a straightforward axiomatization of their properties using the internal language of the presheaf toposes from which these model are constructed. We get around this problem by extending the internal language with a modal operator for expressing properties of global elements. In this setting we show how to construct a universe that classifies the Cohen-Coquand-Huber-Mortberg (CCHM) notion of fibration from their cubical sets model, starting from the assumption that the interval is tiny - a property that the interval in cubical sets does indeed have. This leads to an elementary axiomatization of that and related models of homotopy Type Theory within what we call crisp Type Theory.
-
call by name gradual Type Theory
3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018), 2018Co-Authors: Max S New, Daniel R LicataAbstract:We present gradual Type Theory, a logic and Type Theory for call-by-name gradual typing. We define the central constructions of gradual typing (the dynamic Type, Type casts and Type error) in a novel way, by universal properties relative to new judgments for gradual Type and term dynamism. These dynamism judgements build on prior work in blame calculi and on the "gradual guarantee" theorem of gradual typing. Combined with the ordinary extensionality (eta) principles that Type Theory provides, we show that most of the standard operational behavior of casts is uniquely determined by the gradual guarantee. This provides a semantic justification for the definitions of casts, and shows that non-standard definitions of casts must violate these principles. Our Type Theory is the internal language of a certain class of preorder categories called equipments. We give a general construction of an equipment interpreting gradual Type Theory from a 2-category representing non-gradual Types and programs, which is a semantic analogue of the interpretation of gradual typing using contracts, and use it to build some concrete domain-theoretic models of gradual typing.
-
eilenberg maclane spaces in homotopy Type Theory
Logic in Computer Science, 2014Co-Authors: Daniel R Licata, Eric FinsterAbstract:Homotopy Type Theory is an extension of Martin-Lof Type Theory with principles inspired by category Theory and homotopy Theory. With these extensions, Type Theory can be used to construct proofs of homotopy-theoretic theorems, in a way that is very amenable to computer-checked proofs in proof assistants such as Coq and Agda. In this paper, we give a computer-checked construction of Eilenberg-MacLane spaces. For an abelian group G, an Eilenberg-MacLane space K(G,n) is a space (Type) whose nth homotopy group is G, and whose homotopy groups are trivial otherwise. These spaces are a basic tool in algebraic topology; for example, they can be used to build spaces with specified homotopy groups, and to define the notion of cohomology with coefficients in G. Their construction in Type Theory is an illustrative example, which ties together many of the constructions and methods that have been used in homotopy Type Theory so far.
-
πn sn in homotopy Type Theory
Certified Programs and Proofs, 2013Co-Authors: Daniel R Licata, Guillaume BrunerieAbstract:Homotopy Type Theory [Awodey and Warren, 2009; Voevodsky, 2011] is an extension of Martin-Lof's intensional Type Theory [Martin-Lof, 1975; Nordstrom et al., 1990] with new principles such as Voevodsky's univalence axiom and higher-dimensional inductive Types [Lumsdaine and Shulman, 2013]. These extensions are interesting both from a computer science perspective, where they imbue the equality apparatus of Type Theory with new computational meaning, and from a mathematical perspective, where they allow higher-dimensional mathematics to be expressed cleanly and elegantly in Type Theory.
-
Calculating the Fundamental Group of the Circle in Homotopy Type Theory
2013 28th Annual ACM IEEE Symposium on Logic in Computer Science, 2013Co-Authors: Daniel R Licata, Michael ShulmanAbstract:Recent work on homotopy Type Theory exploits an exciting new correspondence between Martin-Lof's dependent Type Theory and the mathematical disciplines of category Theory and homotopy Theory. The mathematics suggests new principles to add to Type Theory, while the Type Theory can be used in novel ways to do computer-checked proofs in a proof assistant. In this paper, we formalize a basic result in algebraic topology, that the fundamental group of the circle is the integers. Our proof illustrates the new features of homotopy Type Theory, such as higher inductive Types and Voevodsky's univalence axiom. It also introduces a new method for calculating the path space of a Type, which has proved useful in many other examples.
Michael Shulman - One of the best experts on this subject based on the ideXlab platform.
-
a Type Theory for synthetic categories
Higher Structures, 2018Co-Authors: Emily Riehl, Michael ShulmanAbstract:We propose foundations for a synthetic Theory of $(\infty,1)$-categories within homotopy Type Theory. We axiomatize a directed interval Type, then define higher simplices from it and use them to probe the internal categorical structures of arbitrary Types. We define \emph{Segal Types}, in which binary composites exist uniquely up to homotopy; this automatically ensures composition is coherently associative and unital at all dimensions. We define \emph{Rezk Types}, in which the categorical isomorphisms are additionally equivalent to the Type-theoretic identities --- a ``local univalence'' condition. And we define \emph{covariant fibrations}, which are Type families varying functorially over a Segal Type, and prove a ``dependent Yoneda lemma'' that can be viewed as a directed form of the usual elimination rule for identity Types. We conclude by studying homotopically correct adjunctions between Segal Types, and showing that for a functor between Rezk Types to have an adjoint is a mere proposition. To make the bookkeeping in such proofs manageable, we use a three-layered Type Theory with shapes, whose contexts are extended by polytopes within directed cubes, which can be abstracted over using ``extension Types'' that generalize the path-Types of cubical Type Theory. In an appendix, we describe the motivating semantics in the Reedy model structure on bisimplicial sets, in which our Segal and Rezk Types correspond to Segal spaces and complete Segal spaces.
-
modalities in homotopy Type Theory
Logical Methods in Computer Science, 2017Co-Authors: Egbert Rijke, Michael Shulman, Bas SpittersAbstract:Univalent homotopy Type Theory (HoTT) may be seen as a language for the category of $\infty$-groupoids. It is being developed as a new foundation for mathematics and as an internal language for (elementary) higher toposes. We develop the Theory of factorization systems, reflective subuniverses, and modalities in homotopy Type Theory, including their construction using a "localization" higher inductive Type. This produces in particular the ($n$-connected, $n$-truncated) factorization system as well as internal presentations of subtoposes, through lex modalities. We also develop the semantics of these constructions.
-
homotopy Type Theory the logic of space
arXiv: Category Theory, 2017Co-Authors: Michael ShulmanAbstract:This is an introduction to Type Theory, synthetic topology, and homotopy Type Theory from a category-theoretic and topological point of view, written as a chapter for the book "New Spaces for Mathematics and Physics" (ed. Gabriel Catren and Mathieu Anel).
-
the hott library a formalization of homotopy Type Theory in coq
arXiv: Logic in Computer Science, 2016Co-Authors: Andrej Bauer, Michael Shulman, Peter Lefanu Lumsdaine, Matthieu Sozeau, Jason Gross, Bas SpittersAbstract:We report on the development of the HoTT library, a formalization of homotopy Type Theory in the Coq proof assistant. It formalizes most of basic homotopy Type Theory, including univalence, higher inductive Types, and significant amounts of synthetic homotopy Theory, as well as category Theory and modalities. The library has been used as a basis for several independent developments. We discuss the decisions that led to the design of the library, and we comment on the interaction of homotopy Type Theory with recently introduced features of Coq, such as universe polymorphism and private inductive Types.
-
the seifert van kampen theorem in homotopy Type Theory
Computer Science Logic, 2016Co-Authors: Michael ShulmanAbstract:Homotopy Type Theory is a recent research area connecting Type Theory with homotopy Theory by interpreting Types as spaces. In particular, one can prove and mechanize Type-theoretic analogues of homotopy-theoretic theorems, yielding "synthetic homotopy Theory". Here we consider the Seifert-van Kampen theorem, which characterizes the loop structure of spaces obtained by gluing. This is useful in homotopy Theory because many spaces are constructed by gluing, and the loop structure helps distinguish distinct spaces. The synthetic proof showcases many new characteristics of synthetic homotopy Theory, such as the "encode-decode" method, enforced homotopy-invariance, and lack of underlying sets.
Lars Birkedal - One of the best experts on this subject based on the ideXlab platform.
-
guarded dependent Type Theory with coinductive Types
Foundations of Software Science and Computation Structure, 2016Co-Authors: Ales Bizjak, Ranald Clouston, Hans Bugge Grathwohl, Rasmus Ejlers Mogelberg, Lars BirkedalAbstract:We present guarded dependent Type Theory, \(\mathsf {gDTT}\), an extensional dependent Type Theory with a ‘later’ modality and clock quantifiers for programming and proving with guarded recursive and coinductive Types. The later modality is used to ensure the productivity of recursive definitions in a modular, Type based, way. Clock quantifiers are used for controlled elimination of the later modality and for encoding coinductive Types using guarded recursive Types. Key to the development of \(\mathsf {gDTT}\) are novel Type and term formers involving what we call ‘delayed substitutions’. These generalise the applicative functor rules for the later modality considered in earlier work, and are crucial for programming and proving with dependent Types. We show soundness of the Type Theory with respect to a denotational model.
-
guarded cubical Type Theory path equality for guarded recursion
Computer Science Logic, 2016Co-Authors: Lars Birkedal, Bas Spitters, Ales Bizjak, Ranald Clouston, Hans Bugge Grathwohl, Andrea VezzosiAbstract:This paper improves the treatment of equality in guarded dependent Type Theory (GDTT), by combining it with cubical Type Theory (CTT). GDTT is an extensional Type Theory with guarded recursive Types, which are useful for building models of program logics, and for programming and reasoning with coinductive Types. We wish to implement GDTT with decidable Type checking, while still supporting non-trivial equality proofs that reason about the extensions of guarded recursive constructions. CTT is a variation of Martin-Lof Type Theory in which the identity Type is replaced by abstract paths between terms. CTT provides a computational interpretation of functional extensionality, is conjectured to have decidable Type checking, and has an implemented Type checker. Our new Type Theory, called guarded cubical Type Theory, provides a computational interpretation of extensionality for guarded recursive Types. This further expands the foundations of CTT as a basis for formalisation in mathematics and computer science. We present examples to demonstrate the expressivity of our Type Theory, all of which have been checked using a protoType Type-checker implementation, and present semantics in a presheaf category.
Ales Bizjak - One of the best experts on this subject based on the ideXlab platform.
-
denotational semantics for guarded dependent Type Theory
Mathematical Structures in Computer Science, 2020Co-Authors: Ales Bizjak, Rasmus Ejlers MogelbergAbstract:We present a new model of guarded dependent Type Theory (GDTT), a Type Theory with guarded recursion and multiple clocks in which one can program with and reason about coinductive Types. Productivity of recursively defined coinductive programs and proofs is encoded in Types using guarded recursion and can therefore be checked modularly, unlike the syntactic checks implemented in modern proof assistants. The model is based on a category of covariant presheaves over a category of time objects, and quantification over clocks is modelled using a presheaf of clocks. To model the clock irrelevance axiom, crucial for programming with coinductive Types, Types must be interpreted as presheaves internally right orthogonal to the object of clocks. In the case of dependent Types, this translates to a lifting condition similar to the one found in homotopy theoretic models of Type Theory, but here with an additional requirement of uniqueness of lifts. Since the universes defined by the standard Hofmann–Streicher construction in this model do not satisfy this property, the universes in GDTT must be indexed by contexts of clock variables. We show how to model these universes in such a way that inclusions of clock contexts give rise to inclusions of universes commuting with Type operations on the nose.
-
denotational semantics for guarded dependent Type Theory
arXiv: Logic in Computer Science, 2018Co-Authors: Ales Bizjak, Rasmus Ejlers MogelbergAbstract:We present a new model of Guarded Dependent Type Theory (GDTT), a Type Theory with guarded recursion and multiple clocks in which one can program with, and reason about coinductive Types. Productivity of recursively defined coinductive programs and proofs is encoded in Types using guarded recursion, and can therefore be checked modularly, unlike the syntactic checks implemented in modern proof assistants. The model is based on a category of covariant presheaves over a category of time objects, and quantification over clocks is modelled using a presheaf of clocks. To model the clock irrelevance axiom, crucial for programming with coinductive Types, Types must be interpreted as presheaves orthogonal to the object of clocks. In the case of dependent Types, this translates to a lifting condition similar to the one found in homotopy theoretic models of Type Theory, but here with an additional requirement of uniqueness of lifts. Since the universes defined by the standard Hofmann-Streicher construction in this model do not satisfy this property, the universes in GDTT must be indexed by contexts of clock variables. We show how to model these universes in such a way that inclusions of clock contexts give rise to inclusions of universes commuting with Type operations on the nose.
-
guarded dependent Type Theory with coinductive Types
Foundations of Software Science and Computation Structure, 2016Co-Authors: Ales Bizjak, Ranald Clouston, Hans Bugge Grathwohl, Rasmus Ejlers Mogelberg, Lars BirkedalAbstract:We present guarded dependent Type Theory, \(\mathsf {gDTT}\), an extensional dependent Type Theory with a ‘later’ modality and clock quantifiers for programming and proving with guarded recursive and coinductive Types. The later modality is used to ensure the productivity of recursive definitions in a modular, Type based, way. Clock quantifiers are used for controlled elimination of the later modality and for encoding coinductive Types using guarded recursive Types. Key to the development of \(\mathsf {gDTT}\) are novel Type and term formers involving what we call ‘delayed substitutions’. These generalise the applicative functor rules for the later modality considered in earlier work, and are crucial for programming and proving with dependent Types. We show soundness of the Type Theory with respect to a denotational model.
-
guarded cubical Type Theory path equality for guarded recursion
Computer Science Logic, 2016Co-Authors: Lars Birkedal, Bas Spitters, Ales Bizjak, Ranald Clouston, Hans Bugge Grathwohl, Andrea VezzosiAbstract:This paper improves the treatment of equality in guarded dependent Type Theory (GDTT), by combining it with cubical Type Theory (CTT). GDTT is an extensional Type Theory with guarded recursive Types, which are useful for building models of program logics, and for programming and reasoning with coinductive Types. We wish to implement GDTT with decidable Type checking, while still supporting non-trivial equality proofs that reason about the extensions of guarded recursive constructions. CTT is a variation of Martin-Lof Type Theory in which the identity Type is replaced by abstract paths between terms. CTT provides a computational interpretation of functional extensionality, is conjectured to have decidable Type checking, and has an implemented Type checker. Our new Type Theory, called guarded cubical Type Theory, provides a computational interpretation of extensionality for guarded recursive Types. This further expands the foundations of CTT as a basis for formalisation in mathematics and computer science. We present examples to demonstrate the expressivity of our Type Theory, all of which have been checked using a protoType Type-checker implementation, and present semantics in a presheaf category.
Steve Awodey - One of the best experts on this subject based on the ideXlab platform.
-
natural models of homotopy Type Theory
Mathematical Structures in Computer Science, 2018Co-Authors: Steve AwodeyAbstract:The notion of a natural model of Type Theory is defined in terms of that of a representable natural transfomation of presheaves. It is shown that such models agree exactly with the concept of a category with families in the sense of Dybjer, which can be regarded as an algebraic formulation of Type Theory. We determine conditions for such models to satisfy the inference rules for dependent sums Σ, dependent products Π, and intensional identity Types Id, as used in homotopy Type Theory. It is then shown that a category admits such a model if it has a class of maps that behave like the abstract fibrations in axiomatic homotopy Theory: they should be stable under pullback, closed under composition and relative products, and there should be weakly orthogonal factorizations into the class. It follows that many familiar settings for homotopy Theory also admit natural models of the basic system of homotopy Type Theory.
-
homotopy initial algebras in Type Theory
Journal of the ACM, 2017Co-Authors: Steve Awodey, Nicola Gambino, Kristina SojakovaAbstract:We investigate inductive Types in Type Theory, using the insights provided by homotopy Type Theory and univalent foundations of mathematics. We do so by introducing the new notion of a homotopy-initial algebra. This notion is defined by a purely Type-theoretic contractibility condition that replaces the standard, category-theoretic universal property involving the existence and uniqueness of appropriate morphisms. Our main result characterizes the Types that are equivalent to W-Types as homotopy-initial algebras.
-
homotopy Type Theory
Indian Conference on Logic and Its Applications, 2015Co-Authors: Steve AwodeyAbstract:Homotopy Type Theory is a new, homotopical interpretation of constructive Type Theory. It forms the basis of the recently proposed Univalent Foundations of Mathematics program. Combined with a computational proof assistant, and including a new foundational axiom – the Univalence Axiom – this program has the potential to shift the theoretical foundations of mathematics and computer science, and to affect the practice of working scientists. This talk will survey the field and report on some of the recent developments.
-
voevodsky s univalence axiom in homotopy Type Theory
Notices of the American Mathematical Society, 2013Co-Authors: Steve Awodey, Alvaro Pelayo, Michael A WarrenAbstract:In this short note we give a glimpse of homotopy Type Theory, a new field of mathematics at the intersection of algebraic topology and mathematical logic, and we explain Vladimir Voevodsky’s univalent interpretation of it. This interpretation has given rise to the univalent foundations program, which is the topic of the current special year at the Institute for Advanced Study. The Institute for Advanced Study in Princeton is hosting a special program during the academic year 2012-2013 on a new research theme that is based on recently discovered connections between homotopy Theory, a branch of algebraic topology, and Type Theory, a branch of mathematical logic and theoretical computer science. In this brief paper our goal is to take a glance at these developments. For those readers who would like to learn more about them, we recommend a number of references throughout. Type Theory was invented by Bertrand Russell [20], but it was first developed as a rigorous formal system by Alonzo Church [3, 4, 5]. It now has numerous applications in computer science, especially in the Theory of programming languages [19]. Per Martin-Lof [15, 11, 13, 14], among others, developed a generalization of Church’s system which is now usually called dependent, constructive, or simply Martin-Lof Type Theory; this is the system that we consider here. It was originally intended as a rigorous framework for constructive mathematics. In Type Theory objects are classified using a primitive notion of Type, similar to the data-Types used in programming languages. And as in programming languages, these elaborately structured Types can be used to express detailed specifications of the objects classified, giving rise to principles of reasoning about them. To take a simple example, the objects of a product Type A × B are known to be of the form 〈a, b〉, and so one automatically knows how to form them and how to decompose them. This aspect of Type
-
Inductive Types in Homotopy Type Theory
2012 27th Annual IEEE Symposium on Logic in Computer Science, 2012Co-Authors: Steve Awodey, Nicola Gambino, Kristina SojakovaAbstract:Homotopy Type Theory is an interpretation of Martin-Lof's constructive Type Theory into abstract homotopy Theory. There results a link between constructive mathematics and algebraic topology, providing topological semantics for intensional systems of Type Theory as well as a computational approach to algebraic topology via Type Theory-based proof assistants such as Coq. The present work investigates inductive Types in this setting. Modified rules for inductive Types, including Types of well-founded trees, or W-Types, are presented, and the basic homotopical semantics of such Types are determined. Proofs of all results have been formally verified by the Coq proof assistant, and the proof scripts for this verification form an essential component of this research.
