SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

Bisimulation as path type for guarded recursive types

2019-01-02
Rasmus Ejlers Møgelberg , Niccolò Veltri
In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such … In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such as Coq and Agda. Currently, programming and reasoning about coinductive types is difficult for two reasons: The need for recursive definitions to be productive, and the lack of coincidence of the built-in identity types and the important notion of bisimilarity. Guarded recursion in the sense of Nakano has recently been suggested as a possible approach to dealing with the problem of productivity, allowing this to be encoded in types. Indeed, coinductive types can be encoded using a combination of guarded recursion and universal quantification over clocks. This paper studies the notion of bisimilarity for guarded recursive types in Ticked Cubical Type Theory, an extension of Cubical Type Theory with guarded recursion. We prove that, for any functor, an abstract, category theoretic notion of bisimilarity for the final guarded coalgebra is equivalent (in the sense of homotopy type theory) to path equality (the primitive notion of equality in cubical type theory). As a worked example we study a guarded notion of labelled transition systems, and show that, as a special case of the general theorem, path equality coincides with an adaptation of the usual notion of bisimulation for processes. In particular, this implies that guarded recursion can be used to give simple equational reasoning proofs of bisimilarity. This work should be seen as a step towards obtaining bisimilarity as path equality for coinductive types using the encodings mentioned above.
View PDF Chat

Eilenberg-Kelly Reloaded

2020-10-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it … The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it is closed and moreover the adjunction holds internally. We dissect the proof of this theorem and observe that the necessity for a side condition on closedness arises because the standard definition of closed category is left-skew in regards to associativity. We analyze Street's observation that left-skew monoidality is equivalent to left-skew closedness and establish that monoidality is equivalent to closedness unconditionally under an adjusted definition of closedness that requires normal associativity. We also work out a definition of right-skew closedness equivalent to right-skew monoidality. We give examples of each type of structure; in particular, we look at the Kleisli category of a left-strong monad on a left-skew closed category and the Kleisli category of a lax closed monad on a right-skew closed category. We also view skew and normal monoidal and closed categories as special cases of skew and normal promonoidal categories and take a brief look at left-skew prounital-closed categories.

The Sequent Calculus of Skew Monoidal Categories

2018-12-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a … Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context (a list of formulae), and the connectives unit and tensor behave like in intuitionistic non-commutative linear logic (the logic of monoidal categories) except that the left rules may only be applied in stoup position. We show the admissibility of two forms cut (stoup cut and context cut), and prove the calculus sound and complete with respect to existence of maps in the free skew monoidal category. We then introduce an equivalence relation on sequent calculus derivations and prove that there is a one-to-one correspondence between equivalence classes of derivations and maps in the free skew monoidal category. Finally, we identify a subcalculus of focused derivations, and establish that it contains exactly one canonical representative from each equivalence class. As an end result, we obtain simple algorithms both for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates, in particular, for deciding whether there is a map. We have formalized this development in the dependently typed programming language Agda.
View PDF Chat

Proof Theory of Partially Normal Skew Monoidal Categories

2021-01-19
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms … The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms but merely transformations in a particular direction. In previous work, we showed that the free skew monoidal category on a set of generating objects can be concretely presented as a sequent calculus. This calculus enjoys cut elimination and admits focusing, i.e. a subsystem of canonical derivations, which solves the coherence problem for skew monoidal categories. In this paper, we develop sequent calculi for partially normal skew monoidal categories, which are skew monoidal categories with one or more structural laws invertible. Each normality condition leads to additional inference rules and equations on them. We prove cut elimination and we show that the calculi admit focusing. The result is a family of sequent calculi between those of skew monoidal categories and (fully normal) monoidal categories. On the level of derivability, these define 8 weakenings of the (unit,tensor) fragment of intuitionistic non-commutative linear logic.
View PDF Chat

The Sequent Calculus of Skew Monoidal Categories

2021-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
View PDF Chat

Bicategories in univalent foundations

2021-11-01
Benedikt Ahrens , Dan Frumin , Marco Maggesi +2 more
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.
View PDF Chat

Coherence via Focusing for Symmetric Skew Monoidal Categories

2021-01-01
Niccolò Veltri

Constructing Higher Inductive Types as Groupoid Quotients

2021-04-22
Niccolò Veltri , Niels van der Weide
In this paper, we study finitary 1-truncated higher inductive types (HITs) in homotopy type theory. We start by showing that all these types can be constructed from the groupoid quotient. … In this paper, we study finitary 1-truncated higher inductive types (HITs) in homotopy type theory. We start by showing that all these types can be constructed from the groupoid quotient. We define an internal notion of signatures for HITs, and for each signature, we construct a bicategory of algebras in 1-types and in groupoids. We continue by proving initial algebra semantics for our signatures. After that, we show that the groupoid quotient induces a biadjunction between the bicategories of algebras in 1-types and in groupoids. Then we construct a biinitial object in the bicategory of algebras in groupoids, which gives the desired algebra. From all this, we conclude that all finitary 1-truncated HITs can be constructed from the groupoid quotient. We present several examples of HITs which are definable using our notion of signature. In particular, we show that each signature gives rise to a HIT corresponding to the freely generated algebraic structure over it. We also start the development of universal algebra in 1-types. We show that the bicategory of algebras has PIE limits, i.e. products, inserters and equifiers, and we prove a version of the first isomorphism theorem for 1-types. Finally, we give an alternative characterization of the foundamental groups of some HITs, exploiting our construction of HITs via the groupoid quotient. All the results are formalized over the UniMath library of univalent mathematics in Coq.
View PDF Chat

Proof Theory of Skew Non-Commutative MILL

2022-04-13
Tarmo Uustalu , Niccolò Veltri , Cheng-Syuan Wan
Monoidal closed categories naturally model NMILL, non-commutative multiplicative intuitionistic linear logic: the monoidal unit and tensor interpret the multiplicative verum and conjunction; the internal hom interprets linear implication. In recent … Monoidal closed categories naturally model NMILL, non-commutative multiplicative intuitionistic linear logic: the monoidal unit and tensor interpret the multiplicative verum and conjunction; the internal hom interprets linear implication. In recent years, the weaker notion of (left) skew monoidal closed category has been proposed by Ross Street, where the three structural laws of left and right unitality and associativity are not required to be invertible, they are merely natural transformations with a specific orientation. A question arises: is it possible to find a logic which is naturally modelled by skew monoidal closed categories? We answer positively by introducing a cut-free sequent calculus for a skew version of NMILL that is a presentation of the free skew monoidal closed category. We study the proof-theoretic semantics of the sequent calculus by identifying a calculus of derivations in normal form, obtained from an adaptation of Andreoli's focusing technique to the skew setting. The resulting focused sequent calculus peculiarly employs a system of tags for keeping track of new formulae appearing in the antecedent and appropriately reducing non-deterministic choices in proof search. Focusing solves the coherence problem for skew monoidal closed categories by exhibiting an effective procedure for deciding equality of maps in the free such category.
View PDF Chat

Finiteness and rational sequences, constructively

2017-01-01
Tarmo Uustalu , Niccolò Veltri
Abstract Rational sequences are possibly infinite sequences with a finite number of distinct suffixes. In this paper, we present different implementations of rational sequences in Martin–Löf type theory. First, we … Abstract Rational sequences are possibly infinite sequences with a finite number of distinct suffixes. In this paper, we present different implementations of rational sequences in Martin–Löf type theory. First, we literally translate the above definition of rational sequence into the language of type theory, i.e., we construct predicates on possibly infinite sequences expressing the finiteness of the set of suffixes. In type theory, there exist several inequivalent notions of finiteness. We consider two of them, listability and Noetherianness, and show that in the implementation of rational sequences the two notions are interchangeable. Then we introduce the type of lists with backpointers, which is an inductive implementation of rational sequences. Lists with backpointers can be unwound into rational sequences, and rational sequences can be truncated into lists with backpointers. As an example, we see how to convert the fractional representation of a rational number into its decimal representation and vice versa.

Variations on Noetherianness

2016-04-01
Denis Firsov , Tarmo Uustalu , Niccolò Veltri
In constructive mathematics, several nonequivalent notions of finiteness exist. In this paper, we continue the study of Noetherian sets in the dependently typed setting of the Agda programming language. We … In constructive mathematics, several nonequivalent notions of finiteness exist. In this paper, we continue the study of Noetherian sets in the dependently typed setting of the Agda programming language. We want to say that a set is Noetherian, if, when we are shown elements from it one after another, we will sooner or later have seen some element twice. This idea can be made precise in a number of ways. We explore the properties and connections of some of the possible encodings. In particular, we show that certain implementations imply decidable equality while others do not, and we construct counterexamples in the latter case. Additionally, we explore the relation between Noetherianness and other notions of finiteness.
View PDF Chat

Deductive Systems and Coherence for Skew Prounital Closed Categories

2021-01-08
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew … In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew closed categories in turn are a weakening of the closed categories of Eilenberg and Kelly where no structural law is required to be invertible. The presence of a monoidal structure in these categories is not required. We construct several equivalent presentations of the free skew prounital closed category on a given set of generating objects: a categorical calculus (Hilbert-style system), a cut-free sequent calculus and a natural deduction system corresponding to a variant of planar (= non-commutative linear) typed lambda-calculus. We solve the coherence problem for skew prounital closed categories by showing that the sequent calculus admits focusing and presenting two reduction-free normalization procedures for the natural deduction calculus: normalization by evaluation and hereditary substitutions. Normal natural deduction derivations (beta-eta-long forms) are in one-to-one correspondence with derivations in the focused sequent calculus. Unexpectedly, the free skew prounital closed category on a set satisfies a left-normality condition which makes it lose its skew aspect. This pitfall can be avoided by considering the free skew prounital closed category on a skew multicategory instead. The latter has a presentation as a cut-free sequent calculus for which it is easy to see that the left-normality condition generally fails. The whole development has been fully formalized in the dependently typed programming language Agda.
View PDF Chat

