6
$\begingroup$

This is a fairly simple, soft-ish question.

I understand the definition of products and coproducts in category theory, and if I can guess or look up what the product is in a given category, I can usually see how to show that it is indeed the product.

However, is there a more systematic way? That is, given a category (especially a concrete one where the morphisms are structure-preserving functions), is there a way to determine its product (if it has one) that doesn't involve guessing and cleverness?

I'm asking not for an algorithm that would work in every case, because I assume that doesn't exist. Rather, I'm asking for useful heuristics - how does one go about this in practice? I'm interested in other limits as well of course, besides the product and coproduct, it just seems useful to start somewhere simple.

As a simple example: suppose I consider the category of preorders, where the morphisms are order-preserving functions. If I wasn't able to correctly guess what the product was in this category, how would I go about determining it?

(Note: there's a related question here, but the accepted answer just says "For each of these families of categories [concrete categories, categories of algebras of a monad etc.] there is often a common way to construct (co)limits of a certain shape." I'm asking specifically what this common method is in the case of a concrete category.)

$\endgroup$
  • 1
    $\begingroup$ In concrete categories the product is often the Cartesian product. This is the case when there are free objects over every set, i.e. when the forgetful functor to $Set$ has a left adjoint. $\endgroup$ – Berci Mar 21 at 9:36
14
$\begingroup$

If your category $C$ is related to some other category $X$ (e.g. to $\mathbf{Set}$) via some "forgetful functor" (for this heuristics, it's not necessary to have a precise definition, although "faithful" is often what is suggested) $U:C\to X$, and if you know $X$ very well (e.g. $\mathbf{Set}$), then you can try to go from (co)limits in $X$ to (co)limits in $C$.

For instance, $U$ will often preserve limits (that is the case in monadic situations for instance), and in that situation what you can do, if "$C$-objects are structure $X$-objects", is take the limit in $X$ and then try to find the appropriate structure ("of type $C$") on that limit. In algebraic cases, it will often be uniquely determined by the diagram.

This is even more so the case for the product, where a structure on the product is just the "coordinate-wise" structure (whatever that means)

The above strategy is guaranteed to win if $U$ creates limits, which, again, is the case in monadic situations.

So, let's take preorders as an example. Then we have the forgetful functor $\mathbf{Preord\to Set}$ which just sends a poset to its underlying set.

We can prove it has a left adjoint : this just sends a set to the discrete ordering on it. Therefore $U$ preserves limits, so if $P,Q$ are preordered sets, I know $P\times Q$ will have $UP\times UQ$ as underlying set. Now I have to think a bit : $P\times Q\to P$ is nondecreasing, so for all $p,q,p',q'$, $(p,q)\leq_{P\times Q} (p',q') \implies p\leq_P p'$

Same for $P\times Q\to Q$. So this proves that our preordering is contained in the following preorder : "$(p,q)\leq (p',q') \iff p\leq p'\land p'\leq q'$". Since this one is maximal, it serves as a good candidate for a universal property : you check that it works.

For colimits, the situation should be dual, but it turns out that very often we're interested in a functor to $\mathbf{Set}$ and so we can't dualize everything in practice. In practice, colimits will often look much uglier in concrete categories, and it can be quite challenging to determine a simple one (e.g. the coproduct in $\mathbf{Grp}$ is already very interesting)

One possible reason is that concrete categories (say, of algebras) often have free objects but not cofree objects, and a free object contains a lot of information about the category. Since a free object on $X$ is just the coproduct $X$ times of the free object on $1$, it stands to reason that determining coproducts is already challenging.

There are general results about how certain type of colimits behave (especially in monadic or operadic situations), but nothing too general.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ One should possibly mention RAPL (right adjoints preserve limits) and the dual, even if this is what the discussion of "free" objects stands for. The monadic situation is more involved, one has that the forgetful functor creates all limits that exists in the target, and creates all colimits that are preserverd by $T$ and $T^2$ (where $T$ is the monad), hence some of them (but in general not all of them, as one can check in algebraic categories). $\endgroup$ – piombino Mar 21 at 9:58
  • $\begingroup$ This is really useful. I will probably accept this answer, once I've left some time for others to weigh in. $\endgroup$ – Nathaniel Mar 21 at 10:00
  • $\begingroup$ Also, asking for myself, is faithfulness of any relevance? $\endgroup$ – piombino Mar 21 at 10:04
  • 2
    $\begingroup$ @piombino : I might add that, yes. As for your second question, no, not the way I described the heuristics. However, what we will usually call a forgetful functor is something that is faithful. Morally, this is what will allow you to reconstruct the limit in $C$ from the limit in $X$ ("$C$-objects are structure $X$-objects" is a motto that one can assimilate to "$U$ is faithful"), so in that sense it is relevant $\endgroup$ – Maxime Ramzi Mar 21 at 10:09
1
$\begingroup$

I want to expand on the creation of limits in the case of monads, and in particular I want to add to the existing discussion the case of the product of two groups. The hope is that this can give an idea.


Let $$ U \colon \operatorname{Grp} \to \operatorname{Set} \qquad F \colon \operatorname{Set} \to \operatorname{Grp} $$ be respectively "the" forgetful and free functors. Hopefully you are familiar with the free group generated by a set; just to remember, here is how you can do it in two steps.

  • From a set $S$ add "formal inverses", hence consider the set $$X' = X \,\sqcup\, \{x^{-1} \,\mid\, x \in X\}.$$

  • Consider now the free monoid over $X'$ (= "formal strings" in the alphabet $X'$) and quotient out by the relations $$x^{-1} \cdot x = 1 = x \cdot x^{-1}.$$

