Mathematical Structures in Computer Science


A quantum double construction in Rel


a1 Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan Email:


We study bialgebras and Hopf algebras in the compact closed category Rel of sets and binary relations. Various monoidal categories with extra structure arise as the categories of (co)modules of bialgebras and Hopf algebras in Rel. In particular, for any group G, we derive a ribbon category of crossed G-sets as the category of modules of a Hopf algebra in Rel that is obtained by the quantum double construction. This category of crossed G-sets serves as a model of the braided variant of propositional linear logic.

(Received December 15 2010)

(Revised September 30 2011)

(Online publication May 18 2012)


This is a revised and expanded version of the work presented at the Conference on the Mathematical Foundations of Programming Semantics (MFPS XXVI): see Hasegawa (2010).

This work was partly supported by the Grant-in-Aid for Scientific Research (C) 20500010 and the Grant-in-Aid for Scientific Research (C) 23500016.