In this post, I continue to follow chapter by chapter from Category Theory for Programmers By Bartosz Milewski, this time looking at Chapter 3: Categories Great and Small.
Types of Categories
Empty Category – This category is like the empty set. It’s the category that has no objects in it.
Free Category – Any directed graph can be turned into a category by taking each node to be an object and each arrow a function/arrow/morphism. However, to make it a valid category you’d then have to draw arrows from every single node to any node you can reach from there (i.e. the composition of functions) plus add identity arrows for each node. This might create a graph with infinitely many arrows, but that’s beside the point. This final graph now has the minimum requirements to be a category and is called a “Free Category.”
Preorder – Imagine a category where each morphism between objects represents that object is less than or equal to the other object. So imagine a category of integers and 1 has an arrow to 2 because 1 is less than or equal to 2. Since every object is less than or equal to itself, that means every integer also has an identity arrow. However, the integers are a bad example of a preorder (they are actually a total order — see below) because a preorder has no requirement that every object is in relationship to every other object (like the integers are). Instead, imagine a corporate hierarchy where the subordinates are below the boss in the hierarchy but are otherwise peers and one is not “greater” than the other. I believe that chart could qualify as a preorder. Cycles are allow for a preorder.
Partial Order – A partial order is the same as a preorder but with the additional constraint that if a ⩽ b and b ⩽ a than a must be the same as b. An example here might be rock, paper, scissors where rock ⩽ paper ⩽ scissors ⩽ rock. However, cycles are not allowed for a partial order, so this would only work if you dropped the scissor ⩽ rock.
Total Order – As previously mentioned, the integers are a total order because they have all the properties of both a preorder and partial order but have the additional constraint that every object has a relationship to every other object.
Thin Category – A thin category is one where there is at most a single arrow going from one object to another. A preorder is an example of a Thin Category according to the book, but I’m unclear why. (Wouldn’t my hierarchy example still have composition to people up the hierarchy?)
A hom-set (written C(a,b)) is the set of morphisms/arrows from object a to object b.
For a thin category, the hom-set between objects would be a singleton or empty.
Monoid – A Monoid can be thought of as a set that has these qualities:
- binary operator over a set.
- It’s associative.
- It has a unit element
For example, both addition and multiplication are monoids because they are binary operators, they are associative, and both have a unit element (i.e. 0 for addition and 1 for multiplication.)
Commutativity is not required for a monoid. String concatenation is a monoid even though it’s not commutative.
Monoid as Category – So why does the word “monoid” have “mono” in it? When we think of a monoid as a category we think of it as being a category with a single object with a bunch of morphisms. In other words, think of the monoid as the set of integers with, say, a function called “add 5” (which maps 0 to 5, 1, to 6, etc.) Now imagine that you have both the function “add 1” and “add 5”. You could compose them to make a new function “add 6.” In essence, the monoid is no longer a “set” but a category of morphisms/functions that follow the rules of a category.
I admit that I don’t fully understand that last paragraph. It makes sense, as far as it goes, but I’m confused about what the mono-object is in the Monoid-as-Category view of the world. The book didn’t explain this very well in my opinion. Is there anyone else out there that can help me understand it better?
The Hom-Set of a Monoid Category – Every monoid-as-category can have a set extracted from it. The hom-set of a monoid category is the set of all morphisms/functions for that object. That would be every function and every composition of function. Since all the functions have the same input and output object (since there is only one of them) they can all be composed.
This implies that we can always recover a set monoid from a category monoid by just taking the hom-set of the object. Just take the hom-set M(m,m) where m is the monoid object. This returns the set of all functions for the monoid.
I’m, again, unclear on what the above really means. If anyone can explain this better than the book, that would be helpful.
Locally Small Categories – Some categories are larger than sets. (I would need an example of this, but the book provided none.) A category in which morphisms between any two objects form a set is called locally small.