4. Isomorphism

4.1. A categorical view of bijections

If we think of morphisms as the “functions” between objects in a category, then it is natural to ask whether there is a categorical analog of a bijection.

A morphism \(f: A → B\) is called an isomorphism if there exists a morphism \(g: A → B\) such that \(g ∘ f=\operatorname{id}_A\) and \(f ∘ g=\operatorname{id}_B\). We write \(f^{-1}\) to denote \(g\) when it exists.

---

Exercise 4.1.1: Show that there exists a unique choice for \(g\) in the above definition, from which it follows that the notation \(f^{-1}\) is unambiguous.

Exercise 4.1.2: Show that every morphism from a object to an object in a category is an isomorphism.

---

In \(\mathbf{Set}\) a function is an isomorphism if and only if it is a bijection, so isomorphism is a valid generalization of bijection.

In \(\mathbf{Grph}\) the isomorphisms are the morphisms which are bijective on both vertices and edges. In \(\mathbf{Mon}\) the isomorphisms are the bijective morphisms. However, in \(\mathbf{Pos}\) the isomorphisms are not just the bijective morphisms. Consider for example the objects \(\mathcal{A}= \langle \{a,b,c\}, \leq \rangle\), \(\mathcal{B}= \langle \{u,v,w\}, \preccurlyeq \rangle\) in \(\mathbf{Pos}\) shown in the figure below.

Let \(f\colon \mathcal A\to \mathcal B\) be the morphism defined as follows: \(f(a) = u\), \(f(b) = v\), \(f(c) = w\). Then \(f\) is clearly bijective and preserves the ordering—i.e., \(x \leq y \implies f(x) {{\preccurlyeq}}f(y)\). However, the inverse map \(f^{-1}\colon \mathcal B\to \mathcal A\) is not order preserving, and \(\mathcal A\) and \(\mathcal B\) are not isomorphic posets.

---

Exercise 4.1.3: What are the isomorphisms of Rel?

---

Let \(\mathcal X= \langle X, \leq \rangle\) and \(\mathcal Y= \langle Y, \preccurlyeq \rangle\) be objects in \(\mathbf{Pos}\). Recall, the morphisms are the order-preserving maps; that is, \(\phi : \mathcal X\rightarrow \mathcal Y\) is a morphism of \(\mathbf{Pos}\) iff \(a \leq b\) implies \(\phi(a) \preccurlyeq \phi(b)\).

Let \(\mathcal L= \langle L, \vee, \wedge\rangle\) and \(\mathcal M= \langle M, \curlyvee, \curlywedge\rangle\) be objects in \(\mathbf{Lat}\). Then \(\psi: \mathcal L\rightarrow \mathcal M\) is a morphism in \(\mathbf{Lat}\) iff for all \(a, b \in L\) we have \(\psi( a \vee b ) = \psi(a) \curlyvee \psi(b)\) and \(\psi( a \wedge b ) = \psi(a) \curlywedge \psi(b)\).

It is not hard to see that a lattice \(\langle L, \vee, \wedge\rangle\) can be represented by a poset \(\langle L, \leq \rangle\) with respect to the partial order \(\leq\) defined by \((\forall x, y) (x \leq y\; \longleftrightarrow \; x \wedge y = x)\).

---

Exercise 4.1.4: Show that every lattice homomorphism is order-preserving. Show that not every order-preserving map is a lattice homomorphism.

Exercise 4.1.5: Find a nontrivial category with no nontrivial isomorphisms.

Exercise 4.1.6: Find a nontrivial category where every morphism is an isomorphism.

---

4.2. Monomorphism

We can also give a categorical generalization of injections.