Ticking clocks as dependent right adjoints: Denotational semantics for clocked type theory

2020-01-01
Bassel Mannaa , Rasmus Ejlers Møgelberg , Niccolò Veltri
Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming … Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming language features using an abstract form of step-indexing. CloTT has previously been shown to enjoy a number of syntactic properties including strong normalisation, canonicity and decidability of the equational theory. In this paper we present a denotational semantics for CloTT useful, e.g., for studying future extensions of CloTT with constructions such as path types. The main challenge for constructing this model is to model the notion of ticks on a clock used in CloTT for coinductive reasoning about coinductive types. We build on a category previously used to model guarded recursion with multiple clocks. In this category there is an object of clocks but no object of ticks, and so tick-assumptions in a context can not be modelled using standard tools. Instead we model ticks using dependent right adjoint functors, a generalisation of the category theoretic notion of adjunction to the setting of categories with families. Dependent right adjoints are known to model Fitch-style modal types, but in the case of CloTT, the modal operators constitute a family indexed internally in the type theory by clocks. We model this family using a dependent right adjoint on the slice category over the object of clocks. Finally we show how to model the tick constant of CloTT using a semantic substitution. This work improves on a previous model by the first two named authors which not only had a flaw but was also considerably more complicated.
View PDF Chat

Deductive systems and coherence for skew prounital closed categories

2020-06-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew … In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew closed categories in turn are a weakening of the closed categories of Eilenberg and Kelly where no structural law is required to be invertible. The presence of a monoidal structure in these categories is not required. We construct several equivalent presentations of the free skew prounital closed category on a given set of generating objects: a categorical calculus (Hilbert-style system), a cut-free sequent calculus and a natural deduction system corresponding to a variant of planar (= non-commutative linear) typed lambda-calculus. We solve the coherence problem for skew prounital closed categories by showing that the sequent calculus admits focusing and presenting two reduction-free normalization procedures for the natural deduction calculus: normalization by evaluation and hereditary substitutions. Normal natural deduction derivations (beta-eta-long forms) are in one-to-one correspondence with derivations in the focused sequent calculus. Unexpectedly, the free skew prounital closed category on a set satisfies a left-normality condition which makes it lose its skew aspect. This pitfall can be avoided by considering the free skew prounital closed category on a skew multicategory instead. The latter has a presentation as a cut-free sequent calculus for which it is easy to see that the left-normality condition generally fails. The whole development has been fully formalized in the dependently typed programming language Agda.

Inductive and Coinductive Predicate Liftings for Effectful Programs

2021-12-27
Niccolò Veltri , Niels Voorneveld
We formulate a framework for describing behaviour of effectful higher-order recursive programs. Examples of effects are implemented using effect operations, and include: execution cost, nondeterminism, global store and interaction with … We formulate a framework for describing behaviour of effectful higher-order recursive programs. Examples of effects are implemented using effect operations, and include: execution cost, nondeterminism, global store and interaction with a user. The denotational semantics of a program is given by a coinductive tree in a monad, which combines potential return values of the program in terms of effect operations. Using a simple test logic, we construct two sorts of predicate liftings, which lift predicates on a result type to predicates on computations that produce results of that type, each capturing a facet of program behaviour. Firstly, we study inductive predicate liftings which can be used to describe effectful notions of total correctness. Secondly, we study coinductive predicate liftings, which describe effectful notions of partial correctness. The two constructions are dual in the sense that one can be used to disprove the other. The predicate liftings are used as a basis for an endogenous logic of behavioural properties for higher-order programs. The program logic has a derivable notion of negation, arising from the duality of the two sorts of predicate liftings, and it generates a program equivalence which subsumes a notion of bisimilarity. Appropriate definitions of inductive and coinductive predicate liftings are given for a multitude of effect examples. The whole development has been fully formalized in the Agda proof assistant.
View PDF Chat

Normalization by Evaluation for the Lambek Calculus

2022-04-13
Niccolò Veltri
The syntactic calculus of Lambek is a deductive system for the multiplicative fragment of intuitionistic non-commutative linear logic. As a fine-grained calculus of resources, it has many applications, mostly in … The syntactic calculus of Lambek is a deductive system for the multiplicative fragment of intuitionistic non-commutative linear logic. As a fine-grained calculus of resources, it has many applications, mostly in formal computational investigations of natural languages. This paper introduces a calculus of beta-eta-long normal forms for derivations in the Lambek calculus with multiplicative unit and conjunction among its logical connectives. Reduction to normal form follows the normalization by evaluation (NbE) strategy: (i) evaluate a derivation in a Kripke model of Lambek calculus; (ii) extract normal forms from the obtained semantic values. The implementation of the NbE algorithm requires the presence of a strong monad in the Kripke interpretation of positive formulae, in analogy with the extension of intuitionistic propositional logic with falsity and disjunction. The NbE algorithm can also be instantiated with minor variations to calculi for related substructural logics, such as multiplicative and dual intuitionistic linear logic (MILL and DILL).
View PDF Chat

Semi-Substructural Logics with Additives

2024-04-21
Niccolò Veltri , Cheng-Syuan Wan
This work concerns the proof theory of (left) skew monoidal categories and their variants (e.g. closed monoidal, symmetric monoidal), continuing the line of work initiated in recent years by Uustalu … This work concerns the proof theory of (left) skew monoidal categories and their variants (e.g. closed monoidal, symmetric monoidal), continuing the line of work initiated in recent years by Uustalu et al. Skew monoidal categories are a weak version of Mac Lane's monoidal categories, where the structural laws are not required to be invertible, they are merely natural transformations with a specific orientation. Sequent calculi which can be modelled in such categories can be identified as deductive systems for restricted substructural fragments of intuitionistic linear logic. These calculi enjoy cut elimination and admit a focusing strategy, sharing resemblance with Andreoli's normalization technique for linear logic. The focusing procedure is useful for solving the coherence problem of the considered categories with skew structure. Here we investigate possible extensions of the sequent calculi of Uustalu et al. with additive connectives. As a first step, we extend the sequent calculus with additive conjunction and disjunction, corresponding to studying the proof theory of skew monoidal categories with binary products and coproducts satisfying a left-distributivity condition. We introduce a new focused sequent calculus of derivations in normal form, which employs tag annotations to reduce non-deterministic choices in bottom-up proof search. The focused sequent calculus and the proof of its correctness have been formalized in the Agda proof assistant. We also discuss extensions of the logic with additive units, a form of skew exchange and linear implication.
View PDF Chat

Bisimulation as path type for guarded recursive types

2018-10-31
Rasmus Ejlers Møgelberg , Niccolò Veltri
In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such … In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such as Coq and Agda. Currently, programming and reasoning about coinductive types is difficult for two reasons: The need for recursive definitions to be productive, and the lack of coincidence of the built-in identity types and the important notion of bisimilarity. Guarded recursion in the sense of Nakano has recently been suggested as a possible approach to dealing with the problem of productivity, allowing this to be encoded in types. Indeed, coinductive types can be encoded using a combination of guarded recursion and universal quantification over clocks. This paper studies the notion of bisimilarity for guarded recursive types in Ticked Cubical Type Theory, an extension of Cubical Type Theory with guarded recursion. We prove that, for any functor, an abstract, category theoretic notion of bisimilarity for the final guarded coalgebra is equivalent (in the sense of homotopy type theory) to path equality (the primitive notion of equality in cubical type theory). As a worked example we study a guarded notion of labelled transition systems, and show that, as a special case of the general theorem, path equality coincides with an adaptation of the usual notion of bisimulation for processes. In particular, this implies that guarded recursion can be used to give simple equational reasoning proofs of bisimilarity. This work should be seen as a step towards obtaining bisimilarity as path equality for coinductive types using the encodings mentioned above.

Non-wellfounded sets in homotopy type theory

2020-01-01
Håkon Robbestad Gylterud , Elisabeth Stenholm , Niccolò Veltri
Non-wellfounded material sets have previously been modeled in Martin-L\"of type theory by Lindstr\"om using setoids. In this paper we construct models of non-wellfounded material sets in Homotopy Type Theory (HoTT) … Non-wellfounded material sets have previously been modeled in Martin-L\"of type theory by Lindstr\"om using setoids. In this paper we construct models of non-wellfounded material sets in Homotopy Type Theory (HoTT) where equality is interpreted as the identity type. The first model satisfies Scott's Anti-Foundation Axiom (SAFA) and dualises the construction of iterative sets. The second model satisfies Aczel's Anti-Foundation Axiom (AFA), and is constructed by adaption of Aczel--Mendler's terminal coalgebra theorem to type theory, which requires propositional resizing. In an bid to extend coalgebraic theory and anti-foundation axioms to higher type levels, we formulate generalisations of AFA and SAFA, and construct a hierarchy of models which satisfies the SAFA generalisations. These generalisations build on the framework of Univalent Material Set Theory, previously developed by two of the authors. Since the model constructions are based on M-types, the paper also includes a characterisation of the identity type of M-types as indexed M-types. Our results are formalised in the proof-assistant Agda.
View PDF Chat

Bicategories in Univalent Foundations

