Bialgebras in Rel

We study bialgebras in the compact closed category Rel of sets and binary relations. We show that various monoidal categories with extra structure arise as the categories of (co)modules of bialgebras 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 which 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.