Algebra - 1

Last time, we stopped with the first isomorphism theorem for groups. In this entry, we will encounter some categorification of set-and-function stuff.

---

0 - Factorizations of Functions

Definition. We say a function $f: A \to B$ is factorized by $x: A \to C$, $y: C \to B$ if $y \circ x = f$. In this case we call $x$ the left factor, and $y$ the right factor (yes, I know the composition is written the other way around).

If $x$ is not injective, then $y \circ x$ cannot be injective. However, it is possible for $y$ to be non-injective and $y \circ x$ to still be injective: precisely when $y(c) = y(c')$ with $c \in \mathrm{Im}_x(A)$ and $c' \notin \mathrm{Im}_x(A)$.

Similarly, if $y$ is not surjective, $y \circ x$ cannot be surjective. However, it is possible for $x$ to be non-surjective, as long as $\mathrm{Im}_y(\mathrm{Im}_x(A)) = B$.

Thus, factorizations of injective and surjective maps may be represented by the diagrams below.

(We will use maps-to arrows for injections/monomorphisms, and double-arrow heads for surjections/epimorphisms.)

---

1 - Characterizing Injective and Surjective Maps

Theorem (Characterization of injective maps): The following statements are equivalent:

1. $f: A \to B$ is injective.
2. There exists $q: B \to A$ such that $q \circ f = \mathrm{id}_A$.
3. For any set $C$ and any maps $u, v: C \to A$, $f \circ u = f \circ v$ implies $u = v$. (This is the obvious candidate for categorification. Statement (2) seems fine too, but investigating this distinction is exactly what got me into this rabbit hole in the first place.)

Proof.

$(1 \Rightarrow 2)$ Suppose $f$ is injective. Define $q$ by sending any $b \in \mathrm{Im}_f(A)$ to the unique element of $f^{-1}(\{b\})$, and any $b \notin \mathrm{Im}_f(A)$ to an arbitrary fixed element of $A$. Then $q(f(a)) = a$, since $f(a) \in \mathrm{Im}_f(A)$ by definition.

$(2 \Rightarrow 1)$ Suppose $f$ has a left inverse $q$. Suppose $f(a) = f(a')$. Then $q(f(a)) = q(f(a'))$, therefore $a = a'$. Thus $f$ is injective.

$(1 \Rightarrow 3)$ Suppose $f$ is injective, and $f \circ u = f \circ v$. That is, for each $c \in C$, $f(u(c)) = f(v(c))$, so by injectivity $u(c) = v(c)$, i.e. $u = v$.

$(3 \Rightarrow 1)$ Suppose $f$ is such that for any $u, v: C \to A$, $f \circ u = f \circ v$ implies $u = v$. Suppose toward contradiction that $f$ is not injective, so there exist $a_1 \neq a_2 \in A$ with $f(a_1) = f(a_2)$.

Define $u: A \to A$ by $u(a) = \begin{cases} a & a \notin \{a_1, a_2\} \\ a_1 & a \in \{a_1, a_2\} \end{cases}$ and set $v = \mathrm{id}_A$.

Then $f \circ u = f$: for $a \notin \{a_1,a_2\}$, $f(u(a)) = f(a)$ trivially. And, $f(u(a_1)) = f(a_1)$, $f(u(a_2)) = f(a_1) = f(a_2)$ (using $f(a_1)=f(a_2)$). So $f \circ u = f = f \circ v$. But $u \neq v$, since $u(a_2) = a_1 \neq a_2 = v(a_2)$. This contradicts our assumption, so $f$ is injective. $\blacksquare$

Theorem (Characterization of surjective maps): The following statements are equivalent:

1. $f: A \to B$ is surjective.
2. There exists $q: B \to A$ such that $f \circ q = \mathrm{id}_B$.
3. For any set $C$ and any maps $u, v: B \to C$, $u \circ f = v \circ f$ implies $u = v$.

Proof.