2019-03-04
Benedikt Ahrens , Dan Frumin , Marco Maggesi +2 more
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.

The sequent calculus of skew monoidal categories (extended version)

2020-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger

Formalizing π-calculus in guarded cubical Agda

2020-01-01
Niccolò Veltri , Andrea Vezzosi

Constructing Higher Inductive Types as Groupoid Quotients

2021-01-01
Niccolò Veltri , Niels van der Weide
In this paper, we study finitary 1-truncated higher inductive types (HITs) in homotopy type theory. We start by showing that all these types can be constructed from the groupoid quotient. … In this paper, we study finitary 1-truncated higher inductive types (HITs) in homotopy type theory. We start by showing that all these types can be constructed from the groupoid quotient. We define an internal notion of signatures for HITs, and for each signature, we construct a bicategory of algebras in 1-types and in groupoids. We continue by proving initial algebra semantics for our signatures. After that, we show that the groupoid quotient induces a biadjunction between the bicategories of algebras in 1-types and in groupoids. Then we construct a biinitial object in the bicategory of algebras in groupoids, which gives the desired algebra. From all this, we conclude that all finitary 1-truncated HITs can be constructed from the groupoid quotient. We present several examples of HITs which are definable using our notion of signature. In particular, we show that each signature gives rise to a HIT corresponding to the freely generated algebraic structure over it. We also start the development of universal algebra in 1-types. We show that the bicategory of algebras has PIE limits, i.e. products, inserters and equifiers, and we prove a version of the first isomorphism theorem for 1-types. Finally, we give an alternative characterization of the foundamental groups of some HITs, exploiting our construction of HITs via the groupoid quotient. All the results are formalized over the UniMath library of univalent mathematics in Coq.

The Sequent Calculus of Skew Monoidal Categories

2020-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
Szlach\'anyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a … Szlach\'anyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context, and the connectives behave like in the standard monoidal sequent calculus except that the left rules may only be applied in stoup position. We prove that this calculus is sound and complete with respect to existence of maps in the free skew monoidal category, and moreover that it captures equality of maps once a suitable equivalence relation is imposed on derivations. We then identify a subsystem of focused derivations and establish that it contains exactly one canonical representative from each equivalence class. This coherence theorem leads directly to simple procedures for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates. Finally, and in the spirit of Lambek's work, we describe the close connection between this proof-theoretic analysis and Bourke and Lack's recent characterization of skew monoidal categories as left representable skew multicategories. We have formalized this development in the dependently typed programming language Agda.
View PDF Chat

Bisimulation as path type for guarded recursive types

2018-01-01
Rasmus Ejlers Møgelberg , Niccolò Veltri
In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such … In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such as Coq and Agda. Currently, programming and reasoning about coinductive types is difficult for two reasons: The need for recursive definitions to be productive, and the lack of coincidence of the built-in identity types and the important notion of bisimilarity. Guarded recursion in the sense of Nakano has recently been suggested as a possible approach to dealing with the problem of productivity, allowing this to be encoded in types. Indeed, coinductive types can be encoded using a combination of guarded recursion and universal quantification over clocks. This paper studies the notion of bisimilarity for guarded recursive types in Ticked Cubical Type Theory, an extension of Cubical Type Theory with guarded recursion. We prove that, for any functor, an abstract, category theoretic notion of bisimilarity for the final guarded coalgebra is equivalent (in the sense of homotopy type theory) to path equality (the primitive notion of equality in cubical type theory). As a worked example we study a guarded notion of labelled transition systems, and show that, as a special case of the general theorem, path equality coincides with an adaptation of the usual notion of bisimulation for processes. In particular, this implies that guarded recursion can be used to give simple equational reasoning proofs of bisimilarity. This work should be seen as a step towards obtaining bisimilarity as path equality for coinductive types using the encodings mentioned above.
View PDF Chat

Coherence via focusing for symmetric skew monoidal and symmetric skew closed categories

2024-10-10
Niccolò Veltri
Abstract The symmetric skew monoidal categories of Bourke and Lack are a weakening of Mac Lane’s symmetric monoidal categories where (i) the three structural laws of left and right unitality … Abstract The symmetric skew monoidal categories of Bourke and Lack are a weakening of Mac Lane’s symmetric monoidal categories where (i) the three structural laws of left and right unitality and associativity are not required to be invertible, they are merely natural transformations with a specific orientation; (ii) the structural law of symmetry is a natural isomorphism involving three objects rather than two. In a similar fashion, symmetric skew closed categories are a weakening of de Schipper’s symmetric closed categories with non-invertible structural laws of left and right unitality. In this paper, we study the structural proof theory of symmetric skew monoidal and symmetric skew closed categories, progressing the project initiated by Uustalu et al. on deductive systems for categories with skew structure. We discuss three equivalent presentations of the free symmetric skew monoidal (resp. closed) category on a set of generating objects: a Hilbert-style categorical calculus; a cut-free sequent calculus; a focused subsystem of derivations, corresponding to a sound and complete goal-directed proof search strategy for the cut-free sequent calculus. Focusing defines an effective normalization procedure for maps in the free symmetric skew monoidal (resp. closed) category, as such solving the coherence problem for symmetric skew monoidal (resp. closed) categories.

Coherence via focusing for symmetric skew monoidal and symmetric skew closed categories

2024-10-10
Niccolò Veltri
Abstract The symmetric skew monoidal categories of Bourke and Lack are a weakening of Mac Lane’s symmetric monoidal categories where (i) the three structural laws of left and right unitality … Abstract The symmetric skew monoidal categories of Bourke and Lack are a weakening of Mac Lane’s symmetric monoidal categories where (i) the three structural laws of left and right unitality and associativity are not required to be invertible, they are merely natural transformations with a specific orientation; (ii) the structural law of symmetry is a natural isomorphism involving three objects rather than two. In a similar fashion, symmetric skew closed categories are a weakening of de Schipper’s symmetric closed categories with non-invertible structural laws of left and right unitality. In this paper, we study the structural proof theory of symmetric skew monoidal and symmetric skew closed categories, progressing the project initiated by Uustalu et al. on deductive systems for categories with skew structure. We discuss three equivalent presentations of the free symmetric skew monoidal (resp. closed) category on a set of generating objects: a Hilbert-style categorical calculus; a cut-free sequent calculus; a focused subsystem of derivations, corresponding to a sound and complete goal-directed proof search strategy for the cut-free sequent calculus. Focusing defines an effective normalization procedure for maps in the free symmetric skew monoidal (resp. closed) category, as such solving the coherence problem for symmetric skew monoidal (resp. closed) categories.

Semi-Substructural Logics with Additives

2024-04-21
Niccolò Veltri , Cheng-Syuan Wan
This work concerns the proof theory of (left) skew monoidal categories and their variants (e.g. closed monoidal, symmetric monoidal), continuing the line of work initiated in recent years by Uustalu … This work concerns the proof theory of (left) skew monoidal categories and their variants (e.g. closed monoidal, symmetric monoidal), continuing the line of work initiated in recent years by Uustalu et al. Skew monoidal categories are a weak version of Mac Lane's monoidal categories, where the structural laws are not required to be invertible, they are merely natural transformations with a specific orientation. Sequent calculi which can be modelled in such categories can be identified as deductive systems for restricted substructural fragments of intuitionistic linear logic. These calculi enjoy cut elimination and admit a focusing strategy, sharing resemblance with Andreoli's normalization technique for linear logic. The focusing procedure is useful for solving the coherence problem of the considered categories with skew structure. Here we investigate possible extensions of the sequent calculi of Uustalu et al. with additive connectives. As a first step, we extend the sequent calculus with additive conjunction and disjunction, corresponding to studying the proof theory of skew monoidal categories with binary products and coproducts satisfying a left-distributivity condition. We introduce a new focused sequent calculus of derivations in normal form, which employs tag annotations to reduce non-deterministic choices in bottom-up proof search. The focused sequent calculus and the proof of its correctness have been formalized in the Agda proof assistant. We also discuss extensions of the logic with additive units, a form of skew exchange and linear implication.
View PDF Chat

Proof Theory of Skew Non-Commutative MILL

2022-04-13
Tarmo Uustalu , Niccolò Veltri , Cheng-Syuan Wan
Monoidal closed categories naturally model NMILL, non-commutative multiplicative intuitionistic linear logic: the monoidal unit and tensor interpret the multiplicative verum and conjunction; the internal hom interprets linear implication. In recent … Monoidal closed categories naturally model NMILL, non-commutative multiplicative intuitionistic linear logic: the monoidal unit and tensor interpret the multiplicative verum and conjunction; the internal hom interprets linear implication. In recent years, the weaker notion of (left) skew monoidal closed category has been proposed by Ross Street, where the three structural laws of left and right unitality and associativity are not required to be invertible, they are merely natural transformations with a specific orientation. A question arises: is it possible to find a logic which is naturally modelled by skew monoidal closed categories? We answer positively by introducing a cut-free sequent calculus for a skew version of NMILL that is a presentation of the free skew monoidal closed category. We study the proof-theoretic semantics of the sequent calculus by identifying a calculus of derivations in normal form, obtained from an adaptation of Andreoli's focusing technique to the skew setting. The resulting focused sequent calculus peculiarly employs a system of tags for keeping track of new formulae appearing in the antecedent and appropriately reducing non-deterministic choices in proof search. Focusing solves the coherence problem for skew monoidal closed categories by exhibiting an effective procedure for deciding equality of maps in the free such category.
View PDF Chat

Normalization by Evaluation for the Lambek Calculus

