21
$\begingroup$

There are a number of results which count the number of possible algebraic structures on a set of $n$ elements. Notable previous MO questions are for example here and here. The analogous question for finite categories does not seem to enjoy the same attention as other algebraic structures. The only source I could find was the following OEIS entry. Simply put the first question is as follows:

How many categories with at most $n$ morphisms are there up to isomorphism? Up to equivalence?

Comparing with the analogous OEIS entry for monoids, we see that for small $n$, "almost all" categories are monoids.

In general, under some appropriate weighting scheme (which?), are almost all categories monoids, in the sense that the quotient $$\frac{\text{Number of monoids with at most }n \text{ elements}}{\text{Number of categories with at most }n \text{ morphisms}}\rightarrow 1$$ as $n\rightarrow \infty$ ?

Tom Leinster asks a similar question about groups on the $n$-category Café.

$\endgroup$
2
  • 4
    $\begingroup$ Given how hard it is to count monoids and to count posets this must be extremely hard. $\endgroup$ Mar 9, 2014 at 21:36
  • 1
    $\begingroup$ In an analogy with similar counting problems I'd suggest also the following variant: let the set of objects $\ Q\ $ be fixed, and introduce fixed parameter $\ q:=|Q|.\ $ Let $\ M\ $ be the (intended) upper bound number on the number of morphisms. What is the number $\ m:=m(q\ M)\ $ of all categories $\ C\ $ such that $\ Obj(C) = Q\ $ and $\ |Mor(C)|\le M\ $ $ $\endgroup$ Dec 29, 2014 at 2:39

1 Answer 1

6
$\begingroup$

Note: I originally posted an answer claiming the opposite, and then deleted it because it was wrong. I have since reworked it and made this post community wiki.

This doesn't directly answer your question, but you may be interested to know that the conjecture is true in the infinite case. In fact, for every infinite $\kappa$ there are $2^\kappa$ categories with $\leq\kappa$ morphisms, up to equivalence or isomorphism, $2^\kappa$ of which are monoids. Of course, in the infinite case, it's more general to ask how many categories there are with $<\kappa$ morphisms rather than $\leq \kappa$ morphisms, but I think this question is more complicated.

On the one hand, $2^\kappa$ is an obvious upper bound on the number of categories with $\leq \kappa$ morphisms: since composition is a partial binary operation on the set of morphisms, there are at most $\sum_{\lambda \leq \kappa} 2^{\lambda \times \lambda \times \lambda} \leq \kappa 2^\kappa = 2^\kappa$ categories with $\leq \kappa$ morphisms.

On the other hand, it's easy to find $\kappa$-many pairwise-inequivalent connected categories with $\leq\kappa$ morphisms: for instance, it suffices to consider the oridnals $<\kappa$. By taking disjoint unions of these, we get $2^\kappa$ pairwise-inequivalent categories with $\leq \kappa$ morphisms.

We can tweak this construction to get $2^\kappa$ pairwise-inequivalent monoids. For each $S\subseteq \kappa$, we can adjoin a bottom element to $\coprod_{\lambda \in S} \lambda$ to get a semilattice $(\coprod_{\lambda \in S} \lambda)_{\bot}$, and then consider the corresponding monoid under $\vee$. We obtain $2^\kappa$ monoids this way by taking different $S$, and they are still pairwise nonisomorphic as monoids, because a monoid isomoprhism entails a semilattice isomorphism, which entails an isomorphism of the original disjoint-union categories, which are clearly pairwise inequivalent.

$\endgroup$
1
  • 3
    $\begingroup$ Of course, there are also $2^\kappa$ categories with $\leq \kappa$ morphisms which are not monoids. $\endgroup$
    – Tim Campion
    Dec 28, 2014 at 23:55

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.