3. Initial and Terminal ObjectΒΆ

3.1. Universal PropertyΒΆ

We now introduce an idea that plays an important role in abstract mathematicsβ€”the concept of universal property.

An object \(\mathbf{0}\) in a category \(\mathcal C\) is called an initial (or free) object if for every object \(A∈ \mathcal C_{\mathrm{obj}}\) there exists a unique morphism \(!_A :\mathbf{0}\to A\).

This unique morphism property of initial objects is called a universal property, and we say that the initial object in a category \(\mathcal C\) is universal for all objects in \(\mathcal C\).

To give a better sense of the notion of universal property, let us look at another example, which is one of the most fundamental definitions of algebra.

Let \(\mathcal V\) be a variety of algebras of a certain signature. [1] Let \(X\) be a set. The free algebra generated by \(X\) is denoted by \(𝔽(X)\) and is defined as follows: for every algebra \(𝐀 = ⟨A, \dots⟩ ∈ \mathcal V\) and every function \(f : X β†’ A\), there exists a unique homomorphism \(h:𝔽(X) β†’ 𝐀\) such that \(βˆ€ x ∈ X, h(x) = f(x)\). We say that \(𝔽(X)\) is universal for \(\mathcal V\).

An object \(\mathbf{1}\) is called a terminal (or bound) object if for every object \(A\) in the same category there exists a unique morphism \(\langle\rangle_A : A\to\mathbf{1}\).

We have already seen many examples of free and bound objects; these are summarized in the table below.

Category Initial (free) object Terminal (bound) object
Set empty set βˆ… singleton set \(\{a\}\)
Grph empty graph \((\varnothing,\varnothing)\) single loop \((\{a\},\{(a,a)\})\)
Mon trivial monoid \((\{e\},\{(e,e,e)\},e)\) trivial monoid \((\{e\},\{(e,e,e)\},e)\)
Grp trivial group \((\{e\},\{(e,e,e)\},e)\) trivial group \((\{e\},\{(e,e,e)\},e)\)
Par empty set βˆ… empty set βˆ…
Rel empty set βˆ… empty set βˆ…

Exercise 3.1.1: Verify all entries in the above table.

3.2. DualityΒΆ

Every definition and theorem in category theory can be dualized by reversing the direction of its arrows.

Given a category \(\mathcal C\) the opposite (or dual) category \(\mathcal C^{\mathrm{op}}\) has the same objects as \(\mathcal C\) and whenever \(f : A→ B\) is a morphism in \(\mathcal C\) we define \(f : B→ A\) to be a morphism in \(\mathcal C^{\mathrm{op}}\).

The identity morphisms in \(\mathcal C^{\mathrm{op}}\) are the same as those in \(\mathcal C\) and given morphisms \(g : C β†’ B\) and \(f : B β†’ A\) in \(\mathcal C^{\mathrm{op}}\) we define the composition \(f\circ_{\mathrm{op}} g : Cβ†’ A\) to be the morphism \(g ∘ f : A β†’ C\) in \(\mathcal C\).

[semithick,->,node distance=3cm]
\node (G1) {$A$};
\node (G2) [right of=G1] {$B$};
\node (G3) [right of=G2] {$C$};
\node (G4) [right of=G3] {$A$};
\node (G5) [right of=G4] {$B$};
\node (G6) [right of=G5] {$C$};
\node (C) at (3,1) {{\Large $\mathcal C$}};
\node (Cop) at (12,1) {{\Large $\mathcal C^{\mathrm{op}}$}};
\draw (G1) to node[above] {$f$} (G2); \draw[->] (G2) to node[above] {$g$} (G3);
\draw[bend right] (G1) to node[below] {$g\circ f$} (G3);
\draw (G5) to node[above] {$f$}  (G4); \draw[->] (G6) to node [above] {$g$} (G5);
\draw[bend left] (G6) to node[below] {$g\circ_{\mathrm{op}} f$} (G4);