2022-04-13
Niccolò Veltri
The syntactic calculus of Lambek is a deductive system for the multiplicative fragment of intuitionistic non-commutative linear logic. As a fine-grained calculus of resources, it has many applications, mostly in … The syntactic calculus of Lambek is a deductive system for the multiplicative fragment of intuitionistic non-commutative linear logic. As a fine-grained calculus of resources, it has many applications, mostly in formal computational investigations of natural languages. This paper introduces a calculus of beta-eta-long normal forms for derivations in the Lambek calculus with multiplicative unit and conjunction among its logical connectives. Reduction to normal form follows the normalization by evaluation (NbE) strategy: (i) evaluate a derivation in a Kripke model of Lambek calculus; (ii) extract normal forms from the obtained semantic values. The implementation of the NbE algorithm requires the presence of a strong monad in the Kripke interpretation of positive formulae, in analogy with the extension of intuitionistic propositional logic with falsity and disjunction. The NbE algorithm can also be instantiated with minor variations to calculi for related substructural logics, such as multiplicative and dual intuitionistic linear logic (MILL and DILL).
View PDF Chat

Inductive and Coinductive Predicate Liftings for Effectful Programs

2021-12-27
Niccolò Veltri , Niels Voorneveld
We formulate a framework for describing behaviour of effectful higher-order recursive programs. Examples of effects are implemented using effect operations, and include: execution cost, nondeterminism, global store and interaction with … We formulate a framework for describing behaviour of effectful higher-order recursive programs. Examples of effects are implemented using effect operations, and include: execution cost, nondeterminism, global store and interaction with a user. The denotational semantics of a program is given by a coinductive tree in a monad, which combines potential return values of the program in terms of effect operations. Using a simple test logic, we construct two sorts of predicate liftings, which lift predicates on a result type to predicates on computations that produce results of that type, each capturing a facet of program behaviour. Firstly, we study inductive predicate liftings which can be used to describe effectful notions of total correctness. Secondly, we study coinductive predicate liftings, which describe effectful notions of partial correctness. The two constructions are dual in the sense that one can be used to disprove the other. The predicate liftings are used as a basis for an endogenous logic of behavioural properties for higher-order programs. The program logic has a derivable notion of negation, arising from the duality of the two sorts of predicate liftings, and it generates a program equivalence which subsumes a notion of bisimilarity. Appropriate definitions of inductive and coinductive predicate liftings are given for a multitude of effect examples. The whole development has been fully formalized in the Agda proof assistant.
View PDF Chat

Bicategories in univalent foundations

2021-11-01
Benedikt Ahrens , Dan Frumin , Marco Maggesi +2 more
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.
View PDF Chat

Constructing Higher Inductive Types as Groupoid Quotients

2021-04-22
Niccolò Veltri , Niels van der Weide
In this paper, we study finitary 1-truncated higher inductive types (HITs) in homotopy type theory. We start by showing that all these types can be constructed from the groupoid quotient. … In this paper, we study finitary 1-truncated higher inductive types (HITs) in homotopy type theory. We start by showing that all these types can be constructed from the groupoid quotient. We define an internal notion of signatures for HITs, and for each signature, we construct a bicategory of algebras in 1-types and in groupoids. We continue by proving initial algebra semantics for our signatures. After that, we show that the groupoid quotient induces a biadjunction between the bicategories of algebras in 1-types and in groupoids. Then we construct a biinitial object in the bicategory of algebras in groupoids, which gives the desired algebra. From all this, we conclude that all finitary 1-truncated HITs can be constructed from the groupoid quotient. We present several examples of HITs which are definable using our notion of signature. In particular, we show that each signature gives rise to a HIT corresponding to the freely generated algebraic structure over it. We also start the development of universal algebra in 1-types. We show that the bicategory of algebras has PIE limits, i.e. products, inserters and equifiers, and we prove a version of the first isomorphism theorem for 1-types. Finally, we give an alternative characterization of the foundamental groups of some HITs, exploiting our construction of HITs via the groupoid quotient. All the results are formalized over the UniMath library of univalent mathematics in Coq.
View PDF Chat

Proof Theory of Partially Normal Skew Monoidal Categories

2021-01-19
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms … The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms but merely transformations in a particular direction. In previous work, we showed that the free skew monoidal category on a set of generating objects can be concretely presented as a sequent calculus. This calculus enjoys cut elimination and admits focusing, i.e. a subsystem of canonical derivations, which solves the coherence problem for skew monoidal categories. In this paper, we develop sequent calculi for partially normal skew monoidal categories, which are skew monoidal categories with one or more structural laws invertible. Each normality condition leads to additional inference rules and equations on them. We prove cut elimination and we show that the calculi admit focusing. The result is a family of sequent calculi between those of skew monoidal categories and (fully normal) monoidal categories. On the level of derivability, these define 8 weakenings of the (unit,tensor) fragment of intuitionistic non-commutative linear logic.
View PDF Chat

Deductive Systems and Coherence for Skew Prounital Closed Categories

2021-01-08
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew … In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew closed categories in turn are a weakening of the closed categories of Eilenberg and Kelly where no structural law is required to be invertible. The presence of a monoidal structure in these categories is not required. We construct several equivalent presentations of the free skew prounital closed category on a given set of generating objects: a categorical calculus (Hilbert-style system), a cut-free sequent calculus and a natural deduction system corresponding to a variant of planar (= non-commutative linear) typed lambda-calculus. We solve the coherence problem for skew prounital closed categories by showing that the sequent calculus admits focusing and presenting two reduction-free normalization procedures for the natural deduction calculus: normalization by evaluation and hereditary substitutions. Normal natural deduction derivations (beta-eta-long forms) are in one-to-one correspondence with derivations in the focused sequent calculus. Unexpectedly, the free skew prounital closed category on a set satisfies a left-normality condition which makes it lose its skew aspect. This pitfall can be avoided by considering the free skew prounital closed category on a skew multicategory instead. The latter has a presentation as a cut-free sequent calculus for which it is easy to see that the left-normality condition generally fails. The whole development has been fully formalized in the dependently typed programming language Agda.
View PDF Chat

The Sequent Calculus of Skew Monoidal Categories

2021-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
View PDF Chat

Constructing Higher Inductive Types as Groupoid Quotients

2021-01-01
Niccolò Veltri , Niels van der Weide
In this paper, we study finitary 1-truncated higher inductive types (HITs) in homotopy type theory. We start by showing that all these types can be constructed from the groupoid quotient. … In this paper, we study finitary 1-truncated higher inductive types (HITs) in homotopy type theory. We start by showing that all these types can be constructed from the groupoid quotient. We define an internal notion of signatures for HITs, and for each signature, we construct a bicategory of algebras in 1-types and in groupoids. We continue by proving initial algebra semantics for our signatures. After that, we show that the groupoid quotient induces a biadjunction between the bicategories of algebras in 1-types and in groupoids. Then we construct a biinitial object in the bicategory of algebras in groupoids, which gives the desired algebra. From all this, we conclude that all finitary 1-truncated HITs can be constructed from the groupoid quotient. We present several examples of HITs which are definable using our notion of signature. In particular, we show that each signature gives rise to a HIT corresponding to the freely generated algebraic structure over it. We also start the development of universal algebra in 1-types. We show that the bicategory of algebras has PIE limits, i.e. products, inserters and equifiers, and we prove a version of the first isomorphism theorem for 1-types. Finally, we give an alternative characterization of the foundamental groups of some HITs, exploiting our construction of HITs via the groupoid quotient. All the results are formalized over the UniMath library of univalent mathematics in Coq.

Coherence via Focusing for Symmetric Skew Monoidal Categories

2021-01-01
Niccolò Veltri

Eilenberg-Kelly Reloaded

2020-10-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it … The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it is closed and moreover the adjunction holds internally. We dissect the proof of this theorem and observe that the necessity for a side condition on closedness arises because the standard definition of closed category is left-skew in regards to associativity. We analyze Street's observation that left-skew monoidality is equivalent to left-skew closedness and establish that monoidality is equivalent to closedness unconditionally under an adjusted definition of closedness that requires normal associativity. We also work out a definition of right-skew closedness equivalent to right-skew monoidality. We give examples of each type of structure; in particular, we look at the Kleisli category of a left-strong monad on a left-skew closed category and the Kleisli category of a lax closed monad on a right-skew closed category. We also view skew and normal monoidal and closed categories as special cases of skew and normal promonoidal categories and take a brief look at left-skew prounital-closed categories.

Deductive systems and coherence for skew prounital closed categories

2020-06-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew … In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew closed categories in turn are a weakening of the closed categories of Eilenberg and Kelly where no structural law is required to be invertible. The presence of a monoidal structure in these categories is not required. We construct several equivalent presentations of the free skew prounital closed category on a given set of generating objects: a categorical calculus (Hilbert-style system), a cut-free sequent calculus and a natural deduction system corresponding to a variant of planar (= non-commutative linear) typed lambda-calculus. We solve the coherence problem for skew prounital closed categories by showing that the sequent calculus admits focusing and presenting two reduction-free normalization procedures for the natural deduction calculus: normalization by evaluation and hereditary substitutions. Normal natural deduction derivations (beta-eta-long forms) are in one-to-one correspondence with derivations in the focused sequent calculus. Unexpectedly, the free skew prounital closed category on a set satisfies a left-normality condition which makes it lose its skew aspect. This pitfall can be avoided by considering the free skew prounital closed category on a skew multicategory instead. The latter has a presentation as a cut-free sequent calculus for which it is easy to see that the left-normality condition generally fails. The whole development has been fully formalized in the dependently typed programming language Agda.

