The n-Category Café

This different viewpoint comes from the observation that in the category of sets, the injections are precisely the coproduct inclusions (coprojections)

$$A \to A + B.$$

Certainly every coproduct inclusion in the category of sets is injective. And conversely, any injection is a coproduct inclusion, because every subset of a set has a complement.

So, the injections between sets are the specialization to $\mathbf{Set}$ of the general categorical concept of coproduct coprojection. The dual of that general categorical concept is product projection. Hence one can reasonably say that the dual concept of injection is that of product projection

$$A \times B \to A,$$

where $A$ and $B$ are sets.

Which maps of sets are product projections? It’s not hard to show that they’re exactly the functions $f: X \to Y$ whose fibres are all isomorphic:

$$f^{-1}(y) \cong f^{-1}(y')$$

for all $y, y' \in Y$. You could reasonably call these “uniform” maps, or “even coverings”, or maybe there’s some other good name, but in this post I’ll just call them projections (with the slightly guilty feeling that this is already an overworked term).

Projections are always surjections, except in the trivial case where the fibres are all empty, which means that our map is of the form $\varnothing \to Y$. On the other hand, most surjections aren’t projections. A surjection is a function whose fibres are nonempty, but there’s no guarantee that all the fibres will be isomorphic, and usually they’re not.

A projection appears in a little puzzle I heard somewhere. Suppose someone hands you a tangle of string, a great knotted mass with who knows how many bits of string all jumbled together. How do you count the number of pieces of string?

The slow way is to untangle everything, separate the strands, then count them. But the fast way is to simply count the ends of the pieces of string, then divide by two. The point is that there’s a projection — specifically, a two-to-one map — from the set of ends to the set of pieces of string.

String theory aside, does this alternative viewpoint on the dual concept of injection have any importance? I think it does, at least a little. Let me give two illustrations.

Factorization, graphs and cographs

It’s a standard fact that any function between sets can be factorized as a surjection followed by an injection, and the same is true in many other familiar categories. But here are two other methods of factorization, dual to one another, that also work in many familiar categories. One involves injections, and the other projections.

• In any category with finite coproducts, any map $f: X \to Y$ factors as

  $$X \to X + Y \stackrel{\binom{f}{1}}{\to} Y,$$

  where the first map is the coproduct coprojection. This is a canonical factorization of $f$ as a coproduct coprojection followed by a (canonically) split epic. In $\mathbf{Set}$, it’s a canonical factorization of a function $f$ as an injection followed by a surjection (or “split surjection”, if you don’t want to assume the axiom of choice).

  Unlike the usual factorization involving a surjection followed by an injection, this one isn’t unique: there are many ways to factor $f$ as an injection followed a surjection. But it is canonical.

• In any category with finite products, any map $f: X \to Y$ factors as

  $$X \stackrel{(1, f)}{\to} X \times Y \to Y,$$

  where the second map is the product projection. This is a canonical factorization of $f$ as a split monic followed by a projection. In $\mathbf{Set}$, “split monic” just means a function with a retraction, or concretely, an injection with the property that if the domain is empty then so is the codomain.

  (I understand that in some circles, this or a similar statement is called the “fundamental theorem of reversible computing”. This seems like quite a grand name, but I don’t know the context.)

  Again, even in $\mathbf{Set}$, this factorization is not unique: most functions can be factored as a split monic followed by a projection in multiple ways. But again, it is canonical.

These factorizations have a role in basic set theory. Let’s consider the second one first.

Take a function $f: X \to Y$. The resulting function

$$(1, f): X \to X \times Y$$

is injective, which means it represents a subset of $X \times Y$, called the graph of $f$. A subset of $X \times Y$ is also called a relation between $X$ and $Y$; so the graph of $f$ is a relation between $X$ and $Y$.

The second factorization shows that $f$ can be recovered from its graph, by composing with the projection $X \times Y \to Y$. Thus, the set of functions from $X$ to $Y$ embeds into the set of relations between $X$ and $Y$. Which relations between $X$ and $Y$ correspond to functions? The answer is well-known: it’s the set of relations that are “functional”, meaning that each element of $X$ is related to exactly one element of $Y$.

This correspondence between functions and their graphs is very important for many reasons, which I won’t go into here. But it has a much less well known dual, which involves the first factorization.

Here I have to take a bit of a run-up. The injections into a set $S$, taken up to isomorphism over $S$, correspond to the subsets of $S$. Dually, the surjections out of $S$, taken up to isomorphism under $S$, correspond to the equivalence relations on $S$. (This is more or less the first isomorphism theorem for sets.) And just as we define a relation between sets $X$ and $Y$ to be a subset of $X \times Y$, it’s good to define a corelation between $X$ and $Y$ to be an equivalence relation on $X + Y$.

Now, given a function $X \to Y$, the resulting function

$$\binom{f}{1}: X + Y \to Y$$

is surjective, and so represents an equivalence relation on $X + Y$. This equivalence relation on $X + Y$ is called the cograph of $f$, and is a corelation between $X$ and $Y$.

The first of the two factorizations above shows that $f$ can be recovered from its cograph, by composing with the injection $X \to X + Y$. Thus, the set of functions from $X$ to $Y$ embeds into the set of corelations between $X$ and $Y$. Which corelations between $X$ and $Y$ correspond to functions? This isn’t so well known, but — recalling that a corelation between $X$ and $Y$ is an equivalence relation on $X + Y$ — you can show that it’s the corelations with the property that every equivalence class contains exactly one element of $Y$.

I’ve digressed enough already, but I can’t resist adding that the dual graph/cograph approaches correspond to the two standard types of picture that we draw when talking about functions: graphs on the left, and cographs on the right.

        

For example, cographs are discussed in Lawvere and Rosebrugh’s book Sets for Mathematics.

Back to the injection-projection duality! I said I’d give two illustrations of the role it plays. That was the first one: the canonical factorization of a map as an injection followed by a split epic or a split monic followed by a projection. Here’s the second.

Free and cofree presheaves

Let $A$ be a small category. If you’re given a set $P(a)$ for each object $a$ of $A$ then this does not, by itself, constitute a functor $A \to \mathbf{Set}$. A functor has to be defined on maps too. But $P$ does generate a functor $A \to \mathbf{Set}$. In fact, it generates two of them, in two dual universal ways.

More exactly, we’re starting with a family $(P(a))_{a \in A}$ of sets, which is in object of the category $\mathbf{Set}^{ob\ A}$. There’s a forgetful functor

$$\mathbf{Set}^A \to \mathbf{Set}^{ob\ A},$$

and the general lore of Kan extensions tells us that it has both a left adjoint $L$ and a right adjoint $R$. Better still, it provides explicit formulas: the functors $L(P), R(P): A \to \mathbf{Set}$ are given by

$$(L(P))(a) = \sum_b A(b, a) \times P(b)$$

(where $\sum$ means coproduct or disjoint union), and

$$(R(P))(a) = \prod_b P(b)^{A(a, b)}.$$

I’ll call $L(P)$ the free functor on $P$, and $R(P)$ the cofree functor on $P$.

Example   Let $G$ be a group, seen as a one-object category. Then we’re looking at the forgetful functor $\mathbf{Set}^G \to \mathbf{Set}$ from $G$-sets to sets, which has both adjoints.

The left adjoint $L$ sends a set $P$ to $G \times P$ with the obvious $G$-action, which is indeed usually called the free $G$-set on $P$.

The right adjoint $R$ sends a set $P$ to the set $P^G$ with its canonical action: acting on a family $(p_g)_{g \in G} \in P^G$ by an element $u \in G$ produces the family $(p_{g u})_{g \in G}$. This is a cofree $G$-set.

Cofree group actions are important in some parts of the theory of dynamical systems, where $G$ is often the additive group $\mathbb{Z}$. A $\mathbb{Z}$-set is a set equipped with an automorphism. The cofree $\mathbb{Z}$-set on a set $P$ is the set $R(P) = P^{\mathbb{Z}}$ of double sequences of elements of the “alphabet” $P$, where the automorphism shifts a sequence along by one. This is called the full shift on $P$, and it’s a fundamental object in symbolic dynamics.

What’s this got to do with the injection-projection duality? The next example gives a strong clue.

Example   Let $A$ be the category $(0 \to 1)$ consisting of a single nontrivial map. Then an object of $\mathbf{Set}^{ob\ A}$ is a pair $(P_0, P_1)$ of sets, and an object of $\mathbf{Set}^A$ is a function $X_0 \stackrel{f}{\to} X_1$ between a pair of sets.

The free functor $A \to \mathbf{Set}$ on $P$ is the injection

$$A \to A + B.$$

The cofree functor $A \to \mathbf{Set}$ on $P$ is the projection

$$A \times B \to B.$$

More generally, it’s a pleasant exercise to prove:

• Any free functor $X: A \to \mathbf{Set}$ preserves monics. In other words, if $u$ is a monic in $A$ then $X(u)$ is an injection.

• Any cofree functor $X: A \to \mathbf{Set}$ sends epics to projections. In other words, if $u$ is an epic in $A$ then $X(u)$ is a projection.

These necessary conditions for being a free or cofree functor aren’t sufficient. (If you want a counterexample, think about group actions.) But they give you some feel for what free and cofree functors are like.

For instance, if $A$ is the free category on a directed graph, then every map in $A$ is both monic and epic. So when $X: A \to \mathbf{Set}$ is free, the functions $X(u)$ are all injections, for every map $u$ in $A$. When $X$ is cofree, they’re all projections. This imposes a severe restriction on which functors can be free or cofree.

(Question: do quiver representation people ever look at cofree representations? Here we’d replace $\mathbf{Set}$ by $\mathbf{Vect}$.)

In another post, I’ll explain why I’ve been thinking about this.