Categories Great and Small

Bartosz Milewski · 2014 · Category Theory for Programmers, Ch. 3

Prereqs: 🍞 Chapter 1 (Category). 5 min.

Orders and monoids are both categories in disguise. A preorder is a category where each hom-set has at most one morphism. A monoid is a category with exactly one object. Recognizing this collapses two chapters of abstract algebra into two sentences of category theory.

Small categories — finite objects, finite arrows

A small category has a set (not a proper class) of objects. The simplest is the empty category: no objects, no morphisms. Next up: a single object with its identity morphism. Then categories with a handful of objects and arrows between them, as long as they close under composition and every object has an identity.

Scheme

; The smallest categories
; 0: empty category — no objects, no morphisms
; 1: one object, one morphism (identity)
; 2: two objects, an arrow between them (plus identities)

; We can represent a finite category as
; (objects, morphisms, compose, id)

(define (make-cat objects morphisms compose id)
  (list objects morphisms compose id))

; Category with one object and one morphism (identity)
(define one
  (make-cat '(A)
            '((A A))          ; id_A
            (lambda (f g) f)  ; id . id = id
            (lambda (x) (list x x))))

(display "Objects: ") (display (car one)) (newline)
(display "Morphisms: ") (display (cadr one)) (newline)
; One object, one arrow. That's a valid category.

Free categories — from graphs to categories

Start with a directed graph. Add an identity arrow at every node. Then close under composition: for every path A→B→C, add a composite arrow A→C. Keep going until no new arrows appear. The result is the free category generated by that graph. A graph with one node and one edge produces infinitely many morphisms: the edge, the edge composed with itself, and so on.

Scheme

; Free category from a graph
; Graph: one node, one edge (a loop)
; Free category: id, e, e.e, e.e.e, ...