Non-wellfounded sets in homotopy type theory

2020-01-01
Håkon Robbestad Gylterud , Elisabeth Stenholm , Niccolò Veltri
Non-wellfounded material sets have previously been modeled in Martin-L\"of type theory by Lindstr\"om using setoids. In this paper we construct models of non-wellfounded material sets in Homotopy Type Theory (HoTT) … Non-wellfounded material sets have previously been modeled in Martin-L\"of type theory by Lindstr\"om using setoids. In this paper we construct models of non-wellfounded material sets in Homotopy Type Theory (HoTT) where equality is interpreted as the identity type. The first model satisfies Scott's Anti-Foundation Axiom (SAFA) and dualises the construction of iterative sets. The second model satisfies Aczel's Anti-Foundation Axiom (AFA), and is constructed by adaption of Aczel--Mendler's terminal coalgebra theorem to type theory, which requires propositional resizing. In an bid to extend coalgebraic theory and anti-foundation axioms to higher type levels, we formulate generalisations of AFA and SAFA, and construct a hierarchy of models which satisfies the SAFA generalisations. These generalisations build on the framework of Univalent Material Set Theory, previously developed by two of the authors. Since the model constructions are based on M-types, the paper also includes a characterisation of the identity type of M-types as indexed M-types. Our results are formalised in the proof-assistant Agda.
View PDF Chat

Ticking clocks as dependent right adjoints: Denotational semantics for clocked type theory

2020-01-01
Bassel Mannaa , Rasmus Ejlers Møgelberg , Niccolò Veltri
Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming … Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming language features using an abstract form of step-indexing. CloTT has previously been shown to enjoy a number of syntactic properties including strong normalisation, canonicity and decidability of the equational theory. In this paper we present a denotational semantics for CloTT useful, e.g., for studying future extensions of CloTT with constructions such as path types. The main challenge for constructing this model is to model the notion of ticks on a clock used in CloTT for coinductive reasoning about coinductive types. We build on a category previously used to model guarded recursion with multiple clocks. In this category there is an object of clocks but no object of ticks, and so tick-assumptions in a context can not be modelled using standard tools. Instead we model ticks using dependent right adjoint functors, a generalisation of the category theoretic notion of adjunction to the setting of categories with families. Dependent right adjoints are known to model Fitch-style modal types, but in the case of CloTT, the modal operators constitute a family indexed internally in the type theory by clocks. We model this family using a dependent right adjoint on the slice category over the object of clocks. Finally we show how to model the tick constant of CloTT using a semantic substitution. This work improves on a previous model by the first two named authors which not only had a flaw but was also considerably more complicated.
View PDF Chat

The sequent calculus of skew monoidal categories (extended version)

2020-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger

Formalizing π-calculus in guarded cubical Agda

2020-01-01
Niccolò Veltri , Andrea Vezzosi

The Sequent Calculus of Skew Monoidal Categories

2020-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
Szlach\'anyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a … Szlach\'anyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context, and the connectives behave like in the standard monoidal sequent calculus except that the left rules may only be applied in stoup position. We prove that this calculus is sound and complete with respect to existence of maps in the free skew monoidal category, and moreover that it captures equality of maps once a suitable equivalence relation is imposed on derivations. We then identify a subsystem of focused derivations and establish that it contains exactly one canonical representative from each equivalence class. This coherence theorem leads directly to simple procedures for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates. Finally, and in the spirit of Lambek's work, we describe the close connection between this proof-theoretic analysis and Bourke and Lack's recent characterization of skew monoidal categories as left representable skew multicategories. We have formalized this development in the dependently typed programming language Agda.
View PDF Chat

Bicategories in Univalent Foundations

2019-03-04
Benedikt Ahrens , Dan Frumin , Marco Maggesi +2 more
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.

Bisimulation as path type for guarded recursive types

2019-01-02
Rasmus Ejlers Møgelberg , Niccolò Veltri
In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such … In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such as Coq and Agda. Currently, programming and reasoning about coinductive types is difficult for two reasons: The need for recursive definitions to be productive, and the lack of coincidence of the built-in identity types and the important notion of bisimilarity. Guarded recursion in the sense of Nakano has recently been suggested as a possible approach to dealing with the problem of productivity, allowing this to be encoded in types. Indeed, coinductive types can be encoded using a combination of guarded recursion and universal quantification over clocks. This paper studies the notion of bisimilarity for guarded recursive types in Ticked Cubical Type Theory, an extension of Cubical Type Theory with guarded recursion. We prove that, for any functor, an abstract, category theoretic notion of bisimilarity for the final guarded coalgebra is equivalent (in the sense of homotopy type theory) to path equality (the primitive notion of equality in cubical type theory). As a worked example we study a guarded notion of labelled transition systems, and show that, as a special case of the general theorem, path equality coincides with an adaptation of the usual notion of bisimulation for processes. In particular, this implies that guarded recursion can be used to give simple equational reasoning proofs of bisimilarity. This work should be seen as a step towards obtaining bisimilarity as path equality for coinductive types using the encodings mentioned above.
View PDF Chat

The Sequent Calculus of Skew Monoidal Categories

2018-12-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a … Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context (a list of formulae), and the connectives unit and tensor behave like in intuitionistic non-commutative linear logic (the logic of monoidal categories) except that the left rules may only be applied in stoup position. We show the admissibility of two forms cut (stoup cut and context cut), and prove the calculus sound and complete with respect to existence of maps in the free skew monoidal category. We then introduce an equivalence relation on sequent calculus derivations and prove that there is a one-to-one correspondence between equivalence classes of derivations and maps in the free skew monoidal category. Finally, we identify a subcalculus of focused derivations, and establish that it contains exactly one canonical representative from each equivalence class. As an end result, we obtain simple algorithms both for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates, in particular, for deciding whether there is a map. We have formalized this development in the dependently typed programming language Agda.
View PDF Chat

Bisimulation as path type for guarded recursive types

2018-10-31
Rasmus Ejlers Møgelberg , Niccolò Veltri
In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such … In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such as Coq and Agda. Currently, programming and reasoning about coinductive types is difficult for two reasons: The need for recursive definitions to be productive, and the lack of coincidence of the built-in identity types and the important notion of bisimilarity. Guarded recursion in the sense of Nakano has recently been suggested as a possible approach to dealing with the problem of productivity, allowing this to be encoded in types. Indeed, coinductive types can be encoded using a combination of guarded recursion and universal quantification over clocks. This paper studies the notion of bisimilarity for guarded recursive types in Ticked Cubical Type Theory, an extension of Cubical Type Theory with guarded recursion. We prove that, for any functor, an abstract, category theoretic notion of bisimilarity for the final guarded coalgebra is equivalent (in the sense of homotopy type theory) to path equality (the primitive notion of equality in cubical type theory). As a worked example we study a guarded notion of labelled transition systems, and show that, as a special case of the general theorem, path equality coincides with an adaptation of the usual notion of bisimulation for processes. In particular, this implies that guarded recursion can be used to give simple equational reasoning proofs of bisimilarity. This work should be seen as a step towards obtaining bisimilarity as path equality for coinductive types using the encodings mentioned above.

Bisimulation as path type for guarded recursive types

2018-01-01
Rasmus Ejlers Møgelberg , Niccolò Veltri
In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such … In type theory, coinductive types are used to represent processes, and are thus crucial for the formal verification of non-terminating reactive programs in proof assistants based on type theory, such as Coq and Agda. Currently, programming and reasoning about coinductive types is difficult for two reasons: The need for recursive definitions to be productive, and the lack of coincidence of the built-in identity types and the important notion of bisimilarity. Guarded recursion in the sense of Nakano has recently been suggested as a possible approach to dealing with the problem of productivity, allowing this to be encoded in types. Indeed, coinductive types can be encoded using a combination of guarded recursion and universal quantification over clocks. This paper studies the notion of bisimilarity for guarded recursive types in Ticked Cubical Type Theory, an extension of Cubical Type Theory with guarded recursion. We prove that, for any functor, an abstract, category theoretic notion of bisimilarity for the final guarded coalgebra is equivalent (in the sense of homotopy type theory) to path equality (the primitive notion of equality in cubical type theory). As a worked example we study a guarded notion of labelled transition systems, and show that, as a special case of the general theorem, path equality coincides with an adaptation of the usual notion of bisimulation for processes. In particular, this implies that guarded recursion can be used to give simple equational reasoning proofs of bisimilarity. This work should be seen as a step towards obtaining bisimilarity as path equality for coinductive types using the encodings mentioned above.
View PDF Chat

Finiteness and rational sequences, constructively

2017-01-01
Tarmo Uustalu , Niccolò Veltri
Abstract Rational sequences are possibly infinite sequences with a finite number of distinct suffixes. In this paper, we present different implementations of rational sequences in Martin–Löf type theory. First, we … Abstract Rational sequences are possibly infinite sequences with a finite number of distinct suffixes. In this paper, we present different implementations of rational sequences in Martin–Löf type theory. First, we literally translate the above definition of rational sequence into the language of type theory, i.e., we construct predicates on possibly infinite sequences expressing the finiteness of the set of suffixes. In type theory, there exist several inequivalent notions of finiteness. We consider two of them, listability and Noetherianness, and show that in the implementation of rational sequences the two notions are interchangeable. Then we introduce the type of lists with backpointers, which is an inductive implementation of rational sequences. Lists with backpointers can be unwound into rational sequences, and rational sequences can be truncated into lists with backpointers. As an example, we see how to convert the fractional representation of a rational number into its decimal representation and vice versa.

