# Describing the Bool-And monoid in terms of categories

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.

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$$.
• 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. – varkor Jun 6 at 14:24
• 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. – varkor Jun 6 at 14:26
• 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. – varkor Jun 6 at 14:47
• @Enrico: $\top$ and $\bot$ stand for "true" and "false" respectively (see, for instance, the Wikipedia page for truth values). – varkor Nov 2 at 20:02