$(1 \Rightarrow 2)$ Suppose $f$ is surjective. Then for any $b \in B$, we have $f^{-1}(\{b\}) \subseteq A$ nonempty, with $a \in f^{-1}(\{b\})$ implying $f(a) = b$. Construct a candidate $q: B \to A$ by choosing (invoking the axiom of choice) some $a \in f^{-1}(\{b\})$ for each $b \in B$. Then $f(q(b)) = b$ for each $b \in B$, i.e. $f \circ q = \mathrm{id}_B$.

$(2 \Rightarrow 1)$ Suppose $q$ is a right inverse of $f$, i.e. $f \circ q = \mathrm{id}_B$. Notice $\mathrm{Im}_{f\circ q}(B) \subseteq \mathrm{Im}_f(A)$, i.e. $B \subseteq \mathrm{Im}_f(A)$. Thus $\mathrm{Im}_f(A) = B$.

$(1 \Rightarrow 3)$ Suppose $f$ is surjective, and $u \circ f = v \circ f$. Then for each $a \in A$, $u(f(a)) = v(f(a))$. But for any $b \in B$, there is some $a \in A$ for which $b = f(a)$, thus $u(b) = v(b)$ for every $b \in B$, hence $u = v$.

$(3 \Rightarrow 1)$ Suppose $f$ is such that, for any set $C$ and any maps $u, v: B \to C$, $u \circ f = v \circ f$ implies $u = v$. Suppose toward contradiction that $f$ is not surjective, so there exists $b^* \in B$ for which there is no $a \in A$ with $f(a) = b^*$.

Let $C = B$, and choose $u = \mathrm{id}_B$ and $v(b) = \begin{cases} b & b \neq b^* \\ b' & b = b^* \end{cases}$ for any fixed $b' \neq b^*$.

Clearly $u(f(a)) = f(a) = v(f(a))$ for every $a \in A$, since $f(a) \neq b^*$ always (as $b^*$ has no preimage). So $u \circ f = v \circ f$. But $u \neq v$, since $u(b^*) = b^* \neq b' = v(b^*)$. This contradicts our assumption, so $f$ is surjective. $\blacksquare$

Cool. It is quite evident that characterization (3) of injectivity and surjectivity is best suited to being lifted into categories.

---

2 - Categories, Monomorphisms, and Epimorphisms

Definition (Category): A category $\mathsf{C}$ consists of:

• A class of objects $\operatorname{Obj}(\mathsf{C})$.
• For any $A,B \in \operatorname{Obj}(\mathsf{C})$, a possibly empty set of morphisms $\operatorname{Hom}_{\mathsf{C}}(A,B)$. The sets $\operatorname{Hom}_{\mathsf{C}}(A,B)$ and $\operatorname{Hom}_{\mathsf{C}}(C,D)$ are completely disjoint when $(A,B) \neq (C,D)$, and equal when $(A,B)=(C,D)$.
• For any $A,B,C \in \operatorname{Obj}(\mathsf{C})$, a function $\operatorname{Hom}(A,B) \times \operatorname{Hom}(B,C) \to \operatorname{Hom}(A,C)$ known as composition.
• For any $A \in \operatorname{Obj}(\mathsf{C})$, an identity morphism $1_A \in \operatorname{Hom}(A,A)$.

These satisfy the following axioms:

• (Associativity) For any $A,B,C,D \in \operatorname{Obj}(\mathsf{C})$ and morphisms $f \in \operatorname{Hom}(A,B)$, $g \in \operatorname{Hom}(B,C)$, and $h \in \operatorname{Hom}(C,D)$: $h \circ (g \circ f) = (h \circ g) \circ f$

• (Identity) For any $A,B \in \operatorname{Obj}(\mathsf{C})$ and $f \in \operatorname{Hom}(A,B)$: $f \circ 1_A = f = 1_B \circ f$

It is often painful to write out $\operatorname{Hom}$ and this and that, so we would rather just use arrows.

Definition (Monomorphism): Let $\mathsf{C}$ be a category. A morphism $A \overset{f}{\longrightarrow} B$ is a monomorphism if, for any object $C$ and any two morphisms $C \overset{u}{\longrightarrow} A$ and $C \overset{v}{\longrightarrow} A$, we have that $f \circ u = f \circ v$ implies $u=v$.