Variations on Noetherianness

2016-04-01
Denis Firsov , Tarmo Uustalu , Niccolò Veltri
In constructive mathematics, several nonequivalent notions of finiteness exist. In this paper, we continue the study of Noetherian sets in the dependently typed setting of the Agda programming language. We … In constructive mathematics, several nonequivalent notions of finiteness exist. In this paper, we continue the study of Noetherian sets in the dependently typed setting of the Agda programming language. We want to say that a set is Noetherian, if, when we are shown elements from it one after another, we will sooner or later have seen some element twice. This idea can be made precise in a number of ways. We explore the properties and connections of some of the possible encodings. In particular, we show that certain implementations imply decidable equality while others do not, and we construct counterexamples in the latter case. Additionally, we explore the relation between Noetherianness and other notions of finiteness.
View PDF Chat
Coauthor Papers Together
Tarmo Uustalu 11
Noam Zeilberger 8
Niels van der Weide 4
Rasmus Ejlers Møgelberg 4
Dan Frumin 2
Marco Maggesi 2
Cheng-Syuan Wan 2
Benedikt Ahrens 2
Elisabeth Stenholm 1
Bassel Mannaa 1
Denis Firsov 1
Niels Voorneveld 1
Andrea Vezzosi 1
Håkon Robbestad Gylterud 1

Skew-monoidal categories and bialgebroids

2012-08-10
Kornél Szlachányi
View PDF Chat

Skew monoidal categories and skew multicategories

2018-03-23
John Bourke , Stephen Lack
View PDF Chat

Triangulations, orientals, and skew monoidal categories

2014-03-28
Stephen Lack , Ross Street
A concrete model of the free skew-monoidal category Fsk on a single generating object is obtained. The situation is clubbable in the sense of G.M. Kelly, so this allows a … A concrete model of the free skew-monoidal category Fsk on a single generating object is obtained. The situation is clubbable in the sense of G.M. Kelly, so this allows a description of the free skew-monoidal category on any category. As the objects of Fsk are meaningfully bracketed words in the skew unit I and the generating object X, it is necessary to examine bracketings and to find the appropriate kinds of morphisms between them. This leads us to relationships between triangulations of polygons, the Tamari lattice, left and right bracketing functions, and the orientals. A consequence of our description of Fsk is a coherence theorem asserting the existence of a strictly structure-preserving faithful functor from Fsk to the skew-monoidal category of finite non-empty ordinals and first-element-and-order-preserving functions. This in turn provides a complete solution to the word problem for skew monoidal categories.
View PDF Chat

The Catalan simplicial set

2014-12-03
Mitchell Buckley , Richard Garner , Stephen Lack +1 more
The Catalan numbers are well-known to be the answer to many different counting problems, and so there are many different families of sets whose cardinalities are the Catalan numbers. We … The Catalan numbers are well-known to be the answer to many different counting problems, and so there are many different families of sets whose cardinalities are the Catalan numbers. We show how such a family can be given the structure of a simplicial set. We show how the low-dimensional parts of this simplicial set classify, in a precise sense, the structures of monoid and of monoidal category. This involves aspects of combinatorics, algebraic topology, quantum groups, logic, and category theory.
View PDF Chat

Skew-closed categories

2012-10-22
Ross Street

On MacLane's conditions for coherence of natural associativities, commutativities, etc.

1964-12-01
G. M. Kelly

Skew monoidales, skew warpings and quantum categories

2012-04-01
Stephen Lack , Ross Street
Kornel Szlachanyi [28] recently used the term skew-monoidal category for a particular laxi ed version of monoidal category. He showed that bialgebroids H with base ring R could be characterized … Kornel Szlachanyi [28] recently used the term skew-monoidal category for a particular laxi ed version of monoidal category. He showed that bialgebroids H with base ring R could be characterized in terms of skew-monoidal structures on the category of one-sided R-modules for which the lax unit was R itself. We de ne skew monoidales (or skew pseudo-monoids) in any monoidal bicategory M . These are skew-monoidal categories when M is Cat. Our main results are presented at the level of monoidal bicategories. However, a consequence is that quantum categories [10] with base comonoid C in a suitably complete braided monoidal category V are precisely skew monoidales in Comod(V ) with unit coming from the counit of C. Quantum groupoids (in the sense of [6] rather than [10]) are those skew monoidales with invertible associativity constraint. In fact, we provide some very general results connecting opmonoidal monads and skew monoidales. We use a lax version of the concept of warping de ned in [3] to modify monoidal structures.

Monads need not be endofunctors

2015-03-06
Thosten Altenkirch , James Chapman , Tarmo Uustalu
We introduce a generalization of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed lambda-calculus syntax and indexed containers. We … We introduce a generalization of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed lambda-calculus syntax and indexed containers. We show that the Kleisli and Eilenberg-Moore constructions carry over to relative monads and are related to relative adjunctions. Under reasonable assumptions, relative monads are monoids in the functor category concerned and extend to monads, giving rise to a coreflection between relative monads and monads. Arrows are also an instance of relative monads.
View PDF Chat

Free skew monoidal categories

2017-12-20
John Bourke , Stephen Lack
View PDF Chat

Coherence for Skew-Monoidal Categories

