Reference. The Sequent Calculus of Skew Monoidal Categories
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, 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.
Cite
Cites 29 works (2 here)
With notes (2)
A sequent calculus for a semi-associative law zeilberger-2019-a
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 .
External (27)
- The sequent calculus of skew monoidal categories (2018)
- Skew monoidal categories and skew multicategories (2017)
- Free skew monoidal categories (2017)
- Homotopy of operads and Grothendieck–Teichmüller groups (2017)
- Monads need not be endofunctors (2015)
- Coherence for Skew-Monoidal Categories (2014)
- The Catalan simplicial set (2013)
- Triangulations, orientals, and skew monoidal categories☆ (2013)
- Skew-closed categories (2012)
- Skew monoidales, skew warpings and quantum categories (2012)
- Skew-monoidal categories and bialgebroids (2012)
- Associahedra, tamari lattices and related structures : Tamari memorial festschrift (2012)
- Sur le nombre d'intervalles dans les treillis de Tamari (2006)
- Higher Operads, Higher Categories (2004)
- Representable multicategories (2000)
- Logic Programming with Focusing Proofs in Linear Logic (1992)
- A new constructive logic: classic logic (1991)
- Categories for the Working Mathematician (2nd ed.) (1978)
- Deductive systems and categories II. Standard constructions and closed categories (1969)
- The collected papers of Gerhard Gentzen (1969)
- Deductive systems and categories I: Syntactic calculus and residuated categories (1968)
- On MacLane's conditions for coherence of natural associativities, commutativities, etc (1964)
- Natural Associativity and Commutativity (1963)
- Catégories avec multiplication (1963)
- On the Calculus of Syntactic Types (1961)
- Monoïdes préordonnés et chaînes de Malcev (1954)
- Untersuchungen über das logische Schließen. I (1935)