Free categories and foundations

Here, I will be going through the Free Categories and Foundations sections of Awodey’s Category Theory - pages 18 through 25.

The definition of a free monoid is basically the same as that of a free group. However, I skim past and see the word “functor” appearing in the “no noise” statement, so I’ll actually read this section properly. Everything is familiar up until the definition of the universal mapping property. One bit confuses me for a moment - “every monoid has an underlying set, and every monoid homomorphism an underlying function; this is a functor” - until I realise that by “this”, Awodey means “this construction” rather than “this underlying function”.

Now comes the Universal Mapping Property of free monoids. This is a painful definition - I’ve spent fifteen minutes trying and failing to understand it - so I’ll skip past it and come back when I’ve read some more.

Proposition 1.9: this is a proof in an area where I’m wrestling to keep everything in my mind at once, so I’ll just prove the proposition myself, using Awodey to take short-cuts. Let \(i: A \to \vert A^* \vert\) be defined by inclusion - that is, taking \(a\) to the single-character word \(a\). Let \(N\) be a monoid and \(f: A \to \vert N \vert\). Define \(\bar{f}: A^* \to N\) as stated; it’s clearly a homomorphism. It has \(\vert \bar{f} \vert \circ i = f\): indeed, \(\vert \bar{f} \vert \circ i(a) = f(a)\) manifestly. The homomorphism is unique, as Awodey proves at the end. Very well: I’m satisfied that \(A^*\) has the UMP of the free monoid on \(A\).

Apparently the UMP captures “no junk and no noise”. What Awodey says is plausible to me in that it hits the right words on the mark scheme, but the definition of the UMP is just too abstract. I’ll try and break it into parts.

“There is a function \(i : A \to \vert M(A) \vert\).” That bit’s fine: it’s saying that the inclusion exists. “Words are built up from the set in some way.”

“Given any monoid \(N\) and any function \(f: A \to \vert N \vert \), there is a monoid homomorphism \(\bar{f} : M(A) \to N\) such that \(\vert \bar{f} \vert \circ i = f\).” The final equality is saying “we may represent \(f\) instead by first including into the free group, then applying some analog of \(f\)". Makes sense: “if we know where members of the free group go, then we definitely know where the generators go”.

“Moreover, \(\bar{f}\) is unique.” Well, if it weren’t unique, we would have a choice of places to send a word in the free group, even if we knew where all the generators went.

I think I understand it better now. Still not on a particularly intuitive level, but now I’m convinced by Awodey’s explanation.

Let’s move on to Proposition 1.10, that the free monoid is determined uniquely up to isomorphism. That seems plain enough, on a syntactic level.

The bit about graphs is clear, but now there’s another UMP to worry about. (Ah, I’m starting to understand that a UMP is a class of property, not just one particular property. Presumably there’s one for lots of different structures.) The forgetful functor from Cat to Graphs is fine; the “different point of view” of a graph homomorphism makes me stop. Let’s break down that diagram more carefully.

\(i: C_0 \to C_1\) is indeed a valid map: we may view the identity arrow operation as taking an object to its associated identity. The codomain and domain functions do indeed take arrows to objects. The composition operation takes pairs of arrows (which have the right codomain/domain) to single arrows. OK, that’s not too scary a diagram, and I agree that a functor is as claimed.

After the same process of thought, I agree with the formulation of Graphs; and then I get to the description of the forgetful function Cat to Graphs. That is immediately comprehensible, and my first thought is that I don’t know why Awodey didn’t just come out with it straight away.

“Similarly for functors…” - this bit is “easier to demonstrate with chalk”, but I’ll just go back and do it mentally. It works out in the obvious way.

Finally, our second universal mapping property, this time the free category generated by a graph. Armed with the (meagre) intuition from the free-monoid UMP, this is easier to understand. “We may include the graph into the free category, and given somewhere to map the generators, there is a unique way to determine where elements of the free category go”. I had one of those rare moments of “I know exactly what is going on here”, which is hopefully a good sign.

I’m intuitively happy with the examples given in the epilogue. If I were less lazy, I’d check from the UMP that the examples worked (that is, show that categories so defined were unique, and that the free catgory satisfied the UMP).

Page 24 (on foundations) is familiar to me. I note the definition of “small” and “large” categories - natural enough. The definition of “locally small” looks a bit frightening at first, but on second glance it really is just what you’d expect “locally small” to mean. What would it mean for \(Cat\), the collection of small categories, to not be locally small? There would have to be two small categories such that the collection of functors between them was not a set. But the two categories are small, so they are sets, and there is a set of all functions between two sets. (However, the category of locally small categories would not be locally small: pick a non-small member \(C\), and define a functor \(1 \to C\) which selects an element. There are non-set-many of these.)

Finally, the warning that “concrete” is not “small”. Once given the example of the poset category \(\mathbb{R}\), I’m satisfied.


I took a few days to understand this section, not working at it very hard but just letting it trickle in when the mood took me. It was massively more difficult than the previous sections, but I think I’ve got my head around the universal mapping properties described. I don’t know whether I could come up with them myself to describe other free objects, but I could certainly give it a go.

The exercises at the end of this chapter will be the true test of understanding.