nLab
finite category

A finite category $C$ is a category internal to the category FinSet of finite sets.

This means that a finite category consists of

• a finite set of objects;
• a finite set of morphisms.

(Notice that the latter implies the former, since for every object there is the identity morphism on that object).

Similarly, a locally finite category is a category enriched over $\mathrm{Fin}\mathrm{Set}$, that is a category whose hom-sets are all finite.

(Locally) finite categories may also be called (locally) $\omega$-small; this generalises from $\omega$ (the set of natural numbers) to (other) inaccessible cardinals (or, equivalently, Grothendieck universes).

Limits and colimits

One is often interested in whether an arbitrary category $D$ has limits and colimits indexed by finite categories. A category with all finite limits is called finitely complete or left exact (or lex for short). A category with all finite colimits is called finitely cocomplete or right exact.

Discussion

Eric: Is the following statement correct?

For any finite category $C$, there is a directed graph $G$ such that its quiver $Q(G)$ is equivalent to $C$.

Mike Shulman: No, this is false. The “walking commutative square”

$$\begin{array}{ccc}& \to & \\ \downarrow & & \downarrow \\ & \to & \end{array}$$\array{ & \to & \\ \downarrow && \downarrow\\ & \to & }

is a finite category which is not free on any directed graph.

Toby: The walking commutative triangle is an even simpler counterexample. Rather, we should say that any finite category is a quotient of some quiver; the nontrivial commutation relations (triangles, squares, etc) give us this quotient. But in fact, there is nothing special about finite categories here; every category is a quotient of the quiver on its underlying graph. So I think that the only point to be made here is that, for a finite category, the graph may also be taken to be finite, but even that is obvious since the underlying graph is finite.

Eric: Thanks! That is interesting. This reminds me of the universal differential envelope on a complete directed graph. Any discrete calculus is a quotient of the universal discrete calculus obtained by removing some edges.

Toby: Sure, there are lots of adjunctions that work this way. (I forget the precise adjective that I should put before ‘adjunction’ here.)

Mike Shulman: If the “walking commutative triangle” means what I think it does, then it actually is a quiver. The hypotenuse is freely generated as the composite of the other two sides.

• Toby: Erm … right. It's still a quiver; it's just not the quiver of the graph that I was thinking of! Sorry about that.

Eric: Wait a second. Does the “walking commutative square” consist of 4 objects? If so, then the diagonal should be a morphism because it is the composite of two sides so the diagram is not complete as drawn. It should include the diagonal. I’m sure I’m confused. What am I missing?

Mike Shulman: Yes, the diagonal is a morphism. I didn’t draw it because we don’t usually draw the diagonal when we draw a commutative square, just like we don’t usually draw identity morphisms.

Eric: Ok. I thought the missing diagonal was the barrier to being “free”. What is the barrier then? If you start with a directed graph as you drew without the diagonal then the corresponding quiver contains the diagonal as it should. There must be something else I’m missing. Thanks.

Urs Schreiber: apart from looking at the counterexample that Mike gave, it shoud be useful to say in words in full generality what is going on:

In a free category on a directed graph composition of morphisms is always just a concatenation operation. Nothing really happens when you compose any two morphisms.

So another good counterexample to think of is a delooping category $BA$ of a monoid $A$ or $BG$ of a group $G$: in as far as the product operation in $A$ and $G$ actually does something instead of just saying that $a\cdot b$ is $ab$, the corresponding category is not a free category.

Eric: I’m still confused. What is it about these counterexamples that make them counterexamples? For example, if $G$ is finite, then there is a finite number of elements $g_1,g_2,\dots$ that generate all of $G$. We can construct a graph with one node and directed edge for each generator. Wouldn’t the resulting quiver be equivalent to $BG$?

• Toby: It would if and only if $G$ is a free group generated by the elements $g_1,g_2,\dots$. (And in that case, it would not be a finite category, except in the degenerate case where there are no elements $g_1,g_2,\dots$ at all.)

Mike Shulman: The point is that in the free category on the directed graph

$$\begin{array}{ccc}& \to & \\ \downarrow & & \downarrow \\ & \to & \end{array}$$\array{ & \to & \\ \downarrow && \downarrow\\ & \to & }

there are two diagonals, one being generated by the top-right composite and the other by the bottom-left composite. If you included the diagonal itself as a generator in the directed graph, then there would be three diagonals.

Eric: Thanks Mike. That is very helpful. So given JUST a square graph, it’s quiver will have TWO diagonals. So we need more information. We need to specify something like a “curvature” that tells you how paths having the same start and end points fail to commute. When that curvature is zero, the paths commute.