It looks a bit complicate but it exists (group operations should be clear). We also need to know the unit and counit of the adjunction $F \vdash U$.

  • The unit it the inclusion (of sets) $$ \begin{align} \eta_X \colon X &\to U(F(X)) \\ x &\mapsto [x] \end{align} $$ (the element $x$ is sent into the word containing only the symbol $x$).

  • The counit is the group morphism $$ \begin{align} \varepsilon_G \colon F(U(G)) &\to G \\ [g_1^{\alpha_1}, \ldots, g_n^{\alpha_n}] &\mapsto g_1^{\alpha_1} \cdots g_n^{\alpha_n} \end{align} $$ (where $\alpha_i = \pm 1$), ie. it evaluates the formal strings using the group operations of $G$.


To every adjunction corresponds monad, where

  • the endofunctor (of the category of sets) is $$T = U \circ F,$$
  • the unit of the monad $$\eta_X \colon X \to T(X)$$ is the unit of the adjunction,
  • the multiplication of the monad $$\mu_X \colon T(T(X)) \to T(X)$$ is defined as $\mu_X = U(\varepsilon_{F(X)})$.

It is important to understand how the multiplication operates. Recall that $T(X)$ are strings in the extended alphabet $X'$. To give two representative examples

$$ \mu_X \left[[x,y], [z]\right] = [x, y, z], \qquad \mu_X \left[[x, y]^{-1}\right] = [y^{-1}, x^{-1}]. $$

(I'm not using parentheses when giving a string as an argument to a function).


An Eilenberg-Algebra for a monad $T$ is a pair $(X, \xi)$ where $X$ is an object (in our case a set) and $$ \xi \colon T(X) \to X$$ is an arrow (a function) called structural morphism, which satisfies the two axioms

$\hskip1in$ axioms of structural morphism

A morphism of $T$-algebras $f \colon (X, \xi_X) \to (Y, \xi_Y)$ is an arrow $f \colon X \to Y$ such that

$\hskip2in$ diagram morphism of algebras

One can check that $(T(X), \mu_X)$ is an algebra (the free one generated by $X$), and so the structural morphism can be seen as an algebra morphism $$\xi \colon (T(X), \mu_X) \to (X, \xi).$$

Going back to groups, this tell us that a group can be seen as a set $G$ endowed with a function $$\xi \colon T(G) \to G$$ such that $$ \xi \,[x] = x, \quad \xi \,[x, y] = x \cdot y, \quad \xi \,[x]^{-1} = x^{-1} $$ and so on. That is, a set together with an interpretation of all formulae that you can make language of groups (and as variables the elements of the group).


The family of Eilenberg-Moore algebras and corresponding morphisms form a category, which is denoted as $C^{T}$; there is an evident forgetful functor $$U^T \colon C^T \to C$$ which has as left adjoint the functor sending the object $X$ to the free algebra $(T(X), \mu_X)$.

With this we can quote the result of interest.

Theorem. The forgetful functor $U^T$ creates all limits.

The proof of this general theorem is easy. See for example the free book "Category theory in context" written by Riehl, theorem 5.6.5.


Now I want to illustrate how it works in the situation of binary product of groups.

Let $(G_1, \xi_1)$ and $(G_2, \xi_2)$ be two groups, and let $$ G = G_1 \times G_2$$ be the product in set and let $\pi_i \colon G \to G_i$ be the canonical projections. We claim that $G$ has a structural morphism $\xi$ such that the pair is a product in the category of groups. The functions $$ T(G) \xrightarrow{T(\pi_i)} T(G_i) \xrightarrow{\xi_i} G_i $$ form a cone, hence by the universal property of the product there exists a unique arrow $$\xi \colon T(G) \to G$$ such that $$ \tag{1} \pi_i \circ \xi = \xi_i \circ T(\pi_i). $$ One can now check that $\xi$ is a structural morphism (satisfies the two axioms above) and that $\pi_i \colon (G, \xi) \to (G_i, \xi_i)$ are the projections of the product in the category of groups. The proof essentially uses universal properties.
Fun fact: at some point the proof uses the fact that $U^T$ is faithful :)

Suppose now that you want to know what is the product $$(g_1, g_2) \cdot (h_1, h_2) = \xi \,[(g_1, g_2), (h_1, h_2)].$$ By equation (1) you have that $$ \begin{align} \pi_i \circ \xi \,[(g_1, g_2), (h_1, h_2)] &= \xi_i \circ T(\pi_i) \,[(g_1, g_2), (h_1, h_2)] \\ &= \xi_i \,[g_i, h_i] = g_i \cdot h_i \end{align} $$ and so $$ (g_1, g_2) \cdot (h_1, h_2) = (g_1 \cdot h_1, g_2 \cdot h_2). $$

A similar calculation can be done for the inverse.


In the plain situation of concrete categories the result can be false.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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