Category Theory for Programmers Chapter 3: Categories Great and Small

The notion of orders is introduced here and it’s not totally clear from the text what their definitions entail or what they’re actually trying to convey if you don’t already know what preorders, partial orders, and total orders are. Preorders are pretty straight forward and there isn’t much to add. This mostly just states things are related to themselves and that the transitivity of the relation holds.

Partial orders add antisymmetry by stating if a is related to b and b is related to a, then a is b. This makes cycles impossible.

Lastly, total orders have the connex relation which means for any two elements, they can be related in some way, either a is related to b or b is related to a.

  1. Generating free categories from graphs.
    1. One node, v, and no edges. There exists only one morphism, 1v, the identity morphism.
    2. One node, v, and one directed edge, f. There exists the following morphisms: 1v, f, f ∘ f, f ∘ f ∘ f, …
    3. A graph with two nodes, v, w, and one edge f:v → w. There exists the following morphisms: 1v, f, 1w.
    4. A graph with one node, v, and 26 edges, a, b, …, z. There exists the following morphisms: 1v, a, aa, aardvark, …, zyzzyvas, zzzzzzzzz, …
  2. Describe the order.
    1. A set of sets with inclusion as the relation. For this to be a total order, for any two sets A and B, either A ⊂ B or B ⊂ A. But without extra information, it’s possible for neither to hold, ie, discrete sets {a} and {b}. So it’s a partial order.
    2. I’m guessing this is also a partial order since types are like sets. You can have subtypes that in disjoint subtype trees.
  3. (Bool, AND) is a monoid with true as identity. (Bool, OR) is a monoid with false as identity.
  4. (Bool, AND) as a category has two morphisms:
    1. 1Bool = t:b↦b AND true,
    2. f: b ↦ b AND false. Any compositions just get us back to those:
    3. t ∘ f = f ∘ t = f ∘ f = f,
    4. t ∘ t = t = 1Bool.
  5. (ℤ/3ℤ, +) has morphisms (+ 0) = 1ℤ/3ℤ, (+ 1), and (+ 2) = (+ 1) ∘ (+ 1). There are no more morphisms as (+ 2) ∘ (+ 1) = (+ 0).