If we label the directed edges $T$,$B$,$L$,$R$, then when we construct the composites (to form the quiver) we end up with two diagonal morphisms $\mathrm{RT}$ and $\mathrm{BL}$. We need a 2-morphism $F:\mathrm{RT}\to \mathrm{BL}$. To specify a rule for this 2-morphism, we probably need a 2-edge. In the absence of specifying a directed 2-edges, we could assume the curvature is flat. What this means is that we could have a concept of a “free $n$-category” generated by a directed $n$-graph. If there are no edges above $n$, then it means all closed $(n-1)$-paths commute.

This is a slightly different definition of a quiver where closed paths are assumed to commute. If you want a close $(n-1)$-path to NOT commute, you need to specify a corresponding $n$-edge connecting the two paths.

In other words, I think I’m suggested that we have free categories generated by a directed graph default to having all closed paths commute. If you want a closed path NOT to commute, you need to specify a 2-edge and form a 2-quiver. Does that make any sense?

Here are some pictures. Let’s say we start with a 2-graph square and form a “2-quiver” as illustrated below:

The 2-edge $F$ tells us that the composites $\mathrm{RT}$ and $\mathrm{BL}$ are not the same.

If we fail to include a 2-edge and start with the 1-graph and form its 1-quiver as illustrated below:

then it is as if we HAD included a 2-edge, but it is a trivial 2-edge and its corresponding 2-morphism is simply a 2-identity and the two composites commute.

I think that any finite category can be obtained in this way not via a finite 1-quiver (in which all closed 1-paths commute) but rather by a 2-quiver. If there is any sense to this, it seems to me to indicate that maybe a category with non-commuting paths is secretly a non-trivial 2-category somehow.

Todd: More examples of finite categories which are not quivers: take the group ${\mathbb{Z}}_2$ as a 1-object category. Or the category with two objects and exactly one morphism in each hom-set.

As far as your suggestion goes, I’m inclined to say you seem to have it backwards from how I’d go about it. There is a notion of something called “computad” which all this reminds me of, which come in various dimensional flavors. A 2-computad consists of a directed graph and a collection of “2-cells” or 2-edges whose source and target are directed paths in the directed graph (= morphisms in the free category on the directed graph). In my way of thinking, a 2-cell would provide something like a membrane or bridge or a homotopy which would allow you to identify paths (the source and target of the 2-cell) up to homotopy, instead of distinguishing them as you are doing. So, for any 2-computad, there would be something like its “fundamental category” (like a fundamental groupoid, but with directed paths considered modulo 2-cells), and you could say that any finite category is the fundamental category of some finite 2-computad. (But lots of different 2-computads would have the same fundamental category.)

There is also the notion of free 2-category generated from a 2-computad, and this is the beginning of an induction ladder.

Mike Shulman: Yeah, I’m with Todd; it seems strange to me to try to specify which diagrams don’t commute instead of which ones do.

I’m not sure if this is quite what you were thinking of with “a category with non-commuting paths i.e. a category that isn’t a preorder is secretly a non-trivial 2-category somehow”, but it’s not true that you can make a 2-category out of a category by putting a 2-cell between any two unequal parallel arrows. For one, there would be no identity 2-cells (since an arrow is equal to itself), and for two, you can’t compose inequalities; if $f\ne g$ and $g\ne h$ it can still be that $f=h$.

David Roberts: I like the idea about the fundamental category of a 2-computad - I have some examples of things up my sleeve that I think this (and the next level up - the fundamental bicategory of a 3-computad) would very accurately describe. One of which is the localisation of a (small) category. Even more interesting for me would be the comparison with directed homotopy?, especially if the 2-cells are not invertible.

Eric: Thank you Todd and Mike! This is all very neat. That sounds interesting too David. I was also thinking about directed homotopy. I’m sure you guys are right and it is more natural to specify which diagrams commute rather than which diagrams don’t commute, but my motivation was curvature. If there is no curvature, then parallel transporting a particle along either path doesn’t matter. However, if there is curvature, then a particle will end up “rotated” depending on which path you take. In this analogy, it is the “absence” of curvature that makes the paths commute. It seemed natural that specifying a non-identity 2-edge was like specifying a non-zero curvature.

I like the idea of computads. I thought about that as well (although I didn’t know they were called computads), but I think you really can get away with just directed $n$-graphs. Instead of a single directed edge as I drew in the picture which is more like a morphism between paths of length 2, we could have two 2-edges:

$$F_1:L\to T\text{and}{F}_2:B\to R.$$F_1: L\to T\quad\text{and}\quad F_2:B\to R.

Then

$$F:\mathrm{BL}\to \mathrm{RT}$$F:BL\to RT

