# Notes (CTFP 01/31): Category

# 1 Category: The Essence of Composition

**category**: A structure consisting of objects and arrows between objects, such that arrows compose. That is, if a category has objects `A`

, `B`

and `C`

along with arrows `A -> B`

, `B -> C`

, then it also has the arrow `A -> C`

.

## 1.1 Arrows as Functions.

Arrows are also called morphisms, which comes from the Greek “morphe” meaning form.

Notation:

`.`

is composition,`(g . f)(x) = g(f(x))`

`::`

is type of, like`f :: Integer`

`->`

is an arrow,`f :: A -> B`

means`f`

is a morphism from`A`

to`B`

## 1.2 Properties of Composition

Composition of arrows is associative, so that

`h . (g . f) = (h . g) . f = h . g . f`

This makes sense with the definition of a category. Suppose a category contains objects

`A, B, C, D`

and arrows:`f :: A -> B g :: B -> C h :: C -> D`

Then by definition it contains:

`(f . g) :: A -> C (h . g) :: B -> D (h . g . f) :: A -> D`

Associativity just means that it doesn’t matter what order we compose arrows:

`h . (g . f) == (h . g) . f == h . g . f`

There is an identity arrow

`A -> A`

for every object`A`

, such that`f :: A -> B g :: B -> A id_a :: A -> A f . id_a = f id_a . g = g`

One thing that confuses me is that it seems like this implies that in some cases that there can’t be multiple arrows from one object to another.

Suppose a category `Cat`

has objects `A`

, `B`

and arrows

```
f' :: A -> B
f :: A -> B
g :: B -> A
id_a :: A -> A
id_b :: B -> B
```

If `Cat`

is a category, then the compositions of `g . f`

and `g . f'`

must be arrows in the category:

```
g . f :: A -> A
g . f' :: A -> A
```

But the only arrow of type `A -> A`

is `id_a`

, so

`g . f = g . f' = id_a`

And equivalently:

`f . g = f' . g = id_b`

Which implies:

`f' = f' . id_a = f' . g . f = id_b . f = f`

So, either `Cat`

is not a category, or `f' == f.`

cf. Haskell Wikibook page on Category Theory

I think the important thing to keep in mind here is that when looking at a possible structure to see if its a category, the structure is constant. There aren’t any implicit elements of `Cat`

that could also satisfy the property that e.g `(g . f)`

is in `Cat`

. We actually have to look in `Cat`

to find if something fits the properties. If not, it’s not a category.

When I first approached this topic I confused the statements:

- For any arrows
`g`

and`f`

in a category`C`

, their composition`(g . f)`

must also be an arrow in`C`

. (**Right**) - If arrows
`g`

and`f`

are arrows in`C`

, add a new arrow`(g . f)`

to`C`

. (**Wrong**)

This really confused me for a bit, until I realized that when I was doing the latter I was just trying to build a superset of `C`

that actually was a category. This is apparently called a “free category”.

## 1. 4 Challenges

`I = (\x. x)`

in the lambda calculus.`compose = (\x y z. x (y z))`

`compose I F X = (\x y z. x (y z)) I F X = I (F X) = F X`

`compose F I X = (\x y z. x (y z)) F I X = F (I X) = F X`

- No, links are not composable.
- Friendships are not composable.
When the edges are composable, and every node has a self-directed edge.