A morphism \(f\colon A\to B\) is called a monomorphism if for every object \(X\) and every pair \(h,h'\colon X\to A\) of morphisms, \(f\circ h=f\circ h'\) implies \(h=h'\). When \(f\) is a monomorphism we often say “\(f\) is mono” and write \(f\colon A\rightarrowtail B\).

---

Exercise 4.2.1: Show that in Set the monomorphisms are precisely the injective functions.

---

A morphism \(h\colon X\to A\) is sometimes called a generalized element of \(A\). A morphism \(f\) is mono just in case it is injective on the generalized elements of its domain.

The monomorphisms \(f\) in \(\mathbf{Set}\) are precisely those that are injective on the global elements \(h\colon\mathbf{1}\to A\). Thus, in \(\mathbf{Set}\), to decide whether a morphism is mono, it suffices to check \(X=\mathbf{1}\).

---

Exercise 4.2.2: Does this condition suffice in Grph as well?

---

4.3. Epimorphism

The dual concept to monomorphism generalizes surjections to arbitrary categories.

A morphism \(f\colon A\to B\) is called an epimorphism if for every object \(Y\) and pair \(y_1,y_2\colon B\to Y\) of morphisms, \(y_1\circ f=y_2\circ f\) implies \(y_1=y_2\). When \(f\colon A\to B\) is an epimorphism we often say “\(f\) is epi” and write \(f\colon \twoheadrightarrow B\).

---

Exercise 4.3.1: Show that in Set the epimorphisms are precisely the surjective functions.

Exercise 4.3.2: Is there a single object that we can use in place of a generic \(Y\) to check that a function is epi in Set?

---

4.4. Isomorphism

Recall from above, a morphism \(f\colon A \to B\) in a category \(\mathcal C\) is said to be an isomorphism if there is a morphism \(g\colon B \to A\) such that \(f ∘ g = \mathrm{id}_B\) and \(g ∘ f = \mathrm{id}_A\). When this happens, we say that

• \(g\) is an inverse for \(f\)
• \(f\) is an inverse for \(g\)
• \(A\) and \(B\) are isomorphic, denoted \(A \cong B\)
• the pair \(f, g\) witnesses \(A\cong B\).

Example. In the category determined by a partially ordered set, the only isomorphisms are the identities, and in a preorder \(X\) with \(x, y \in X\) we have \(x \cong y\) iff \(x \leq y\) and \(y \leq x\).

---

4.5. Solutions

Exercise 4.1.1

Solution (to do).

---

Exercise 4.1.2

Solution (to do).

---

Solution to Exercise 4.1.3.

Let \(\psi: 𝐋 → 𝐌\) be a lattice homomorphism. Fix \(a, b ∈ L\) with \(a ≤ b\).

If \(a\) and \(b\) have a greatest lower bound (as they must in a lattice), then the statement \(a ≤ b\) is equivalent to \(a ∧ b = a\). Therefore,

\[ψ(a) = ψ (a ∧ b) = ψ(a) ⋏ ψ(b).\]

(The second equality holds since \(ψ\) is a lattice homomorphism.)

The equation \(ψ(a) = ψ(a) ⋏ ψ(b)\) is equivalent to \(ψ(a) ⪯ ψ(b)\). Thus, if \(ψ\) is a lattice homomorphism and \(a ≤ b\), then \(ψ(a) ⪯ ψ(b)\). That is, lattice homomorphisms are order preserving.

The converse is false. That is, an order preserving map need not be a lattice homomorphism. For example, consider the two lattices shown in the Hasse diagrams below.

To do: insert diagram here.

The map \(ϕ: \{0, 1, 2, 3\} → \{a, b, c\}\) defined by \(ϕ(0) = a\), \(ϕ(2) = b = ϕ(3)\), and \(ϕ(1) = c\) is clearly order preserving, but it is not a lattice homomorphism. For example, \(a = ϕ(0)\) \(= ϕ(2 ∧ 3)\) \(≠ ϕ(2) ∧ \phi(3)\) \(= b ∧ b = b\).

---

Exercise 4.1.4

Solution (to do).

---

Exercise 4.1.5

Solution (to do).

---

Exercise 4.1.6

Solution (to do).

---

Exercise 4.2.1

Solution (to do).

---

Exercise 4.2.2

Solution (to do).

---

Exercise 4.3.1

Solution (to do).

---

Exercise 4.3.2

Solution (to do).