# Notes (CTFP 03/31): Categories Great and Small

# 3 Categories Great and Small

## 3.1 No objects

The empty category!

## 3.2 Simple Graphs

**free category**: A category generated by a directed graph by turning nodes into objects, edges into arrows and adding new edges for every composition of arrows.

Okay so generating free categories is what I was doing in chapter 2 that was confusing me. Subtle!

## 3.3 Orders

**preorder**: If a set `P`

has a binary relation `pre :: P -> P -> Bool`

such that for all

```
x :: P, y :: P, z :: P
pre x x = True -- reflexive
pre x y && pre y z => pre x z -- transitive
```

Then `pre`

is a preorder.

**partial order**: If a set `P`

has a binary relation `part :: P -> P -> Bool`

such that for all

```
x :: P, y :: P
part x y = pre x y -- part is a preorder
part x y && part y x => x == y -- antisymmetric
```

then `part`

is a partial order

**total order**: If a set `P`

has a binary relation `tot :: P -> P -> Bool`

, such that for all

```
x :: P, y :: P
tot x y = part x y -- tot is a partial order
tot x y || tot y x = True -- total (defined for all P)
```

then `tot`

is a total order.`

**thin category**: A category where between any two objects `X`

and `Y`

there is at most one arrow `X -> Y`

from `X`

to `Y`

.

**hom-set**: The set of arrows from an object `X`

to an object `Y`

.

`hom-set :: Category -> Object -> Object -> {Arrow}`

I don’t really like the name “hom-set”. I get that “hom” stands for “homomorphism”, but I hate using apocope (eliding syllables from the ends of words) to generate new terms. It’s slangy, offloads important “info” onto implicit context, sounds ugly and confuses me. Hate it.

I’ve read that some books use “morphisms” as a way to describe “hom-set”. That’s a lot better, but still not perfect…

I kind of like thinking about the set of morphisms from `X`

to `Y`

as the “volley” of arrows from `X`

to `Y`

. I especially like that “volley” comes from Latin “volare: to fly”. And that’s really what we’re after, which arrows “fly” from `X`

to `Y`

:

`volley :: Category -> Object -> Object -> {Arrow}`

We’ll also need term for all the arrow in a whole category, not just between two ojects:

`vol :: Category -> {Arrow}`

Okay, it’s another apocope, but this is actually a meaningful one. “Vol” is a French word meaning “flight”. And we can think of all the arrows in a category as being like a “flock” or a “flight” of arrows.

I’ve also read that the vol (hom-set) of a category is not necessarily a set. So I think the term “hom-set” really fails utterly in all parts for clearly conveying the concept.

I’m going to use my own made-up “vol”, “volley” terminology, mostly because I think it’s pretty. I’ll try to include definitions whenever I stray to far from this context:

```
volley C a b = hom-set_C(a, b)
vol C = all morphisms of C
```

[TODO: Extend archery terminology to other category theory concepts]

## 3.4 Monoid as Set

**monoid** A set `M`

with a binary operation

`mappend :: M -> M -> M`

and an element `

`mempty :: M`

such that for all

```
a :: M, b :: M, c :: M
mappend (mappend a b) c = mappend a (mappend b c) -- associative
mappend mempty a = mappend a mempty = a -- identity element
```

Addition of integers is a monoid:

```
(a + b) + c = a + (b + c)
0 + a = a + 0 = a
```

So is multiplication of integers:

```
(a * b) * c = a * (b * c)
1 * a = a * 1 = a
```

## 3.5 Monoid as Category

Treat `M`

as an object, rather than a set. We can convert all elements of `M`

into arrows:

The identity element turns into the identity arrow:

`mappend a mempty = mappend mempty a = id_M a = a id_M = a -- identity arrow`

And every element `x`

of `M`

turns into:

`mappend x :: M -> M`

where composition of arrows becomes:

`(mappend x1) . (mappend x2) = (mappend (mappend x1 x2)) :: M -> M`

