by Nicolas Wu
Posted on 7 April 2011
Tags: Category Theory
In this article I’ll show how the injective and surjective properties of a function have a nice relationship with the injectivity of the corresponding representable functors, and how the right cancellative definition of surjection can be derived from the standard one. This is a fairly trivial discussion about a simple observation, so don’t expect anything spectacular.
The definition of injectivity is usually given in the following terms, where a function is injective when it is left cancellative:
h is injective iff ∀f, g ⋅ h.f = h.g ⇒ f = g
Surjectivity can be described in similar terms, where a function is surjective when it is right cancellative:
h is surjective iff ∀f, g ⋅ f.h = g.h ⇒ f = g
While these two definitions show the similarity between the injective and surjective properties, this definition of surjectivity isn’t the standard one. The standard definition goes as follows:
h is surjective iff ∀y ⋅ ∃x ⋅ h x = y
I don’t like this definition, since I don’t find it easy to work with in proofs, and it doesn’t show the relationship between surjections and injections well.
The representables, or Hom-functors, are functions from arrows to arrows in a category. These functions come in two flavours, the covariant representable, and the contravariant representable. Given objects S and T in a category ℂ, we write ℂ(S, T) denote the set of all arrows from S to T.
Given a function h : X → Y, the covariant representable, ℂ(S, − ) is defined as:
As shorthand for the above, we usually slot the argument h into the dash:
Given a function h : X → Y, the contravariant representable, ℂ(−,T) is defined as:
Again, we use the following shorthand, where we slot h into the dash:
One feature of these representables that I like particularly is that they give rise to a clean correspondence between injectivity and surjectivity.
The injective Representables give rise to a nice model for injective functions.
Injective Covariant Reperesentable
The following property holds of covariant representables:
ℂ(S, h) is injective iff h is injective.
First we show that if h is injective then ℂ(S, h) is injective:
Then we show that if ℂ(S, h) is injective then h is injective:
Injective Contravariant Reperesentable
Here’s a property of the contravariant representable functor:
ℂ(h, S) is injective iff h is surjective.
We work with the contrapositive to show that if h is surjective, then ℂ(h, S) is injective:
Finally we show that if h is not surjective, then ℂ(h, S) is not injective:
Sadly, I don’t like this part of the proof, since it involves finding a counterexample to the injectivity of ℂ(h, S) when h is not surjective, and I prefer constructive proofs. Nevertheless, we’ve shown that ℂ(h, S) is injective iff h is surjective, which gives us the right cancellative definition of surjection.