Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Enumerating finite categories

Nick Smith (Jul 27 2021 at 02:04):

Is there any "smart" way to systematically construct all finite categories (up to a size limit)? Or are finite categories akin to prime numbers, where the only method guaranteed to enumerate them all is "guess-and-check"?

Jade Master (Jul 27 2021 at 03:53):

By finite category do you mean that the objects and morphisms are both finite sets? There are a lot of those...a category with one object is a monoid, so every finite monoid is also a finite one-object category.

Jade Master (Jul 27 2021 at 03:55):

But finite monoids can definitely be enumerated up to a certain size if the number is small enough...I've seen this sort of thing for groups.

Nick Smith (Jul 27 2021 at 04:42):

Yes I mean finitely many arrows and objects. I did discover a lot of literature on enumerating groups, but I assume the facts from that domain don’t necessarily apply to enumerating categories, because (e.g.) you don’t have to worry about inverses, and you have more ways of combining smaller categories into larger ones.

Nick Smith (Jul 27 2021 at 04:45):

And of course it’s possible to enumerate finite categories via a systematic process, but the only process I can think of that won’t miss any is “trying all possibilities” for a given number of objects and arrows, and throwing out the ones that don’t obey the identity and associativity laws.

John Baez (Jul 27 2021 at 05:33):

One question is why you'd want to enumerate finite categories. A big lesson in finite group theory is that enumerating finite groups of a given order is immensely difficult (it's been done up to 1024) and not very productive of insight into finite groups. Other directions worked out better. I'm sure it's the same for monoids or categories.

Oscar Cunningham (Jul 27 2021 at 05:50):

Geoff Cruttwell and Rejean Leblanc wrote about counting finite categories here: http://www.reluctantm.com/gcruttw/publications/ams2014CruttwellCountingFiniteCats.pdf.
They count categories with up to $10$ arrows, up to isomorphism. There are roughly $10^{14}$ categories with 10 morphisms, so they do indeed grow much more quickly than groups (there are $2$ groups of order $10$).
Geoff sent me some of their code after I emailed him a while back. I haven't gotten around to it yet, but I was thinking that it would be good to count all the skeletal categories of each size, under the logic that this was somehow the right way to count them up to equivalence (see here).

Nick Smith (Jul 27 2021 at 06:29):

One question is why you'd want to enumerate finite categories.

I’m just curious 🙂. I’m trying to get a feel for what finite categories are like. Are they each unique and hard to spot (like primes), or are they easy to enumerate (like natural numbers)? Those slides are helpful Oscar! Thanks.

I did write my own little program as well and it can enumerate up to 5 arrows. But it seems quite tricky to dodge all the isomorphisms!

Nick Smith (Jul 27 2021 at 06:43):

Given the slides confirm my hunch that “almost all finite categories are monoids”, it seems the related question of how to enumerate finite monoids is important too.

Morgan Rogers (he/him) (Jul 27 2021 at 07:35):

Nick Smith said:

I’m just curious 🙂. I’m trying to get a feel for what finite categories are like. Are they each unique and hard to spot (like primes), or are they easy to enumerate (like natural numbers)?

The question about prime numbers seems to suggest a different direction, regarding the possibility of decomposing (finite) categories into pieces which are irreducible in some sense. This is the kind of idea that I think @John Baez was alluding to, identifying how a generic category is built rather than just counting them all.

Clearly one could start by decomposing a category into its connected components. See what further decompositions you can come up with!

Nick Smith (Jul 27 2021 at 08:27):

To be clear, when I say "enumerating", I don't mean counting them, I mean listing them. This does imply some kind of knowledge of how an arbitrary category can be built up. The dumb way is to whack a bunch of arrows together, specify composites, and check afterwards whether the thing you built is a valid category, but I'm looking for a smart way.

I suppose trying to define a notion of "irreducible components" is the right way forward (surely someone has done this before?), but then of course, you can only build categories out of the components you're able to find. If finding the components is computationally hard (like primes), you're back to square one. I suppose my original question can be broken up into pieces:

