Type Slowly

Epic win: why surjective Set-functions are Epimorphisms.

I’ve been (slowly) working my way through Benjamin Pierce’s Basic Category Theory for Computer Scientists recently, with the imediate aim of understanding enough category theory to get to grips with David Spivak’s Simplical Databases paper, as well as for my general edification. It’s a really good, clear introduction to the subject, and is structured in such a way that it’s possible to pick it up for fifteen minutes and get to grips with a single concept (defined, explained and proved in a few paragraphs) at a time. However, I came a bit unstuck when I got to the assertion that the Epimorphic arrows in Set are the surjective total functions. It’s actually very simple to prove this, using the same reductio ad absurdum strategy as Pierce uses to prove that the Monomorphic Set-arrows are the injective total functions, however the proof is left out of the book:

By definition, an arrow $ f: A \longmapsto B $ is Epimorphic if, for any pair of arrows $ g:B \longmapsto C $ and $ h: B \longmapsto C $: $ g \circ f = h \circ f $ implies that $ g = h $:

$$ \exists f: \forall g, h: g \circ f = h \circ f \Longrightarrow g = h $$

So, let’s assume the opposite. Let $ f: A \longmapsto B $ be a surjective function, but let g and h be functions $ g: B \longmapsto C $ and $ h: B \longmapsto C $, such that $ g \circ f = h \circ f $ but $ g \neq h $:

$$ \exists f: \forall g, h: g \circ f = h \circ f \Longrightarrow g \neq h $$

What the last clause here stipulates is:

$$ \exists b \in B: g(b) \neq h(b) $$

Now, by the definition of surjectivity, there must be an element of A that f maps to this b, because f completely covers its codomain:

$$ \exists a \in A: f(a) = b $$

Putting these two together, we have the following:

$$ \exists a \in A: g(f(a)) \neq h(f(a)) $$

or alternatively:

$$ \exists a \in A: g \circ f(a) \neq h \circ f(a) $$

…which directly contradicts our original implication:

$$ \exists f: \forall g, h: g \circ f = h \circ f \Longrightarrow g \neq h $$

… Therefore, the surjective functions must form the Epimorphisms within Set!