Intuitively, \(\mathcal C^{\mathrm{op}}\) is the same as \(\mathcal C\) but all the morphisms go in the other direction.


Exercise 3.2.1: Verify that \(\mathcal C^{\mathrm{op}}\) is a category whenever \(\mathcal C\) is a category.

Usually \(\mathcal C^{\mathrm{op}}\) is very different from \(\mathcal C\). One exception to this is the category Rel. We have that \(\mathbf{Rel}^{\mathrm{op}} = \mathbf{Rel}\), as the definition of relation is symmetric between domain and codomain. Since Rel is its own dual we say that Rel is self-dual.

Our first example of dual concepts in category theory has already appeared: the notions of initial and terminal objects are dual.


Exercise 3.2.2: Show that \(\mathbf{1}\) is a terminal object of a category \(\mathcal C\) if and only if \(\mathbf{1}\) is an initial object of \(\mathcal C^{\mathrm{op}}\). Similarly, show that \(\mathbf{0}\) is an initial object of \(\mathcal C\) if and only if \(\mathbf{0}\) is a terminal object of \(\mathcal C^{\mathrm{op}}\).

3.3. Other interesting categoryΒΆ

We will now take a look at some other interesting category.

Up until now we have only considered category with an infinite number of elements. (Indeed, we have not even seen examples of any category whose objects form a set.)

There are category with a finite set of objects. We will detail a few of them, generally leaving out the identities in the corresponding diagrams.

Example 3.1

The category 1 has only one object, called \(0\), and only one morphism, the identity \(\mathrm{id}_0 : 0\to0\).

[semithick,->]
\node (zero) {$0$};
\path[loop] (zero) edge node[above] {{\small $\mathrm{id}_0$}} (zero);

Note that this is not the only category with one object.


Exercise 3.3.1: Find another category with only one object.

One can also find more than one category with two or three elements, but we provide just one example of each here.

Example 3.2

The category 2 has two objects, \(0\) and \(1\), and one nonidentity morphism \(f : 0β†’ 1\).

[semithick,->]
\node (0) at (0,0) {$0$};
\node (1) at (2,0) {$1$};
\draw (0) to node[above] {$f$} (1);

Note that we did not need to describe any composition rule because the only possible morphism compositions in 2 are trivial. This is not the case for the following category.

Example 3.3

The category 3 has three objects, \(0\), \(1\), and \(2\), and three nonidentity morphisms: \(f : 0β†’ 1\), \(g : 1β†’ 2\), and \(h : 0β†’ 2\). We define \(g∘ f = h\).

[semithick,->]
\node (0) at (0,2) {$0$};
\node (1) at (2,2) {$1$};
\node (2) at (2,0) {$2$};
\draw (0) to node [above] {$f$} (1);
\draw (1) to node [right] {$g$} (2);
\draw (0) to node [below left] {$h$} (2);

Carrying on with the topic of finiteness, consider the next example.

Example 3.4
The category Fin has finite sets for objects; the morphisms are all functions on these sets. The identity morphisms are the identity functions and composition in Fin is the usual function composition.

Exercise 3.3.2: Show that Fin is a category.

We now examine a category that comes from order theory.

A poset \((A, ≀ )\) consists of a set \(A\) and a binary relation \(\leq\, βŠ† A^2\) such that for all \(x,y,z∈ A\) we have

reflexivity:\(x ≀ x\);
antisymmetry:\(x ≀ y\) and \(y ≀ x\) imply \(x=y\);
transitivity:\(x ≀ y\) and \(y ≀ z\) imply \(x ≀ z\).

We have order-preserving maps from one poset to another, defined as follows:

Given posets \((A, ≀ _A)\) and \((B, ≀ _B)\) we say that a function \(f : Aβ†’ B\) is monotone from \((A, ≀ _A)\) to \((B, ≀ _B)\) when for any \(x,y∈ A\) we have that \(x ≀ _Ay\) implies that \(f(x) ≀ _Bf(y)\).