Definition (Epimorphism): Let $\mathsf{C}$ be a category. A morphism $A \overset{f}{\longrightarrow} B$ is an epimorphism if, for any object $C$ and any two morphisms $B \overset{u}{\longrightarrow} C$ and $B \overset{v}{\longrightarrow} C$, we have that $u \circ f = v \circ f$ implies $u=v$.

Theorem (Factoring monomorphisms and epimorphisms): For a morphism $A \overset{f}{\longrightarrow} B$ and any factorization $f=y\circ x$, if $f$ is an epimorphism, then $y$ is an epimorphism; if $f$ is a monomorphism, then $x$ is a monomorphism.

Proof: Let $f$ be an epimorphism, and let $u,v$ be morphisms from $B$ to the same target $C$. Suppose $u \circ y=v\circ y$. Then $u\circ y\circ x=v\circ y\circ x$, i.e. $u\circ f=v\circ f$. This means that $u=v$, showing that $y$ is an epimorphism.

Now let $f$ be a monomorphism, and let $u,v$ be morphisms from the same domain $C$ to $A$. Suppose $x\circ u=x\circ v$. Then $y\circ x\circ u=y\circ x\circ v$; that is, $f\circ u=f\circ v$. This means that $u=v$, showing that $x$ is a monomorphism. $\square$

---

3 - Images and Their Universal Property

Now, we shall try to lift the notion of the image of a function to categories.

Let $f: A \to B$. Then $f$ factors as

$$A \overset{\tilde f}{\longrightarrow} \operatorname{Im}(f) \overset{\iota}{\hookrightarrow} B,$$

where $\tilde f(a) = f(a)$ and $\iota$ is inclusion.

Moreover, $\operatorname{Im}(f)$ is the smallest subset of $B$ through which $f$ factors. Thus, for every

$$\operatorname{Im}(f) \subseteq B' \subseteq B,$$

there is a unique $\tilde f': A \to B'$ such that

$$f = \iota_{B',B} \circ \tilde f'.$$

The inclusions themselves factor as

$$\iota_{\operatorname{Im}(f),B} = \iota_{B',B} \circ \iota_{\operatorname{Im}(f),B'}.$$

Unfortunately, there isn’t really a notion of “subset” in categories, so, with just wishful thinking, we state the following theorem in terms of sets and functions.

Universal Property of Images

Let $f: A \to B$ be a function. We call a set $C$, together with an injection $y: C \to B$, a photo of $f$ if there exists some $x: A \to C$ for which $f = y \circ x$.

Moreover, a photo $y^*: C^* \to B$ of $f$ is called canonical if, for any other photo $y: C \to B$, there exists a unique $h: C^* \to C$ such that $y^* = y \circ h$.

The claim is that $\iota: \mathrm{Im}_f(A) \hookrightarrow B$ is a canonical photo of $f$, and further that any other canonical photo is isomorphic to it.

Proof. Let $y: C \to B$ be any photo of $f$. We will first show $h$ exists, then argue its uniqueness.

Since $y$ is injective, choose any left inverse $y_L$ of $y$ (i.e. $y_L \circ y = \mathrm{id}_C$).

We claim that $h = y_L \circ \iota$ is such that $\iota = y \circ h$. Let $p = y \circ h = y \circ y_L \circ \iota$. Since $y \circ x = f$, it must be that $\mathrm{Im}_f(A) \subseteq \mathrm{Im}_y(C)$. Now, $p(b) = y \circ y_L \circ \iota(b) = y \circ y_L(b)$ for each $b \in \mathrm{Im}_f(A)$, and indeed any choice of $y_L$ sends elements of $\mathrm{Im}_f(A)$ to their unique preimage under $y$, i.e. $p(b) = b$. Thus $p = \iota$.

The uniqueness of $h$ follows from the fact that $y$ is a monomorphism: if $y \circ h = y \circ h' = \iota$, then $h = h'$.

Now we shall show the universal condition. Let $y^*: C^* \to B$ be another canonical photo of $f$. Then there exist unique $h: \mathrm{Im}_f(A) \to C^*$ and $k: C^* \to \mathrm{Im}_f(A)$ such that $\iota = y^* \circ h$ and $y^* = \iota \circ k$ (since both are canonical photos).

Thus, we obtain $\iota \circ \mathrm{id}_{\mathrm{Im}_f(A)} = \iota \circ (k \circ h)$ and $y^* \circ \mathrm{id}_{C^*} = y^* \circ (h \circ k)$. Since $y^*, \iota$ are monomorphisms (or, invoking the uniqueness that canonical photos enjoy as canonical photos of themselves, which is generally how such arguments go for universal properties), we get $k \circ h = \mathrm{id}_{\mathrm{Im}_f(A)}$ and $h \circ k = \mathrm{id}_{C^*}$. Hence $C^* \cong \mathrm{Im}_f(A)$. $\blacksquare$

Universal Property of Co-images

Let $f: A \to B$ be a function. A set $C$, together with a surjection $x: A \to C$, is called a co-photo of $f$ if there exists some $y: C \to B$ such that $y \circ x = f$.

Moreover, a co-photo $x^*: A \to C^*$ is called canonical if, for every co-photo $x: A \to C$, there exists a unique $h: C \to C^*$ such that $x^* = h \circ x$.

We claim that $\pi: A \to A/\sim$, where $a \sim a' \iff f(a) = f(a')$ and $\pi(a)=[a]$, is a canonical co-photo of $f$, and that any other canonical co-photo $x^*:A\to C^*$ has $C^*\cong A/\sim$.

