Injective Representables

Posted on 7 April 2011 by Nicolas Wu
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 \(\forall f, g \cdot h . f = h . g \Rightarrow f = g\)

Surjectivity can be described in similar terms, where a function is surjective when it is right cancellative:

\(h\) is surjective iff \(\forall f, g \cdot f . h = g . h \Rightarrow 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 \(\forall y \cdot \exists x \cdot 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.

Representables

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\).

Covariant Representable

Given a function \(h : X \rightarrow Y\), the covariant representable, \(ℂ(S,-)\) is defined as:

ℂ(S,—) :: (X -> Y) -> ℂ(S, X) -> ℂ(S, Y)
ℂ(S,—) h f = h . f

As shorthand for the above, we usually slot the argument \(h\) into the dash:

ℂ(S, h) = ℂ(S,—) h

Contravariant Representable

Given a function \(h : X \rightarrow Y\), the contravariant representable, \(ℂ(-,T)\) is defined as:

ℂ(—,T) :: (X -> Y) -> ℂ(X, T) -> ℂ(Y, T)
ℂ(—,T) h f = f . h

Again, we use the following shorthand, where we slot \(h\) into the dash:

ℂ(h, T) = ℂ(—,T) h

One feature of these representables that I like particularly is that they give rise to a clean correspondence between injectivity and surjectivity.

Injectivity

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.

Proof

First we show that if \(h\) is injective then \(ℂ(S, h)\) is injective:

ℂ(S, h) f == ℂ(S, h) g
  == {- definition ℂ(S, h) -}
h . f == h . g
  => {- injective h -}
f == g

Then we show that if \(ℂ(S, h)\) is injective then \(h\) is injective:

h . f == h . g
  == {- definition ℂ(S, h) -}
ℂ(S, h) f == ℂ(S, h) g
  => {- injective ℂ(S, h) -}
f == g

Injective Contravariant Reperesentable

Here’s a property of the contravariant representable functor:

\(ℂ(h, S)\) is injective iff \(h\) is surjective.

Proof

We work with the contrapositive to show that if \(h\) is surjective, then \(ℂ(h, S)\) is injective:

f ≠ g
  == {- definition inequality -}
∃ y . f y ≠ g y
  == {- surjective h -}
∃ x . f (h x) ≠ g (h x)
  == {- definition inequality -}
f . h ≠ g . h
  == {- definition ℂ(h, S) -}
ℂ(h, S) f ≠ ℂ(h, S) g

Finally we show that if \(h\) is not surjective, then \(ℂ(h, S)\) is not injective:

let h 0 = 0 {- h : {0} -> {0,1} -}
let f 0 = 0, f 1 = 0
let g 0 = 0, g 1 = 1

then

f . h = g . h
  == {- definition ℂ(h, S) -}
ℂ(h, S) f = ℂ(h, S) g

but

 f ≠ g

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.

Comments