(define (free-category-arrows edge n)
  ; Generate the first n arrows of the free category
  (let loop ((i 0) (arrows '()))
    (if (> i n) (reverse arrows)
        (loop (+ i 1)
              (cons (make-string i (string-ref edge 0))
                    arrows)))))

(define arrows (free-category-arrows "e" 5))
(display "Arrows: ") (newline)
(for-each (lambda (a)
  (display "  ")
  (display (if (= (string-length a) 0) "id" a))
  (newline))
  arrows)

; Composition is concatenation. id is empty string.
(display "compose(ee, eee) = ")
(display (string-append "ee" "eee"))
; 5 edges composed — still an arrow in the free category.

Orders — thin categories

An ordered set is a category where the morphism a→b means "a ≤ b." Reflexivity gives you identity. Transitivity gives you composition. A category where every hom-set has at most one morphism is called thin. Three flavors:

Preorder: reflexive + transitive. That's it. A thin category.
Partial order: preorder + antisymmetric (a ≤ b and b ≤ a implies a = b). No loops.
Total order: partial order where every pair is comparable.

Scheme

; Integers with <= form a total order (thin category)
; Morphism from a to b exists iff a <= b

(define (hom-set a b)
  ; Returns the morphism if it exists, or empty
  (if (<= a b)
      (list (list '<= a b))
      '()))

; Check category axioms:

; 1. Identity: a <= a (reflexivity)
(display "id(3): ") (display (hom-set 3 3)) (newline)

; 2. Composition: a<=b and b<=c implies a<=c (transitivity)
(display "2<=5: ") (display (hom-set 2 5)) (newline)
(display "5<=8: ") (display (hom-set 5 8)) (newline)
(display "2<=8: ") (display (hom-set 2 8)) (newline)

; 3. Thin: at most one morphism per pair
(display "5<=3: ") (display (hom-set 5 3)) (newline)
; Empty — no morphism from 5 to 3.

; Total: every pair is comparable
(define (comparable? a b)
  (or (not (null? (hom-set a b)))
      (not (null? (hom-set b a)))))
(display "3 and 7 comparable? ") (display (comparable? 3 7))

Monoid as a single-object category

A monoid is a set with an associative binary operation and an identity element. String concatenation with the empty string. Addition with zero. The categorical perspective: a monoid is a category with exactly one object. The elements of the monoid become morphisms. The binary operation becomes composition. The identity element becomes the identity morphism. The hom-set M(m, m) is the monoid.

Scheme

; String monoid as a single-object category
; One object: * (the "star")
; Morphisms: strings (elements of the monoid)
; Composition: string concatenation
; Identity: "" (empty string)

(define (monoid-compose f g)
  (string-append f g))

(define monoid-id "")

; Check category axioms:

; 1. Identity law: id . f = f = f . id
(define f "hello")
(display "id . f = ") (display (monoid-compose monoid-id f)) (newline)
(display "f . id = ") (display (monoid-compose f monoid-id)) (newline)

; 2. Associativity: (f . g) . h = f . (g . h)
(define g " world")
(define h "!")
(display "(f.g).h = ")
(display (monoid-compose (monoid-compose f g) h)) (newline)
(display "f.(g.h) = ")
(display (monoid-compose f (monoid-compose g h))) (newline)

; Every string is a morphism from * to *.
; The hom-set M(*,*) = all strings = the monoid itself.

Hom-sets

The set of all morphisms from object a to object b is the hom-set C(a, b). In a thin category (preorder), every hom-set is either empty or a singleton. In a monoid-as-category, there's only one hom-set: M(m, m), and it contains every element of the monoid. A category is locally small if every hom-set is a set (not a proper class).

Scheme

; Hom-sets in different categories

; 1. Thin category (preorder on {1,2,3} with <=)
(define (thin-hom a b)
  (if (<= a b) (list '<=) '()))

(display "Hom(1,3) in preorder: ") (display (thin-hom 1 3)) (newline)
(display "Hom(3,1) in preorder: ") (display (thin-hom 3 1)) (newline)
; At most one morphism — thin.

; 2. Monoid (integers under +, identity = 0)
; Single object, so only one hom-set: M(m,m)
; It contains all integers — the monoid elements.
(define int-monoid-hom '(0 1 2 3 -1 -2 "..."))
(display "Hom(m,m) in Z-monoid: ") (display int-monoid-hom) (newline)

; Composition in the integer monoid is addition:
(display "compose(3, 5) = ") (display (+ 3 5)) (newline)
(display "compose(x, 0) = x: ") (display (+ 7 0)) (newline)
; Identity is 0. Associativity is just (a+b)+c = a+(b+c).

Notation reference

Book	Scheme	Meaning
C(a, b)	(hom-set a b)	Set of morphisms from a to b
\|C(a, b)\| ≤ 1	(thin-hom a b)	Thin category (preorder)
a ≤ b	(<= a b)	Morphism exists in the order-category
m ⊕ n	(monoid-compose f g)	Monoid operation = composition
e	monoid-id	Identity element = identity morphism
Free(G)	(free-category-arrows ...)	Free category generated by graph G

Neighbors

Milewski chapters

🍞 Chapter 1 — Category: the essence of composition
Chapter 4 — Kleisli categories (next)

🍞 Leinster 2021 — entropy as a functor on finite probability spaces
🍞 Spivak 2013 — categories for the working scientist
🔗 Judson Ch.1 Groups — groups are one-object categories where every morphism is invertible

Foundations (Wikipedia)

Translation notes

Milewski covers the Haskell Monoid typeclass (mempty, mappend) and the distinction between point-free and pointwise equality. Here we show the same ideas in Scheme (functions and strings) and Python. The free monoid on an alphabet is the set of all strings over that alphabet with concatenation. Haskell's String type with (++) is exactly this free monoid. The categorical perspective on monoids (single-object category) is what makes them composable with everything else in category theory.

Ready for the real thing? Read the original. Start with "Orders" for thin categories, then "Monoid as Category" for the punchline.

← Types and Functions by june.kim Kleisli Categories →