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: theory: category theory

Topic: The right notion of 'number of morphisms in a category'

Oscar Cunningham (May 25 2021 at 11:52):

I'm looking at oeis.org/A125696, which claims to count the 'Number of categories with $n$ morphisms'. It's based on the work of Geoff Cruttwell and Rejean Leblanc, described in their talk 'Counting finite categories'.

But they only count categories up to isomorphism. Equivalent but nonisomorphic categories count separately.

I'd like to improve on this by counting categories up to equivalence. But I ran in to a fundamental issue. What does it mean for a category to have $n$ morphisms?

My first thought was that we should count the number of morphisms in the skeleton. While I was trying to think of a nonevil way of justifying this I thought of the definition 'number of isomorphism classes in the arrow category'. At first I thought these two definitions were equivalent but they're not. For example if the category is the delooping of a group then the first definition gives the order of the group while the second gives its number of conjugacy classes.

Does anyone see a decisive argument either way?

Nathanael Arkor (May 25 2021 at 12:09):

I would have thought the natural choice was "minimum number of morphisms of any category in the equivalence class". However, this seems an unusual way to count – don't you just want to modify which candidates are thrown out in Crutwell–Leblanc's method, replacing "isomorphic" with "equivalent"? That is, you only compare categories with literally the same number of morphisms, but be more liberal in what you discard.

Oscar Cunningham (May 25 2021 at 12:37):

I think 'minimum number of morphisms of any category in the equivalence class' is the same as 'number of morphisms in the skeleton'. The skeleton identifies the largest number of objects and hence morphisms. And yeah, we can just use their method and discard any nonskeletal category.

I thought of another reason why we wouldn't want to use the 'isomorphism classes in the arrow category' definition. If we do, then I can't easily prove that there are only finitely many categories with $n$ morphisms. That seems like something that should be easy to do! (I know for groups you can bound the number of conjugacy classes below by some function of the order that tends to infinity. But it's hard, and doesn't immediately generalise to categories.)

Morgan Rogers (he/him) (May 25 2021 at 19:37):

Oscar Cunningham said:

But they only count categories up to isomorphism. Equivalent but nonisomorphic categories count separately.

The number of morphisms of a category is invariant under isomorphism but not under arbitrary equivalences, so their choice seems like the natural thing to be counting. What would you say you are trying to capture with your up-to-equivalence count?

Oscar Cunningham (May 25 2021 at 20:36):

Morgan Rogers (he/him) said:

The number of morphisms of a category is invariant under isomorphism but not under arbitrary equivalences, so their choice seems like the natural thing to be counting. What would you say you are trying to capture with your up-to-equivalence count?

It feels wrong to look at categories up to isomorphism, even if it makes counting morphisms easier. If we want to count categories then it should be up to equivalence.

Nathanael Arkor (May 25 2021 at 20:50):

If you're considering categories as essentially algebraic structures, isomorphism is a natural choice (just like other algebraic structures).

Matteo Capucci (he/him) (May 25 2021 at 21:51):

If one were counting morphisms up to conjugation (i.e. precomposing and postcomposing with an iso), then you'd get something invariant up to equivalences, I think.

Matteo Capucci (he/him) (May 25 2021 at 21:52):

This is probably closer to notions of cardinality like groupoid cardinality, which assign to an object with $n$ automorphisms the cardinality $1/n$.

Fawzi Hreiki (May 25 2021 at 22:14):

Groupoid cardinality (of the core of the arrow category I guess) is probably your best bet. I saw a nice fact in Jonathan Wise's AG notes that groupoid cardinality is the only map $\#: \{\text{groupoids}\} \rightarrow \mathbb{N} \cup \{\infty\}$ which satisfies the following four conditions:

• Invariant under equivalence.
• Additive with respect to the coproduct.
• 1 on the singleton groupoid.
• If $C \rightarrow D$ is a functor between groupoids such that every $D$-object and every $D$-morphism has exactly $n$ pre-images then $\#C = n\#D$.

Oscar Cunningham (May 25 2021 at 22:26):

Fawzi Hreiki said:

I saw a nice fact in Jonathan Wise's AG notes that groupoid cardinality is the only map $\#: \{\text{groupoids}\} \rightarrow \mathbb{N} \cup \{\infty\}$ which satisfies the following four conditions:

Do you mean something other than $\mathbb{N} \cup \{\infty\}$ here? I thought a famous thing about groupoid cardinality was that it could produce fractional values.

Matteo Capucci (he/him) (May 26 2021 at 16:04):

I think $\mathbb R^+ \cup \{\infty\}$ is the right codomain.

Joe Moeller (May 26 2021 at 16:05):

Right, the cardinality of the symmetric groupoid is $e$.

Matteo Capucci (he/him) (May 26 2021 at 16:05):

Since groupoids like $\mathbb P$ (the core of $\mathbf{FinSet}$) have non-rational cardinality. Famously, $|\mathbb P| = e$

Matteo Capucci (he/him) (May 26 2021 at 16:05):

Joe Moeller said:

Right, the cardinality of the symmetric groupoid is $e$.

You beated me :) now I know the name

Joe Moeller (May 26 2021 at 16:06):

I like that name because the connected components are the symmetric groups.

Ulrik Buchholtz (May 26 2021 at 17:44):

Related: Tom Leinster, The Euler characteristic of a category.