Semi-Substructural Logics à la Lambek

Cheng-Syuan Wan · 2025

Read Semi-Substructural Logics à la Lambek by Cheng-Syuan Wan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00496.txt.

Introduction

Cheng-Syuan Wan recasts the proof theory of lopsided category structures in the style of Lambek's logic, in work the head dates to 2024. The catalog lists 2025, but the head's year governs. Skew monoidal categories loosen the usual rules: combining objects still works, but the reshuffling laws point one way only and cannot be reversed.

Earlier sequent systems for these structures, built around a special first position called a stoup, handled the left-handed case but broke on right-handed and two-sided variants. Wan builds new calculi that need no cuts and use trees of formulas instead, echoing Lambek's grammar logic. Each new system matches an older formulation, and the two-sided one is proven sound and complete against relational models. A final correspondence links frame conditions to structural laws, clarifying how the left and right versions mirror each other.

Catalog record

CREATORCheng-Syuan Wan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-00496

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Semi-Substructural Logics à la Lambek Cheng-Syuan Wan Abstract This work studies the proof theory of left (right) skew monoidal closed categories and skew monoidal bi-closed categories from the perspective of non-associative Lambek calculus. Skew monoidal closed categories represent a relaxed version of monoidal closed categories, where the structural laws are not invertible; instead, they are natural transformations with a specific orientation. Uustalu et al. used sequents with stoup (the leftmost position of an antecedent that can be either empty or a single formula) to deductively model left skew monoidal closed categories, yielding results regarding proof identities and categorical coherence. However, their syntax does not work well when modeling right skew monoidal closed and skew monoidal bi-closed categories. We solve the problem by constructing cut-free sequent calculi for left skew monoidal closed and skew monoidal bi-closed categories, reminiscent of non-associative Lambek calculus, with trees as antecedents. Each calculus is respectively equivalent to the sequent calculus with stoup (for left skew monoidal categories) and the axiomatic calculus (for skew monoidal bi-closed categories). Moreover, we prove that the latter calculus is sound and complete with respect to its relational models. We also prove a correspondence between frame conditions and structural laws, providing an algebraic way to understand the relationship between the left and right skew monoidal (closed) categories. 1 Introduction Substructural logics are logic systems that lack at least one of the structural rules, weakening, contraction, and exchange. Joachim Lambek’s syntactic calculus [ 17 ] is a well-known example that disallows weakening, contraction, and exchange. Another example, linear logic, proposed by Jean-Yves Girard [ 13 ] , is a substructural logic in which weakening and contraction are in general disallowed but can be recovered for some formulae via modalities. Substructural logics have been found in numerous applications from computational analysis of natural languages to the development of resource-sensitive programming languages. Left skew monoidal categories [ 24 ] are a weaker variant of MacLane’s monoidal categories where the structural morphisms of associativity and unitality are not required to be bidirectional, they are natural transformations with a particular orientation. Therefore, they can be seen as semi-associative and semi-unital variants of monoidal categories. Left skew monoidal categories arise naturally in the semantics of programming languages [ 3 ] , while the concept of semi-associativity is connected with combinatorial structures like the Tamari lattice and Stasheff associahedra [ 33 , 20 ] . In recent years, Tarmo Uustalu, Niccolò Veltri, and Noam Zeilberger started a research project on semi-substructural logics, which is inspired by a series of developments on left skew monoidal categories and related variants by Szlachányi, Street, Bourke, Lack and others [ 24 , 15 , 23 , 16 , 9 , 6 , 7 , 8 ] . We call the languages of left skew monoidal categories and their variants semi-substructural logics, because they are intermediate logics between (certain fragments of) non-associative and associative intuitionistic linear logic (or Lambek calculus). Semi-associativity and semi-unitality are encoded as follows. Sequents are in the form S\mid\Gamma\vdash A , where the antecedent consists of an optional formula S , called stoup, adapted from Girard [ 14 ] , and an ordered list of formulae \Gamma . The succedent is a single formula A . We restrict the application of introduction rules in an appropriate way to allow only one of the directions of associativity and unitality. This approach has successfully captured languages for a variety of categories, including (i) left skew semigroup [ 33 ] , (ii) left skew monoidal [ 29 ] , (iii) left skew (prounital) closed [ 27 ] , (iv) left skew monoidal closed categories [ 25 , 31 ] , and (v) left distributive skew monoidal categories with finite products and coproducts [ 32 ] through skew variants of the fragments of non-commutative intuitionistic linear logic consisting of combinations of connectives (\mathsf{I},\otimes,\multimap,\land,\lor) . Additionally, discussions have covered partial normality conditions, in which one or more structural morphisms are allowed to have an inverse [ 28 ] , as well as extensions with skew exchange à la Bourke and Lack [ 30 , 32 ] . In all of the aforementioned works, internal languages of left skew monoidal categories and their variants are characterized in a similar way which we call sequent calculus à la Girard. These calculi with sequents of the form S\mid\Gamma\vdash A are cut-free and by their rule design, they are decidable. Moreover, they all admit sound and complete subcalculi inspired by Andreoli’s focusing [ 4 ] in which rules are restricted to be applied in a specific order. A focused calculus provides an algorithm to solve both the proof identity problems for its non-focused calculus and coherence problems for its corresponding variant of left skew monoidal category. By reversing all structural morphisms and modifying coherence conditions in left skew monoidal closed categories, right skew monoidal closed categories emerge [ 26 ] . Moreover, skew monoidal bi-closed categories are defined by appropriately integrating left and right skew monoidal closed structures. It is natural for us to consider sound sequent calculi for these categories. However, the implication rules are not well-behaved when just modeling right skew monoidal closed categories with sequent calculus à la Girard. The problem stems from the skew structure concealed within the flat antecedent of S\mid\Gamma\vdash A . While the antecedent S\mid\Gamma is defined similarly to an ordered list, it is actually a tree associating to the left. We start in Section 2 , by introducing the sequent calculus à la Girard ( \mathtt{LSkG} ) for left skew monoidal closed categories from [ 25 ] and its equivalent sequent calculus à la Lambek ( \mathtt{LSkT} ), which is inspired by sequent calculus for non-associative Lambek calculus [ 10 , 21 ] with trees as antecedents. In Section 3 , we introduce definitions of left (right) skew monoidal closed categories and skew monoidal bi-closed categories, and normality conditions for skew categories. In Section 4 , we describe two calculi that characterize skew monoidal bi-closed categories: one is an axiomatic calculus ( \mathtt{SkMBiCA} ), while the other is a sequent calculus ( \mathtt{SkMBiCT} ) similar to the multimodal non-associative Lambek calculus [ 19 ] . In Section 5 , we introduce the relational semantics for \mathtt{SkMBiCA} via preordered sets of possible worlds with ternary relations. Furthermore, we show a correspondence theorem (Theorem 5.7 ) between conditions on ternary relations and structural laws on any frame. The theorem allows us to prove a thin version of main theorems in [ 26 ] . 2 Sequent Calculus We recall the sequent calculus à la Girard for left skew monoidal closed categories from [ 25 ] , which is a skew variant of non-commutative multiplicative intuitionistic linear logic. Formulae ( \mathsf{Fma} ) in \mathtt{LSkG} are inductively generated by the grammar A,B::=X\ |\ \mathsf{I}\ |\ A\otimes B\ |\ A\multimap B , where X comes from a set \mathsf{At} of atoms, \mathsf{I} is a multiplicative unit, \otimes is multiplicative conjunction and \multimap is a linear implication. A sequent is a triple of the form S\mid\Gamma\vdash_{\mathsf{G}}A , where the antecedent splits into: an optional formula S , called stoup [ 14 ] , and an ordered list of formulae \Gamma and succedent A is a single formula.

Read the complete text