FINITE CATEGORIES: JULY 22

NOTES FOR THE REU

A question was left unresolved in the previous lecture.

Question 1.1. Let 𝒟 be a category with three objects and two non-identity morphisms, and let 𝒞 be a category with two objects and one non-identity morphism as in the diagram:

\begin{matrix}b ⟵^{f} a ⟶^{g} c & 𝒟 \\ b ⟵^{f} a & 𝒞 \end{matrix}

I claimed yesterday that there is no direct pair of adjoint functors between 𝒞 and 𝒟, but the question was raised as to whether or not there is some intermediate category (or categories) such that there is a string of adjoint pairs connecting 𝒞 and 𝒟 through the intermediate category?

In fact, the answer to this question comes from a concept discussed in the previous lecture: initial objects, and it leads to a quick proof that even yesterday’s claim is wrong. Notice that a is an initial object in both categories. Since a is initial, the functor ι_{a} : 𝒫 → 𝒞 is left adjoint to p : 𝒟 → 𝒫. And similarly now using a to be an object of 𝒟, the functor ι_{a} : 𝒫 → 𝒞 is left adjoint to p : 𝒟 → 𝒫. Thus, there do exist adjoint pairs (𝒫, 𝒟) and (𝒫, 𝒞). The left adjoints both have domain 𝒫 and thus cannot be composed to give a direct left adjoint. However, the category 𝒞, unlike 𝒟, also has a terminal object, namely b. Therefore the functor ι_{b}: 𝒫 → 𝒞 is right adjoint to p: 𝒞 → 𝒫. Thus we also have an adjoint pair (𝒞 , 𝒫), and now we can compose. The composite ι_{a} ∘ p: 𝒞 → 𝒟 is left adjoint to ι_{b} ∘ p: 𝒟 → 𝒞. All that the original argument showed is that the inclusion 𝒞 → 𝒟 is neither a left nor a right adjoint.

Proposition 1.2. Let F and G be functors from a category 𝒞 to another category 𝒟. If α : F → G is a natural transformation of functors, then α determines a functor H : 𝒞 × ℐ → 𝒟.

Proof. Define H as follows for X, Y ∈ 𝒪 (𝒞) and f : X → Y (1) H(X, [0]) = F (X)

(2) H(f, id_{[0]}) = F (f)
(3) H(X, [1]) = G(X)
(4) H(f, id_{[1]}) = G(f)
(5) H(id_{X}, [I]) = α_{X} : F (X) → G(X).

This defines H for all objects and most morphisms of 𝒞 × ℐ. However, H still needs to be defined for morphisms of the form (f, [I]). This morphism can factor as (f, id_{[1]}) ∘ (id_{X}, [I]) or (id_{Y} , [I]) ∘ (f, id_{[0]}). For H to be a functor, we must have

H(f, id_{[1]}) ∘ H(id_{X}, [I]) = H(id_{Y} , [I]) ∘ H(f, id_{[0]}),

which we have already defined above to be

G(f) ∘ α_{X} = α_{Y} ∘ F (f).

This last equation is true by definition of natural transformation, so H is indeed a functor. □

Clearly the above proof can be reversed to yield the following converse.

Proposition 1.3. Let H : 𝒞 ×ℐ → 𝒟 be a functor. Then H determines a natural transformation α from the functor F to the functor G, where F and G are defined for X, Y ∈ 𝒪 (𝒞) and f : X → Y by

(1) F (X) = H(X, [0])

(2) F (f) = H(f, id_{[0]})

(3) G(X) = H(X, [1])

(4) G(f) = H(f, id_{[1]})

Recall the geometric realization functor | | which takes a category to its geometric realization. The product of two categories 𝒞 and 𝒟 comes with two projection functors 𝒞 × 𝒟 → 𝒞 and 𝒞 × 𝒟 → 𝒟. Applying the geometric realization functor gives two continuous maps | 𝒞 × 𝒟 | → | 𝒞 | and | 𝒞 × 𝒟 | → | 𝒟 |. Thus, by the universal mapping property of products, these are the coordinate projections of a continuous map | 𝒞 × 𝒟 | → | 𝒞 | × | 𝒟 |. In fact, this map is a homeomorphism, but as with many concepts in mathematics, the proof becomes simpler when we generalize the context, as we will in later talks.

1.1. Classifying Small Categories. Now let us try to classify connected small categories. The order of a category is the number of non-identity morphisms it has. Thus, there is only one category of order 0: 𝒫.

The categories of order 1 have all been mentioned already. First, consider categories with only one object. Then a non-identity morphism g will satisfy either g ∘ g = e, which gives the group Π_{2}, or g ∘ g = g, which gives the monoid S^{0} whose morphisms we might write {0, 1}. If the category has two objects, there is only one possible non-identity morphism, and this gives the unit interval category ℐ. Of course, the classification here is up to isomorphism. For example, the category 𝒞 above is isomorphic to ℐ.

The categories of order 2 with one object are the monoids of order 3. A previous exercise already asked for all monoids of order 3. Only one of the monoids of order 3 is a group: Π_{3}. Also, there is the adjoin-a-new-zero-to-a-monoid functor from the category of monoids to itself. Thus, from the two monoids of order 2, there are two monoids of order 3, namely (Π_{2})_{+} and (S^{0})_{+}. There is also an adjoin-a-unit-element-to-a-semigroup functor. A semigroup is a set with an associative product, and one can adjoin a unit to make it into a monoid. If one starts with a monoid, one can forget that it has a unit element and regard it just as a semigroup, and then adjoin a new unit. There is at least one semigroup with two elements that is not a monoid. Exercise: give its multiplication table and check whether or not there are any other two element semigroups. Remembering the two monoids, we have at least three semigroups with two elements, and adjoining a unit gives three more monods of order 2. Exercise: are all the monoids that we have constructed non-isomorphic? The original exercise remains: are there any additional monoids of order 3?

To classify the categories of order 2 with two objects, begin by classifying something simpler: directed graphs. A directed graph consists of a set V of vertices, a set E of edges, and two functions S and T from E to V, called source and target. There is a forgetful functor from categories to directed graphs which forgets the composition law and identity arrows. Thus, for a category 𝒞, the underlying graph has V = 𝒪 (𝒞) and E = 𝒜 (𝒞), the disjoint union over pairs of objects (X, Y) of the sets 𝒞 (X, Y), X and Y giving the source and target. It is interesting to note that we could also forget directedness to get a graph; however this functor removes some structure that we want to retain. Note that the homotopy type of a graph is determined by the number of edges that remain after contracting a spanning (or maximal) tree to a point. Some thought reveals that there are only four connected directed graphs on 2 vertices and 2 edges.

Exercise 1.4. Calculate how many categories arise from the four directed graphs on 2 vertices and 2 edges, and compute the homotopy type of these categories. Many (all?) of these were done in lecture.

There are only three directed graphs with 3 vertices and 2 edges. In fact, all the graphs are the same, but the directions differ:

(1) · ⟵ · ⟶ ·

(2) · ⟶ · ⟵ ·
(3) · ⟶ · ⟶ ·

The first two are the underlying directed graphs of a unique category, since there are no pairs of composable arrows. The last is not the underlying directed graph of a category, since there is no edge connecting the left vertex to the right vertex and thus no way to specify the composite of the two edges.