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

1. Graph G with node A and no edges. Adding
```
id_a :: A -> A
```
  Gives a category.
2. This is a category
3. Graph G with nodes A, B and edge A -> B. Adding
```
id_A :: A -> A
id_B :: B -> B
```
  Gives a category.
4. 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.
1. 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]
2. 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)