E.g, if the monoid is addition of integers:

`(+ 2) . (+ 3) = (+ (2 + 3)) = (+ 5)`

And since `mappend`

is associative, so is composition

```
(mappend x1) . (mappend x2) . (mappend x3)
= ((mappend x1) . (mappend x2)) . (mappend x3)
= (mappend (mappend x1 x2)) . (mappend x3)
= mappend (mappend (mappend x1 x2) x3)
= mappend (mappend x1 (mappend x2 x3))
= (mappend x1) . (mappend (mappend x2 x3))
= (mappend x1) . ((mappend x2) . (mappend x3))
```

E.g. with the integer addition monoid:

```
(+2) . (+3) . (+4) = ((+5) . (+4)) = (+9)
= ((+2) . (+7)) = (+9)
```

And thus we’ve turned `M`

into a category!

And we can just as easily turn `M`

back into a set by taking the set of arrow with `vol :: Category -> {Arrow}`

, (hom-set).

## 3.6 Challenges

Graph

`G`

with node`A`

and no edges. Adding`id_a :: A -> A`

Gives a category.

This is a category

Graph

`G`

with nodes`A`

,`B`

and edge`A -> B`

. Adding`id_A :: A -> A id_B :: B -> B`

Gives a category.

Let the single node be the object

`String`

. from each edge generate prepender and appender arrows for each letter, so the`'a'`

edge becomes`(++ "a")`

and`("a" ++)`

. Then add an empty string (++ "") arrow, which is the identity. Then add arrows for the compositions of all arrows. And now we have the`String`

monoid category.

Inclusion is

reflexive, since by definition all elements of

`A`

are in`A`

transitive, since if

`A`

is in`B`

all elements of`A`

are also in`B`

antisymmetric, since if

`A`

is in`B`

and`B`

is in`A`

. there are no elements that they do not share, so all their elements are the same, and thus`A == B`

not necessarily total from the information given. If the set of sets is the set of sets of integers, for example, then

`{1}, {2}`

are both in the set, but`{2}`

is not in`{1}`

and`{1}`

is not in`{2}`

.But if the set of sets is, e.g. the set of the empty set

`{{}}`

, then the inclusion relation could be total. So this is actually an interesting question:I think we can define this recursively: a set with total order is either the empty set or a set of sets with total order:

`T-Set = {} | Set T`

But then the question is how complicated does this set get? Because all the Von Neumann ordinals:

`0 = {} 1 = {0} = {{}} 2 = {1} = {{{}}} ...`

are in

`T-set`

.Oh, actually, this doesn’t work, because the inclusion relation the question only goes one level deep, I think.

`A,B,C,D`

are not elements of`{{A, B}, {C, D}}`

, so`0`

is not in`2`

with Von Neumann encoding.But if we changed our inclusion relation to:

`A`

is in`B`

if all the elements of`A`

are*included*in elements of`B`

.Then I think we get the

`T-Set`

above for all the sets with total order.But I’m at the limits of my set theory here. I think I’ll add a book to my reading list and come back to this.

[TODO. Do a workthrough on set theory]

Skipping. Don’t care about

`C++`

And-Monoid:

`mempty = True mappend = (&&) x && True = x True && x = x (x && y) && z = z && (y && z)`

Or-Monoid:

`mempty = False mappend = (||) x || False = x False || x = x (x || y) || z = z || (y || z)`

Bool Monoid Category, has object bool and arrows:

`andTrue :: Bool -> Bool -- identity andFalse :: Bool -> Bool -- always returns false andFalse . andFalse = andFalse`

And is commutative, so thats all there is.

Addition Mod 3, has object Int3 and arrows:

`(+ 0) :: Int3 -> Int3 -- identity (+ 1) :: Int3 -> Int3 (+ 2) :: Int3 -> Int3 (+ 1) . (+ 2) = (+ 2) . (+ 1) = (+ 0) (+ 1) . (+ 1) = (+ 2) (+ 2) . (+ 2) = (+ 1)`