Proof. First, we shall show that $\pi: A \to A/\sim$ is indeed a co-photo. Of course $\pi$ is surjective. The function $f_{[]}: [a] \mapsto f(a)$ is well defined, since no matter which representative $a \in [a]$ you pick, they all share the same value $f(a)$. And of course, the composition $f_{[]} \circ \pi = f$.

Now, let $x: A \to C$ be any co-photo of $f$. Since $x$ is surjective, it has a right inverse $x_R$ (i.e. $x \circ x_R = \mathrm{id}_C$). We claim that $h = \pi \circ x_R$ is a candidate.

The central claim of this proof is that for each $c \in C$, $x_R(c) \in \mathrm{fib}_f(y(c))$, where $\mathrm{fib}_f$ denotes the preimage of a single element. Equivalently, $\pi \circ x_R(c) = \mathrm{fib}_f(y(c))$ (note that $\mathrm{fib}_f(y(c))$ is precisely the equivalence class in $A$ whose image under $f$ is $y(c)$).

Suppose $x_R(c) \notin \mathrm{fib}_f(y(c))$, equivalently $f(x_R(c)) \neq y(c)$. But of course $c = x(x_R(c))$, so $f(x_R(c)) \neq y(x(x_R(c)))$, contradicting the assumption that $y \circ x = f$.

Now, for each $a \in A$, $h \circ x(a) = \pi \circ x_R \circ x(a)$. But $\pi \circ x_R(x(a)) = \mathrm{fib}_f(y(x(a))) = \mathrm{fib}_f(f(a)) = [a]$. Thus $h \circ x = \pi$.

We shall omit proving the uniqueness of $h$ and the universality of the co-image, as the argument is dual to the one for the image. $\blacksquare$

A Note on the Proof

The above proof might seem to appear out of the blue. Partly, this is because I like to keep my writing compact. I spent an evening figuring out what $C$ intuitively represents and looking for the most concise proof I could find once I understood it.

The intuition is this: $C$ can be thought of as taking each equivalence class $[a]$, picking out some subset of it, relabeling that subset, and possibly moving pieces of different classes around, a kind of coarser or rearranged partition sitting “underneath” $A/\sim$.

Another way to see it: whatever $y$ does to some $c \in C$, that is, $y(c)$, must be consistent with $f$ on the preimage $x^{-1}(\{c\})$. Concretely, every $a \in x^{-1}(\{c\})$ must satisfy $f(a) = y(c)$, since $y \circ x = f$. But that means every such $a$ lands in the same equivalence class of $A/\sim$, namely the one whose image under $f$ is $y(c)$, otherwise the identity $y \circ x = f$ would break. So the preimage of $c$ under $x$ is entirely contained within a single equivalence class.