• Does a finite category consist of meaningful "prime" components?
• If so, are these "primes" computationally hard to enumerate?
• If they are hard to enumerate, is there no computationally-simpler way of enumerating categories? (e.g. if you want to enumerate fibonacci numbers, you're not going to do it via their prime factorizations.)

Nick Smith (Jul 27 2021 at 08:28):

And to be clear this is merely a curiosity and if the answer is "nobody has ever figured this out" then I'm not about to drop everything I'm doing and do original research on it :P

Javier Prieto (Jul 27 2021 at 09:11):

Oscar Cunningham said:

I was thinking that it would be good to count all the skeletal categories of each size, under the logic that this was somehow the right way to count them up to equivalence

This feels right. Has there been any progress on that front?

Morgan Rogers (he/him) (Jul 27 2021 at 09:19):

I alluded to connected components. You can arrange the categories with $n$ morphisms according to the partitions of $n$, which are well-studied. Another nice thing about that decomposition is that if you present a category as generated from a quiver with some morphisms identified, then its connected components will lift from those of the quiver.

You can go further: the category freely generated from a finite quiver will be finite unless there is a directed loop in the quiver. So you can organize connected quivers according to their direct homology (I don't know how well-developed that is) and treat the presentation as a suitable equivalence relation on the homology monoids. I don't have references; this is just how I would proceed with this project.

Simon Burton (Jul 27 2021 at 09:20):

It's an interesting question... You can use something like Mace4 to generate & enumerate models of theories (https://www.cs.unm.edu/~mccune/prover9/)

Fawzi Hreiki (Jul 27 2021 at 10:11):

If by generate you mean generate under colimits then the answer is yes since the full subcategory spanned by the categories $0, 1, 2, 3$ is dense in $\text{Cat}$.

Fawzi Hreiki (Jul 27 2021 at 10:26):

But this is more analogous to the fact that any natural number is a sum over $1$. I don’t know if some proper subcategory generates $\text{FinCat}$ under limits (which is more like the prime analogy)

Nick Smith (Jul 27 2021 at 10:51):

Fawzi Hreiki said:

If by generate you mean generate under colimits then the answer is yes since the full subcategory spanned by the categories $0, 1, 2, 3$ is dense in $\text{Cat}$.

This sounds interesting. Where can I read more about this? (I didn't even know what a "dense subcategory" was until just now.)

Fawzi Hreiki (Jul 27 2021 at 10:59):

Chapter 5 of Kelly's 'Basic Concepts of Enriched Category Theory' is probably the best reference although he works in the generality of enriched categories.

Patrick Nicodemus (Jul 27 2021 at 10:59):

The notion of density is closely connected to Kan extensions. Mac Lane's CWM has a chapter on Kan extensions, including a section on density.

Fawzi Hreiki (Jul 27 2021 at 11:00):

Yeah I was about to mention that as well. Or the Kan extensions chapter in Riehl's 'Category Theory in Context'

Nick Smith (Jul 27 2021 at 11:01):

Thanks :) . Do these books discuss the Cat case in particular? Or just the general notion of density.

Patrick Nicodemus (Jul 27 2021 at 11:02):

A good way to visualize density is in the case of the category of simplicial sets. In this category, (and in any presheaf category) the representable functors ("standard simplices") are dense. This tells us that every simplicial set is the colimit of the simplices that make it up in a canonical way, which is a nice result as of course we should expect a simplicial complex to be glued together from the simplices that constitute it.

Fawzi Hreiki (Jul 27 2021 at 11:08):

Kelly's book deals with essentially algebraic theories (of which the theory of categories is an example) and he proves that the inclusion of the theory into the category of algebras is dense.

Patrick Nicodemus (Jul 27 2021 at 11:09):

A bit off topic but I read the following interesting density theorem the other day, which I've never seen before: Let M, A be categories. Let m be an object of M, and a an object of A; regard these both as functors from the one-object category 1 to M, A respectively. Then the pointwise left Kan extension of a along m exists if A has coproducts, and is given by Hom(m,-)\cdot a. Call a functor M -> A of this form a "generalized representable functor."
Theorem: The generalized representable functors are dense in the functor category [M,A].

Joe Moeller (Jul 27 2021 at 11:58):

If you want to get a sense of what finite categories are like, maybe quiver representations would be interesting to look at. Quivers are graphs equipped with relations, essentially a presentation of a small category. I don't know the field at all, but I would imagine they focus on finite things, and that there are certain heuristics about the categories which are appreciated more by representation theorists than by category theorists.

John Baez (Jul 28 2021 at 20:07):

A quiver is just a graph and a representation of a quiver is just a functor from the free category on that graph to Vect. A representation is indecomposable if it has no subobjects (subrepresentations) other than 0 and itself.

The most exciting thing about representations of quivers is Gabriel's theorem, which classifies the quivers that have finitely many (isomorphism classes of) indecomposable representations. They're all finite coproducts of quivers coming from the A, D, and E Dynkin diagrams: certain diagrams that can be turned into graphs by putting arrows on their edges pointing any way you want.

John Baez (Jul 28 2021 at 20:08):

This subject is tons of fun if you like examples connected to other branches of math (like Lie theory).

Matteo Capucci (he/him) (Jul 29 2021 at 14:23):

I'm sure we already talked about this here :thinking:

Matteo Capucci (he/him) (Jul 29 2021 at 14:24):

Here it is! link

Henry Story (Jul 29 2021 at 14:26):

(that link pointed to a non-existent discussion - well to the initial pointer to a new one)
I see it's fixed now.

Matteo Capucci (he/him) (Jul 29 2021 at 14:32):

oh jeez, let me fix it