is some kind of horizontal composition. Anyway, whether it is computads or directed graphs or specifying which edges commute or which edge don’t commute, I’m pretty excited. I’m much more comfortable thinking about directed graphs, so the more I can use them to help understand other concepts, the better for me. If finite categories can be reduced to some smaller atomic graph, that would be kind of neat.

Mike Shulman: I’m not sure what you mean by a 2-graph, but if you mean the obvious thing, then you can’t have an edge $L\to T$ in one since $L$ and $T$ aren’t parallel.

By the way, I think the “fundamental category” of a computad is just going to be the reflection of its free 2-category into 1-categories (forcing all 2-cells to become identities). It’s certainly true that any finite category can be presented in this way by a finite computad, although not every category presented by a finite computad is finite (for instance, the monoid of natural numbers regarded as a 1-object category is presented by the computad with one object, one endo-1-cell, and no 2-cells).

Eric: Hi Mike. Here is the page on directed n-graphs. A directed 2-edge simply has a source 1-edge and a target 1-edge. These do not have to be parallel. If there is some problem with that, we should change the page. Any inaccuracies there are my fault :)

Todd Trimble: The notion of directed 2-graph as given there does seem weird to me. The problem is that if we think of a 2-cell as some kind of “shape” with boundary, then according to standard practice we should have something like “boundary of the boundary is zero”. In the computad setting, there are globularity conditions that say “source of the source = source of the target, and target of the source = target of the target” which give the boundary of boundary conditions.

Ultimately we would want some sort of geometric realization of these critters, and it’s hard to see how that would go precisely with the current directed n-graph.

Eric: One of the motivations (for me anyway) for that definition was precisely to get away from the globularity conditions. I come from the perspective of computational physics where the graph is intended to represent a model of spacetime. These types of directed $n$-graphs are precisely what appear in our paper. I kind of think of them as being “pre-geometric”. They become geometric once you form the $n$-quiver OR construct a differential graded algebra from them as Urs and I outlined in that paper.

In our paper, we start with just a directed 1-graph and build up the higher degree elements by introducing a coboundary. I agree, it is not “geometry” until you have a nilpotent coboundary, but these directed $n$-graphs form the basis for building geometries.

You might sense I have aspirations for this stuff. Talking about “pre-geometry” in the hopes it might pertain to “primordial”. Something along the lines, “In the beginning, there was a graph…”

Eric: It was starting to get late last night and I crashed, but kept thinking about this. Mike said:

it’s not true that you can make a 2-category out of a category by putting a 2-cell between any two unequal parallel arrows. For one, there would be no identity 2-cells (since an arrow is equal to itself),

Sorry I wasn’t clear. There are always identity 2-morphisms when you pass to the free category. The absence of a cell in the graph maps to an identity morphism in the quiver. That is why all 1-paths commute by default, i.e.

$$\text{identity 2-morphism}\leftrightarrow \text{1-paths commute}.$$\text{identity 2-morphism} \leftrightarrow \text{1-paths commute}.

Each 1-edge gets mapped to a morphism PLUS an identity 2-morphism (and identity 3-morphism, etc). An edge is a trivial path that commutes with itself, which means each edge comes with an identity 2-morphism when passing to the guiver. This is completely analogous to how an $n$-category can be thought of as an $\mathrm{\infty }$-category where all morphism greater than $n$ are identity morphisms.

I should have made that more clear.

and for two, you can’t compose inequalities; if $f\ne g$ and $g\ne h$ it can still be that $f=h$.

This is fine. We want to think of $\mathrm{FG}:f\to g$, $\mathrm{GH}:g\to h$, $\mathrm{FH}:f\to h$ as $2$-transports. If $\mathrm{FG}$ is not an identity, it means $f\ne g$. If $\mathrm{GH}$ is not an identity, it means $g\ne h$. HOWEVER, if $\mathrm{FH}$ is an identity, then $f=h$. The neat thing about this, which is a feature, not a bug, is that when composing two non-identity 2-morphisms gives an identity 2-morphism, it means that the 3-morphism is an identity 3-morphism.

In other words, the fact that you can’t compose inequalities is fine. In the case that $f\ne g$ and $g\ne h$, but $f=h$, this implies that the 2-paths commute and the corresponding 3-cell is an identity (meaning the 3-curvature vanishes). In fact, that is the default behavior. If you wanted the 2-paths to not commute, you’d have to insert a directed 3-edge giving non-zero 3-curvature.

Toby: A couple of points. First, if you want zero curvature to mean that every diagram commutes (which seems plausible), then zero curvature means that you have a proset, not that you have a quiver. Todd's group $Z_2$ is a good example of both a non-quiver and a non-proset. The walking parallel pair of arrows ($•\rightrightarrows •$ where the two arrows are not equal) is a quiver but not a proset. And Mike's walking commutative square is not a quiver but is a proset. (My epic fail, the walking commutative triangle, is both a quiver and a proset.)

