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: practice: software

Topic: Combinatorially Generating Diagrams

Julius Hamilton (Apr 04 2024 at 20:24):

A “modular” (in the sense that it could be applied variously) skill I would like to have as I learn various concepts is to enumerate categories of increasing size and complexity, and generate their diagrams. I would hope to be able to do this in a language I am already familiar with, like Python or LateX, or maybe Coq.

There are some $n$ unique categories up to isomorphism when $|Ob(C)| = k$ for some $k$.

When $k = 0$, $n = 1$.

When $k = 1$, $n$ is the number of unique commutative monoids up to isomorphism.

When $k = 2$, I do not know the answer.

I am not sure it would be easy to find an algorithm to generate a “good sampling” of categories for each $k$ (because there are so many), but maybe a recursive algorithm has potential.

My question is, a) What’s an acceptably effective algorithm for this purpose? b) What is a good programming library to plot the generated categories as (labeled) diagrams?

Joshua Meyers (Apr 04 2024 at 20:41):

When $k=1$, $n$ is the number of monoids (don't have to be commutative) up to isomorphism, so $n$ is already vast (so big that it is not even the cardinality of any set).

If your goal is to enumerate structures and you want to end up with actual numbers of structures rather than just "vast", I would suggest enumerating categories with a specified number of morphisms rather than a specified number of objects.

That said, there are still interesting conclusions to be drawn in the direction you have started to go in, though they are not quantitative, but qualitative. Things like "a category with one object is equivalent to a monoid" and "a category with two objects is equivalent to two monoids $M$ and $N$, an $(M,N)$-bimodule $A$, an $(N,M)$-bimodule $B$, and some other structure", etc. But probably for your purposes it would be better to start by fixing the number of morphisms and then counting the number of categories up to isomorphism

Julius Hamilton (Apr 05 2024 at 02:58):

Right. I will be working on that tomorrow.

I also want to start thinking about categories with multiple classes of arrows which can only compose with arrows of their class.

John Baez (Apr 05 2024 at 04:48):

That's the same as a bunch of categories that all have the same set of objects, right?

Julius Hamilton (Apr 05 2024 at 04:50):

That’s true, I never thought about that.

Joshua Meyers (Apr 05 2024 at 12:19):

I think it would be the same as a disjoint union of categories. Why? Because if there are two arrows to/from an object $c$, they both compose with $1_c$, so they must be of the same class as $1_c$, and hence the same class as each other.

Mike Shulman (Apr 05 2024 at 15:02):

Julius Hamilton said:

I also want to start thinking about categories with multiple classes of arrows which can only compose with arrows of their class.

What applications/examples do you have in mind?

Julius Hamilton (Apr 12 2024 at 02:41):

It’s more of an open-ended exploration. It came from my attempt to explain category theory to myself in the simplest way possible. It just seemed natural that there could be multiple classes of arrows, since there are multiple kinds of relationships between things.

Simon Burton (Apr 12 2024 at 15:00):

I'm a big fan of these kinds of enumerative ideas.. I would suggest taking an arrow-centric approach, so treating objects as identity arrows, and then finding all categories with $k$ many arrows. This is the kind of sequence i would expect to find in the OEIS.

Nathanael Arkor (Apr 12 2024 at 15:04):

You might be interested in these slides by Geoff Cruttwell about counting finite categories. (I believe this has been discussed on Zulip before.)

Julius Hamilton (Apr 12 2024 at 15:17):

I love it.
My dream is to study each category one by one in order, and study all the properties each one fulfills.

John Baez (Apr 12 2024 at 17:35):

At that rate it will take you a long time to reach $\mathsf{Set}$.

Tim Hosgood (Apr 12 2024 at 18:10):

if you want to look at all finite categories, https://smallcats.info is a really great place to start:

There are currently 164975 categories in the database, including all categories with ≤7 morphisms!