This monograph is a study of the category of polynomial endofunctors on the category of sets and its applications to modeling interaction protocols and dynamical systems. We assume basic categorical …
This monograph is a study of the category of polynomial endofunctors on the category of sets and its applications to modeling interaction protocols and dynamical systems. We assume basic categorical background and build the categorical theory from the ground up, highlighting pictorical techniques and concrete examples to build intuition and provide applications.
The previous chapter has introduced several examples of coalgebras and has illustrated basic coalgebraic notions such as behaviour and invariance (for those examples). This chapter will go deeper into the …
The previous chapter has introduced several examples of coalgebras and has illustrated basic coalgebraic notions such as behaviour and invariance (for those examples). This chapter will go deeper into the study of the area of coalgebra, introducing some basic notions, definitions and terminology. It will first discuss several fundamental set theoretic constructions, such as products, coproducts, exponents and powersets in a suitably abstract (categorical) language. These constructs are used to define a collection of elementary functors, the so-called polynomial functors. As will be shown in Section 2.2, this class of functors is rich enough to capture many examples of interesting coalgebras, including deterministic and non-deterministic automata. One of the attractive features of polynomial functors is that almost all of them have a final coalgebra – except when the (non-finite) powerset occurs. The unique map into a final coalgebra will appear as behaviour morphism, mapping a state to its behaviour. The two last sections of this chapter, Sections 2.4 and 2.5, provide additional background information, namely on algebras (as duals of coalgebras) and on adjunctions. The latter form a fundamental categorical notion describing backand- forth translations that occur throughout mathematics.
Awodey, later with Newstead, showed how polynomial pseudomonads $(u,1,\Sigma)$ with extra structure (termed "natural models" by Awodey) hold within them the categorical semantics for dependent type theory. Their work presented …
Awodey, later with Newstead, showed how polynomial pseudomonads $(u,1,\Sigma)$ with extra structure (termed "natural models" by Awodey) hold within them the categorical semantics for dependent type theory. Their work presented these ideas clearly but ultimately led them outside of the category of polynomial functors in order to explain all of the structure possessed by such models of type theory. This paper builds off that work -- explicating the categorical semantics of dependent type theory by axiomatizing them \emph{entirely} in the language of polynomial functors. In order to handle the higher-categorical coherences required for such an explanation, we work with polynomial functors internally in the language of Homotopy Type Theory, which allows for higher-dimensional structures such as pseudomonads, etc. to be expressed purely in terms of the structure of a suitably-chosen $\infty$-category of polynomial functors. The move from set theory to Homotopy Type Theory thus has a twofold effect of enabling a simpler exposition of natural models, which is at the same time amenable to formalization in a proof assistant, such as Agda. Moreover, the choice to remain firmly within the setting of polynomial functors reveals many additional structures of natural models that were otherwise left implicit or not considered by Awodey \& Newstead. Chief among these, we highlight the fact that every polynomial pseudomonad $(u,1,\Sigma)$ as above that is also equipped with structure to interpret dependent product types gives rise to a self-distributive law $u \triangleleft u\to u \triangleleft u$, which witnesses the usual distributive law of dependent products over dependent sums.
Abstract In earlier work, the second author showed that a closed subset of a polynomial functor can always be defined by finitely many polynomial equations. In follow-up work on $${\text …
Abstract In earlier work, the second author showed that a closed subset of a polynomial functor can always be defined by finitely many polynomial equations. In follow-up work on $${\text {GL}}_\infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mtext>GL</mml:mtext> <mml:mi>∞</mml:mi> </mml:msub> </mml:math> -varieties, Bik–Draisma–Eggermont–Snowden showed, among other things, that in characteristic zero every such closed subset is the image of a morphism whose domain is the product of a finite-dimensional affine variety and a polynomial functor. In this paper, we show that both results can be made algorithmic: there exists an algorithm $$\textbf{implicitise}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>implicitise</mml:mi> </mml:math> that takes as input a morphism into a polynomial functor and outputs finitely many equations defining the closure of the image; and an algorithm $$\textbf{parameterise}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>parameterise</mml:mi> </mml:math> that takes as input a finite set of equations defining a closed subset of a polynomial functor and outputs a morphism whose image is that closed subset.
In earlier work, the second author showed that a closed subset of a polynomial functor can always be defined by finitely many polynomial equations. In follow-up work on $\operatorname{GL}\nolimits_{\infty}$-varieties, Bik-Draisma-Eggermont-Snowden …
In earlier work, the second author showed that a closed subset of a polynomial functor can always be defined by finitely many polynomial equations. In follow-up work on $\operatorname{GL}\nolimits_{\infty}$-varieties, Bik-Draisma-Eggermont-Snowden showed, among other things, that in characteristic zero every such closed subset is the image of a morphism whose domain is the product of a finite-dimensional affine variety and a polynomial functor. In this paper, we show that both results can be made algorithmic: there exists an algorithm $\mathbf{implicitise}$ that takes as input a morphism into a polynomial functor and outputs finitely many equations defining the closure of the image; and an algorithm $\mathbf{parameterise}$ that takes as input a finite set of equations defining a closed subset of a polynomial functor and outputs a morphism whose image is that closed subset.
A syntax and semantics of types, terms and formulas for coalgebras of polynomial functors is developed, extending earlier work [4] on monomial coalgebras to include functors constructed using coproducts. A …
A syntax and semantics of types, terms and formulas for coalgebras of polynomial functors is developed, extending earlier work [4] on monomial coalgebras to include functors constructed using coproducts. A modified ultrapower construction for polynomial coalgebras is introduced, adapting the conventional ultrapower to retain only those states that evaluate observable terms in a standard way. A special role is played by terms that take observable values and are “rigid”: their free variables do not occur in any state-valued subterm. The following “co-Birkhoff” theorem is proved: a class of polynomial coalgebras is definable by Boolean combinations of equations between rigid terms iff the class is closed under disjoint unions, images of bisimulations, and observable ultrapowers.
We study polynomial functors over locally cartesian closed categories. After setting up the basic theory, we show how polynomial functors assemble into a double category, in fact a framed bicategory. …
We study polynomial functors over locally cartesian closed categories. After setting up the basic theory, we show how polynomial functors assemble into a double category, in fact a framed bicategory. We show that the free monad on a polynomial endofunctor is polynomial. The relationship with operads and other related notions is explored.
Given a locally cartesian closed category E, a polynomial (s,p,t) may be defined as a diagram consisting of three arrows in E of a certain shape. In this paper we …
Given a locally cartesian closed category E, a polynomial (s,p,t) may be defined as a diagram consisting of three arrows in E of a certain shape. In this paper we define the homogeneous and monomial terms comprising a polynomial (s,p,t) and give sufficient conditions on E such that the homogeneous terms of polynomials exist. We use these homogeneous terms to exhibit an infinite family of coreflection adjunctions between polynomials and homogeneous polynomials of order n. We show that every locally cartesian closed category E with a strict initial object admits a negation operator and a (dense,closed) orthogonal factorization system. We see that both terms and derivatives of polynomial functors are constructed from this negation operator, and that if one takes the localization of E by the class W of dense monomorphisms, then derivatives of all polynomial functors exist. All results are shown formally using only the theory of extensive categories and distributivity pullbacks.
We prove a generalisation to any characteristic of a result of Macdonald that describes strict polynomial functors in characteristic zero in terms of representations of the groupoid of finite sets …
We prove a generalisation to any characteristic of a result of Macdonald that describes strict polynomial functors in characteristic zero in terms of representations of the groupoid of finite sets and bijections. Our result will give an analogous description in terms of finite multisets and an extension of the notion of bijection appropriate for multisets. A projected application is to the description of strict polynomial monads that will give a notion generalising (linear algebra) operads.
Abstract The concept of a T-discrete object is a generalization of the notion of discrete spaces in concrete categories. In this paper. T-discrete objects are used to define discrete functors. …
Abstract The concept of a T-discrete object is a generalization of the notion of discrete spaces in concrete categories. In this paper. T-discrete objects are used to define discrete functors. Characterizations of discrete functors are given and their relation to other important functors are studied. A faithful functor T: A → X is discrete iff the full subcategory B of A consisting of all T-discrete objects is (X-iso)-coreflective in A. It follows that the existence of bicoreflective subcategories is equivalent to the existence of suitable discrete functors. Finally, necessary and sufficient conditions are found such that for a given functor T: A → X, the full subcategory B of A consisting of all T-discrete A-objects is monocoreflective in A.
Polynomial bounds and tail estimates are derived for additive random recursive sequences, which typically arise as functionals of recursive structures, of random trees, or in recursive algorithms. In particular they …
Polynomial bounds and tail estimates are derived for additive random recursive sequences, which typically arise as functionals of recursive structures, of random trees, or in recursive algorithms. In particular they arise as parameters of divide and conquer type algorithms. We mainly focuss on polynomial tails that arise due to heavy tail bounds of the toll term and the starting distributions. Besides estimating the tail probability directly we use a modified version of a theorem from regular variation theory. This theorem states that upper bounds on the asymptotic tail probability can be derived from upper bounds of the Laplace―Stieltjes transforms near zero.
Polynomial functors were introduced by Professors Eilenberg and Mac Lane in 1954, who used them to study certain homology rings. Strict polynomial functors were invented by Professors Friedlander a ...
Polynomial functors were introduced by Professors Eilenberg and Mac Lane in 1954, who used them to study certain homology rings. Strict polynomial functors were invented by Professors Friedlander a ...
We investigate fundamental properties of adjoint functors to the precomposition functor in the category of strict polynomial functors.
We investigate fundamental properties of adjoint functors to the precomposition functor in the category of strict polynomial functors.
Journal Article Derived Kan Extension for Strict Polynomial Functors Get access Marcin Chałupnik Marcin Chałupnik 1Institute of Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland2Institute of Mathematics PAN, …
Journal Article Derived Kan Extension for Strict Polynomial Functors Get access Marcin Chałupnik Marcin Chałupnik 1Institute of Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland2Institute of Mathematics PAN, ul. Śniadeckich 8, 00-956 Warsaw, Poland Correspondence to be sent to: [email protected] Search for other works by this author on: Oxford Academic Google Scholar International Mathematics Research Notices, Volume 2015, Issue 20, 2015, Pages 10017–10040, https://doi.org/10.1093/imrn/rnu269 Published: 16 January 2015 Article history Received: 07 August 2014 Revision received: 20 November 2014 Accepted: 03 December 2014 Published: 16 January 2015
We investigate fundamental properties of adjoint functors to the precomposition functor in the category of strict polynomial functors.
We investigate fundamental properties of adjoint functors to the precomposition functor in the category of strict polynomial functors.
We explore the relationship between polynomial functors and (rooted) trees. In the first part we use polynomial functors to derive a new convenient formalism for trees, and obtain a natural …
We explore the relationship between polynomial functors and (rooted) trees. In the first part we use polynomial functors to derive a new convenient formalism for trees, and obtain a natural and conceptual construction of the category $\Omega$ of Moerdijk and Weiss; its main properties are described in terms of some factorisation systems. Although the constructions are motivated and explained in terms of polynomial functors, they all amount to elementary manipulations with finite sets. In the second part we describe polynomial endofunctors and monads as structures built from trees, characterising the images of several nerve functors from polynomial endofunctors and monads into presheaves on categories of trees. Polynomial endofunctors and monads over a base are characterised by a sheaf condition on categories of decorated trees. In the absolute case, one further condition is needed, a certain projectivity condition, which serves also to characterise polynomial endofunctors and monads among (coloured) collections and operads.
We explore the relationship between polynomial functors and (rooted) trees. In the first part, we use polynomial functors to derive a new convenient formalism for trees, and obtain a natural …
We explore the relationship between polynomial functors and (rooted) trees. In the first part, we use polynomial functors to derive a new convenient formalism for trees, and obtain a natural and conceptual construction of the category Ω of Moerdijk and Weiss; its main properties are described in terms of some factorization systems. Although the constructions are motivated and explained in terms of polynomial functors, they all amount to elementary manipulations with finite sets. In the second part, we describe polynomial endofunctors and monads as structures built from trees, characterizing the images of several nerve functors from polynomial endofunctors and monads into presheaves on categories of trees. Polynomial endofunctors and monads over a base are characterized by a sheaf condition on categories of decorated trees. In the absolute case, one further condition is needed, a certain projectivity condition, which serves also to characterize polynomial endofunctors and monads among (colored) collections and operads.
We explore the relationship between polynomial functors and (rooted) trees. In the first part we use polynomial functors to derive a new convenient formalism for trees, and obtain a natural …
We explore the relationship between polynomial functors and (rooted) trees. In the first part we use polynomial functors to derive a new convenient formalism for trees, and obtain a natural and conceptual construction of the category $\Omega$ of Moerdijk and Weiss; its main properties are described in terms of some factorisation systems. Although the constructions are motivated and explained in terms of polynomial functors, they all amount to elementary manipulations with finite sets. In the second part we describe polynomial endofunctors and monads as structures built from trees, characterising the images of several nerve functors from polynomial endofunctors and monads into presheaves on categories of trees. Polynomial endofunctors and monads over a base are characterised by a sheaf condition on categories of decorated trees. In the absolute case, one further condition is needed, a certain projectivity condition, which serves also to characterise polynomial endofunctors and monads among (coloured) collections and operads.
We show that the essentially algebraic theory of generalized algebraic theories, regarded as a category with finite limits, has a universal exponentiable arrow in the sense that any exponentiable arrow …
We show that the essentially algebraic theory of generalized algebraic theories, regarded as a category with finite limits, has a universal exponentiable arrow in the sense that any exponentiable arrow in any category with finite limits is the image of the universal exponentiable arrow by an essentially unique functor.
It is commonly believed that algebraic notions of type theory support only universes à la Tarski, and that universes à la Russell must be removed by elaboration. We clarify the …
It is commonly believed that algebraic notions of type theory support only universes à la Tarski, and that universes à la Russell must be removed by elaboration. We clarify the state of affairs, recalling the details of Cartmell's discipline of _generalized algebraic theory_, showing how to formulate an algebraic version of Coquand's cumulative cwfs with universes à la Russell. To demonstrate the power of algebraic techniques, we sketch a purely algebraic proof of canonicity for Martin-Löf Type Theory with universes, dependent function types, and a base type with two constants.
We develop algebraic models of simple type theories, laying out a framework that extends universal algebra to incorporate both algebraic sorting and variable binding. Examples of simple type theories include …
We develop algebraic models of simple type theories, laying out a framework that extends universal algebra to incorporate both algebraic sorting and variable binding. Examples of simple type theories include the unityped and simply-typed λ-calculi, the computational λ-calculus, and predicate logic. Simple type theories are given models in presheaf categories, with structure specified by algebras of polynomial endofunctors that correspond to natural deduction rules. Initial models, which we construct, abstractly describe the syntax of simple type theories. Taking substitution structure into consideration, we further provide sound and complete semantics in structured cartesian multicategories. This development generalises Lambek's correspondence between the simply-typed λ-calculus and cartesian-closed categories, to arbitrary simple type theories.
We contribute XTT, a cubical reconstruction of Observational Type Theory which extends Martin-Löf's intensional type theory with a dependent equality type that enjoys function extensionality and a judgmental version of …
We contribute XTT, a cubical reconstruction of Observational Type Theory which extends Martin-Löf's intensional type theory with a dependent equality type that enjoys function extensionality and a judgmental version of the unicity of identity types principle (UIP): any two elements of the same equality type are judgmentally equal. Moreover, we conjecture that the typing relation can be decided in a practical way. In this paper, we establish an algebraic canonicity theorem using a novel cubical extension (independently proposed by Awodey) of the logical families or categorical gluing argument inspired by Coquand and Shulman: every closed element of boolean type is derivably equal to either 'true' or 'false'.
We develop algebraic models of simple type theories, laying out a framework that extends universal algebra to incorporate both algebraic sorting and variable binding. Examples of simple type theories include …
We develop algebraic models of simple type theories, laying out a framework that extends universal algebra to incorporate both algebraic sorting and variable binding. Examples of simple type theories include the unityped and simply-typed $\lambda$-calculi, the computational $\lambda$-calculus, and predicate logic.
Simple type theories are given models in presheaf categories, with structure specified by algebras of polynomial endofunctors that correspond to natural deduction rules. Initial models, which we construct, abstractly describe the syntax of simple type theories. Taking substitution structure into consideration, we further provide sound and complete semantics in structured cartesian multicategories. This development generalises Lambek's correspondence between the simply-typed $\lambda$-calculus and cartesian-closed categories, to arbitrary simple type theories.
We assemble polynomials in a locally cartesian closed category into a tricategory, allowing us to define the notion of a polynomial pseudomonad and polynomial pseudoalgebra. Working in the context of …
We assemble polynomials in a locally cartesian closed category into a tricategory, allowing us to define the notion of a polynomial pseudomonad and polynomial pseudoalgebra. Working in the context of natural models of type theory, we prove that dependent type theories admitting a unit type and dependent sum types give rise to polynomial pseudomonads, and that those admitting dependent product types give rise to polynomial pseudoalgebras.
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 …
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.
Birkedal et al. recently introduced dependent right adjoints as an important class of (non-fibered) modalities in type theory. We observe that several aspects of their calculus are left underdeveloped and …
Birkedal et al. recently introduced dependent right adjoints as an important class of (non-fibered) modalities in type theory. We observe that several aspects of their calculus are left underdeveloped and that it cannot serve as an internal language. We resolve these problems by assuming that the modal context operator is a parametric right adjoint. We show that this hitherto unrecognized structure is common. Based on these discoveries we present a new well-behaved Fitch-style multimodal type theory, which can be used as an internal language. Finally, we apply this syntax to guarded recursion and parametricity.
We develop bicategory theory in univalent foundations. Guided by the notion of univalence for (1-)categories studied by Ahrens, Kapulkin, and Shulman, we define and study univalent bicategories. To construct examples …
We develop bicategory theory in univalent foundations. Guided by the notion of univalence for (1-)categories studied by Ahrens, Kapulkin, and Shulman, we define and study univalent bicategories. To construct examples of univalent bicategories, we develop the notion of `displayed bicategories', an analog of displayed 1-categories introduced by Ahrens and Lumsdaine. Displayed bicategories allow us to construct univalent bicategories in a modular fashion. We demonstrate the applicability of this notion, and prove that several bicategories of interest are univalent. Among these are the bicategory of univalent categories with families and the bicategory of pseudofunctors between univalent bicategories. Furthermore, we show that every bicategory with univalent hom-category is weakly equivalent to a univalent bicategory. All of our work is formalized in Coq as part of the UniMath library of univalent mathematics.
Abstract When working in homotopy type theory and univalent foundations, the traditional role of the category of sets, $\mathcal{Set}$ , is replaced by the category $\mathcal{hSet}$ of homotopy sets (h-sets); …
Abstract When working in homotopy type theory and univalent foundations, the traditional role of the category of sets, $\mathcal{Set}$ , is replaced by the category $\mathcal{hSet}$ of homotopy sets (h-sets); types with h-propositional identity types. Many of the properties of $\mathcal{Set}$ hold for $\mathcal{hSet}$ ((co)completeness, exactness, local cartesian closure, etc.). Notably, however, the univalence axiom implies that $\mathsf{Ob}\,\mathcal{hSet}$ is not itself an h-set, but an h-groupoid. This is expected in univalent foundations, but it is sometimes useful to also have a stricter universe of sets, for example, when constructing internal models of type theory. In this work, we equip the type of iterative sets $\mathsf{V}^0$ , due to Gylterud ((2018). The Journal of Symbolic Logic 83 (3) 1132–1146) as a refinement of the pioneering work of Aczel ((1978). Logic Colloquium’77 , Studies in Logic and the Foundations of Mathematics, vol. 96, Elsevier, 55–66.) on universes of sets in type theory, with the structure of a Tarski universe and show that it satisfies many of the good properties of h-sets. In particular, we organize $\mathsf{V}^0$ into a (non-univalent strict) category and prove that it is locally cartesian closed. This enables us to organize it into a category with families with the structure necessary to model extensional type theory internally in HoTT/UF. We do this in a rather minimal univalent type theory with W-types, in particular we do not rely on any HITs, or other complex extensions of type theory. Furthermore, the construction of $\mathsf{V}^0$ and the model is fully constructive and predicative, while still being very convenient to work with as the decoding from $\mathsf{V}^0$ into h-sets commutes definitionally for all type constructors. Almost all of the paper has been formalized in $\texttt{Agda}$ using the $\texttt{agda}$ - $\texttt{unimath}$ library of univalent mathematics.
We develop bicategory theory in univalent foundations. Guided by the notion of univalence for (1-)categories studied by Ahrens, Kapulkin, and Shulman, we define and study univalent bicategories. To construct examples …
We develop bicategory theory in univalent foundations. Guided by the notion of univalence for (1-)categories studied by Ahrens, Kapulkin, and Shulman, we define and study univalent bicategories. To construct examples of univalent bicategories in a modular fashion, we develop displayed bicategories, an analog of displayed 1-categories introduced by Ahrens and Lumsdaine. We demonstrate the applicability of this notion, and prove that several bicategories of interest are univalent. Among these are the bicategory of univalent categories with families and the bicategory of pseudofunctors between univalent bicategories. Furthermore, we show that every bicategory with univalent hom-categories is weakly equivalent to a univalent bicategory. All of our work is formalized in Coq as part of the UniMath library of univalent mathematics.
We show that the essentially algebraic theory of a generalized algebraic theory, regarded as a category with finite limits, has a universal exponentiable arrow in the sense that any exponentiable …
We show that the essentially algebraic theory of a generalized algebraic theory, regarded as a category with finite limits, has a universal exponentiable arrow in the sense that any exponentiable arrow in any category with finite limits is the image of the universal exponentiable arrow by an essentially unique functor.
It has been observed [Awo16, Fio12] that the rules governing the essentially algebraic notion of a category with families [Dyb96] precisely match those of a representable natural transformation between presheaves. …
It has been observed [Awo16, Fio12] that the rules governing the essentially algebraic notion of a category with families [Dyb96] precisely match those of a representable natural transformation between presheaves. This provides us with a natural, functorial description of essentially algebraicobjects which are used to model dependent type theory—following Steve Awodey, we call them natural models.We can view natural models from several different viewpoints, of which we focus on three in this thesis. First, natural models are essentially algebraic, meaning that they can be described by specifying operations between sorts, subject to equational axioms—this allows us to assemblenatural models into a category with certain beneficial properties. Second, since natural models are natural transformations between presheaves, they are morphisms in a locally cartesian closed category, meaning that they can be regarded as polynomials [GK13]. Third, since natural models admit interpretations of dependent type theory, we can use them to provide a functorial semantics.This thesis develops the theory of natural models in three new directions by viewing them in these three ways.Natural models as essentially algebraic objects. The first development of the thesis is to bridge the gap between the presentation of natural models as models of an essentially algebraic theory, and the functorial characterisation of natural models as representable natural transformations. Wedemonstrate that the functorial characterisations of natural models and morphisms thereof align as we hope with the essentially algebraic characterisations. Natural models as polynomials. The next development is to apply the theory of polynomials in locally cartesian closed categories to natural models. In doing so, we are able to characterise theconditions under which a natural model admits certain type theoretic structure, and under which a natural transformation is representable, entirely in the internal language of a locally cartesian closed category. In particular, we prove that a natural model admits a unit type and dependentsum types if and only if it is a polynomial pseudomonad, that it admits dependent product types if and only if it is a pseudoalgebra, and we prove various facts about the full internal subcategory associated with a natural model. Natural models as models of dependent type theory. The final development of the thesis is to demonstrate their suitability as a tool for the semantics of dependent type theory. We build the term model of a particularly simple dependent type theory and prove that it satisfies the appropriate universal property, and then we proceed by describing how to turn an arbitrary natural model intoone admitting additional type theoretic structure in an algebraically free way.
We study the notion of a "differential 2-rig", a category R with coproducts and a monoidal structure distributing over them, also equipped with an endofunctor D : R -> R …
We study the notion of a "differential 2-rig", a category R with coproducts and a monoidal structure distributing over them, also equipped with an endofunctor D : R -> R that satisfies a categorified analogue of the Leibniz rule. This is intended as a tool to unify various applications of such categories to computer science, algebraic topology, and enumerative combinatorics. The theory of differential 2-rigs has a geometric flavour but boils down to a specialization of the theory of tensorial strengths on endofunctors; this builds a surprising connection between apparently disconnected fields. We build "free 2-rigs" on a signature, and we prove various initiality results: for example, a certain category of colored species is the free differential 2-rig on a single generator.
We argue that locally Cartesian closed categories form a suitable doctrine for defining dependent type theories, including non-extensional ones. Using the theory of sketches, one may define syntactic categories for …
We argue that locally Cartesian closed categories form a suitable doctrine for defining dependent type theories, including non-extensional ones. Using the theory of sketches, one may define syntactic categories for type theories in a style that resembles the use of Martin-Lof's Logical Framework, following the as types principle. The concentration of type theories into their locally Cartesian closed categories of judgments is particularly convenient for proving syntactic metatheorems by semantic means (canonicity, normalization, etc.). Perhaps surprisingly, the notion of a context plays no role in the definitions of type theories in this sense, but the structure of a class of display maps can be imposed on a theory post facto wherever needed, as advocated by the Edinburgh school and realized by the %worlds declarations of the Twelf proof assistant.
Uemura has proposed representable map categories together with a stratified logical framework for similar purposes. The stratification in Uemura's framework restricts the use of dependent products to be strictly positive, in contrast to the tradition of Martin-Lof's logical framework and Schroeder-Heister's analysis of higher-level deductions. We prove a semantic adequacy result for locally Cartesian closed categories relative to Uemura's representable map categories: if a theory is definable in the framework of Uemura, the locally Cartesian closed category that it generates is a conservative (fully faithful) extension of its syntactic representable map category. On this basis, we argue for the use of locally Cartesian closed categories as a simpler alternative to Uemura's representable map categories.
The Univalence Principle is the statement that equivalent mathematical structures are indistinguishable. We prove a general version of this principle that applies to all set-based, categorical, and higher-categorical structures defined …
The Univalence Principle is the statement that equivalent mathematical structures are indistinguishable. We prove a general version of this principle that applies to all set-based, categorical, and higher-categorical structures defined in a non-algebraic and space-based style, as well as models of higher-order theories such as topological spaces. In particular, we formulate a general definition of indiscernibility for objects of any such structure, and a corresponding univalence condition that generalizes Rezk's completeness condition for Segal spaces and ensures that all equivalences of structures are levelwise equivalences.
Our work builds on Makkai's First-Order Logic with Dependent Sorts, but is expressed in Voevodsky's Univalent Foundations (UF), extending previous work on the Structure Identity Principle and univalent categories in UF. This enables indistinguishability to be expressed simply as identification, and yields a formal theory that is interpretable in classical homotopy theory, but also in other higher topos models. It follows that Univalent Foundations is a fully equivalence-invariant foundation for higher-categorical mathematics, as intended by Voevodsky.
We introduce MTT, a dependent type theory which supports multiple modalities. MTT is parametrized by a mode theory which specifies a collection of modes, modalities, and transformations between them. We …
We introduce MTT, a dependent type theory which supports multiple modalities. MTT is parametrized by a mode theory which specifies a collection of modes, modalities, and transformations between them. We show that different choices of mode theory allow us to use the same type theory to compute and reason in many modal situations, including guarded recursion, axiomatic cohesion, and parametric quantification. We reproduce examples from prior work in guarded recursion and axiomatic cohesion -- demonstrating that MTT constitutes a simple and usable syntax whose instantiations intuitively correspond to previous handcrafted modal type theories. In some cases, instantiating MTT to a particular situation unearths a previously unknown type theory that improves upon prior systems. Finally, we investigate the metatheory of MTT. We prove the consistency of MTT and establish canonicity through an extension of recent type-theoretic gluing techniques. These results hold irrespective of the choice of mode theory, and thus apply to a wide variety of modal situations.
Despite extensive research both on the theoretical and practical fronts, formalising, reasoning about, and implementing languages with variable binding is still a daunting endeavour - repetitive boilerplate and the overly …
Despite extensive research both on the theoretical and practical fronts, formalising, reasoning about, and implementing languages with variable binding is still a daunting endeavour - repetitive boilerplate and the overly complicated metatheory of capture-avoiding substitution often get in the way of progressing on to the actually interesting properties of a language. Existing developments offer some relief, however at the expense of inconvenient and error-prone term encodings and lack of formal foundations. We present a mathematically-inspired language-formalisation framework implemented in Agda. The system translates the description of a syntax signature with variable-binding operators into an intrinsically-encoded, inductive data type equipped with syntactic operations such as weakening and substitution, along with their correctness properties. The generated metatheory further incorporates metavariables and their associated operation of metasubstitution, which enables second-order equational/rewriting reasoning. The underlying mathematical foundation of the framework - initial algebra semantics - derives compositional interpretations of languages into their models satisfying the semantic substitution lemma by construction.
In previous work ("From signatures to monads in UniMath"), we described a category-theoretic construction of abstract syntax from a signature, mechanized in the UniMath library based on the Coq proof …
In previous work ("From signatures to monads in UniMath"), we described a category-theoretic construction of abstract syntax from a signature, mechanized in the UniMath library based on the Coq proof assistant. In the present work, we describe what was necessary to generalize that work to account for simply-typed languages. First, some definitions had to be generalized to account for the natural appearance of non-endofunctors in the simply-typed case. As it turns out, in many cases our mechanized results carried over to the generalized definitions without any code change. Second, an existing mechanized library on $\omega$-cocontinuous functors had to be extended by constructions and theorems necessary for constructing multi-sorted syntax. Third, the theoretical framework for the semantical signatures had to be generalized from a monoidal to a bicategorical setting, again to account for non-endofunctors arising in the typed case. This uses actions of endofunctors on functors with given source, and the corresponding notion of strong functors between actions, all formalized in UniMath using a recently developed library of bicategory theory. We explain what needed to be done to plug all of these ingredients together, modularly. The main result of our work is a general construction that, when fed with a signature for a simply-typed language, returns an implementation of that language together with suitable boilerplate code, in particular, a certified monadic substitution operation.
We develop algebraic models of simple type theories, laying out a framework that extends universal algebra to incorporate both algebraic sorting and variable binding. Examples of simple type theories include …
We develop algebraic models of simple type theories, laying out a framework that extends universal algebra to incorporate both algebraic sorting and variable binding. Examples of simple type theories include the unityped and simply-typed λ-calculi, the computational λ-calculus, and predicate logic.
Game semantics is a rich and successful class of denotational models for programming languages. Most game models feature a rather intuitive setup, yet surprisingly difficult proofs of such basic results …
Game semantics is a rich and successful class of denotational models for programming languages. Most game models feature a rather intuitive setup, yet surprisingly difficult proofs of such basic results as associativity of composition of strategies. We seek to unify these models into a basic abstract framework for game semantics, game settings. Our main contribution is the generic construction, for any game setting, of a category of games and strategies. Furthermore, we extend the framework to deal with innocence, and prove that innocent strategies form a subcategory. We finally show that our constructions cover many concrete cases, mainly among the early models [5, 23] and the recent, sheaf-based ones [40].
We introduce MTT, a dependent type theory which supports multiple modalities. MTT is parametrized by a mode theory which specifies a collection of modes, modalities, and transformations between them. We …
We introduce MTT, a dependent type theory which supports multiple modalities. MTT is parametrized by a mode theory which specifies a collection of modes, modalities, and transformations between them. We show that different choices of mode theory allow us to use the same type theory to compute and reason in many modal situations, including guarded recursion, axiomatic cohesion, and parametric quantification. We reproduce examples from prior work in guarded recursion and axiomatic cohesion, thereby demonstrating that MTT constitutes a simple and usable syntax whose instantiations intuitively correspond to previous handcrafted modal type theories. In some cases, instantiating MTT to a particular situation unearths a previously unknown type theory that improves upon prior systems. Finally, we investigate the metatheory of MTT. We prove the consistency of MTT and establish canonicity through an extension of recent type-theoretic gluing techniques. These results hold irrespective of the choice of mode theory, and thus apply to a wide variety of modal situations.
We study the enrichment of models of axiomatic domain theory. To this end, we introduce a new and broader notion of domain, via, that of complete cuboidal set, that complies …
We study the enrichment of models of axiomatic domain theory. To this end, we introduce a new and broader notion of domain, via, that of complete cuboidal set, that complies with the axiomatic requirements. We show that the category of complete cuboidal sets provides a general notion of enrichment for a wide class of axiomatic domain-theoretic structures.
This paper studies fundamental connections between profunctors (that is, distributors, or bimodules), open maps and bisimulation. In particular, it proves that a colimit preserving functor between presheaf categories (corresponding to …
This paper studies fundamental connections between profunctors (that is, distributors, or bimodules), open maps and bisimulation. In particular, it proves that a colimit preserving functor between presheaf categories (corresponding to a profunctor) preserves open maps and open map bisimulation. Consequently, the composition of profunctors preserves open maps as 2-cells. A guiding idea is the view that profunctors, and colimit preserving functors, are linear maps in a model of classical linear logic. But profunctors, and colimit preserving functors, as linear maps, are too restrictive for many applications. This leads to a study of a range of pseudo-comonads and of how non-linear maps in their co-Kleisli bicategories preserve open maps and bisimulation. The pseudo-comonads considered are based on finite colimit completion, 'lifting', and indexed families. The paper includes an appendix summarising the key results on coends, left Kan extensions and the preservation of colimits. One motivation for this work is that it provides a mathematical framework for extending domain theory and denotational semantics of programming languages to the more intricate models, languages and equivalences found in concurrent computation, but the results are likely to have more general applicability because of the ubiquitous nature of profunctors.
We study polynomial functors over locally cartesian closed categories. After setting up the basic theory, we show how polynomial functors assemble into a double category, in fact a framed bicategory. …
We study polynomial functors over locally cartesian closed categories. After setting up the basic theory, we show how polynomial functors assemble into a double category, in fact a framed bicategory. We show that the free monad on a polynomial endofunctor is polynomial. The relationship with operads and other related notions is explored.
This paper studies normalisation by evaluation for typed lambda calculus from a categorical and algebraic viewpoint. The first part of the paper analyses the lambda definability result of Jung and …
This paper studies normalisation by evaluation for typed lambda calculus from a categorical and algebraic viewpoint. The first part of the paper analyses the lambda definability result of Jung and Tiuryn via Kripke logical relations and shows how it can be adapted to unify definability and normalisation, yielding an extensional normalisation result. In the second part of the paper the analysis is refined further by considering intensional Kripke relations (in the form of glueing) and shown to provide a function for normalising terms, casting normalisation by evaluation in the context of categorical glueing. The technical development includes an algebraic treatment of the syntax and semantics of the typed lambda calculus that allows the definition of the normalisation function to be given within a simply typed meta-theory.