To signify that a function \(f\) from \(A\) to \(B\) is monotone with respect to order relations \(≀ _A\) and \(≀ _B\), we write \(f : (A, ≀ _A)\to(B, ≀ _B)\).

Here are more examples of important categories.

Example 3.5
The category Pos has posets for objects and monotone functions as morphisms. The identity morphisms are the identity functions and composition in Pos is the usual function composition.
Example 3.6
The objects of Lat are lattices (i.e., posets closed under finite meets and joins), the morphisms are the lattice homomorphisms.
Example 3.7
The objects of CLat are complete lattices (i.e., posets closed under arbitrary meets and joins); the morphisms are the complete lattice homomorphisms.
Example 3.8
The objects of BLat are the Boolean lattices, the morphisms are the Boolean lattice homomorphisms. By definition, such a homomorphism is a function \(f : X β†’ Y\) preserving finite meets and joins (a lattice homomorphism) and preserving complementation, but every lattice homomorphism between Boolean lattices automatically preserves complementation. So we may characterize the morphisms of this category more simply as the lattice homomorphisms.
Example 3.9
The objects of HLat are the Heyting lattices. The morphisms are the Heyting lattice homomorphisms, that is, functions \(f : X β†’ Y\) preserving finite meets and joins, as well as Heyting implications: if \(x, x' ∈ X\), then \(f(x β†’ x') = f(x) β†’ f(x')\).
Example 3.10

The objects of ACLat are the algebraic, complete lattices; the morphisms are the complete lattice homomorphisms.

Important note: in ACLat the morphisms are not required to preserve a certain part of the structure of the objects; specifically, compact elements need not map to compact elements.


Exercise 3.3.3: Show that Pos is a category and determine whether it has initial and/or terminal objects.

3.4. Hom set and global elementΒΆ

In Set every object \(A\) is completely described by the morphisms \(f : \mathbf{1} β†’ A\).

If \(A\) and \(B\) are objects from a category \(\mathcal C\), then the collection of morphisms from \(A\) to \(B\) is often denoted by \(\mathcal C(A,B)\), and we will follow this convention when it’s convenient to do so.

Some authors require that \(\mathcal C(A,B)\) always be a set and call \(\mathcal C(A,B)\) the hom set from \(A\) to \(B\). For the most part we will be concerned with categories for which \(\mathcal C(A,B)\) is always a set, but this distinction is something to be aware of.

If \(A\) is a set, then \(A β‰…\) Set \((\mathbf{1},A)\). That is, there exists a bijection between \(A\) and the set Set \((\mathbf{1},A)\) of functions from \(\mathbf{1}\) to \(A\).

Given a category with an initial object \(\mathbf{1}\) and another object \(A\), the morphisms with domain \(\mathbf{1}\) and codomain \(A\) are called the points or global elements of \(A\).

In categories other than Set the initial object \(\mathbf{1}\) is not sufficient to completely describe all objects. For example, Grph \((\mathbf{1}, 𝐆)\) only describes the loops of G, as we see in the diagram below.

[semithick,->]
\draw[font=\Large] (0,1.35) node {$\mathbf{1}$};
\draw[font=\large] (5,2.35) node {$\mathbf{G}$};
\draw[gray] (-1,-1) -- (1,-1) -- (1,1) -- (-1, 1) -- (-1,-1);
\draw[gray] (3,-2) -- (7,-2) -- (7,2) -- (3, 2) -- (3,-2);
\node[circle,draw,inner sep=0.8pt] at (5, 1) {}; \node (1) at (5, 1) {};
\node[circle,draw,inner sep=0.8pt] at (4,-1) {}; \node (2) at (4,-1) {};
\node[circle,draw,inner sep=0.8pt] at (6,-1) {}; \node (3) at (6,-1) {};
\node[circle,draw,inner sep=0.8pt] at (0, 0) {}; \node (0) at (0, 0) {};
\draw[loop] (1) to (1);
\draw[loop] (0) to (0);
\draw[bend left] (0) to (1);
\draw[bend right] (2) to (3);
\draw[bend right] (3) to (2);
\draw[bend right] (1) to (2);
\draw[bend left] (1) to (3);

Question. Can we find other objects that describe 𝐆 completely?

We can!

Example 3.11

Consider the graph \(𝐇_V = (\{a\}, βˆ…)\) with one vertex and no edges, and the graph \(𝐇_E = (\{a,b\}, \{(a,b)\})\) with two vertices and a single edge from one vertex to the other. These lie in the boxed regions in the figure below.

We have that \(V_{𝐆} β‰… \mathbf{Grph}(𝐇_V, 𝐆)\) and \(E_{𝐆} β‰… \mathbf{Grph}(𝐇_E, 𝐆)\). Moreover, if \(e ∈ \mathbf{Grph}(𝐇_E, 𝐆)\) then \(s_{𝐆}(e)=e(a)\) and \(t_{𝐆}(e)=e(b)\), so we can view \(s_{𝐆}(e)\) and \(t_{𝐆}(e)\) as members of \(\mathbf{Grph}(𝐇_V, 𝐆)\).

[semithick,->,scale=1.25,every node/.style={scale=1.25}]
\draw[gray] (-1,-1) -- (1,-1) -- (1,1.25) -- (-1, 1.25) -- (-1,-1);
\draw[gray] (-1,3) -- (1,3) -- (1,4.5) -- (-1, 4.5) -- (-1,3);
\node at (-1.5,0.25)  {$\mathbf H_E$};
\node at (-1.5,3.5)  {$\mathbf H_V$};
\node (g) at (4,2)  {$\mathbf G$};
\node (13) at (1,4) {};
\node[circle,draw,inner sep=0.8pt] (2) at (0,3.75)  {};
\node[circle,draw,inner sep=0.8pt] (0) at (0,-0.25) {};
\node[circle,draw,inner sep=0.8pt] (1) at (0,0.75) {};
\draw (1) to (0);
\path[bend right] (2) edge node [fill=white,anchor=center] {{\small source}} (-.1,.85);
\path[bend left] (2) edge node [fill=white,anchor=center] {{\small target}} (.1,-.15);
\path[bend right] (1.2,0) edge node [fill=white,anchor=center] {{\small $\cong$ vertices of $\mathbf G$}} (g);
\path[bend left] (13) edge node [fill=white,anchor=center] {{\small $\cong$ edges of $\mathbf G$}} (g);


Exercise 3.4.1: In other categories (for example, Mon), find one or more objects such that every object \(A\) is completely described by the morphisms from those objects to \(A\). What does "completely describes" mean formally?

3.5. SolutionsΒΆ

Solution to Exercise 3.1.1.

Let \(A\) be a set and \(f: βˆ… β†’ A\) a function. By definition of function,

\[f βŠ† βˆ… Γ— A = \{(x,a) | x ∈ βˆ… ∧ a ∈ A\} = βˆ…,\]

so \(f = βˆ…\) is the unique function with domain βˆ… and codomain \(A\).

Thus, we see that the function \(f: βˆ… β†’ A\) does exist and there is only one such function for each set \(A\), so βˆ… is initial in Set.

Consider a singleton set \(\{a\}\) and a set \(B\). Given a function \(f: B β†’ \{a\}\), we must have \(f(b) = a\) for each \(b\in B\). This completely determines \(f\), so there is exactly one function from a set \(B\) to \(\{a\}\). Thus, \(\{a\}\) is terminal in Set.

Let \(G\) be a graph. We exhibit a graph homomorphism \(f: (βˆ…, βˆ…) β†’ G\). Necessarily both \(f_v: βˆ… β†’ V(G)\) and \(f_e: βˆ… β†’ E(G)\) are empty functions. Since \((βˆ…, βˆ…)\) has no edges, it is vacuously true that \(f = (f_v, f_e)\) is a graph homomorphism from \((βˆ…, βˆ…)\) to \(G\). Thus, we find that \(f\) exists and is uniquely determined, so the empty graph is initial in Grph.

Again let \(G\) be a graph and let \(A = (\{a\}, \{(a,a)\})\) be the graph with one vertex and a single loop. Since \(V(A) = \{a\}\) and \(E(A) = \{(a, a)\}\) are both singletons, we have unique choices for the functions \(f_v: V(G) β†’ \{a\}\) and \(f_e: E(G) β†’ \{(a,a)\}\). This establishes uniqueness.

To see that this pair \(f = (f_v, f_e)\) is a graph morphism from \(G\) to \(A\), note that for each edge \(e = (v_1, v_2) ∈ E(G)\) we have \(f_e(e) = (a, a) = (f_v(v_1), f_v(v_2))\). Thus, the single loop \(A\) is terminal in Grph.

Let \(𝐌 = (M, β‹… , e_{𝐌)}\) be a monoid and consider a monoid morphism \(h\) from the trivial monoid \((\{e\}, \{(e,e,e)\}, e)\) to a monoid 𝐌. Since we require that \(h(e) = e_{𝐌}\) in order for \(h\) to be a monoid homomorphism there can be at most one such \(h\). The function \(h:\{e\} \to M\) given by \(h(e) = e_{𝐌}\) is indeed a monoid homomorphism, since

\[h(e e) = h(e) = e_{𝐌} = e_{𝐌} e_{𝐌} = h(e) h(e).\]

Therefore, the trivial monoid is initial in Mon.

Now instead consider a monoid morphism \(h\) from 𝐌 to the trivial monoid. Since there is a unique function \(h: M β†’ \{e\}\), and since this function trivially satisfies the definition of a monoid morphism, we have that there is a unique morphism \(h\) from any monoid 𝐌 to the trivial monoid. Thus, the trivial monoid is terminal in Mon.

The argument that the trivial group is initial in Grp is essentially identical to that for the trivial monoid being initial in Mon. The underlying functions for the unique morphisms to and from the trivial group are the same, so it only remains to check that they respect the inversion operation. In both cases the desired conclusion follows immediately.

In order to see that βˆ… is initial in Par, note that for every set \(A\) and every partial function \(f: βˆ… ⇀ A\) we must have that \(\mathrm{dom}_f = βˆ…\) and that \(f\) is a total function \(f: βˆ… β†’ A\). There does exist a unique such a function, which is the empty function, so there is exactly one morphism from emptyset to any set \(A\) in Par.

Also, βˆ… is terminal in Par. Consider an arbitrary partial function \(f: A ⇀ βˆ…\). Since \(f: \mathrm{dom}_f β†’ βˆ…\) must be a total function, and since there is no total function from a nonempty set to βˆ…, we must have \(\mathrm{dom}_f = βˆ…\). Again we find that \(f\) can only be the empty function, which certainly exists, so βˆ… is terminal in Par.

Note that the difference between Par and Set in this case is that there are no total functions at all from a nonempty \(A\) to βˆ…, but there are partial functions from a nonempty \(A\) to βˆ….

The empty set is also both initial and terminal in Rel. Given a set \(A\) we have that every relation \(R: A β†’ βˆ…\) is a subset of \(A Γ— βˆ… = βˆ…\), so \(R\) must be the empty relation.

Similarly, if \(R: βˆ… β†’ A\) then again \(R\) is subset of \(βˆ… Γ— A = βˆ…\), so \(R\) is the empty relation.


Solution to Exercise 3.2.1.

Note that objects, morphisms, and composition in \(\mathcal C^{\mathrm{op}}\) are well-defined.

By definition \(\mathrm{id}_A\) in \(\mathcal C^{\mathrm{op}}\) is \(\mathrm{id}_A\) in \(\mathcal C\), so \(\mathrm{id}_A: A β†’ A\) is indeed a morphism in \(\mathcal C^{\mathrm{op}}\). The composition of two morphisms \(g: C β†’ B\) and \(f: B β†’ A\) is defined by \(f ∘_\mathrm{op} g = g ∘ f\), so \(f ∘_\mathrm{op} g: C β†’ A\) and \(f ∘_\mathrm{op} g\) has the appropriate domain and codomain. It then remains to verify the identity and associativity laws.

Given \(f: B β†’ A\) in \(\mathcal C^{\mathrm{op}}\) we have that \(f\) is a morphism from \(A\) to \(B\) in \(\mathcal C\). By definition of composition in \(\mathcal C^{\mathrm{op}}\) and the identity law for \(\mathcal C\) we see that

\[f ∘_\mathrm{op} \mathrm{id}_B = \mathrm{id}_B ∘ f = f = f ∘ \mathrm{id}_A = \mathrm{id}_A ∘_\mathrm{op} f,\]

as desired.

Similarly, given \(h: D β†’ C\), \(g: C β†’ B\), and \(f: B β†’ A\) in \(\mathcal{C}^\mathrm{op}\) we find that

\[f ∘_\mathrm{op} (g ∘_\mathrm{op} h) = (h ∘ g) ∘ f = h ∘ (g ∘ f) = (f ∘_\mathrm{op} g) ∘_\mathrm{op} h,\]

so the associative law holds, as well.


Solution to Exercise 3.2.2.

Suppose that \(\mathbf{1}\) is terminal in \(\mathcal C\). Then given an object \(A\) in \(\mathcal C\), there is a unique morphism \(⟨\ ⟩_A: A β†’ \mathbf{1}\) in \(\mathcal C\). Consider a morphism \(f:\mathbf{1} β†’ A\) in \(\mathcal C^\mathrm{op}\). By the definition of \(\mathcal C^\mathrm{op}\) the only such morphism is the unique morphism \(⟨\ ⟩_A: A β†’ \mathbf{1}\) in \(\mathcal C\), so there is a unique morphism from \(\mathbf{1}\) to any object in \(\mathcal C^\mathrm{op}\). That is, \(\mathbf{1}\) is initial in \(\mathcal C^\mathrm{op}\).

On the other hand, suppose that \(\mathbf{1}\) is initial in \(\mathcal C^\mathrm{op}\). Then given an object \(A\) in \(\mathcal C^\mathrm{op}\), there is a unique morphism \(!_A:\mathbf{1} \to A\) in \(\mathcal C^\mathrm{op}\).

Consider a morphism \(f: A β†’ \mathbf{1}\) in \(\mathcal C\). By definition of \(\mathcal C^\mathrm{op}\), the only such morphism is the unique morphism \(!_A:\mathbf{1} β†’ A\) in \(\mathcal C^\mathrm{op}\), so there is a unique morphism from each object in \(\mathcal C\) to \(\mathbf{1}\). That is, \(\mathbf{1}\) is terminal in \(\mathcal C\).

In addition to the obvious symmetry in the two directions of the argument above, note that in order to show \(\mathbf{0}\) is initial in \(\mathcal C\) iff \(\mathbf{0}\) is terminal in \(\mathcal C^\mathrm{op}\), we can reuse what we have already shown by noting that \((\mathcal C^\mathrm{op})^\mathrm{op}\) is \(\mathcal C\), so this second statement reduces immediately to the first.


Solution to Exercise 3.3.1.

(to do)


Solution to Exercise 3.3.2.

(to do)


Solution to Exercise 3.3.3.

(to do)


Solution to Exercise 3.4.1.

(to do)


Footnotes

[1]Don’t worry if you don’t know words like β€œvariety” or β€œsignature” mean. The point here is to give an example illustrating a universal property, and not to undertake a detailed study of algebraic structures.