2. Basic Definitions

2.1. A motivating example

Example 2.1 (the category of graphs)

We begin our study of categories by way of an example.

A directed graph \(𝐆\) consists of

• vertices. a set \(V\)
• edges. a subset \(E ⊆ V²\)

We call \(V\) the vertex set of \(𝐆\) and we call \(E\) the edge set of \(𝐆\).

We won’t talk about undirected graphs here so we will use the term “graph” to refer to directed graphs as defined above. We will write \(𝐆 = (V, E)\) if we want to give the vertex and edge sets explicitly.

Given a graph \(𝐆 = (V, E)\) and an edge \(e = (v₁,v₂) ∈ E\), we refer to \(v₁\) as the source vertex for \(e\) and we refer to \(v₂\) as the target vertex for \(e\). We define the maps \(s, t : E → V\) where \(s(e) = v₁\) and \(t(e) = v₂\) for any edge \(e = (v₁, v₂) ∈ E\).

For example, the figure below displays a graph \(𝐆 = (V,E)\) with vertex set \(V = \{A, B, C, D\}\) and edge set \(E = \{u, w, x, y, z\}\).

The following table lists the values of the source and target functions for the graph \(𝐆\) shown above.

\(e\)	\(s(e)\)	\(t(e)\)
\(u\)	\(C\)	\(C\)
\(w\)	\(A\)	\(B\)
\(x\)	\(B\)	\(C\)
\(y\)	\(A\)	\(D\)
\(z\)	\(C\)	\(D\)

One reason we study mathematical structures is to understand the inherent structure of these structures!

For that purpose, it helps to define a special kind of function between structures, which will be called a “morphism,” but they are also referred to as “structure preserving maps.”

What is a good definition of such a function between graphs? It should probably

1. map elements of one graph to elements of another and
2. preserve the “relations” between elements.

