1
$\begingroup$

Normally I put the question before the context, but in this case I want to admit the possibility that the context and my understanding nullify the question. Plus it helps me think through my question.

I recently started reading Category Theory for Programmers (Bartosz Milewski), and this is my understanding of categories: they are "algebraic structures" which consist of objects and arrows/morphisms between those objects. The morphisms have to obey the laws of associativity, so

$$ a \rightarrow ( b \rightarrow c ) = ( a \rightarrow b ) \rightarrow c $$

And there must be an identity morphism for each object.

Now, Milewski goes on to explain that monoids (which I'm pretty comfortable with in the set-theoretic sense) are also viewable as categories. This is the part I am having trouble with. One of the exercises in the book is to consider the Boolean-and monoid (booleans with the and operator) as a category:

Represent the Bool monoid with the AND operator as a category: List the morphisms and their rules of composition.

I want to give some examples, which I'll do in a SML (though I'll borrow Haskell names).

The monoid could be described set-theoretically with the following signature:

signature MONOID = sig
  type m
  val mempty : m
  val mappend : m -> m -> m
end

Further, the monoid for booleans with the and operator would be given as

structure BoolAnd : MONOID = struct
  type m = bool
  val mempty = true
  fun mappend x y = x andalso y
end

So, here is my understanding of this monoid as a category and its morphisms: is it correct?

  • The objects in the category are booleans (true and false) and functions from booleans to booleans
  • BoolAnd.mappend is a morphism from the former to the latter
  • mappend true is an identity morphism for the function objects in the category (I say "an" because isn't the actual identity function fun id x = x also an identity morphism for the functions, thanks to polymorphic types? Or does that not count in category-land? I know that mappend true is equivalent to the identity function under composition of functions with type bool -> bool.)
  • the identity morphism for boolean objects appears to be just fun id (b:bool) = b
  • the given identity morphisms should be associative:
(* example, not proof *)
- open BoolAnd;
- (id o (mappend true)) o not;
val it = fn : bool -> bool
- it false;
val it = true
- id o ((mappend true) o not);
val it = fn : bool -> bool
- it false;
val it = true

The rules of composition seem to be that mappend true is the identity, while mappend false is a "sink" of sorts, causing the resulting function to always return false. But id and mappend don't directly compose, because the types do not align (when id is specialized to booleans, as in the bullets above).

Am I missing something? Is something wrong? Did I give too much detail (there seems to be an emphasis on avoiding digging in to the objects too much)?

I ask this both to confirm my understanding so that I have a good foundation for the remainder of the book and also because it took me a long time to identify the objects and morphisms at work; some of them I am still shaky about.

$\endgroup$
1
$\begingroup$

Monoids are one-object categories. The elements are morphisms, monoid multiplication is composition and the monoid identity is the identity morphism.

In the case of Booleans-with-AND the monoid is $M = (\{\top, \bot\}, \land, \top)$. The category therefore has a single object (we could call it $M$) with two morphisms $\top : M \to M$ and $\bot : M \to M$. Composition is given by $\land$ and the identity morphism is $\top$.


To give a little more context, there is a way to view a monoid in such a way that the objects are the elements of the monoid: as a discrete (no non-identity morphisms) monoidal category. Category Theory for Programmers covers the topic of monoidal categories in Chapter 22, "Monads Categorically".

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I see how composition and identity work in this construction, but I’m unsure how to interpret top/true as an arrow from M to M (naïvely, I am attempting to consider a function, perhaps due to the suggestive notation, but is there a better interpretation?). Given that there is a single object M, of course the morphisms have to go from M to M, but I cant make heads or tails of how true and false fit into that $\endgroup$ – D. Ben Knoble Jun 6 at 14:19
  • $\begingroup$ Morphisms are completely abstract: in general, they are not functions (though in certain cases, like the category of sets, they happen to be functions). Illustrative examples of this are monoids as one-object categories, and the category of matrices (in which morphisms are matrices). Remember that in the definition of a category, the morphisms from an object $A$ to an object $B$ form some set: there's no requirement for them to be functions or similar. If you have some things that can be composed, they can be morphisms in a category. $\endgroup$ – varkor Jun 6 at 14:24
  • $\begingroup$ The fact the morphisms in this example go from $M$ to $M$ doesn't really mean anything (though it suggests that morphisms in a category may be thought of "generalised elements" in some sense). It's simply a repackaging of the data of a monoid into the data of a category. You could call the single object whatever you like: it's simply there to provide a domain and codomain for the morphisms. $\endgroup$ – varkor Jun 6 at 14:26
  • $\begingroup$ Hm.. you’ve given me a lot to think about. Category of matrices makes sense from my linear algebra days. But if they aren’t necessarily function-like, how do they domain/codomain? Perhaps my definition of those terms is too restrictive. // Though again I do see the necessity of allowing M -> M ( -> M...) for composition purposes. $\endgroup$ – D. Ben Knoble Jun 6 at 14:35
  • 1
    $\begingroup$ The category of matrices is described here. The objects are natural numbers, and a morphism from $m$ to $n$ is an $n \times m$ matrix. Composition is matrix multiplication. Your description of the monoid of natural numbers is correct. $\endgroup$ – varkor Jun 6 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.