Full Definability in a Profunctorial Model
Takeshi Tsukada, Kazuyuki Asada, Kengo Hirata · 2026
Read Full Definability in a Profunctorial Model by Takeshi Tsukada, Kazuyuki Asada, Kengo Hirata (2026) 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-2604-26829.txt.
Introduction
Tsukada, Asada and Hirata study full definability in a model built from profunctors on groupoids, a proof-relevant cousin of the relational model. Full definability means each item of the model is the sense of a proof or program. Though profunctors are far more tangled than relations, the authors show that relational-model ideas plus stability in them give a full account of definable profunctors. All families of stable and total ones are definable by proof-nets of multiplicative linear logic with MIX, and stability works as a correctness test.
Catalog record
| CREATOR | Takeshi Tsukada, Kazuyuki Asada, Kengo Hirata |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105688 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26829
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Full Definability in a Profunctorial Model Takeshi Tsukada, Kazuyuki Asada, Kengo Hirata Abstract . A semantic model enjoys full definability if every semantic element in the model is a denotation of some proof or program. Full definability indicates that the model captures programs and proofs in a highly detailed manner. This paper studies full definability in a model based on the (bi)category of profunctors on groupoids, which is a proof-relevant variant of the relational model. Despite the fact that a profunctor is far more complicated than a relation, we show that a rather straightforward application of the ideas for the relational model, together with the notion of stability in profunctors, provides a complete characterisation of definable profunctors. More precisely, all logical families of stable and total profunctors are definable by proof-nets of multiplicative linear logic with MIX. As a part of the full definability proof, we show that the stability serves as a correctness criterion, which we think is of independent interest. 1. Introduction The relational model based on the category of sets and relations is one of the most fundamental models of linear logic ( 19 ) . It is both concise and conceptually rich, and it connects naturally to a wide range of other notions, including intersection types ( 8 ) and a game model ( 22 ) . The relational model itself forms a compact closed category, so the tensor product \otimes and par \invamp collapse in the relational model. However, by equipping sets with additional structure and restricting to relations that respect that structure, one can obtain many important models that are not necessarily compact closed. Examples of such models include coherence spaces ( 19 ) , hypercoherences ( 13 ) , finiteness spaces ( 12 ) , and totality spaces ( 25 ) . The (bi)category of profunctors can be seen as a categorification of the category of relations. While a relation records only whether two elements are related or not, a profunctor carries richer information: it can encode how many ways two objects may be related, and even some relationships among those ways. Owing to this additional structure, profunctor-based models are deeply connected to several important themes, including the Taylor expansion ( 32 ; 33 ) (in the sense of Danos and Ehrhard ( 6 ) ), type derivations in intersection type systems ( 27 ) , and game semantics ( 4 ; 5 ) . For this reason, the (bi)category of profunctors has attracted considerable attention in recent years ( 14 ; 32 ; 33 ; 27 ; 4 ; 17 ) . It is known that profunctors arising as interpretations of linear-logic proofs and of \lambda -terms enjoy special properties. For instance, one can associate a matrix to a profunctor; although this passage is not functorial for arbitrary profunctors, it behaves as a functor when restricted to profunctors that are denotations of \lambda -terms ( 33 ; 4 ) . It is therefore natural to ask what intrinsic properties characterize profunctors that are representable by proofs or \lambda -terms. This paper addresses this question and, as an answer, presents a fully definable model based on profunctors. A model is said to be fully definable (or fully complete ) if every element of the model arises as the denotation of some proof or \lambda -term. A number of fully definable models have been constructed. For example, Loader ( 25 ) proposed the totality space model , which is based on the relational model and fully definable for \mathsf{MLL}+\mathsf{Mix} ; Devarajan et al. ( 9 ) shows that a model based on Chu spaces is fully definable for \mathsf{MLL} (without \mathsf{Mix} ); and fully definable game models have been developed for a wide range of programming languages and proof systems (see, e.g., ( 2 ; 1 ; 21 ; 26 ) ). Our construction is based on two key ideas in the literature. The first is Loader’s totality ( 25 ) , which was employed to obtain a fully definable model built on the relational model. Since profunctors generalize relations, totality also plays a central role in our study of profunctors. The second idea is the concept of stable profunctor , introduced by Taylor ( 31 ) and further developed by Fiore et al. ( 16 ; 17 ; 15 ) . The concept of stable profunctor was motivated by Berry’s stable domain theory ( 3 ) and Girard’s normal functor ( 20 ) and proposed as a categorification of the stable domain model. Fortunately, these two ideas can both be understood as instances of orthogonality in the sense of Hyland and Schalk ( 23 ) . We propose stably total orthogonality , which combines these two notions, and construct a fully definable model by using this orthogonality. Given that profunctors are significantly more intricate than relations, it is perhaps surprising that such a simple construction yields a fully definable model. In contrast to the construction of the model, the proof of full definability is not straightforward. Furthermore, we obtain some observations that may be of independent interest. First, we prove that the stability of profunctors yields a correctness criterion ( theorem 11 ). This result can be understood as the profunctorial analogue of Retoré’s result ( 29 ) that coherence of the relational interpretation provides a correctness criterion. Retoré’s proof and ours share the same high level idea of the proof, which suggests a close relationship between coherence and stability; however, at present we do not have a precise correspondence between them in any formal sense. Second, we observe that strict factorization systems naturally arise in the stably total model ( proposition 4 ). Strict factorization systems on groupoids have previously been used for combinatorial analyses of profunctor models and related semantics ( 33 ; 27 ; 4 ; 5 ) . The appearance of strict factorization systems in this paper seems to have the same origin. However, the way strict factorization systems arise here differs from earlier work in two respects. First, in this paper, strict factorization systems emerge from the notions of stability and totality, which at first sight appear unrelated to strict factorization systems. This provides a new perspective that further justifies the role of strict factorization systems in the study of profunctors. Second, whereas existing approaches typically equip each object with a single strict factorization system, in this paper we associate multiple strict factorization systems with each object. Moreover, part of the information of \mathsf{MLL} proofs is also encoded in the choice of which strict factorization system to adopt among these alternatives. The technical contributions of this paper can be summarized as follows. • We construct a new model based on profunctors that is fully definable with respect to \mathsf{MLL}+\mathsf{Mix} . Our result shows that definable profunctors are characterized by using totality and stability . • We show that stability provides a new semantic correctness criterion for \mathsf{MLL}+\mathsf{Mix} . • We show that strict factorization systems arise from stability and totality. This provides a new perspective on the relevance of strict factorization systems in the analysis of profunctors. 1.1. Related Work The definability result of this paper is inspired by Loader’s approach ( 25 ) . Other technically related