Let us consider an example of such a map for the graphs \(𝐆\) and \(𝐆'\) shown below.

A function \(f : 𝐆 → 𝐆'\) might map \(B\) to \(A'\), and map \(v\) to \(v'\) for every other vertex \(v ≠ B\) in \(𝐆\).

A function that preserves the edge relations of a graph in this way is called a morphism of graphs, or graph morphism. The figure above should give you an intuitive idea of what such a thing might look like, but here is a more precise definition.

Let \(𝐆₁ = (V₁, E₁)\) and \(𝐆₂ = (V₂, E₂)\) be graphs. We say that a pair of functions \(f = (f_v, f_e)\) is a graph morphism (or homomorphism) from \(𝐆₁\) to \(𝐆₂\) when \(f_v : V₁ → V₂\), \(f_e : E₁ → E₂\), and for any edge \(e = (v₁, v₂) ∈ E₁\) we have that

\[f_e(e)=(f_v(v_1),f_v(v_2)).\]

We write \(f : 𝐆₁ → 𝐆₂\) to indicate that \(f\) is a graph morphism from \(𝐆₁\) to \(𝐆₂\).

---

Exercise 2.1.1: Let \(s_1 : E_1 → V_1\) and \(t_1 : E_1 → V_1\) denote the source and target maps, respectively, for the graph \(𝐆_1\). Define \(s_2\) and \(t_2\) analogously for the second graph \(𝐆_2\). Show that \(f = (f_v, f_e)\) is a graph morphism from \(𝐆_1\) to \(𝐆_2\) if and only if for every \(e ∈ E_1\) we have \(f_v(s_1(e)) = s_2(f_e(e))\) and \(f_v(t_1(e)) = t_2(f_e(e))\).

---

The previous exercise shows that graph morphisms are precisely those pairs of maps that preserve the source and target maps. Since these maps are “relations” between graph elements, we see that graph morphisms are good candidates for a natural concept of a “function” between graphs.

Example 2.2 (the identity morphism)

We now consider an example of a graph morphism that, although trivial, will nonetheless be very important for us.

Let \(𝐆 = (V, E)\) be a graph and let \(\operatorname{id}_V : V → V\) and \(\operatorname{id}_E : E → E\) denote the identity maps on \(V\) and \(E\), respectively. We refer to the graph morphism \(\operatorname{id}_{𝐆} = (\operatorname{id}_V, \operatorname{id}_E)\) as the identity morphism on \(𝐆\). (This is analogous to the identity map on a set.)

---

Exercise 2.1.2: Show that for any graph \(𝐆\) the identity morphism \(\mathrm{id}_{𝐆} : 𝐆 → 𝐆\) is in fact a graph morphism.

---

We now introduce an analog of function composition for graph morphisms.

Let \(𝐆₁ = (V₁, E₁)\), \(𝐆₂ = (V₂, E₂)\), and \(𝐆₃ = (V₃, E₃)\) be graphs.

Let \(f : 𝐆₁ → 𝐆₂\) and \(g : 𝐆₂ → 𝐆₃\) be graph morphisms.

The composition \(g ∘ f\) of \(g\) with \(f\) is given by

\[g ∘ f = (gᵥ ∘ fᵥ, gₑ ∘ fₑ),\]

where \(g_v ∘ f_v\) is the usual function composition of \(g_v\) with \(f_v\) and \(g_e ∘ f_e\) is the usual function composition of \(g_e\) with \(f_e\).

Just as two functions compose to give a new function, so do morphisms compose to give a new morphism.

---

Exercise 2.1.3: Show that if \(f : 𝐆_1 → 𝐆_2\) and \(g : 𝐆_2 → 𝐆_3\) are graph morphisms then the composition \(g ∘ f\) is a morphism from \(𝐆_1\) to \(𝐆_3\).

---

Identity and composition of morphisms satisfy the following identities:

\[f ∘ \mathrm{id}_{𝐆₁} = f \qquad \mathrm{id}_{𝐆₂} ∘ f = f\]

\[h ∘ (g ∘ f) = (h ∘ g) ∘ f\]

The first two identities assert that \(\mathrm{id}_{𝐆₁}\) and \(\mathrm{id}_{𝐆₂}\) are the right and left identities with respect to morphism composition, and the third identity asserts that morphism composition is associative, as illustrated in the diagram below.

---

Exercise 2.1.4: Show that for any graphs \(𝐆_1\), \(𝐆_2\), \(𝐆_3\), and \(𝐆_4\), and any graph morphisms \(f : 𝐆_1 → 𝐆_2\), \(g : 𝐆_2 → 𝐆_3\), and \(h : 𝐆_3 → 𝐆_4\) we have that \(f ∘ \mathrm{id}_{𝐆_1} = f\), \(\mathrm{id}_{𝐆_2} ∘ f = f\), and \(h ∘ (g ∘ f) = (h ∘ g) ∘ f\).

---

Notice that these identities are the same ones that the usual identity function and composition operation on sets satisfy.

Other mathematical structures have their own definition of morphism, but there are always the identity morphisms and an associative composition operation, which leads to the abstract notion of a category. We will define categories more precisely below, but for now consider the following informal definition.

A category is a system of mathematical structures of a certain kind, together with morphisms between them, including all identity morphisms, and an associative composition operation.

2.2. Definition of a category

If \(f : A → B\) is a function or relation from \(A\) to \(B\), then \(A\) and \(B\) are called the domain and codomain (resp.) of \(f\); we denote these by \(\operatorname{dom}f\) and \(\operatorname{cod}f\) (resp.).

If \(f : A → B\) and \(g : B → C\), then \(\operatorname{cod}f = \operatorname{dom}g\) and we say that \(f\) and \(g\) are consecutive functions.

If \(f₁ : A_0 → A₁\) and \(f₂ : A₁ → A₂\) and \(f₃ : A₂ → A₃\), so that \(\operatorname{cod}f_i = \operatorname{dom}f_{i+1}\) for each \(i ∈ \{1, 2\}\), then we call \(f₁, f₂, f₃\) a chain of consecutive functions, and we write \(A_{0} \xrightarrow{f₁} A₁ \xrightarrow{f₂} A₂ \xrightarrow{f₃} A₃\).

If for all \(i ∈ ℤ\) we have \(f_i : A_{i-1} → A_i\), so that \(\operatorname{cod}f_i = \operatorname{dom}f_{i+1}\) for all \(i ∈ ℤ\). Then we call \(\dots, f_{i-1}, f_i, f_{i+1}, \dots\) a chain of consecutive functions, and we write

\[\cdots A_{i-1} \xrightarrow{f_{i}} A_{i} \xrightarrow{f_{i+1}} A_{i+1} \xrightarrow{f_{i+2}} A_{i+2} \cdots.\]

A category \(\mathcal C\) is specified by the following data:

objects:

\(A\), \(B\), \(C\), etc.

The class of objects of \(\mathcal C\) will be denoted by \(\mathcal C_{\mathrm{obj}}\).

morphisms:

\(f : A → B\), \(\; g : B → C\), \(\; h : C → D\), etc.

The class of morphisms of \(\mathcal C\) will be denoted by \(\mathcal C_{\mathrm{mor}}\).

identity morphisms:  

\(\operatorname{id}_A : A → A\), one for each object \(A\).

composition:

a partial binary operation on \(\mathcal C_{\mathrm{mor}}\) that takes each pair \(f : A → B\), \(g : B → C\) of consecutive morphisms to their composition morphism \(g ∘ f : A → C\) such that for all \(A\), \(B\), \(C\), \(D\) in \(\mathcal C_{\mathrm{obj}}\) and all consecutive morphism chains \(A \xrightarrow{f} B \xrightarrow{g} C \xrightarrow{h} D\) in \(\mathcal C_{\mathrm{mor}}\), the following identity and associative laws hold:

\[f ∘ \operatorname{id}_A = f = \operatorname{id}_B ∘ f \; \text{ and } \; h ∘ (g ∘ f) = (h ∘ g) ∘ f.\]

While we won’t dwell on this, note that in our above definition we avoided saying that the objects or the morphisms for a category form a set. There are difficulties that arise if we try to require that either of these collections, especially the objects of a category, form a set. There are various ways of formalizing what a “collection” is, but nothing we do here is going to require that we delve into these issues.

Example 2.3 (the category of sets)

Our prototypical category is the category of sets, which we denote by Set. It has sets for objects and has all functions \(f : A → B\) (for sets \(A\) and \(B\)) as its morphisms.

The identity morphisms in Set are the usual identity functions. (If \(A\) is a set, then for all \(a ∈ A\), \(\mathrm{id}_A(a) = a\).) Composition of morphisms in Set is the usual function composition.

---

Exercise 2.2.1: Show that Set is indeed a category.

---

The category Set illustrates why we can’t say the objects of a category form a set. In set theory we have Cantor’s Theorem, which implies that there cannot exist a set whose elements are all possible sets. Consequently the collection of all objects of Set is not iteself a set.

We would really like that Set is a category, since we came up with the definition of a category by trying to generalize some properties of functions to other classes of mathematical objects, like graphs. On that note, we also have a category of graphs.

Example 2.4 (the category of graphs)

The category Grph has (directed) graphs for objects and has graph homomorphisms for morphisms. The identity morphisms and morphism composition in Grph are those described in the previous section.

Given what we looked at in the previous section, the next exercise should follow rather quickly.

---

Exercise 2.2.2: Show that Grph is indeed a category.

---

Many familiar algebraic structures also form categories. We review definitions for those who are not yet fluent in algebra.

A monoid \(𝐌 = (M, e, ⋆)\) consists of a set \(M\) with a a unit element \(e ∈ M\) and a binary operation \(⋆ : M² → M\) such that for all \(x, y, z ∈ M\),

1. (identity) \(x ⋆ e = x = e ⋆ x\) and
2. (associativity) \((x ⋆ y) ⋆ z = x ⋆ (y ⋆ z)\).

Monoids have their own morphisms, called monoid morphisms (or homomorphisms).

Given monoids \(𝐌₁ = (M₁, e₁, ⋆)\) and \(𝐌₂ = (M₂, e₂, ∗)\) we say that a function \(f : M₁ → M₂\) is a monoid homomorphism from \(𝐌₁\) to \(𝐌₂\) provided \(f\) preserves the nullary (identity) and binary operations; that is,

1. \(f(e₁) = e₂\) and
2. for all \(x, y ∈ M₁\), \(f (x ⋆ y) = f(x) ∗ f(y)\).

We indicate that \(f : M₁ → M₂\) is a monoid homomorphism from \(𝐌₁\) to \(𝐌₂\) by writing \(f : 𝐌₁ → 𝐌₂\).

Example 2.5 (the category of monoids)

The objects of Mon are monoids and the morphisms are the monoid homomorphisms. For each monoid \(𝐌 = (M, e, ⋆)\) the corresponding identity morphism is the identity function on \(M\). Composition of morphisms in Mon is the usual function composition.

We haven’t stressed this until now, but make sure in the following exercise that you show that the composition of monoid morphisms is well-defined. That is, show that when you can compose two monoid morphisms \(f\) and \(g\) you always get a monoid morphism \(g ∘ f\) and the morphism you get doesn’t change depending on how you write \(f\) or \(g\).

---

Exercise 2.2.3: Verify that Mon is a category.

---

To summarize, here’s a list of the ingredients you need when

Defining a Category

1. Define the objects.
2. Define what constitutes a morphisms from an object A to an object B.
3. Define the identity functions and prove they are morphisms.
4. Define composition and prove that the composition of two morphisms is also a morphism.
5. Prove the identity law holds.
6. Prove the associativity of composition.

You may wish to go back over the categories Set, Grph, and Mon and make sure that each of these steps has been performed satisfactorily.

In many cases there will be little or nothing to show. Don’t let yourself be lulled into a stupor by this. Ensure that you are able to identify when there is work to be done, and that you can carry out this work even if it seems trivial.

---

Exercise 2.2.4: Think of a category for which the proof of the associative property of morphism composition is nontrivial.

---

We now consider the category of groups, which are essentially “monoids with inverses”.

A group \(𝐆 = (G, e, \phantom{i}^{-1}, ⋆)\) consists of a set \(G\) together with a nullary (constant) operation \(e\), a unary (inverse) operation \(\phantom{i}^{-1} : G → G\), and a binary operation \(⋆ : G² → G\), such that

1. \((G, e, ⋆)\) is a monoid.
2. \(x ⋆ x^{-1} = e\) for all \(x ∈ G\).

Now that we have seen some basic examples, we won’t fill in quite as many details in the examples that follow. However, we aim to provide just enough so that a typical reader could fill in whatever details we omit without too much difficulty.

---

Exercise 2.2.5: Define morphisms, identity morphisms, and composition of morphisms for groups and show that groups under these morphisms form a category Grp.

---

The examples of categories we have seen thus far are instances of what have come to be known as concrete categories.

A concrete category is one whose objects are sets and whose morphisms are functions on these sets (possibly satisfying some other special properties).

An abstract category is one whose objects are not sets or whose morphisms are not functions defined on sets. Our next example is somewhere in between. The objects are sets, but the morphisms are not necessarily total functions; that is, they may be defined on only a part of the source object.

Given sets \(A\) and \(B\), a total function \(f\) from \(A\) to \(B\) is what we typically mean by a “function” from \(A\) to \(B\).

In contrast, a partial function from \(A\) to \(B\) is a total function on some (potentially proper) subset \(\operatorname{dom}_f\) of \(A\).

In other words, \(f\) is a partial function from \(A\) to \(B\) if it is a function \(f : \operatorname{dom}_f → B\), for some subset \(\operatorname{dom}_f ⊆ A\). The set \(\operatorname{dom}_f\) is called the domain of \(f\), and \(B\) is the codomain of \(f\).

We write \(f : A ⇀ B\) to indicate that \(f\) is a partial function from \(A\) to \(B\). When \(f\) is a partial function it is understood that it is undefined outside of \(\operatorname{dom}_f\).

Note that a total function \(f : A → B\) is a partial function whose domain is \(\operatorname{dom}_f = A\).

Given partial functions \(f : A ⇀ B\) and \(g : B ⇀ C\) we define the composition \(g ∘ f : A ⇀ C\) to be the partial function with domain

\[\operatorname{dom}_{g\circ f}=\{x\in\operatorname{dom}_f\mid f(x)\in\operatorname{dom}_g\}\]

whose values are given by \((g ∘ f)(x) = g(f(x))\).

Example 2.6

The category Par has sets for objects and partial functions as its morphisms. The identity morphisms in Par are the identity functions and composition of morphisms in Par is the partial function composition described above.

We usually name a category after its objects. When we use nonstandard definitions of morphisms we name the corresponding category after the morphisms instead.

Be careful to note the distinction between the domain \(\operatorname{dom}_f\) of a partial function \(f : A ⇀ B\) and the domain \(A\) of \(f\) viewed as a morphism from Par. It will also be convenient to observe that every function is a partial function. This is why it is valid to designate the identity function for a set \(A\) as the identity morphism for \(A\) as an object of Par. Conventional functions (that is, partial functions \(f : A ⇀ B\) where \(\operatorname{dom}_f = A\)) are also called total functions for emphasis.

---

Exercise 2.2.6: Verify that Par is a category. (This is not completely trivial: check the domains in the associativity law.)

---

We are going to use sets again as the objects of a category, but this final example will have an even more broad generalization of functions as its morphisms.

Given sets \(A\) and \(B\), a relation \(f\) between \(A\) and \(B\) is a set \(f ⊆ A × B\).

It is common to write \(a \mathrel{f} b\) to indicate that \((a, b) ∈ f\) for a relation \(f\) between \(A\) and \(B\). In our context it will be useful to write \(f : A → B\) to indicate that \(f\) is a relation between \(A\) and \(B\).

Given relations \(R : A → B\) and \(S : B → C\) we define the composition \(S ∘ R : A → C\) by

\[S ∘ R = \{ (a,c) : (∃ b ∈ B) a \mathrel{R} b \text{ and } b \mathrel{S} c\}.\]

Again we have a category.

Example 2.7

The category Rel has sets for objects and has relations as its morphisms. The identity morphisms in Rel are the identity functions and composition of morphisms in Rel is the relation composition described above.

---

Exercise 2.2.7: Verify that Rel is a category.

---

2.3. Philosophy of category theory

The essential philosophy of category theory is that we ought to study mathematical structures from the categorical point of view. That is,

1. forget about the nature of the objects in question and
2. make constructions and study properties only using arrangements of morphisms.

Depending on one’s mathematical background, this restriction may seem artificial or obtuse. Even for those with some experience it can be surprising how little anything we actually prove has to do with “internal” (not describable via morphisms) aspects of the objects we study.

As a concrete example, take the study of elementary set theory. What do the theorems discuss? At first one is inclined to say “sets, of course”, but recall that in set theory we don’t really focus on the elements of sets as much as the functions between them. We don’t care if we are looking at \(\{a, b, c\}\) or \(\{1, 2, 3\}\). Rather, we are interested in the fact that there exists a bijection between them. Cantor’s Theorem, which we mentioned earlier, deals with the existence of a certain kind of function, while constructions like the Cartesian product and disjoint union can be written in terms of projections and injections.

The remainder of these notes will elaborate on this theme and its power to organize and unify much of mathematics.

---

2.4. Solutions

Solution to Exercise 2.1.1

First suppose that \(f\) is a graph morphism and let \(e ∈ E_1\).

By definition of graph morphism we have for any such edge \(e=(v_1,v_2)\) that \(f_e(e)=(f_v(v_1),f_v(v_2))\). It follows that \(s_2(f_e(e))=f_v(v_1)\).

Since \(s_1(e)=v_1\) and \(f_v(v_1)=s_2(f_e(e))\) we find that

\[f_v(s_1(e))=s_2(f_e(e)).\]

Similarly, note that \(t_2(f_e(e))=f_v(v_2)\). Since \(t_1(e)=v_2\) and \(f_v(v_2)=t_2(f_e(e))\) we find that

\[f_v(t_1(e))=t_2(f_e(e)).\]

This establishes the forward implication.

Now instead suppose for \(e ∈ E_1\) that we have \(f_v(s_1(e))=s_2(f_e(e))\) and \(f_v(t_1(e))=t_2(f_e(e))\). In order to show that \(f\) is a graph morphism we must show that for every \(e ∈ E_1\) we have \(f_e(e)=(f_v(v_1),f_v(v_2))\).

Let \(e ∈ E_1\). Since \(f_e\) maps edges from \(G_1\) to edges from \(G_2\) we know that \(f_e(e) ∈ E_2\) with source \(s_2(f_e(e))=f_v(s_1(e))\) and target \(t_2(f_e(e))=f_v(t_1(e))\). The edge \(f_e(e)\) can only be

\[f_e(e)=(f_v(s_1(e)),f_v(t_1(e))),\]

so we conclude that \(f\) is indeed a graph morphism.

---

Solution to Exercise 2.1.2.

In order to show that \(\mathrm{id}_G\) is a graph morphism we must show that for any edge \(e = (v_1,v_2) ∈ E\) we have that \(\mathrm{id}_e(e) = (\mathrm{id}_v(v_1), \mathrm{id}_v(v_2))\).

Let \(e = (v_1,v_2) ∈ E\). By definition of the identity function we find that

\[\mathrm{id}_e(e)=e=(v_1,v_2)=(\mathrm{id}_v(v_1),\mathrm{id}_v(v_2)),\]

as desired.

---

Solution to Exercise 2.1.3.

In order to show that \(g ∘ f\) is a graph morphism we must show for each \(e = (v_1,v_2) ∈ E_1\) that

\[(g ∘ f)_e(e)=((g ∘ f)_v(v_1),(g ∘ f)_v(v_2)).\]

Since \(f\) is a graph morphism we have for each \(e = (v_1,v_2) ∈ E_1\) that

\[f_e(e)=(f_v(v_1),f_v(v_2)).\]

Similarly, since \(g\) is a graph morphism we have for each \(e'=(v_3,v_4) ∈ E_2\) that

\[g_e(e') = (g_v(v_3),g_v(v_4)).\]

Taking \(e'=f_e(e)\) (and hence \(v_3=f_v(v_1)\) and \(v_4=f_v(v_2)\)) we observe that

\[\begin{split}(g ∘ f)_e(e) &= g_e(f_e(e)) \\ &= g_e(e') \\ &= (g_v(f_v(v_1)),g_v(f_v(v_2))) \\ &= ((g ∘ f)_v(v_1),(g ∘ f)_v(v_2)).\end{split}\]

Thus, \(g ∘ f\) is a graph morphism.

---

Solution to Exercise 2.1.4.

Let \(\mathrm{id} = \mathrm{id}_{G_1}\). By definition of graph morphism composition we have \(f ∘ \mathrm{id}_{G_1} = (f_v ∘ \mathrm{id}_v, f_e ∘ \mathrm{id}_e)\).

By definition of the identity function we find that \(f ∘ \mathrm{id}_{G_1} = (f_v,f_e)\), as desired.

Now instead let \(\mathrm{id} = \mathrm{id}_{G_2}\). By definition of graph morphism composition we have \(\mathrm{id}_{G_2} ∘ f = (\mathrm{id}_v ∘ f_v, \mathrm{id}_e ∘ f_e)\).

By definition of the identity function we find that \(\mathrm{id}_{G_2} ∘ f = (f_v,f_e)\), as desired.

We now show that \(h ∘ (g ∘ f) = (h ∘ g) ∘ f\). By definition of graph morphism composition and the associativity of function composition we have,

\[\begin{split}h ∘ (g ∘ f) &= (h_v ∘ (g ∘ f)_v, h_e ∘ (g ∘ f)_e) \\ &= (h_v ∘ (g_v ∘ f_v),h_e ∘ (g_e ∘ f_e)) \\ &= ((h_v ∘ g_v) ∘ f_v,(h_e ∘ g_e) ∘ f_e) \\ &= ((h ∘ g)_v ∘ f_v,(h ∘ g)_e ∘ f_e) \\ &= (h ∘ g) ∘ f.\end{split}\]

Thus, graph morphism composition is associative, as well.

---

Solution to Exercise 2.2.1.

Since the objects, morphisms, identities, and composition for Set are evidently well-defined it remains only to show that the identity and associative laws hold.

Let \(A\), \(B\), \(C\), and \(D\) be sets with \(f: A → B\), \(g: B → C\), and \(h: C → D\) functions.

By definition of the identity function we have for every \(a ∈ A\) that

\[(f ∘ \mathrm{id}_A)(a) = f(\mathrm{id}_A(a)) = f(a) = \mathrm{id}_B(f(a)) = (\mathrm{id}_B ∘ f)(a),\]

so the identity law does hold in Set. It follows immediately from the associativity of function composition that the associative law holds in Set.

---

Solution to Exercise 2.2.2.

The solution to this exercise was precisely the content of two previous exercises about graph morphisms, although we had not yet stated the category axioms at that point.

---

Solution to Exercise 2.2.3.

It is immediate that objects and morphisms in Mon are well-defined with the domain and codomain of each morphism \(f: 𝐌_2 → 𝐌_2\) an object of Mon.

We also see that the identity morphism \(\mathrm{id}_𝐌\) is a morphism from 𝐌 to itself since \(\mathrm{id}(e) = e\) and for any \(x,y ∈ M\) we have that

\[\mathrm{id} (x ⋆ y) = x ⋆ y = \mathrm{id}(x) ⋆ \mathrm{id}(y).\]

It remains to show that morphisms compose and that the identity and associative laws hold.

Let \(𝐌_i = (M_i, ⋆_i, e_i)\) for \(i ∈ \{1,2,3\}\) be monoids. In order to show that morphisms compose we must show that for every pair of monoid homomorphisms \(f: 𝐌_1 → 𝐌_2\) and \(g: 𝐌_2 → 𝐌_3\) we have that \(g ∘ f\) is a homomorphism from \(𝐌_1\) to \(𝐌_2\).

By the definition of homomorphism we have for all \(x,y\in M_1\) that

\[(g ∘ f)(e_1) = g(f(e_1)) = g(e_2) = e_3\]

and

\[\begin{split}(g ∘ f)(x ⋆_1 y) & = g(f(x ⋆_1 y)) \\ & = g(f(x) ⋆_2 f(y)) \\ & = g(f(x)) ⋆_3 g(f(y)) \\ & = (g ∘ f)(x) ⋆_3 (g ∘ f)(y).\end{split}\]

Thus, \(g ∘ f\) is a homomorphism from \(𝐌_1\) to \(𝐌_3\).

The identity law and associative law follow immediately from the corresponding identities for Set once we know that morphisms compose in Mon.

---

Solution to Exercise 2.2.4.

We define a category encoding Pythhagorean triples, called Pyth. The objects and morphisms of Pyth are nonnegative real numbers. Given objects \(a\) and \(c\) from Pyth we say that a nonnegative real \(b\) is a morphism in Pyth from \(a\) to \(c\) when \(a^2 + b^2 = c^2\).

We write \(b: a → c\) to indicate this. The identity morphism for \(a\) is \(0\). We see that \(0: a → a\) is indeed a morphism since \(a^2 + 0^2=a^2\). We write \(0_a: a → a\) to emphasize that we are viewing \(0\) as the identity morphism for \(a\).

Given morphisms \(b: a → c\) and \(d: c → e\) we define \(d ∘ b := \sqrt{b^2 + d^2}\). This is indeed a morphism from \(a\) to \(e\) since

\[a^2 + (\sqrt{b^2 + d^2})^2=a^2 + b^2 + d^2=c^2 + d^2=e^2.\]

The identity law holds since

\[b ∘ 0_a = \sqrt{0^2 + b^2} = b = \sqrt{b^2 + 0^2}=0_c ∘ b.\]

To see that the associative law holds let \(b: a → c\), \(d: c → e\), and \(f: e → g\) be morphisms and observe that

\[\begin{split}f ∘ (d ∘ b) &= f ∘ \sqrt{b^2 + d^2} \\ &= \sqrt{\bigl(\sqrt{b^2 + d^2}\bigr)^2 + f^2} \\ &= \sqrt{b^2 + d^2 + f^2} \\ &= \sqrt{b^2 + \bigl(\sqrt{d^2 + f^2}\bigr)^2} \\ &= \sqrt{d^2 + f^2} ∘ b \\ &= (f ∘ d) ∘ b.\end{split}\]

If this example is still too straightforward, construct a new category in analogy with Pyth which uses only nonnegative integers as objects and morphisms and defines \(b: a → c\) to be a morphism when there exists some \(n ≥ 2\) such that \(a^n + b^n = c^n\). Define composition as in Pyth. Proving that this new category is indeed a category requires the use of Fermat’s Last Theorem.

---

Solution to Exercise 2.2.5.

Let \(𝐆_i = (G_i, ⋆_i, \ ^{-1_i}, e_i)\) for \(i ∈ \{1,2,3\}\) be groups.

We say that a function \(f: G_1\to G_2\) is a (group) homomorphism from \(𝐆_1\) to \(𝐆_2\) just in case \(f:(G_1, ⋆_1, e_1) → (G_2, ⋆_2, e_2)\) is a monoid homomorphism and for every \(x ∈ G_1\) we have,

\[f(x^{-1_1}) = (f(x))^{-1_2}.\]

As usual, we write \(f: 𝐆_1 → 𝐆_2\) to indicate this.

Group homomorphisms are the morphisms for Grp.

The identity morphism for a group \(𝐆 = (G, ⋆, \ ^{-1}, e)\) is the identity function, \(\mathrm{id}_G: G → G\), on the set \(G\).

The argument that \(\mathrm{id} = \mathrm{id}_G\) is a group homomorphism is the same as the one given for the identity in Mon, except we must verify that \(\mathrm{id}\) preserves inverses.

Since \(\mathrm{id}(x^{-1}) = x^{-1} = (\mathrm{id}(x))^{-1}\), this is indeed the case, so the identities in Grp are indeed morphisms.

Composition of two morphisms \(f: 𝐆_1 → 𝐆_2\) and \(g: 𝐆_2 → 𝐆_3\) is given by the usual (set) function composition \(g ∘ f\). The argument here is again the same as for monoid homomorphisms, except we must check that composition respects the inversion operation.

Observe that by the definition of group homomorphism we have

\[(g ∘ f)(x^{-1_1}) = g(f(x^{-1_1})) = g((f(x))^{-1_2}) = (g(f(x)))^{-1_3} = ((g ∘ f)(x))^{-1_3},\]

so \(g ∘ f\) is a morphism in Grp.

Note that, again, the identity and associative laws follow immediately form the corresponding identities in Set once we know that morphisms compose in Grp.

---

Solution to Exercise 2.2.6.

Since we noted above that every total function is a partial function, we have that the identity function from a set to itself is a morphism in Par.

Given two morphisms \(f: A ⇀ B\) and \(g: B ⇀ C\) as a partial function with domain \(\mathrm{dom}_{g ∘ f} ⊆ A\) and codomain \(C\), the composition \(g ∘ f\) is always a morphism in Par with the appropriate domain and codomain.

It remains to show that the identity and associative laws hold.

Since any partial function \(f: A ⇀ B\) is a total function on \(\mathrm{dom}\), \(f: \mathrm{dom}_f → B\), we have,

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

so the identity law does hold in Par.

Let \(f\) and \(g\) be as before and let \(h: C ⇀ D\) be a partial function. Then,

\[\begin{split}\mathrm{dom}_{h ∘ (g ∘ f)} & = \{x ∈ \mathrm{dom}_{g ∘ f} | (g ∘ f)(x) ∈ \mathrm{dom}_h\} \\ & = \{x ∈ \{x ∈ \mathrm{dom}_f | f(x) ∈ \mathrm{dom}_g\}\mid(g \circ f)(x) ∈ \mathrm{dom}_h\} \\ & = \{x ∈ \mathrm{dom}_f | f(x) ∈ \mathrm{dom}_g\land(g \circ f)(x) ∈ \mathrm{dom}_h\} \\ & = \{x ∈ \mathrm{dom}_f | f(x) ∈ \{x \in\mathrm{dom}_g\mid g(x) ∈ \mathrm{dom}_h\}\} \\ & = \{x ∈ \mathrm{dom}_f | f(x) ∈ \mathrm{dom}_{h ∘ g}\} \\ & = \mathrm{dom}_{(h ∘ g) ∘ f}.\end{split}\]

Since \(h ∘ (g ∘ f)\) and \((h ∘ g) ∘ f\) are both partial functions with the same domain, it follows from the definition of partial function composition and the associativity of total function composition that for every \(x ∈ \mathrm{dom}_{h ∘ (g ∘ f)} = \mathrm{dom}_{(h ∘ g) ∘ f}\) we have that \((h ∘ (g ∘ f))(x) = ((h ∘ g) ∘ f))(x)\) agree everywhere on their domains. Therefore, they must be the same partial function, and the associative law holds in Par.

---

Solution to Exercise 2.2.7.

Note that for any set \(A\) the identity function is a subset of \(A × A\) and hence a morphism from \(A\) to itself, so the identity morphisms in Rel are well-defined.

Given any relations \(R: A → B\) and \(S: B → C\) we see that the composition \(S ∘ R\) is defined to be a subset of \(A × C\), so \(S ∘ R\) is a relation with the appropriate domain and codomain.

In order to see that the identity law holds in Rel observe that for any set \(A\) we have \(a\mathrel{\mathrm{id}_A}b\) if and only if \(a = b\), so

\[\begin{split}R ∘ \mathrm{id}_A &= \{(a,c) | (\exists b\in A) a \mathrel{\mathrm{id}_A} b \text{ and } b\mathrel{R} c \} \\ &= \{(a,c) | a \mathrel{R} c\} \\ &= \{(a,c) | (\exists b\in B) a \mathrel{R} b \text{ and } b \mathrel{\mathrm{id}_B} c\} \\ &= \mathrm{id}_B ∘ R,\end{split}\]

as desired.

Let \(R: A \to B\), \(S: B \to C\), and \(T: C \to D\). Suppose that \((a,d)\in T \circ(S \circ R)\). Then there exists some \(c\in C\) such that \(a\mathrel{S \circ R}c\) and \(c\mathrel{T}d\).

Again using the definition of composition we see that there exists some \(b\in B\) such that \(a\mathrel{R}b\) and \(b\mathrel{S}c\).

Since there exists some \(c\in C\) such that \(b\mathrel{S}c\) and \(c\mathrel{T}d\), we find that \(b\mathrel{T \circ S}d\). We then have that there exists some \(b\in B\) such that \(a\mathrel{R}b\) and \(b\mathrel{T \circ S}d\), so \((a,d)\in(T \circ S) \circ R\). Thus, \(T \circ(S \circ R)\subseteq(T \circ S) \circ R\). An essentially identical analysis shows the other containment, so the associative law holds in Rel.