FS

Thursday, July 05, 2007

Basic Catagory Theory for Computer Scientists

I'm not in grad school anymore (which is a story!), so now I have to practice on my own time to keep my academic knife sharp.

To that end I'm working through Pierce's Basic Category Theory for Computer Scientists. So far, category theory isn't hard conceptually - but the concepts are so abstract that I find it difficult to internalize them. But then, it's not like I spent a lot of time in the math dept. back when I was in school (as much as I liked the mathematical tools I used).

Although I shouldn't be going on about how "not hard" it is while I'm still in chapter one.

Onward!

1.3.10 Exercises

2 Show that in any category, if two arrows f and g are both monic then their composition (g . f) is monic. Also, if (g . f) is monic then so is f.

The first part:
• Let (g . f) . a = (g. f) . b
• -> g . (f . a) = g . (f . b)
• Because g is monic -> f . a = f . b
• Because f is monic -> a = b
Therefore (g . f) is monic

The second part:

Suppose that (g . f) is monic.
Let's further suppose that there exists two arrows a and b such that:

f . a = f . b, a \= b

• g . (f . a) = g . (f . b), a \=b, via arrow composition
• (g . f) . a = (g . f) . b, a\=b, via associativity of composition
Which violates my first assumption. Therefore: If (g . f) is monic, for all pairs of arrows a and b such (f . a) = (f . b), a = b. Therefore f is monic.

3 Dualize the previous exercise: state and prove the analogous proposition for epics.

Along the same lines as the previous proof:
1. Let (g . f) be epic.
2. Let there exist two arrows a and b such that a . g = b . g and a \= b.
(a . g) . f = (b . g) . f, a \=b via composition of arrows
a . (g . f) = b . (g . f), a \= b via associativity of composition

My assumptions are in contradiction. Therefore, if (g . f) is epic, there exist no two arrows a and b such that a . g = b . g and a \=b - that is, g is epic.

More to come. Let me know if my math is crap.