Now, if you want nonzero curvature to be given by some sort of $2$-morphism, you might want to consider a $2$-category whose hom-categories are enriched over an interesting monoid such as $(\mathbb{Z},+)$. Then each parallel pair of morphisms, instead of having a (possibly finite) set of $2$-morphisms between them, will have a number as $2$-morphism between them (note I did not say a number of $2$-morphisms between them). The number $0$ indicates that they are equal (so the diagram commutes); but a nonzero number indicates a failure of commutativity to some degree. The rule for composition is addition; if $f\to g$ is $i$ and $g\to h$ is $j$, then $f\to h$ must be $i+j$ (and $f\to f$ is always $0$, which works since $f=f$). Note that it is possible to have $f\ne g$ and $g\ne h$ but $f=h$ (that is, $f\to g$ and $g\to h$ are nonzero but $f\to h$ is zero) since we are using $\mathbb{Z}$; that would not be possible using $\mathbb{N}$. (Of course, you could just as well use $\mathbb{Q}$, $ℝ$, or even $ℂ$ in place of $\mathbb{Z}$, but perhaps $\mathbb{Z}$ appeals to your desire for discreteness.)

Eric: I knew I should have put “‘s on the word “quiver”. This going to sound strange, but I’d say that the “walking commutative square” is not a quiver, but IS a 1-quiver. What people generally refer to as a “quiver” would actually be (related to) a 2-quiver coming from a 2-graph where the 2-cells help designate non-commuting paths. All 1-paths commute in a 1-quiver. All 2-paths commute in a 2-quiver, but not all 1-paths commute in a 2-quiver.

Currently, I’m proposing that any finite category is obtained from the 2-quiver of some finite directed 2-graph by turning all 2-morphisms into identities (is there a term for a subcategory obtained by turning all $k$-morphisms for $k$ greater than some number to identities?).

Toby: If you start with an $\mathrm{\infty }$-category $C$ and turn all $k$-morphisms for $k\ge j$ into equivalences, then you get an $(\mathrm{\infty },j-1)$-category that I would call the $j$-core of $C$. (I just made up ‘$j$-core’, but the $1$-core is the ordinary core, which is an $(\mathrm{\infty }\mathrm{,0})$-category, that is an $\mathrm{\infty }$-groupoid). And if you then turn all of the $k$-equivalences for $k\ge j$ into equivalences, then you get a $(j-1)$-category which is (I am not making this up) the $(j-1)$-truncation? of the $j$-core of $C$. Probably people would be happy to call this the $(j-1)$-truncation of $C$ itself, but now I am making up terms again, as far as I know. So in summary, if you turn all $k$-morphisms for $k>j$ (note my subtle level shift here) into identities, then you get the $j$-truncation of $C$.

Eric: Here is an attempt at something semi-formal:

Proposition

A finite category is the 1-truncation? of a free 2-poset for some Hasse 2-graph.

Proof

???

Mike Shulman: Eric, I’m very confused. Can you maybe use something other than “n-quiver” for whatever it is you’re trying to describe? In general we try to make a “1-foo” be the same as a “foo”.

Also, as I said at directed n-graph, I really don’t like that term; saying ”$n$-graph” automatically makes me think ”$n$-globular set”. Moreover, for purposes of freely generating $n$-categories I think the extra generality of not requiring the globularity conditions is superfluous; the free functor from $n$-nonglobular sets to $n$-categories factors through $n$-globular sets, so you might as well start with an $n$-globular set.

Thirdly, I don’t think you have any hope of getting only finite categories this way; you’re always going to get some finitely presented categories that are not finite (like the monoid $\mathbb{N}$ as a one-object category).

Toby, what I would call the ”$j$-core” is what you get by discarding $k$-morphisms for $k\ge j$ that are not equivalences. Is that what you meant?

• Toby: No, I was just messed up. It was Eric who wanted to make all $2$-morphisms into equivalences (and indeed identities), so the core is not correct.

Eric: Sure. Sorry about that. Until a better name is found, I think I’ll just call it a free n-poset. I’m trying to develop some ideas at Hasse n-graph. Toby and I were discussing this a bit here.

By the way, I’m not hoping to get only finite categories this way. My only hope is that I can find a way to obtain any finite category this way (or some way similar).

Mike Shulman: As I said at directed n-graph, it sounds like maybe you really want a computad. It is true that any (finite) category can be obtained as the 1-truncation of the free 2-category on some (finite) 2-computad; in fact this is more or less the definition of a “finitely presented category.”

I still don’t understand your response to me above (beginning with “Sorry I wasn’t clear”).