## 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*.

- Generating free categories from graphs.
- One node,
**v**, and no edges. There exists only one morphism,*1*_{v}, the identity morphism. - One node,
**v**, and one directed edge,*f*. There exists the following morphisms:*1*_{v},*f*,*f*∘*f*,*f*∘*f*∘*f*, … - A graph with two nodes,
**v**,**w**, and one edge*f*:**v**→**w**. There exists the following morphisms:*1*_{v},*f*,*1*_{w}. - A graph with one node,
**v**, and 26 edges,*a*,*b*, …,*z*. There exists the following morphisms:*1*_{v},*a*,*aa*,*aardvark*, …,*zyzzyvas*,*zzzzzzzzz*, …

- One node,
- Describe the order.
- 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*. - I’m guessing this is also a partial order since types are like sets. You can have subtypes that in disjoint subtype trees.

- A set of sets with inclusion as the relation. For this to be a total
order, for any two sets
- (
`Bool`

,*AND*) is a monoid with`true`

as identity. (`Bool`

,*OR*) is a monoid with`false`

as identity. - (
`Bool`

,*AND*) as a category has two morphisms:*1*_{Bool}=*t*:`b`

↦`b`

*AND*`true`

,*f*:`b`

↦`b`

*AND*`false`

. Any compositions just get us back to those:*t*∘*f*=*f*∘*t*=*f*∘*f*=*f*,*t*∘*t*=*t*=*1*_{Bool}.

- (ℤ/3ℤ, +) has morphisms (+
`0`

) =*1*_{ℤ/3ℤ}, (+`1`

), and (+`2`

) = (+`1`

) ∘ (+`1`

). There are no more morphisms as (+`2`

) ∘ (+`1`

) = (+`0`

).