Basic category theory, products, coproducts, and free objects.

Part of the first section of Hungerford’s Algebra is on category theory, with a focus on products, coproducts, and free objects.

The distinction between classes and sets in Hungerford is informal. We start with undefined notions of class, membership, and equality. A class can be thought of as an object that satisfies a formula. Classes are very similar to sets except that we do not allow classes to be members of other classes and they are thought to be defined purely defined in terms of the formula. Some classes can manifest as a set. The classes that are not sets are said to be proper classes. Classes were invented to avoid sets that lead to paradoxes such as Russel’s paradox. A set of all sets, or a set of all groups does not exist, but we commonly discuss the categories $\catname{Set}$ and $\catname{Grp}$.

A category consists of a class $\operatorname{ob}(\mathcal{C})$ of objects, a class $\operatorname{hom}(\mathcal{C})$ of morphisms, and a binary operation $\circ$, called composition of morphisms.

Each morphism $f$ has a source object $a$ and a target object $b$, and this is denoted $f: a \to b$. $\operatorname{hom}(a,b)$ denotes the hom-class of all morphisms from $a$ to $b$. The binary operation $\circ$ is such that $$\circ: \operatorname{hom}(b,c) \times \operatorname{hom}(a,b) \to \operatorname{a,c}$$ The composition of $f: a \to b, g: b \to c$ is written as $g \circ f$ or $gf$, and satisfies associativity and the existence of an identity:

  1. $h \circ (g \circ f) = (h \circ g) \circ f$

  2. Every object $x$ has a morphism $\text{id}_x : x \to x$ called the identity morphism for $x$ such that for every morphism $f: a \to b$, $\text{id}_b \circ f = f = f \circ \text{id}_a$.

These definitions are reminiscent of functions between sets. In concrete categories, objects are sets and morphisms are simply functions.

\begin{definition} A concrete category is a category $\mathcal{C}$ together with a function $\sigma$ that assigns to each object $A$ of $\mathcal{C}$ a set $\sigma(A)$ in such a way that \begin{enumerate} \item Every morphism $A \to B$ of $\mathcal{C}$ is a function on the underlying sets $\sigma(A) \to \sigma(B).$ \item The identity morphism of each object $A$ of $\mathcal{C}$ is the identity function on $\sigma(A).$ \item Composition of morphisms in $\mathcal{C}$ agrees with composition of functions on underlying sets. \end{enumerate} \end{definition}

A morphism $f: A \to B$ is called an equivalence if there is a morphism $g: B \to A$ such that $g \circ f = \text{id}_A, f \circ g = \text{id}_B$. If $f: A \to B$ is an equivalence, $A$ and $B$ are said to be equivalent. A morphism to itself is called an endomorphism.

Next, we define products and coproducts.

\begin{definition} Let $\mathcal{C}$ be a category and $\{A_i \mid i \in I\}$ a family of objects in $\mathcal{C}$. A product for the family $\{A_i \mid i \in I\}$ is an object $P$ of $\mathcal{C}$ together with a family of morphisms $\{\pi_i: P \to A_i \mid i \in I\}$ such that for any object $B$ and family of morphisms $\{\phi_i: B \to A_i \mid i \in I\}$ there is a unique morphism $\phi: B \to P$ such that $\pi_i \circ \phi = \phi_i$ for all $i \in I$. \end{definition}

A product $P$ of $\{A_i \mid i \in I\}$ is usually denoted $\prod_{i \in I}A_i$. A family of objects in a category need not have a product. In category theory, we can always interchange the source and target of each morphism to obtain the dual statement.

For a category $\mathcal{C}$, the dual category $\mathcal{C}^{\text{op}}$ is a category with the same objects but where the morphisms have interchanged the source and target. A dual statement is obtained by interchanging the source and target of each morphism and interchanging the order of composing two morphisms, e.g. $g \circ f$ is replaced by $f \circ g$. We see that a statement is true in $\mathcal{C}$ iff its dual statement is true in $\mathcal{C}^{\text{op}}$.

The coproduct is the dual notion of a product. Its definition is as follows:

\begin{definition} A coproduct or sum for the family $\{A_i \mid i \in I\}$ of objects in a category $\mathcal{C}$ is an object $S$ of $\mathcal{C}$ together with a family of morphisms $\{\iota_i: A_i \to S \mid i \in I\}$ such that for any object $B$ and family of morphisms $\{\psi_i: A_i \to B \mid i \in I\}$, there is a unique morphism $\psi: S \to B$ such that $\psi \circ \iota_i = \psi_i$ for all $i \in I$. \end{definition}

Although there is no uniform notation for coproduct, $\coprod_{ i \in I} A_i$ is sometimes used.

In the category \catname{Set}, the category of sets, the product is the Cartesian product, defined as $$\prod_{i \in I} A_i = \left\{ \left. f : I \to \bigcup_{i \in I} A_i \right| \forall i \in I, f(i) \in A_i \right\}.$$ The coproduct in \catname{Set} is the disjoint union, defined as $$\bigsqcup_{i \in I} A_i = \bigcup_{i \in I} \{ (x,i) \mid x \in A_i \}.$$

Next, we discuss free objects.

\begin{definition} Let $F$ be an object in a concrete category $\mathcal{C}$, $X$ a nonempty set, and $i: X \to F$ a map. $F$ is free on the set $X$ provided that for any object $A$ of $\mathcal{C}$ and function $f: X \to A$, there exists a unique morphism of $\mathcal{C}$, $\bar{f}: F \to A$ such that $\bar{f} \circ i = f$ as a function between sets. \end{definition}