2014-06-05
Tarmo Uustalu
I motivate a variation (due to K. Szlach\'{a}nyi) of monoidal categories called skew-monoidal categories where the unital and associativity laws are not required to be isomorphisms, only natural transformations. Coherence … I motivate a variation (due to K. Szlach\'{a}nyi) of monoidal categories called skew-monoidal categories where the unital and associativity laws are not required to be isomorphisms, only natural transformations. Coherence has to be formulated differently than in the well-known monoidal case. In my (to my knowledge new) version, it becomes a statement of uniqueness of normalizing rewrites. I present a proof of this coherence theorem and also formalize it fully in the dependently typed programming language Agda.
View PDF Chat

Skew monoidales, skew warpings and quantum categories

2012-01-01
Stephen Lack , Ross Street
Kornel Szlach\'anyi recently used the term skew-monoidal category for a particular laxified version of monoidal category. He showed that bialgebroids $H$ with base ring $R$ could be characterized in terms … Kornel Szlach\'anyi recently used the term skew-monoidal category for a particular laxified version of monoidal category. He showed that bialgebroids $H$ with base ring $R$ could be characterized in terms of skew-monoidal structures on the category of one-sided $R$-modules for which the lax unit was $R$ itself. We define skew monoidales (or skew pseudo-monoids) in any monoidal bicategory $\mathscr M$. These are skew-monoidal categories when $\mathscr M$ is $\mathrm{Cat}$. Our main results are presented at the level of monoidal bicategories. However, a consequence is that quantum categories in the sense of Day-Street with base comonoid $C$ in a suitably complete braided monoidal category $\mathscr V$ are precisely skew monoidales in $\mathrm{Comod} (\mathscr V)$ with unit coming from the counit of $C$. Quantum groupoids are those skew monoidales with invertible associativity constraint. In fact, we provide some very general results connecting opmonoidal monads and skew monoidales. We use a lax version of the concept of warping defined recently by Booker-Street to modify monoidal structures.
View PDF Chat

Proof Theory of Partially Normal Skew Monoidal Categories

2021-01-19
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms … The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms but merely transformations in a particular direction. In previous work, we showed that the free skew monoidal category on a set of generating objects can be concretely presented as a sequent calculus. This calculus enjoys cut elimination and admits focusing, i.e. a subsystem of canonical derivations, which solves the coherence problem for skew monoidal categories. In this paper, we develop sequent calculi for partially normal skew monoidal categories, which are skew monoidal categories with one or more structural laws invertible. Each normality condition leads to additional inference rules and equations on them. We prove cut elimination and we show that the calculi admit focusing. The result is a family of sequent calculi between those of skew monoidal categories and (fully normal) monoidal categories. On the level of derivability, these define 8 weakenings of the (unit,tensor) fragment of intuitionistic non-commutative linear logic.
View PDF Chat

Skew structures in 2-category theory and homotopy theory

2015-12-08
John Bourke
View PDF Chat

Braided skew monoidal categories

2020-01-21
John Bourke , Stephen Lack
We introduce the notion of a braiding on a skew monoidal category, whose curious feature is that the defining isomorphisms involve three objects rather than two. These braidings are shown … We introduce the notion of a braiding on a skew monoidal category, whose curious feature is that the defining isomorphisms involve three objects rather than two. These braidings are shown to arise from, and classify, cobraidings (also known as coquasitriangular structures) on bialgebras. Using a multicategorical approach we also describe examples of braidings on skew monoidal categories arising from 2-category theory.

Eilenberg-Kelly Reloaded

2020-10-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it … The Eilenberg-Kelly theorem states that a category C with an object I and two functors ⊗:C×C→C and ⊸:Cop×C→C related by an adjunction −⊗B⊣B⊸− natural in B is monoidal iff it is closed and moreover the adjunction holds internally. We dissect the proof of this theorem and observe that the necessity for a side condition on closedness arises because the standard definition of closed category is left-skew in regards to associativity. We analyze Street's observation that left-skew monoidality is equivalent to left-skew closedness and establish that monoidality is equivalent to closedness unconditionally under an adjusted definition of closedness that requires normal associativity. We also work out a definition of right-skew closedness equivalent to right-skew monoidality. We give examples of each type of structure; in particular, we look at the Kleisli category of a left-strong monad on a left-skew closed category and the Kleisli category of a lax closed monad on a right-skew closed category. We also view skew and normal monoidal and closed categories as special cases of skew and normal promonoidal categories and take a brief look at left-skew prounital-closed categories.

A sequent calculus for a semi-associative law

2019-02-05
Noam Zeilberger
We introduce a sequent calculus with a simple restriction of Lambek's product rules that precisely captures the classical Tamari order, i.e., the partial order on fully-bracketed words (equivalently, binary trees) … We introduce a sequent calculus with a simple restriction of Lambek's product rules that precisely captures the classical Tamari order, i.e., the partial order on fully-bracketed words (equivalently, binary trees) induced by a semi-associative law (equivalently, right rotation). We establish a focusing property for this sequent calculus (a strengthening of cut-elimination), which yields the following coherence theorem: every valid entailment in the Tamari order has exactly one focused derivation. We then describe two main applications of the coherence theorem, including: 1. A new proof of the lattice property for the Tamari order, and 2. A new proof of the Tutte-Chapoton formula for the number of intervals in the Tamari lattice $Y_n$. Comment: This article is an extended version of a paper presented at FSCD 2017. [v2: minor rev] arXiv admin note: text overlap with arXiv:1701.02917

Internal type theory

1996-01-01
Peter Dybjer

The Sequent Calculus of Skew Monoidal Categories

2018-12-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a … Szlachányi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context (a list of formulae), and the connectives unit and tensor behave like in intuitionistic non-commutative linear logic (the logic of monoidal categories) except that the left rules may only be applied in stoup position. We show the admissibility of two forms cut (stoup cut and context cut), and prove the calculus sound and complete with respect to existence of maps in the free skew monoidal category. We then introduce an equivalence relation on sequent calculus derivations and prove that there is a one-to-one correspondence between equivalence classes of derivations and maps in the free skew monoidal category. Finally, we identify a subcalculus of focused derivations, and establish that it contains exactly one canonical representative from each equivalence class. As an end result, we obtain simple algorithms both for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates, in particular, for deciding whether there is a map. We have formalized this development in the dependently typed programming language Agda.
View PDF Chat

The Sequent Calculus of Skew Monoidal Categories

2021-01-01
Tarmo Uustalu , Niccolò Veltri , Noam Zeilberger
View PDF Chat

Univalent categories and the Rezk completion

2015-01-19
Benedikt Ahrens , Krzysztof Kapulkin , Michael Shulman
We develop category theory within Univalent Foundations, which is a foundational system for mathematics based on a homotopical interpretation of dependent type theory. In this system, we propose a definition … We develop category theory within Univalent Foundations, which is a foundational system for mathematics based on a homotopical interpretation of dependent type theory. In this system, we propose a definition of ‘category’ for which equality and equivalence of categories agree. Such categories satisfy a version of the univalence axiom, saying that the type of isomorphisms between any two objects is equivalent to the identity type between these objects; we call them ‘saturated’ or ‘univalent’ categories. Moreover, we show that any category is weakly equivalent to a univalent one in a universal way. In homotopical and higher-categorical semantics, this construction corresponds to a truncated version of the Rezk completion for Segal spaces, and also to the stack completion of a prestack.
View PDF Chat

Univalent higher categories via complete Semi-Segal types

2017-12-27
Paolo Capriotti , Nicolai Kraus
Category theory in homotopy type theory is intricate as categorical laws can only be stated "up to homotopy", and thus require coherences. The established notion of a univalent category (as … Category theory in homotopy type theory is intricate as categorical laws can only be stated "up to homotopy", and thus require coherences. The established notion of a univalent category (as introduced by Ahrens et al.) solves this by considering only truncated types, roughly corresponding to an ordinary category. This fails to capture many naturally occurring structures, stemming from the fact that the naturally occurring structures in homotopy type theory are not ordinary, but rather higher categories. Out of the large variety of approaches to higher category theory that mathematicians have proposed, we believe that, for type theory, the simplicial strategy is best suited. Work by Lurie and Harpaz motivates the following definition. Given the first ( n +3) levels of a semisimplicial type S , we can equip S with three properties: first, contractibility of the types of certain horn fillers; second, a completeness property; and third, a truncation condition. We call this a complete semi-Segal n -type . This is very similar to an earlier suggestion by Schreiber. The definition of a univalent (1-) category by Ahrens et al. can easily be extended or restricted to the definition of a univalent n -category (more precisely, ( n ,1)-category) for n ∈ {0,1,2}, and we show that the type of complete semi-Segal n -types is equivalent to the type of univalent n -categories in these cases. Thus, we believe that the notion of a complete semi-Segal n -type can be taken as the definition of a univalent n -category. We provide a formalisation in the proof assistant Agda using a completely explicit representation of semi-simplicial types for levels up to 4.
View PDF Chat

On Higher Inductive Types in Cubical Type Theory

2018-06-27
Thierry Coquand , Simon Huber , Anders Mörtberg
Cubical type theory provides a constructive justification to certain aspects of homotopy type theory such as Voevodsky's univalence axiom. This makes many extensionality principles, like function and propositional extensionality, directly … Cubical type theory provides a constructive justification to certain aspects of homotopy type theory such as Voevodsky's univalence axiom. This makes many extensionality principles, like function and propositional extensionality, directly provable in the theory. This paper describes a constructive semantics, expressed in a presheaf topos with suitable structure inspired by cubical sets, of some higher inductive types. It also extends cubical type theory by a syntax for the higher inductive types of spheres, torus, suspensions, truncations, and pushouts. All of these types are justified by the semantics and have judgmental computation rules for all constructors, including the higher dimensional ones, and the universes are closed under these type formers.
View PDF Chat

Natural models of homotopy type theory

2016-11-17
Steve Awodey
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.
View PDF Chat

Coherence in nonmonoidal closed categories

1977-01-01
Miguel L. Laplaza
A Trionmonoidal closed category is a category with an internal homomorphism functor, left Yoneda natural arrows, unity object and some natural transformations and coherence axioms. The object of this paper … A Trionmonoidal closed category is a category with an internal homomorphism functor, left Yoneda natural arrows, unity object and some natural transformations and coherence axioms. The object of this paper is to give a complete solution of the coherence problem in this structure: we use a cut-elimination theorem as basic tool to prove that the elementary natural transformations are characterized by their graph (roughly speaking the graph is the type of identification imposed by a natural transformation on the arguments of its domain and codomain).

Introduction to bicategories

1967-01-01
Jean Bénabou

Finite sets in homotopy type theory

2018-01-08
Dan Frumin , Herman Geuvers , Léon Gondelman +1 more
We study different formalizations of finite sets in homotopy type theory to obtain a general definition that exhibits both the computational facilities and the proof principles expected from finite sets. … We study different formalizations of finite sets in homotopy type theory to obtain a general definition that exhibits both the computational facilities and the proof principles expected from finite sets. We use higher inductive types to define the type K(A) of "finite sets over type A" à la Kuratowski without assuming that K(A) has decidable equality. We show how to define basic functions and prove basic properties after which we give two applications of our definition.
View PDF Chat

Finitary Higher Inductive Types in the Groupoid Model

2018-04-01
Peter Dybjer , Hugo Moeneclaey
A higher inductive type of level 1 (a 1-hit) has constructors for points and paths only, whereas a higher inductive type of level 2 (a 2-hit) has constructors for surfaces … A higher inductive type of level 1 (a 1-hit) has constructors for points and paths only, whereas a higher inductive type of level 2 (a 2-hit) has constructors for surfaces too. We restrict attention to finitary higher inductive types and present general schemata for the types of their point, path, and surface constructors. We also derive the elimination and equality rules from the types of constructors for 1-hits and 2-hits. Moreover, we construct a groupoid model for dependent type theory with 2-hits and point out that we obtain a setoid model for dependent type theory with 1-hits by truncating the groupoid model.
View PDF Chat

Homotopy Type Theory: Univalent Foundations of Mathematics

2013-01-01
Peter Aczel , Benedikt Ahrens , Thorsten Altenkirch +7 more
Homotopy type theory is a new branch of mathematics, based on a recently discovered connection between homotopy theory and type theory, which brings new ideas into the very foundation of … Homotopy type theory is a new branch of mathematics, based on a recently discovered connection between homotopy theory and type theory, which brings new ideas into the very foundation of mathematics. On the one hand, Voevodsky's subtle and beautiful "univalence axiom" implies that isomorphic structures can be identified. On the other hand, "higher inductive types" provide direct, logical descriptions of some of the basic spaces and constructions of homotopy theory. Both are impossible to capture directly in classical set-theoretic foundations, but when combined in homotopy type theory, they permit an entirely new kind of "logic of homotopy types". This suggests a new conception of foundations of mathematics, with intrinsic homotopical content, an "invariant" conception of the objects of mathematics -- and convenient machine implementations, which can serve as a practical aid to the working mathematician. This book is intended as a first systematic exposition of the basics of the resulting "Univalent Foundations" program, and a collection of examples of this new style of reasoning -- but without requiring the reader to know or learn any formal logic, or to use any computer proof assistant.
View PDF Chat

A Model of Countable Nondeterminism in Guarded Type Theory

2014-01-01
Aleš Bizjak , Lars Birkedal , Marino Miculan

A theory of linear typings as flows on 3-valent graphs

2018-06-27
Noam Zeilberger
Building on recently established enumerative connections between lambda calculus and the theory of embedded graphs (or "maps"), this paper develops an analogy between typing (of lambda terms) and coloring (of … Building on recently established enumerative connections between lambda calculus and the theory of embedded graphs (or "maps"), this paper develops an analogy between typing (of lambda terms) and coloring (of maps). Our starting point is the classical notion of an abelian group-valued "flow" on an abstract graph (Tutte, 1954). Typing a linear lambda term may be naturally seen as constructing a flow (on an embedded 3-valent graph with boundary) valued in a more general algebraic structure consisting of a preordered set equipped with an "implication" operation and unit satisfying composition, identity, and unit laws. Interesting questions and results from the theory of flows (such as the existence of nowhere-zero flows) may then be re-examined from the standpoint of lambda calculus and logic. For example, we give a characterization of when the local flow relations (across vertices) may be categorically lifted to a global flow relation (across the boundary), proving that this holds just in case the underlying map has the orientation of a lambda term. We also develop a basic theory of rewriting of flows that suggests topological meanings for classical completeness results in combinatory logic, and introduce a polarized notion of flow, which draws connections to the theory of proof-nets in linear logic and to bidirectional typing.
View PDF Chat

Closed categories and the theory of proofs

1981-01-01
G. E. Mints

Non-Wellfounded Trees in Homotopy Type Theory

2015-01-01
Benedikt Ahrens , Paolo Capriotti , Régis Spadotti
We prove a conjecture about the constructibility of conductive types - in the principled form of indexed M-types - in Homotopy Type Theory. The conjecture says that in the presence … We prove a conjecture about the constructibility of conductive types - in the principled form of indexed M-types - in Homotopy Type Theory. The conjecture says that in the presence of inductive types, coinductive types are derivable. Indeed, in this work, we construct coinductive types in a subsystem of Homotopy Type Theory; this subsystem is given by Intensional Martin-Lof type theory with natural numbers and Voevodsky's Univalence Axiom. Our results are mechanized in the computer proof assistant Agda.

The clocks they are adjunctions:Denotational semantics for Clocked Type Theory

2018-01-01
Bassel Mannaa , Rasmus Ejlers Møgelberg
Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming … Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming language features using an abstract form of step-indexing. CloTT has previously been shown to enjoy a number of syntactic properties including strong normalisation, canonicity and decidability of type checking. In this paper we present a denotational semantics for CloTT useful, e.g., for studying future extensions of CloTT with constructions such as path types. The main challenge for constructing this model is to model the notion of ticks used in CloTT for coinductive reasoning about coinductive types. We build on a category previously used to model guarded recursion, but in this category there is no object of ticks, so tick-assumptions in a context can not be modelled using standard tools. Instead we show how ticks can be modelled using adjoint functors, and how to model the tick constant using a semantic substitution.

Efficient solutions to the braid isotopy problem

2008-03-06
Patrick Dehornoy
View PDF Chat

Higher Operads, Higher Categories

2004-07-22
Tom Leinster
Higher-dimensional category theory is the study of n-categories, operads, braided monoidal categories, and other such exotic structures. It draws its inspiration from areas as diverse as topology, quantum algebra, mathematical … Higher-dimensional category theory is the study of n-categories, operads, braided monoidal categories, and other such exotic structures. It draws its inspiration from areas as diverse as topology, quantum algebra, mathematical physics, logic, and theoretical computer science. The heart of this book is the language of generalized operads. This is as natural and transparent a language for higher category theory as the language of sheaves is for algebraic geometry, or vector spaces for linear algebra. It is introduced carefully, then used to give simple descriptions of a variety of higher categorical structures. In particular, one possible definition of n-category is discussed in detail, and some common aspects of other possible definitions are established. This is the first book on the subject and lays its foundations. It will appeal to both graduate students and established researchers who wish to become acquainted with this modern branch of mathematics.
View PDF Chat

Coequational logic for accessible functors

2010-05-18
Daniel Schwencke

Relating Coalgebraic Notions of Bisimulation

2009-01-01
Sam Staton
View PDF Chat

Syntactic aspects of hypergraph polytopes

2018-08-13
Pierre-Louis Curien , Jovana Obradović , Jelena Ivanović
View PDF Chat

Ribbon Tensorial Logic

2018-06-27
Paul-André Melliès
We introduce a topologically-aware version of tensorial logic, called ribbon tensorial logic. To every proof of the logic, we associate a ribbon tangle which tracks the flow of tensorial negations … We introduce a topologically-aware version of tensorial logic, called ribbon tensorial logic. To every proof of the logic, we associate a ribbon tangle which tracks the flow of tensorial negations inside the proof. The translation is functorial: it is performed by exhibiting a correspondence between the notion of dialogue category in proof theory and the notion of ribbon category in knot theory. Our main result is that the translation is also faithful: two proofs are equal modulo the equational theory of ribbon tensorial logic if and only if the associated ribbon tangles are equal up to topological deformation. This "proof-as-tangle" theorem may be understood as a coherence theorem for balanced dialogue categories, and as a mathematical foundation for topological game semantics.
View PDF Chat

On embedding closed categories

1978-06-01
Brian J. Day , Miguel L. Laplaza
This article contains one method of fully embedding a symmetric closed category into a symmetric monoidal closed category. Such an embedding is very useful in the study of coherence problems. … This article contains one method of fully embedding a symmetric closed category into a symmetric monoidal closed category. Such an embedding is very useful in the study of coherence problems. Also we give an example of a non-symmetric closed category for which, under the embedding discussed in this article, the resultant monoidal closed structure has associativity not an isomorphism.
View PDF Chat

Sur le nombre d'intervalles dans les treillis de Tamari

2006-01-01
Frédéric Chapoton
We enumerate the intervals in the Tamari lattices. For this, we introduce an inductive description of the intervals. Then a notion of "new interval" is defined and these are also … We enumerate the intervals in the Tamari lattices. For this, we introduce an inductive description of the intervals. Then a notion of "new interval" is defined and these are also enumerated. A a side result, the inverse of two special series is computed in a group of tree-indexed series.
View PDF Chat

Braided Tensor Categories

1993-11-01
André Joyal , Ross Street

Categories for the Working Mathematician

1971-01-01
Saunders Mac Lane
View PDF Chat

A model of type theory in cubical sets

2014-01-01
M Bezem , Thierry Coquand , Simon Huber
We present a model of type theory with dependent product, sum, and identity, in cubical sets. We describe a universe and explain how to transform an equivalence between two types … We present a model of type theory with dependent product, sum, and identity, in cubical sets. We describe a universe and explain how to transform an equivalence between two types into an equality. We also explain how to model propositional truncation and the circle. While not expressed internally in type theory, the model is expressed in a constructive metalogic. Thus it is a step towards a computational interpretation of Voevodsky's Univalence Axiom.

Axioms for Modelling Cubical Type Theory in a Topos

2016-08-25
Ian Orton , Andrew M. Pitts
The homotopical approach to intensional type theory views proofs of equality as paths. We explore what is required of an interval-like object I in a topos to give a model … The homotopical approach to intensional type theory views proofs of equality as paths. We explore what is required of an interval-like object I in a topos to give a model of type theory in which elements of identity types are functions with domain I. Cohen, Coquand, Huber and Mortberg give such a model using a particular category of presheaves. We investigate the extent to which their model construction can be expressed in the internal type theory of any topos and identify a collection of quite weak axioms for this purpose. This clarifies the definition and properties of the notion of uniform Kan filling that lies at the heart of their constructive interpretation of Voevodsky's univalence axiom. Furthermore, since our axioms can be satisfied in a number of different ways, we show that there is a range of topos-theoretic models of homotopy type theory in this style.

Biequivalences in tricategories

2011-01-01
Nick Gurski
We show that every internal biequivalence in a tricategory T is part of a biadjoint biequivalence. We give two applications of this result, one for transporting monoidal structures and one … We show that every internal biequivalence in a tricategory T is part of a biadjoint biequivalence. We give two applications of this result, one for transporting monoidal structures and one for equipping a monoidal bicategory with invertible objects with a coherent choice of those inverses.

First steps in synthetic guarded domain theory: step-indexing in the topos of trees

2012-10-03
Lars Birkedal , Rasmus Ejlers Møgelberg , Jan Schwinghammer +1 more
We present the topos S of trees as a model of guarded recursion. We study the internal dependently-typed higher-order logic of S and show that S models two modal operators, … We present the topos S of trees as a model of guarded recursion. We study the internal dependently-typed higher-order logic of S and show that S models two modal operators, on predicates and types, which serve as guards in recursive definitions of terms, predicates, and types. In particular, we show how to solve recursive type equations involving dependent types. We propose that the internal logic of S provides the right setting for the synthetic construction of abstract versions of step-indexed models of programming languages and program logics. As an example, we show how to construct a model of a programming language with higher-order store and recursive types entirely inside the internal logic of S. Moreover, we give an axiomatic categorical treatment of models of synthetic guarded domain theory and prove that, for any complete Heyting algebra A with a well-founded basis, the topos of sheaves over A forms a model of synthetic guarded domain theory, generalizing the results for S.
View PDF Chat

A Coherent Approach to Pseudomonads

2000-06-01
Stephen Lack

An Alternative Description of Braided Monoidal Categories

2013-11-12
Alexei Davydov , Ingo Runkel
View PDF Chat

Denotational semantics of recursive types in synthetic guarded domain theory

2016-07-05
Rasmus Ejlers Møgelberg , Marco Paviotti
Guarded recursion is a form of recursion where recursive calls are guarded by delay modalities. Previous work has shown how guarded recursion is useful for reasoning operationally about programming languages … Guarded recursion is a form of recursion where recursive calls are guarded by delay modalities. Previous work has shown how guarded recursion is useful for reasoning operationally about programming languages with advanced features including general references, recursive types, countable non-determinism and concurrency.
View PDF Chat