In the previous instalment of Category Theory for Programmers we talked about the category of types and functions. If you’re new to the series, here’s the Table of Contents.
You can get real appreciation for categories by studying a variety of examples. Categories come in all shapes and sizes and often pop up in unexpected places. We’ll start with something really simple.
No Objects
The most trivial category is one with zero objects and, consequently, zero morphisms. It’s a very sad category by itself, but it may be important in the context of other categories, for instance, in the category of all categories (yes, there is one). If you think that an empty set makes sense, then why not an empty category?
Simple Graphs
You can build categories just by connecting objects with arrows. You can imagine starting with any directed graph and making it into a category by simply adding more arrows. First, add an identity arrow at each node. Then, for any two arrows such that the end of one coincides with the beginning of the other (in other words, any two composable arrows), add a new arrow to serve as their composition. Every time you add a new arrow, you have to also consider its composition with any other arrow (except for the identity arrows) and itself. You usually end up with infinitely many arrows, but that’s okay.
Another way of looking at this process is that you’re creating a category, which has an object for every node in the graph, and all possible chains of composable graph edges as morphisms. (You may even consider identity morphisms as special cases of chains of length zero.)
Such a category is called a free category generated by a given graph. It’s an example of a free construction, a process of completing a given structure by extending it with a minimum number of items to satisfy its laws (here, the laws of a category). We’ll see more examples of it in the future.
Orders
And now for something completely different! A category where a morphism is a relation between objects: the relation of being less than or equal. Let’s check if it indeed is a category. Do we have identity morphisms? Every object is less than or equal to itself: check! Do we have composition? If a <= b and b <= c then a <= c: check! Is composition associative? Check! A set with a relation like this is called a preorder, so a preorder is indeed a category.
You can also have a stronger relation, that satisfies an additional condition that, if a <= b and b <= a then a must be the same as b. That’s called a partial order.
Finally, you can impose the condition that any two objects are in a relation with each other, one way or another; and that gives you a linear order or total order.
Let’s characterize these ordered sets as categories. A preorder is a category where there is at most one morphism going from any object a to any object b. Another name for such a category is “thin.” A preorder is a thin category.
A set of morphisms from object a to object b in a category C is called a hom-set and is written as C(a, b) (or, sometimes, HomC(a, b)). So every hom-set in a preorder is either empty or a singleton. That includes the hom-set C(a, a), the set of morphisms from a to a, which must be a singleton, containing only the identity, in any preorder. You may, however, have cycles in a preorder. Cycles are forbidden in a partial order.
It’s very important to be able to recognize preorders, partial orders, and total orders because of sorting. Sorting algorithms, such as quicksort, bubble sort, merge sort, etc., can only work correctly on total orders. Partial orders can be sorted using topological sort.
Monoid as Set
Monoid is an embarrassingly simple but amazingly powerful concept. It’s the concept behind basic arithmetics: Both addition and multiplication form a monoid. Monoids are ubiquitous in programming. They show up as strings, lists, foldable data structures, futures in concurrent programming, events in functional reactive programming, and so on.
Traditionally, a monoid is defined as a set with a binary operation. All that’s required from this operation is that it’s associative, and that there is one special element that behaves like a unit with respect to it.
For instance, natural numbers with zero form a monoid under addition. Associativity means that:
(a + b) + c = a + (b + c)
(In other words, we can skip parentheses when adding numbers.)
The neutral element is zero, because:
0 + a = a
and
a + 0 = a
The second equation is redundant, because addition is commutative (a + b = b + a), but commutativity is not part of the definition of a monoid. For instance, string concatenation is not commutative and yet it forms a monoid. The neutral element for string concatenation, by the way, is an empty string, which can be attached to either side of a string without changing it.
In Haskell we can define a type class for monoids — a type for which there is a neutral element called mempty
and a binary operation called mappend
:
class Monoid m where mempty :: m mappend :: m -> m -> m
The type signature for a two-argument function, m->m->m
, might look strange at first, but it will make perfect sense after we talk about currying. You may interpret a signature with multiple arrows in two basic ways: as a function of multiple arguments, with the rightmost type being the return type; or as a function of one argument (the leftmost one), returning a function. The latter interpretation may be emphasized by adding parentheses (which are redundant, because the arrow is right-associative), as in: m->(m->m)
. We’ll come back to this interpretation in a moment.
Notice that, in Haskell, there is no way to express the monoidal properties of mempty
and mappend
(i.e., the fact that mempty
is neutral and that mappend
is associative). It’s the responsibility of the programmer to make sure they are satisfied.
Haskell classes are not as intrusive as C++ classes. When you’re defining a new type, you don’t have to specify its class up front. You are free to procrastinate and declare a given type to be an instance of some class much later. As an example, let’s declare String
to be a monoid by providing the implementation of mempty
and mappend
(this is, in fact, done for you in the standard Prelude):
instance Monoid String where mempty = "" mappend = (++)
Here, we have reused the list concatenation operator (++)
, because a String
is just a list of characters.
A word about Haskell syntax: Any infix operator can be turned into a two-argument function by surrounding it with parentheses. Given two strings, you can concatenate them by inserting ++
between them:
"Hello " ++ "world!"
or by passing them as two arguments to the parenthesized (++)
:
(++) "Hello " "world!"
Notice that arguments to a function are not separated by commas or surrounded by parentheses. (This is probably the hardest thing to get used to when learning Haskell.)
It’s worth emphasizing that Haskell lets you express equality of functions, as in:
mappend = (++)
Conceptually, this is different than expressing the equality of values produced by functions, as in:
mappend s1 s2 = (++) s1 s2
The former translates into equality of morphisms in the category Hask (or Set, if we ignore bottoms, which is the name for never-ending calculations). Such equations are not only more succinct, but can often be generalized to other categories. The latter is called extensional equality, and states the fact that for any two input strings, the outputs of mappend
and (++)
are the same. Since the values of arguments are sometimes called points (as in: the value of f at point x), this is called point-wise equality. Function equality without specifying the arguments is described as point-free. (Incidentally, point-free equations often involve composition of functions, which is symbolized by a point, so this might be a little confusing to the beginner.)
The closest one can get to declaring a monoid in C++ would be to use the (proposed) syntax for concepts.
template<class T> T mempty = delete; template<class T> T mappend(T, T) = delete; template<class M> concept bool Monoid = requires (M m) { { mempty<M> } -> M; { mappend(m, m); } -> M; };
The first definition uses a value template (also proposed). A polymorphic value is a family of values — a different value for every type.
The keyword delete
means that there is no default value defined: It will have to be specified on a case-by-case basis. Similarly, there is no default for mappend
.
The concept Monoid
is a predicate (hence the bool
type) that tests whether there exist appropriate definitions of mempty
and mappend
for a given type M
.
An instantiation of the Monoid concept can be accomplished by providing appropriate specializations and overloads:
template<> std::string mempty<std::string> = {""}; std::string mappend(std::string s1, std::string s2) { return s1 + s2; }
Monoid as Category
That was the “familiar” definition of the monoid in terms of elements of a set. But as you know, in category theory we try to get away from sets and their elements, and instead talk about objects and morphisms. So let’s change our perspective a bit and think of the application of the binary operator as “moving” or “shifting” things around the set.
For instance, there is the operation of adding 5 to every natural number. It maps 0 to 5, 1 to 6, 2 to 7, and so on. That’s a function defined on the set of natural numbers. That’s good: we have a function and a set. In general, for any number n there is a function of adding n — the “adder” of n.
How do adders compose? The composition of the function that adds 5 with the function that adds 7 is a function that adds 12. So the composition of adders can be made equivalent to the rules of addition. That’s good too: we can replace addition with function composition.
But wait, there’s more: There is also the adder for the neutral element, zero. Adding zero doesn’t move things around, so it’s the identity function in the set of natural numbers.
Instead of giving you the traditional rules of addition, I could as well give you the rules of composing adders, without any loss of information. Notice that the composition of adders is associative, because the composition of functions is associative; and we have the zero adder corresponding to the identity function.
An astute reader might have noticed that the mapping from integers to adders follows from the second interpretation of the type signature of mappend
as m->(m->m)
. It tells us that mappend
maps an element of a monoid set to a function acting on that set.
Now I want you to forget that you are dealing with the set of natural numbers and just think of it as a single object, a blob with a bunch of morphisms — the adders. A monoid is a single object category. In fact the name monoid comes from Greek mono, which means single. Every monoid can be described as a single object category with a set of morphisms that follow appropriate rules of composition.
String concatenation is an interesting case, because we have a choice of defining right appenders and left appenders (or prependers, if you will). The composition tables of the two models are a mirror reverse of each other. You can easily convince yourself that appending “bar” after “foo” corresponds to prepending “foo” after prepending “bar”.
You might ask the question whether every categorical monoid — a one-object category — defines a unique set-with-binary-operator monoid. It turns out that we can always extract a set from a single-object category. This set is the set of morphisms — the adders in our example. In other words, we have the hom-set M(m, m) of the single object m in the category M. We can easily define a binary operator in this set: The monoidal product of two set-elements is the element corresponding to the composition of the corresponding morphisms. If you give me two elements of M(m, m) corresponding to f
and g
, their product will correspond to the composition g∘f
. The composition always exists, because the source and the target for these morphisms are the same object. And it’s associative by the rules of category. The identity morphism is the neutral element of this product. So we can always recover a set monoid from a category monoid. For all intents and purposes they are one and the same.
There is just one little nit for mathematicians to pick: morphisms don’t have to form a set. In the world of categories there are things larger than sets. A category in which morphisms between any two objects form a set is called locally small. As promised, I will be mostly ignoring such subtleties, but I thought I should mention them for the record.
A lot of interesting phenomena in category theory have their root in the fact that elements of a hom-set can be seen both as morphisms, which follow the rules of composition, and as points in a set. Here, composition of morphisms in M translates into monoidal product in the set M(m, m).
Acknowledgments
I’d like to thank Andrew Sutton for rewriting my C++ monoid concept code according to his and Bjarne Stroustrup’s latest proposal.
Challenges
- Generate a free category from:
- A graph with one node and no edges
- A graph with one node and one (directed) edge (hint: this edge can be composed with itself)
- A graph with two nodes and a single arrow between them
- A graph with a single node and 26 arrows marked with the letters of the alphabet: a, b, c … z.
- What kind of order is this?
- A set of sets with the inclusion relation: A is included in B if every element of A is also an element of B.
- C++ types with the following subtyping relation: T1 is a subtype of T2 if a pointer to T1 can be passed to a function that expects a pointer to T2 without triggering a compilation error.
- Considering that Bool is a set of two values True and False, show that it forms two (set-theoretical) monoids with respect to, respectively, operator
&&
(AND) and||
(OR). - Represent the Bool monoid with the AND operator as a category: List the morphisms and their rules of composition.
- Represent addition modulo 3 as a monoid category.
Next: A programming example of pure functions that do logging using Kleisli categories.
Follow @BartoszMilewski
December 16, 2014 at 5:10 pm
[…] Categories Great and Small Follow […]
December 17, 2014 at 1:20 am
Whilst it’s true that sorting with respect to a preorder requires that preorder to be total, it’s amusingly the case that the conditions for being a preorder in the first place aren’t critical to sorting. As I showed in “How to Keep Your Neighbours in Order”, if you just want to ensure local sorting, i.e., that neighbours in the output are related by <=, you need only know that (x <= y) or (y <= x) for any x and y, not that <= is a preorder. Of course, once you've sorted, if you want to make useful deductions about elements in the output which are not neighbours, you do need <= to be a preorder.
The list [Stone, Paper, Scissors] is locally sorted with respect to the "does not defeat" relation.
December 17, 2014 at 1:29 am
I wrote a comment and then when I wanted to post it, it wanted me to log in, so I had to do a password reset, and then when I logged in, it had forgotten my comment. It was something about sorting algorithms relying more on the “total” than the “preorder”. The usual sorting algorithms arrange lists over {Stone, Paper, Scissors} with respect to “does not defeat” in such a way that all immediate pairs of neighbours in the output satisfy that relation, even though it’s not a preorder. But I have forgotten it. It may not be worth remembering.
December 23, 2014 at 6:49 pm
[…] the previous installment of Categories for Programmers, Categories Great and Small, I gave a few examples of simple categories. In this installment we’ll work through a more […]
December 24, 2014 at 6:39 am
I found the notion of a monoid rather confusing at first. When thinking about graphs, I think of edges as ordered pairs of nodes. (That is, I don’t work with multigraphs.) Since the monoid has multiple arrows with the same start and end node, that’s clearly not what’s going on here. You have to think of arrows having their own identities.
Collapsing all the set members into a single node without also collapsing arrows seems like a particularly strange move. Each arrow represents a mapping from a particular input to a particular output, so it seems like we want to forget about the particular instances and concentrate on the function’s type, except that we’re keeping all the arrows, so not really.
December 28, 2014 at 2:29 am
[…] Categories Great and Small by Bartosz Milewski. […]
January 14, 2015 at 3:36 am
Hi. Just want to say thanks about your hard work on this series. I tried to learn Haskell myself for a while. After reading this series, I derived all the functor / applicative functor / monad laws on paper and suddenly everything ticked!
Looking forward to the sequel 🙂
January 24, 2015 at 4:30 pm
I dont understand how is possible to build category and infinite number of arrows from graph of finite size.
January 24, 2015 at 10:58 pm
@Luka: In a category, you can have many arrows connecting the same two objects. In a graph, it would correspond to multiple (directed) edges connecting two nodes. Such graphs are sometimes called multigraphs with loops.
January 24, 2015 at 11:13 pm
How do you determine whether two arrows are actually the same? As a programmer I’m used to thinking of nodes as having unique ids and edges as being ordered pairs of nodes. Obviously that won’t work here.
January 25, 2015 at 11:40 am
@Brian: You have to label your edges as well. In the example of the category of sets, functions have names like f, g, h.
April 30, 2015 at 6:10 am
Reading “(in other words, any two composable arrows)”, I am not sure if the identity arrows are composable. The next sentence explicitly excludes identity arrows, but it’s not clear if this applies to the previous sentence or not.
Assuming that identity arrows are never composable, it might be more clear to make “add an identity arrow at each node” be the last step instead of the first.
(Really enjoying this series, thank you!)
April 30, 2015 at 9:11 am
Identity arrows are composable; it’s just that you don’t have to consider them as sources of new connections. Composing an identity with any arrow gives back the same arrow, not a new connection.
April 30, 2015 at 10:29 pm
Despite reading the series carefully from start, I have not understood the category theory concepts; categories, morphisms, arrows etc. It’s just too abstract. Any helpful resources?
April 30, 2015 at 10:35 pm
Hello Bartosz, are you planning to provide solutions to the challenges? It would really help me (and probably others as well) to understand all this. Thanks!
May 6, 2015 at 11:13 am
Very good series of posts, Bartosz!
+1 tabel. I would also like to see solutions to the challenges.
May 9, 2015 at 11:47 am
Much, much, much more code, please – preferably Haskell. As a non-mathematician but Haskell lover I use the code samples to understand what you are talking about.
May 9, 2015 at 11:52 am
I understand f and g and f.g to “represent” the identity function. But what is a “hom-set”? Is it possible to show it in code?
May 9, 2015 at 1:49 pm
Klaus-Yussuf: No, they don’t represent identity. They represent, for instance, operations like
(+2)
or(+10)
(Haskell operator slices), which you can compose like this:Identity is
(+0)
. A hom-set is a set of all these operations. Here, it’s a subset of functions of the typeInt -> Int
.May 23, 2015 at 12:04 am
I’m stuck with this part of the chapter: “So we can always recover a set monoid from a category monoid.”
I think I understand in general what you meant there, but I fail to apply formal lingo. So, if I took the adders, example, this system can be expressed with multiple ways:
(1) a set of numbers with + operator and 0 as unit element (monoid),
(2) A category with one object – a set of numbers – and composable arrows – adders (category),
(3) a set of adders with “composition” operator and “+0” as unit element (monoid).
Here I assume that (3) is a set monoid here, and category monoid is… (1) and (2)? That’s what gets me, I don’t see why it’s called a category monoid, is it shorthand for “category with one object, which is a monoid”?
May 23, 2015 at 8:34 am
What is the dual of monoid?
May 23, 2015 at 10:17 am
@adrian: A categorical monoid is (3) because you’re not saying anything about what the object is. It just is, period. It serves as the attachment point for the arrows. All information is encoded in the rules of composition for those arrows — the “arrow multiplication table.”
The arrows, however, form a set. In this set we can easily define a binary operator — the result of “multiplying” two arrows is the arrow we obtain by composing them. Now forget about the fact that these are arrow and just treat them as elements of a set. You get a set with a binary operator (and unity) so that’s your set-theoretical monoid.
These are two equivalent ways of looking at the same thing.
May 23, 2015 at 10:23 am
@misha: Take a monoid and reverse all arrows in it. You still get a category (the dual category) with one object. Any category with a single object is a monoid. So the dual of a monoid is a monoid. It’s not necessarily the same monoid though. For instance, take the string monoid with string-append arrows. The dual will be a string-prepend monoid.
You might find people talking about comonoids, but these are defined in the context of categories with more structure — monoidal categories.
July 5, 2015 at 2:02 pm
I would like to re-ask, what is the graph here you started with? I fail to understand the collapse of integers into a single object either. You say that is type, what is important, we should ignore the values and then, magically, people somehow realize that Void has only one map to Bool whereas () has two distinguished map to Bool. If target value is important then why you don’t distinguish between them in Void -> Bool case?
July 5, 2015 at 2:20 pm
I mean that M(Bool, Bool) should have 1 object and 4 reflective functions (morphisms) if we count the values and 1 self-reference if we don’t. From your this week cnallanges I see that values don’t matter. However, the single pig drawing with multiple reflecting morphisms suggests otherwise in the text. The previous week responses to challanges demonstrate the total chaos: some values are taken into account, some are not. Particularly, I may have m^n functions for N -> M where types N and M take n and m values correspondingly. This means that Void -> Bool should have 2^0 = 1 function, () -> Bool should have 2^1 = 2 functions. Well, that starting making sense now. But, I still do not understand how to complete the graph in this week since you do not say how many values every node can take.
July 5, 2015 at 5:42 pm
Categories are an abstraction, which means you take something and remove (subtract) details from it until you get the essence. In this case, you take a set of values {True, False} and define functions on it. One function ANDs these values with True, another ANDs them with False. Look at the composition of these functions. You get some kind of a “multiplication table” of functions. Write it down.
Now forget about the values inside the set and treat it as an opaque object. You have one object and two morphisms together with composition rules that you have just defined. It’s a category (is it?). If so, it’s a monoid because you have only one object.
July 25, 2015 at 3:56 pm
If I understood it right, the monoid is a special type of category, that has the same structure in every point.
Namely, if we have object “1” with arrows “1 -> 3”, than “the same” arrow exist in point “3”: “3 -> 5”. In this sense we can say that “1 -> 3” and “3 -> 5” are “the same” arrow, and then we can forget about differencies between “1” and “3” and go to the single object “Set” with generalized arrows.
Is that right, or there is another restriction for the category to be monoidal?
July 25, 2015 at 4:37 pm
@nepalez: First of all, what’s a “point”? There is only one object in a monoid as a category. Try doing exercises 3 to 5 to get some experience in switching between the set-based picture and the category picture.
Also, a “monoidal category” is yet another concept, which I haven’t talked about yet.
July 26, 2015 at 8:36 pm
Bartosz, Yeah, I understood how monoid works.
I’m trying to imagine what conditions should satisfy a category of “+” (whose objects are numbers and arrows are additions to numbers) to be “equivalent” to some monoid.
As far as I understood, the addition by module also should be monoid with finite number of arrows. And many other operations too.
August 23, 2015 at 6:57 pm
Challenge 1.4.
Adding arrow marked as ø
Adding infinity set of rows marked as aa, ab, ac, … az, ba, bb, bc, …, aaa, …. ba, bb, bc, ….. (all combinations of latin alphabetic).
Composition of row marked as ø and row marked by n symbols x1….xn is arrow x1…xn.
Composition of ø and ø is ø
Composition of arrow x1…xn and arrow y1….ym is arrow marked as x1…xny1…ym
ø is id arrow
August 23, 2015 at 6:59 pm
Challenge 5.
arrows are (+ 0), (+ 1), (+ 2).
September 9, 2015 at 4:36 am
Just to make sure I understand monoids: From the monoid-as-category point of view, we have a single object with many morphisms that point to itself. Hence, each of these morphisms is an identity morphism for the object. From this point of view, all the morphisms in the category are isomorphic, because they all map the object to itself.
However, from the monoid-as-set point of view, these morphisms are not isomorphic at all, because each one represents a different function. In particular, one of the morphisms corresponds to the neutural element, and only this morphism can be interpreted as an identity function within the monoid, because it maps any element of the set to itself.
As an example, if the monoid is natural numbers under addition, then the category’s single object is the set of natural numbers. Each morphism corresponds to an “adder” such as +0, +1, +5, etc. From the category’s point of view, +5 is still an identity morphism because it maps natural numbers to natural numbers. But from the monoid-as-set’s point of view, +5 is not an identity, because x+5 does not equal x. Only +0 is an identity from both the set’s and the category’s point of view.
In other words, we have identity morphisms (within the category) and identity functions (operating on elements of the set), and exactly one of the identity functions is also an identity morphism. Yes?
September 13, 2015 at 8:32 pm
@brianberns: “each of these morphisms is an identity morphism for the object” No! Only one of them is the identity. The others are not. And they are not isomorphic in any sense.
I noticed that a lot of people make this mistake of thinking that you can identify all morphisms that connect the same pair of objects. Morphisms between two fixed objects form a set. They are all different points within this set. You can’t identify points in a set.
The same applies to morphisms from an object to itself. They are all different points in a set. One of these points is the identity morphism.
BTW, this set is called the hom-set, and I talk about it more and more in the following installments.
September 24, 2015 at 12:52 am
I’m not seeing that. What’s the subtlety that would make that work?
September 24, 2015 at 12:53 am
Never mind, I think I got it: All the strings are mirrors in the two worlds (I was trying to get identical strings across the worlds).
December 9, 2015 at 9:32 am
@Bartosz, you said there is a “category of all categories”.
However, this man here claims that this is not true, and even gives a proof:
http://cs.nyu.edu/pipermail/fom/1999-May/003117.html
What do you think?
December 9, 2015 at 10:06 am
@Bartosz, you said in a comment:
“Take a monoid and reverse all arrows in it. You still get a category (the dual category) with one object. Any category with a single object is a monoid. So the dual of a monoid is a monoid. It’s not necessarily the same monoid though. For instance, take the string monoid with string-append arrows. The dual will be a string-prepend monoid.”
Are you sure that is right? I mean, if I take the arrow corresponding to an operation which appends “bar” to a string, and look at what happens when I bring back the string set structure to the object, I get something else. Let’s say we have a string “foo” and apply the “bar” appending arrow to it: I get “foobar”. Now what happens if we reverse the arrow? It goes backwards, and it maps “foobar” to what? I say it maps “foobar” to “foo”. So the reverse operation would be “cutting” tails of strings.
But maybe applying set intuitions to abstract concepts like morphisms (e. g. saying that these morphisms do something more than just “being there”) doesn’t make sense?
December 9, 2015 at 2:57 pm
@Kamil: Yes, it’s a little tricky and I’m afraid we both got it wrong. What you are talking about is the inverse morphism. The inverse of appending would indeed be cutting. But reversing the direction of morphisms is not the same as inverting them. It’s an operation on the “mutliplication table” of morphisms.
If in the original monoid you have an arrow marked “foo” and another marked “bar”, their compositon “bar” after “foo” would give you an arrow marked “foobar”. All these arrows go from m to m.
If you reverse their direction, you get “foo”op after “bar”op resulting in the arrow marked “foobar”op. Reversion or arrows resulted in the transposition of the “multiplication law.”
If you want to understand this new multiplication table in terms of a set of strings, you have to interpret the arrow “foo”op as prepending “foo” and “bar”op as prepending “bar”. If you prepend “bar”op after prepending “foo”op you get the same result as prepending “foobar”.
I’ll fix the text.
December 9, 2015 at 3:13 pm
@Kamil: About the category of all categories: Yes, it’s a very tricky subject. There are standard ways of avoiding paradoxes. Mac Lane distinguishes between small and large categories and he defines a category of small categories (which really is a 2-category). Grothendieck came up with a hierarchy of universes — a solution similar to Russell’s theory of types. But as I said in the introduction, I don’t want to go too deep into foundations of mathematics — although it is a fascinating topic.
December 10, 2015 at 5:24 am
@Bartosz, thanks for your answers.
Indeed, when I look closer at what happens when composing these inverse arrows, I clearly see that it means prepending. I think that we just have to look what happens between the morphisms themselves, not what they “do inside the object” (since they actually don’t do anything to the object, they just are).
Also I understand the “category of categories” subject is difficult, but I still think you shouldn’t leave “category of all categories (yes, there is one)” as it is now in the post, especially when in the Functors chapter you say:
“It’s a category of categories. But a category of all categories would have to include itself, and we would get into the same kinds of paradoxes that made the set of all sets impossible.”
The reader WILL be confused 😛
Anyway, the book is great, a very interesting read (and easy to understand). Thank you for it and keep it up!
January 18, 2016 at 8:25 am
Not sure what you mean about composition of <= being associative. Normally <= returns boolean, so let’s feed it with booleans for simplicity and define True>False. Then ((F <= T) <= F) = (T <= F) = F but (F <= (T <= F)) = (F <= F) = T.
January 18, 2016 at 1:20 pm
Morphisms in the order category are not functions. They are abstract arrows. There is either no arrow from a to b, if a is NOT less or equal to b; or a single arrow, if a <= b. So an arrow points to an object that is either grater or equal to the source object. This is a good example of a category because it takes you away from thinking of arrows as functions.
January 19, 2016 at 8:09 am
So what does associativity mean when we’re not talking about functions?
January 19, 2016 at 9:07 pm
You still have composition of morphisms (a <= b && b <= c then there is a composite arrow a <= c). Associativity means that when composing three such morphisms it doesn’t matter if you first compose the first two, or the last two.
January 20, 2016 at 9:34 am
But that seems like it would always be true because you said that a<=c exists by the axioms of category theory. Is there an example where it isn’t true?
January 20, 2016 at 3:54 pm
The word “axiom” is a bit confusing. If somebody gives you a category (cross my heart, this is a category!), than you can use the “axioms.” But here we are trying to show that something is a category (maybe it’s not?). We have to prove that we can define composition using the operator that defines ordering. There are some axioms of ordering, and we use them to prove “axioms” of category.
January 20, 2016 at 10:56 pm
@Bartosz Milewski
first of all, thank you for these great articles.
My question is :
is Hask category a thin-category?
it seems between 2 types, there could by many functions.
But the Hask category seems a preorder set, it is reflexive and transitive.
Seems all categories are preorder set, they all need have id morphism and can composite. (reflexive and transitive)
I am confused.
thanks
Gavin
January 21, 2016 at 3:37 pm
@Gavin: Hask is not a thin category, therefore it’s not a preorder. But the intuition makes sense, and I sometimes call a category a “thick” preorder.
January 27, 2016 at 3:35 am
Am a programmer, okay. And I read about functional programming and category on occasion. What still eludes me, is what it gives me in a practical situation (am engineer, not mathematician, spent lots of time with embedded programming, real time, systems, drivers). Why not give a really practical example which shows how it all comes together? E.g. 2 communicating finite state machines, running asynchronously, then showing how the 2 can “compose”, how you can use category theory to proof stuff (e.g. reachable states)…?
March 30, 2016 at 3:46 pm
“bottoms” makes its first appearance without a prior or nearby definition..
May 25, 2016 at 8:51 am
@BartoszMilewski
I’m confused by this (from comment #33, above):
“I noticed that a lot of people make this mistake of thinking that you can identify all morphisms that connect the same pair of objects. Morphisms between two fixed objects form a set. They are all different points within this set. You can’t identify points in a set.”
Why do you say that we can’t identify points in a set? If I have the set, {1, 2, 3}, I can certainly identify its elements.
Thanks!
-db
May 25, 2016 at 9:55 am
Maybe the word “identify” is confusing here. In math it means stating that two things are identical. In your case it would be saying that, for instance, 1=3, which is not true.
May 25, 2016 at 12:47 pm
@BartoszMilewski, in challenges 1.2 and 1.4, do we end up with an infinite number of reflective arrows, due to infinitely recursive composability?
May 25, 2016 at 1:02 pm
Yes.
June 25, 2016 at 3:57 am
Hi, thanks a lot for your work.
I have a quick clarification if you don’t mind.
“A set with a relation like this is called a preorder, so a preorder is indeed a category.”
In wikipedia it is stated that preorder is a relation itself, and set equipped with preorder is called preordered set.
I am not nitpicking at all, I am just trying to understand all these mathematical stuff.
I am confused now. if preorder is a relation and category could be preorder, then is category a relation?
Thanks.
June 26, 2016 at 3:38 am
Thanks a lot for this work.
I just want to clarify my understanding about Monoid. Are there just two points of view on Monoids described here – one as set + 1 operation and one as category with one object and set of operations? Or there are three and I just missed one?
Another question regarding categories.
You stated that category theory abstracts away from the concrete “examples/instances” of objects. So object will always be just abstract unknown object and the whole essence is in morhisms(arrows)?
Thanks.
June 26, 2016 at 11:23 am
@Yuriy: There are internet resources that provide formal definitions. One of them is wikipedia, another one is nlab. However, the ability to look at the same thing from many different perspectives is very useful. You may look at a preorder as a relation between sets, or you may look at it as a category. Here’s a sentence from nlab: “preorders may be regarded as certain categories (namely, thin categories)”.
The same goes for monoids. The third definition of monoids is in the context of a monoidal category.
Objects in a category have no structure.
June 27, 2016 at 11:17 pm
the concept definition:
{ mappend(m, m); } -> M;
should be
{ mappend(m, m) } -> M;
September 19, 2016 at 1:44 am
@Bartek this is very interesting article serie. I enjoy reading it.
Could you please explain from programmer’s point of view what is a morphism?
One can read definition of morphism but it is still hard to understand what does it really mean for programmer? For example what does it mean that map preserves structure? How should I understand structure in this context?
Definition from quora:
It is a generalisation of the so-called “structure preserving maps” of various algebraic, combinatorial, geometric structures – functions between sets (there is no additional structure to preserve, here), homomorphisms between groups (or rings, fields, etc.), linear transformations between vector spaces, homomorphisms between graphs (in graph theory), continuous maps in topology, etc.
Definition from wiki:
In many fields of mathematics, morphism refers to a structure-preserving map from one mathematical structure to another.
September 25, 2016 at 2:04 am
I think I’m still getting tripped up by the single object M category. I recognize that for instance integer addition and string addition have the same “shape” and follow the same laws, so they fall into the same category. But can I not say the same thing about the SET category? Why is every possible set its own object in SET, but two different monoids are the same object in M?
You mention that in M one can “explode” all arrows into a table of possible combinations, and conversely all these combinations collapse into the single object in M. Why does that not happen for SET? Don’t sets all have the same structure and follow the same laws too, especially if we “abstract away” their elements when looking at them with “categorical glasses”?
September 25, 2016 at 1:02 pm
@Matthias There are many single-object categories, each with a different rules for composition of morphisms. Each of them represents a different monoid. Interestingly, those different monoids form a category of their own, with monoid homomorphisms as arrows. I describe this in the post about free monoids, where I also show how they relate to Set.
September 25, 2016 at 1:17 pm
Ah interesting–that makes sense. I hadn’t gotten to the part about free monoids yet. Thanks Bartosz!
September 25, 2016 at 1:17 pm
@Paweł : Programmers work (most of the time) in a particular category of types and functions. Functions are maps between sets, and sets have no structure to preserve. But if you want to work, for instance, in a category of monoids, then you want your morphisms to preserve monoidal structure. That structure is defined by multiplication and unit. In particular, you want morphisms between monoids to map the unit of one monoid to the unit of the other.
Of course, once you construct your category of monoids, you forget about their internal structure. You are only left with morphisms between them and their composition table, which was derived from the knowledge of how the structure-preserving maps composed.
So you start with structure preserving maps to generate a category, and then you promptly forget about the structure.
October 1, 2016 at 7:17 am
Hi, I’m a new reader to the series. Thanks a lot for your work!
I have trouble understanding morphisms. Am I right in saying that even for Set, not all morphisms need to be functions? Is it okay to say that a morphism exists between set A and B if A is a subset of B? (Similar to partial order)
October 2, 2016 at 10:50 pm
Siddharth: In category Set all morphisms are functions.
There is another category in which objects are also sets, but morphisms are defined by the subset relation. That category is not called Set though. And it is indeed a partial order.
October 23, 2016 at 1:09 pm
Great article!
I just didn’t understand this part:
There is just one little nit for mathematicians to pick: morphisms don’t have to form a set. In the world of categories there are things larger than sets. A category in which morphisms between any two objects form a set is called locally small.
1.Why “morphisms don’t have to form a set”? If there are no morphisms between two objects, the morphisms form the empty set. So they will always form a set, right?
2.”In the world of categories there are things larger than sets.” What are you referring to?
October 23, 2016 at 9:38 pm
The empty set if fine. That’s not the problem. The problem is that you can define things bigger than sets. The classic example is the collection of all sets — it’s not a set!
The reasoning goes something like this: For every set, the set of all its subsets is strictly larger than the set itself (Cantor’s theorem). But the set of all sets would have to contain all its subsets. But there are more of them than there are sets in the set of all sets. So it’s a paradox.
We can define a category of all sets, but its objects (sets) don’t for a set. So it’s not a small category.
Functors are morphisms between categories. Morphisms between two large categories don’t form a set — there are too many of them. So the category of all categories is not locally small.
November 2, 2016 at 3:53 pm
[…] A Monoid is such a type class and relates to category theory. (Also see Categories Great and Small). […]
November 23, 2016 at 12:33 pm
@Bartosz: Probably more intuitive is the set of sets that do not contain themselves. Then just think about whether this “super-set” is an element of itself. If yes, the set would contain itself, which is against its definition. But if no, the set would not contain itself, which is also against its definition. When Russels paradoxon came up, they had to start reasoning more precise about sets.
January 4, 2017 at 10:00 pm
Thanks for the article! One small point, though. I think the following is incorrect: “you can easily convince yourself that any directed acyclic graph generates a partial order as its free category.” For example, in the DAG {(A,B), (A,C), (B,D), (C,D)}, there are two paths from A to D, so the free category is not thin. To get to the partial order, I guess you can take the “free thin category” generated by the graph.
January 4, 2017 at 11:22 pm
@Darsh: You’re right. I’ll just remove this statement.
January 11, 2017 at 9:48 pm
[…] Bartosz […]
April 5, 2017 at 6:39 pm
Wonder if you could give the permission to let me translate your Category-Theory-Series to Chinese on my Blog?
April 5, 2017 at 9:22 pm
Absolutely! Feel free to translate my blog. There is already a Russian translation in progress, and a French one.
October 10, 2017 at 2:09 am
The C++ syntax:
Instead one can use:
Sadly it’s pretty ugly.
A SFINAE version is also doable giving a clearer error message but leading to more code (which may not be relevant in this case).
November 7, 2017 at 6:55 pm
Hi @Bartosz. I’m a little confused by challenge 1b. I assume that the directed edge is separate from the identity function and does not point to any node? Does this edge represent a function that returns undefined? I’m unclear how to interpret this and the meaning of composing an edge with itself when the edge does not point to another node. Perhaps I am missing something obvious, but I would be very thankful for some guidance here!
November 8, 2017 at 1:35 am
An edge must always go from node to node. Since there is only one node, the edge must necessarily loop back.
November 8, 2017 at 3:56 am
okay thank you for clarifying! how is it that in order to generate a free category from this graph that we must compose these edges with themselves infinitely while this does not appear to be necessary for the identity function?
November 8, 2017 at 4:12 am
Please disregard the above – I re-read that section and see that there are special exceptions for the identity morphism.
By the way, thank you for putting this book together!
January 28, 2018 at 6:33 pm
Reading https://en.wikipedia.org/wiki/Free_category would clarify what the challenges are looking for.
August 20, 2018 at 3:47 am
“Every monoid can be described as a single object category with a set of morphisms that follow appropriate rules of composition.”
but a Monoid is defined like this with only one function.
(M, e, *)
M is a set
e is a neutral element
* is a function *: M x M -> M
Does this mean that for each adder function we have something like this?
(ℕ, 0, add0)
(ℕ, 0, add1)
(ℕ, 0, add2)
…
for multiplication we have this
(ℕ, 1, multiply0)
(ℕ, 1, multiply1)
(ℕ, 1, multiply2)
…
Is this correct?
And if we were to put this in graph notation we would have a node for each of these functions representing the set of Natural Numbers?
Sorry if I am wrong I am new to Category Theory 🙂
August 20, 2018 at 10:06 am
Notice that, even though your * is just one function, it’s a function of two arguments. You can think of it as a different function for each choice of the first argument. These will be functions of the type multiply0, multiply1, etc. They are all composable, e.g., multipy2 . multiply3 = multiply6, and so on. These functions will correspond to the morphism in the single-object category for this monoid.
September 14, 2018 at 8:59 am
You are falling into the trap of explaining it like a mathematician..eg. explaining it so that the only people who can understand it..are people who already understands it…a lot of foreign concepts comes up constantly with no explanation of what they are.
October 12, 2018 at 4:45 pm
I am confused about problem 1(a) and 1(b), and why we end up with infinitely many arrows in one and a single arrow in the other. In (a) we are given a single node and no edge. Ok, to turn this into a category I need to add a single identity morphism. In (b) we are given a single node and one edge (that must necessarily loop back on itself). Can’t we claim that the looping back edge is the identity morphism and it’s already fulfilled its requirements of being a category?
October 12, 2018 at 5:11 pm
Call this edge f. You’re saying that f . f = f. Where did you get this equation from? It wasn’t in the original graph, and the free construction doesn’t impose any such equations.
October 12, 2018 at 5:15 pm
aha! Thank you!
October 13, 2018 at 1:54 am
This one confused me for the longest time, too. I thought to myself, “how can an arrow from an object to itself be anything other than identity?” Then a friend reminded me that “objects” in categories aren’t necessarily singular. They may have sub-objects. We’re just discouraged from thinking about those sub-objects, when learning Category Theory.
November 26, 2018 at 10:37 am
Hi Bartosz,
Bart mention in the section about Orders “You may, however, have cycles in a preorder. Cycles are forbidden in a partial order.”.
Can you elaborate on what is meant by cycles in this context?
November 26, 2018 at 9:15 pm
The simplest cycle is when you have two objects such that a <= b and b <= a but a is not equal to b.
January 31, 2019 at 6:10 pm
Hi!
“String concatenation is an interesting
case, because we have a choice of defining right appenders and left appenders (or
prependers, if you will). The composition
tables of the two models are a mirror reverse of each other. You can easily convince yourself that appending “bar” after
“foo” corresponds to prepending “foo” after prepending “bar”.”
Let’s try it.
m -> (m -> m) – just a reminder how adders are created
I’ll write pseudocode.
in case of appenders we have “appending “bar” after
“foo”” with right to left composition, appending to letter “x”
bar . foo = xfoobar
in case of prependers “prepending “foo” after prepending “bar”.”
foo . bar = foobarx
xfoobar and foobarx don’t mirror each other, but if we say prepending “bar” after “foo” then
bar . foo = barfoox
xfoobar and barfoox are mirroring each other.
I know I must be wrong since someone would point it out during the years but where am I wrong? 🙂
January 31, 2019 at 10:21 pm
You have to read the strings backwards.
May 5, 2019 at 1:49 pm
I’ m reading your wonderfull book.
I can’t undestand “It’s worth emphasizing that Haskell lets you express equality of functions, as in: mappend = (++)”
It’s not an assignment ?
What I’m missing ?
thanks
May 5, 2019 at 4:18 pm
Assignment is when you modify an existing value. It’s mutation. Here it’s just a statement that mappend is equal to (++) and you can substitute one for another anywhere in your code.
May 6, 2019 at 12:54 am
thanks a lot, perfect. I was misunderstanding “express equality” as “test equality”.
My mistake !
September 5, 2020 at 4:14 pm
From this chapter, couldn’t understand anything.. Suddenly high learning curve.
September 5, 2020 at 4:23 pm
Could you explain 3.1 to 3.3 chapters pictorially? Suddenly, hard to understand.
June 28, 2021 at 11:22 pm
“The monoidal product of two set-elements is the element corresponding to the composition of the corresponding morphisms.” That was your first use of the term “monoidal product”, in a way that doesn’t look like a significant definition (but probably is?). It threw me for a while, especially as my “what the hell is that” reaction led me down a rabbit hole of coproducts and god-knows what else. I’m not sure that the set view of monoids helped, given that a lot of us probably haven’t dealt with monoids in any form before (we’re Programmers, or in my case Electrical Engineers). Why “monoidal product”? Is it because the dot of function composition looks like the dot of multiplication? Wikipedia barges off into tensors at this point – that doesn’t help much either.
June 29, 2021 at 10:46 am
That’s one of the dangers of writing: you sometimes don’t notice things that you take for granted. I should have said that “mappend” in the definition of Monoid is often called the monoidal product. (Even though the example I gave uses addition.)
May 4, 2022 at 8:25 pm
Thank you so much! Your articles help me a lot, but there is a sentence I don’t understand. “A preorder is a category where there is at most one morphism going from any object a to any object b.” I think a preorder category can have
more than one morphism going from a to b, and if there is at most one morphism, it should be a partial category. Could you explain more about this? Thank you.
May 4, 2022 at 8:44 pm
Let’s say we want a preorder based on numbers. Take two objects m and n. If m <= n, draw an arrow from m to n. Otherwise don’t. So either there is an arrow or not. The set of arrows from m to n is either a singleton, or empty.
February 28, 2023 at 10:48 pm
I’m confused about hom-sets in categories which are not locally small. If the hom-sets are collections larger than sets, how this conversion of a monoid category to a set works? Probably Yoneda lemma will also not work if the hom-sets in a category are larger than sets?
March 1, 2023 at 1:14 am
You can find some discussion there.