This is precisely what lets us define $h:C\to A/\sim$: it simply records which equivalence class each $c\in C$ “belongs to” by sending $c$ to the class containing $x^{-1}(\{c\})$.

---

4 - Categorical Images and Co-images

Categorical definition of image: Let $f: A \to B$ be a morphism. The image of $f$ is a monomorphism $\iota: \mathrm{Im}(f) \to B$, together with a morphism $\tilde f: A \to \mathrm{Im}(f)$ satisfying $\iota \circ \tilde f = f$, such that for any monomorphism $y: C \to B$ and morphism $x: A \to C$ with $y \circ x = f$, there exists a unique $h: \mathrm{Im}(f) \to C$ with $y \circ h = \iota$.

Categorical definition of co-image: Let $f: A \to B$ be a morphism. The co-image of $f$ is an epimorphism $\pi: A \to \mathrm{Coim}(f)$, together with a morphism $f_{[]}: \mathrm{Coim}(f) \to B$ satisfying $f_{[]} \circ \pi = f$, such that for any epimorphism $x: A \to C$ and morphism $y: C \to B$ with $y \circ x = f$, there exists a unique $h: C \to \mathrm{Coim}(f)$ with $h \circ x = \pi$.

Both are unique up to isomorphism, being defined via universal properties. Notice both definitions are stated entirely in terms of morphisms and their composition, no reference to elements, subsets, or preimages, exactly the object-agnostic flavor we wanted from categorification. Image and co-image end up dual to each other: image factors $f$ through the smallest mono into $B$, co-image factors $f$ through the largest epi out of $A$, and one is obtained from the other by reversing all arrows. Also note that the other triangle in each of the diagrams can easily be shown to commute, and requires nothing about set theory to do so.

---

5 - Canonical Decomposition in Sets

Theorem (Canonical Decomposition). Let $f: A \to B$ be a function, and let $\sim$ be the equivalence relation on $A$ given by $a \sim a' \iff f(a) = f(a')$. Then there is a canonical isomorphism $A/\sim \; \cong \; \mathrm{Im}_f(A)$, such that $f$ factors as

$$A \xrightarrow{\ \pi\ } A/\sim \; \xrightarrow{\ \cong\ } \mathrm{Im}_f(A) \xhookrightarrow{\ \iota\ } B,$$

where $\pi$ is the canonical surjection $a \mapsto [a]$ and $\iota$ is the inclusion. That is, every function $f: A \to B$ decomposes, uniquely up to this isomorphism, as a surjection followed by a bijection followed by an injection.

Proof. $\mathrm{Im}_f(A)$, together with $\tilde f$ and $\iota$, is a co-photo of $f$. Since $A/\sim$ is the canonical co-photo, we get a unique $h: \mathrm{Im}_f(A) \to A/\sim$ with $h \circ \tilde f = \pi$.

Symmetrically, $A/\sim$, together with $\pi$ and $f_{[]}$, is a photo of $f$. Since $\mathrm{Im}_f(A)$ is the canonical photo, we get a unique $h^{-1}: A/\sim \to \mathrm{Im}_f(A)$ with $\iota \circ h^{-1} = f_{[]}$.

We check $h, h^{-1}$ are mutually inverse. Notice $\iota \circ (h^{-1} \circ \pi) = f_{[]} \circ \pi = f = \iota \circ \tilde f$, and $\iota$ is mono, so $h^{-1} \circ \pi = \tilde f$. Then $h^{-1} \circ h \circ \tilde f = h^{-1} \circ \pi = \tilde f,$ and since $\tilde f$ is epi, $h^{-1} \circ h = \mathrm{id}_{\mathrm{Im}_f(A)}$.

Dually (swapping the roles of $\tilde f$/epi and $f_{[]}$/mono), $h \circ h^{-1} = \mathrm{id}_{A/\sim}$.

Thus $h$ is an isomorphism, and $A/\sim \; \cong \; \mathrm{Im}_f(A)$. $\blacksquare$

This roughly covers Section 2 of Chapter 1 of Aluffi’s text. Most of the exercises in Section 2 are pretty chill.