11
$\begingroup$

Is there a known description of the free category with both product and coproduct?

That is, given a small category $C$, I want to consider a category $U C$ which has product and coproduct, a functor $C \to U C$ and such that $UC$ is universal for functor preserving both product and coproduct. The case $C = \emptyset$ is already interesting.

I'm also happy to focus on finite product and finite coproduct, especially if it avoids some size problems, though I don't think this is essential.

My guess is that this category should be a category of two-player games (player and opponent) with morphisms being simulation and where outcome of the game are marked by objects of $C$ (if $C = \emptyset$ we should just have a win/lose outcome):

The coproduct of a family of games is the game where the player first chooses which game he wants to play in the family, while their product is the game where the opponent chooses which game he wants to play. The initial object is the game where player loses at the start, and the final object is the one where opponent loses at the start.

But the details of this, and especially the proper definition of the morphisms are a bit involved, so I'm curious whether this has been worked out somewhere.

Of course, as soon as we assume compatibility between product and coproduct (for e.g. distributivity) there are simple description, but here I'm interested in the completely unconstrained situation.

$\endgroup$
5
  • 3
    $\begingroup$ A syntactic construction of the free finite product/coproduct bicompletion is given in Cockett–Seely's Finite sum–product logic. There are also the earlier, suggestively-named papers Free bicomplete categories and Free bicompletion of enriched categories of Joyal, though I couldn't find these online. Hu–Joyal's Coherence Completions of Categories and Their Enriched Softness describes the free completion under products, coproducts and a zero object. $\endgroup$
    – varkor
    May 8, 2020 at 16:43
  • 1
    $\begingroup$ Hughes' A canonical graphical syntax for non-empty finite products and sums treats nonempty finite products and coproducts on discrete categories, where they state that (at point of publication) a categorical formulation of the result for non-discrete categories and empty products/coproducts was an open question. $\endgroup$
    – varkor
    May 8, 2020 at 16:48
  • $\begingroup$ Thank you very much for the references, that sounds very interesting. $\endgroup$ May 8, 2020 at 16:52
  • 1
    $\begingroup$ One last reference: the introduction to Cockett–Santocanale's On the word problem for ΣΠ-categories, and the properties of two-way communication is a nice survey, and also describes this category in terms of games. As far as I can tell, there hasn't been progress on this since, which would suggest the problem is still open. $\endgroup$
    – varkor
    May 8, 2020 at 17:06
  • $\begingroup$ @vakor : You should post these as an answer. I havn't finished studied all these paper, but they seem to answer my question. or at least give a pretty good account of what is known on the topic. especially the last one. $\endgroup$ May 8, 2020 at 20:03

1 Answer 1

13
$\begingroup$

The general problem of giving a categorical construction of the free category with finite coproducts and products (or "free sum–product category") seems to still be open, though there are several works on special cases of the problem.

Cockett–Santocanale's On the word problem for ΣΠ-categories, and the properties of two-way communication gives a good introduction to the problem. They state:

There have been, directly or indirectly, a number of contributions towards our goal in this paper. [...] These related results, however, work only for the fragment without units – or, more precisely, for the fragment with a common initial and final object. As far we know, there is no representation theorem for the full fragment with distinct units.

Special cases of interest include:

Joyal has two related papers (at least for general colimits and limits), but unfortunately without explicit constructions or proofs:

$\endgroup$
1
  • 2
    $\begingroup$ Joyal's papers are available here and here. $\endgroup$ May 13, 2020 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.