Essentially, to define a morphism with domain $F$, it suffices to specify it on the image $i(X)$. As an example, consider the category \catname{Grp} of groups. Let $X = \{1\}$ and $i: X \to \mathbb{Z}$ be the inclusion map. Then $\mathbb{Z}$ is free on $X$ in $\catname{Grp}$. Let $G$ be a group and $f: X \to G$. Let $g = f(1) \in G$. The map $\bar{f}: \mathbb{Z} \to G$ defined by $\bar{f}(n) = g^n$ is the unique homomorphism $\mathbb{Z} \to G$ with $1 \mapsto g$.

The notation seems to suggest that $i$ is an injection. Indeed, it usually is an injection.

\begin{theorem} Let $F$ be a free object on a set $X$ with $i: X \to F$ in a concrete category $\mathcal{C}$. If $\mathcal{C}$ contains an object whose underlying set has at least two elements in it, then $i$ is an injective map of sets. \end{theorem}

Proof. If $|X| = 1$, then $i$ is injective. Assume $|X| > 1$. Assume $i$ is not injective. That is, there exists $x \neq y, x, y \in X, i(x) = i(y)$. Let $A$ be an object in $\mathcal{C}$ with $|\sigma(A)| > 1$ and let $f: X \to A$ where $f(x) = a, f(y) = b$, where $a \neq b$. Because $F$ is free, there is a unique morphism $\bar{f}: F \to A$ where $\bar{f} \circ i = f$ as a map of sets. But $$a = f(x) = \bar{f} \circ i (x) = \bar{f} \circ i (y) = f(y) = b,$$ a contradiction. ◻

Products, coproducts, and free objects are all similar in that they are defined by the existence of a unique morphism up to equivalence. This is called a universal property.

\begin{definition} An object $I$ in a category $\mathcal{C}$ is said to be universal (initial) if for each object $C$ of $\mathcal{C}$, there exists one and only one morphism $I \to C$. An object $T$ of $\mathcal{C}$ is said to be couniversal (terminal) if for each object $C$ of $\mathcal{C}$, there exists one and only one morphism $C \to T$. \end{definition}

Clearly, universal and couniversal are dual concepts. There is only one universal or couniversal object in a category up to equivalence.

\begin{theorem} Any two universal objects in a category are equivalent. \end{theorem}

Proof. Let $I$ and $J$ be universal objects in $\mathcal{C}$. Since $I$ is universal, there is a unique morphism $f: I \to J$. Similarly, there is a unique morphism $g: J \to I$. The composition $g \circ f: I \to I$ is a morphism of $\mathcal{C}$. Since $\text{id}_I: I \to I$ is also a morphism of $\mathcal{C}$, by universality, $g \circ f = \text{id}_I$. Likewise, $f \circ g: J \to J$ is a morphism so $f \circ g = \text{id}_J$. Thus $f$ is an equivalence. ◻

As an example, $\langle e \rangle$ is both a universal and couniversal object in \catname{Grp}.

We shall show that products, coproducts, and free objects are universal objects in an appropriately defined category:

Let $F$ be a free object on the set $X$ in a concrete category $\mathcal{C}$. Define a new category $\mathcal{D}$ as follows: objects of $\mathcal{D}$ are maps of sets $f: X \to A$, where $A$ is an object of $\mathcal{C}$. A morphism in $\mathcal{D}$ from $f: X \to A$ to $g: X \to B$ is a morphism $h: A \to B$ of $\mathcal{C}$ such that $h \circ f = g$. Note that $\text{id}_f$ in $\mathcal{D}$ is $\text{id}_A$ in $\mathcal{C}$. Also, $h$ is an equivalence in $\mathcal{D}$ iff $h$ is an equivalence in $\mathcal{C}$. Since $F$ is free on $X$, for each function $f: X \to A$ there is a unique morphism $\bar{f}: F \to A$ such that $\bar{f} \circ i = f$. Thus $i: X \to F$ is a universal object in the category $\mathcal{D}$.

\begin{theorem} If $\mathcal{C}$ is a concrete category, $F$ and $F'$ are objects of $\mathcal{C}$ such that $F$ is free on the set $X$ and $F'$ is free on the set $X'$. If $|X| = |X'|$, then $F$ is equivalent to $F'$. \end{theorem}

Proof. Let $i: X \to F$, $j: X' \to F'$ be the functions defined by the definition of free objects. There is a bijection $f: X \to X'$. Since $i$ is a universal object in $\mathcal{D}$ as defined above, there is a unique morphism $\phi: i \to j \circ f$ in $\mathcal{D}$ which implies that there is a unique morphism $\phi: F \to F'$ in $\mathcal{C}$ such that $\phi \circ i = j \circ f$. Let $f': X' \to X$ be the inverse of $f$. By similar reasoning, there is a unique morphism $\psi: F' \to F$ in $\mathcal{C}$ such that $\psi \circ j = i \circ f'$. Thus $$\psi \circ (\phi \circ i) = \psi \circ (j \circ f) = i \circ f' \circ f = i$$ Since $i$ is universal in $\mathcal{D}$, $\psi \circ \phi = \text{id}_F$. Similarly, $\phi \circ \psi = \text{id}_{F'}$ Thus $\phi$ is an equivalence. ◻

The converse is false in general.

Now we show that a product is a couniversal object in an appropriate category. By duality, this would also imply that a coproduct is a universal object in an appropriate category.

Let $\{A_i \mid i \in I\}$ be a family of objects in a category $\mathcal{C}$. Define a category $\mathcal{E}$ whose objects are all pairs $(B, \{f_i \mid i \in I\})$, where $B$ is an object of $\mathcal{C}$ and $f_i: B \to A_i$ is a morphism of $\mathcal{C}$. A morphism in $\mathcal{E}