[ct/3] Adjunctions


Adjoints

For a fixed field \(K\), consider the functors

\[ \begin{xy} \xymatrix{ \textbf{Set}\ar@<.5ex>[r]^V & \textbf{Vct}_K\ar@<.5ex>[l]^U } \end{xy} \]

\(U\) is the forgetful functor which takes the vector field to the corresponding set of vectors, while \(V\) takes \(\textbf{Set}\) to a basis. For set \(X\), \(V(X)\) is the finite formal set of linear combinations \(\sum r_i x_i\), with scalar coefficents \(r_i\), and \(x_i \in X\). For vector space \(W\), \(g : X \rightarrow U(W)\) extends to \(f : V(X) \rightarrow W\), and hence there is a bijection \[\varphi : \textbf{Set}(X, U(W)) \cong \textbf{Vec}_K(V(X), W)\]

Setting \(h : X' \rightarrow X, h^* g = g \circ h\), naturality in \(X, W\) are obtained from the following diagram:

\[ \begin{xy} \xymatrix{ \textbf{Set}(X, U(W))\ar[r]^\varphi\ar[d]^{h^*} & \textbf{Vec}_K(V(X), W)\ar[d]^{(Vh)^*} \\ \textbf{Set}(X', U(W))\ar[r]^\varphi & \textbf{Vec}_K(V(X'), W) } \end{xy} \]

As another example, consider the [free category](/ct/1#graphs-and-free-categories) over a small graph \(G\), \(C = FG\), and \(D : \textbf{Grph} \rightarrow \textbf{Cat}\) given by; it is related to the forgetful functor \(U : \textbf{Cat} \rightarrow \textbf{Grph}\) since \(D : G \rightarrow UB\) extends to \(D' : FG \rightarrow B\). Moreover \(D \mapsto D'\) is a natural isomorphism: \[\textbf{Cat}(FG, B) \cong \textbf{Grph}(G, UB)\]

In the category of small sets, the function \(g : T \times R \rightarrow S\), a function of two variables, can be considered as \(\varphi g : T \rightarrow \text{Hom}(R, S)\), a function of one variable, so that the following bijection holds: \[\varphi : \text{Hom}(T \times R, S) \cong \text{Hom}(T, \text{Hom}(R, S))\]

For modules \(A, B, C\) in a commutative ring \(K\), a similar bijection holds: \[\text{Hom}(A \otimes_K B, C) \cong \text{Hom}(A, \text{Hom}_K(B, C))\]

The `adjuction` from category \(X\) to category \(A\), where \(F, G\) are functors, is given by the triple \(\langle F, G, \varphi \rangle : X \rightharpoonup A\)

\[ \begin{xy} \xymatrix{ X\ar@<.5ex>[r]^F & A\ar@<.5ex>[l]^G } \end{xy} \]

while \(\varphi\) is a function such that: \[\varphi = \varphi_{x, y} : A(Fx, a) \cong X(x, Ga)\]

Here, \(A(Fx, a)\) is the bifunctor:

\[X^{op} \times A \xrightarrow{F^{op} \times \text{Id}} A^{op} \times A \xrightarrow{\text{hom}} \textbf{Set}\]

For all \(h : x' \rightarrow x, k : a \rightarrow a'\), it satisfies the diagrams:

\[ \begin{xy} \xymatrix{ A(Fx, a)\ar[r]^\varphi\ar[d]^{k_*} & X(x, Ga)\ar[d]^{(Gk)_*} \\ A(Fx, a')\ar[r]^\varphi & X(x, Ga') } \end{xy} \begin{xy} \xymatrix{ A(Fx, a)\ar[r]^\varphi\ar[d]^{(Fh)^*} & X(x, Ga)\ar[d]^{h^*} \\ A(Fx', a)\ar[r]^\varphi & X(x', Ga) } \end{xy} \]

Here, \(h^* = X(h, Ga), k_* = A(Fx, k)\).

An adjunction can also be described without talking about hom-sets, directly in terms of arrows. There is a bijection which assigns to each of the arrows \(f : Fx \rightarrow a\) arrows \(\varphi f = \text{rad } f : x \rightarrow Ga\), the `right adjunct` of \(f\), in such a way that the natural compositions hold: \[\varphi(k \circ f) = Gk \circ \varphi f \quad \varphi(f \circ Fh) = \varphi f \circ h\]

\(F\) is said to be `right adjoint` for \(G\), and \(G\) is the `left adjoint` for \(F\).

Every adjunction yields a universal arrow. Call the hom-set that contains the identity \(1 : Fx \rightarrow Fx\) the \(\varphi\)-image of \(\eta_x\). \(\eta_x\) is a universal arrow by [Yoneda's proposition](/ct/2#yoneda-lemma): \[\eta_x : x \rightarrow GFx \quad \eta_x = \varphi(1_{Fx})\]

The adjunction gives such a universal arrow \(\eta_x\) for every object \(x\). The function \(x \mapsto \eta_x\) is an NT \(I_x \rightarrow GF\). We obtain the following diagrams:

\[ \begin{xy} \xymatrix{ x'\ar[r]^{\eta_{x'}}\ar[d]_h & GFx'\ar[d]^{GFh} \\ x\ar[r]^{\eta_x} & GFx } \end{xy} \]

\[ \begin{xy} \xymatrix{ A(x', Fx')\ar[r]^{(Fh)_*}\ar[d]^\varphi & A(x', Fx)\ar[d]^\varphi & A(x, Fx)\ar[l]_{(Fh)^*}\ar[d]^\varphi \\ X(x', GFx')\ar[r]^{(GFh)_*} & X(x', GFx) & X(x, GFx)\ar[l]_{h^*} } \end{xy} \]

where \(h_* = X(1, h)\) and \(h^* = X(h, 1)\).

The bijection \(\varphi\) can be expressed as: \[\varphi(f) = G(f)\eta_x \quad f = Fx \rightarrow a\]

and we obtain:

\[ \begin{xy} \xymatrix{ A(Fx, Fx)\ar[r]^\varphi\ar[d]^{f_*} & X(x, GFx)\ar[d]^{(Gf)_*} \\ A(Fx, a)\ar[r]^\varphi & X(x, Ga) } \end{xy} \begin{xy} \xymatrix{ 1\ar@{|->}[r]\ar@{|->}[d] & \eta_x\ar@{|->}[d] \\ f \circ 1 \mapsto \varphi f\ar@{}[r]|{=} & Gf \circ \eta_x } \end{xy} \]

To summarize, every adjunction \(\langle F, G, \varphi \rangle : X \rightharpoonup A\) determines:

  1. A natural transform \(\eta : I_x \overset{\bullet}{\rightarrow} GF\) such that for each object \(x\), the arrow \(\eta_x\) is universal from \(x\) to \(G\), and right adjunct \(f : Fx \rightarrow a\) is detemined by \(\varphi f = Gf \circ \eta_x : x \rightarrow Ga\)
  2. Dually, another natural transform \(\epsilon : FG \overset{\bullet}{\rightarrow} I_x\) such that every arrow \(\epsilon_a\) is universal from \(G\) to \(a\), and left adjunct \(g : x \rightarrow Ga\) is determined by \(\varphi^{-1} g = \epsilon_a \circ Fg : Fx \rightarrow a\)

Moreover, the following composites are identities: \[G \xrightarrow{\eta G} GFG \xrightarrow{G \epsilon} G \quad F \xrightarrow{F \eta} FGF \xrightarrow{\epsilon F} F\]

\(\eta\) is termed `unit` and \(\epsilon\) is termed `counit` of the adjunction.

The adjunct is completely determined by one of the following items:

  1. Functors \(F, G\) and NT \(\eta : 1_x \overset{\bullet}{\rightarrow} GF\) such that every \(\eta_x : x \rightarrow GFx\) is universal. Then, \(\varphi f = Gf \circ \eta_x : x \rightarrow Ga\).
  2. Functor \(G : A \rightarrow X\), object \(F_0 x \in A\), and universal arrow \(\eta_x : x \rightarrow GF_0 x\), from \(x\) to \(G\). Then, functor \(F\) has object function \(F_0\) and, on arrow \(h : x \rightarrow x'\), by \(GFh \circ \eta_x \rightarrow \eta_{x'}\).
  3. Functors \(F, G\), and NT \(\epsilon : FG \overset{\bullet}{\rightarrow} I_A\) such that every \(\epsilon_a : FGa \rightarrow a\) is universal. Then, \(\varphi^{-1} g = \epsilon_a \circ Fg : Fx \rightarrow a\).
  4. Functor \(F : X \rightarrow A\), object \(G_0 \in X\), and universal arrow \(\epsilon_a : FG_0 a \rightarrow a\), from \(F\) to \(a\).
  5. Functors \(F, G\) and NTs \(\eta : I_X \overset{\bullet}{\rightarrow} GF\) and \(\epsilon : FG \overset{\bullet}{\rightarrow} I_A\).

Due to (v), we can also write the adjunct \(\langle F, G, \varphi \rangle\) as \(\langle F, G, \eta, \epsilon \rangle : A \rightharpoonup X\).

To prove (i), or its dual (iii), notice:

\[ \begin{xy} \xymatrix{ Fx\ar@{.>}[d]_g & x\ar[r]^{\eta_x}\ar[dr]_f & GFx\ar@{.>}[d]^{Gg} \\ a & & Ga } \end{xy} \]

To prove (ii), or its dual (iv), notice:

\[ \begin{xy} \xymatrix{ F_0 x\ar@{.>}[d] & x\ar[r]^{\eta_x}\ar[d]^h & GF_0 x\ar@{.>}[d] \\ F_0 x' & x'\ar[r]^{\eta_{x'}} & GF_0 x' } \end{xy} \]

To prove (v), given \(\eta, \epsilon\), define:

\[ \begin{xy} \xymatrix{ A(Fx, a)\ar@<.5ex>[r]^\varphi & X(x, Ga)\ar@<.5ex>[l]^\theta } \end{xy} \]

by \(\varphi f = Gf \circ \eta_x\) for all \(f : Fx \rightarrow a\), and \(\theta g = \epsilon_a \circ Fg\) for all \(g : x \rightarrow Ga\). Since \(G\) is a functor and \(\varphi\) an NT, we have: \[\varphi \theta g = G \eta_a \circ GFg \circ \eta_x = G \eta_a \circ \eta_{Ga} \circ g\]

Now, since \(G \eta_a \circ \eta_{Ga} = 1\), \(\varphi \theta\) is identity. Dually, \(\theta \varphi\) is also identity, and therefore, \(\varphi\) is a bijection with inverse \(\theta\). It is clearly natural, and hence an adjunction.

The result is very useful; for instance, (iii) and (iv) let us construct an adjuction whenever we have a universal arrow from or to all objects in a category. For example, \(C\) has finite products when for each pair \(\langle a, b \rangle \in C \times C\), when there is a universal arrow \(\Delta : C \rightarrow C \times C\) to \(\langle a, b \rangle\). From the result, we conclude that the function \(\langle a, b \rangle \rightarrow a \times b\) giving a product object is actually a functor \(C \times C \rightarrow C\), and this functor is right adjoint to \(\Delta\): \[\varphi : (C \times C)(\Delta c, \langle a, b \rangle) \cong C(c, a \times b)\]

Using the definition of arrows in \(C \times C\), we get: \[\varphi : C(c, a) \times C(c, b) \cong C(c, a \times b)\]

The counit of this adjuction is \(\langle a \times b, a \times b \rangle \rightarrow \langle a, b \rangle\); it is thus just projections of the product. The adjunction \(\varphi^{-1}\) sends the pair \(f : c \rightarrow a \times b\) to the pair \(\langle pf, qf \rangle\); this is the way in which the adjuction \(\varphi\) is determined by the counit \(\epsilon\).

Similarly, if the category \(C\) has coproducts \(\langle a, b \rangle \rightarrow a \sqcup b\), they define the coproduct functor \(C \times C \rightarrow C\) which is left adjoint to \(\Delta\): \[C(a \sqcup b, c) \cong (C \times C)(\langle a, b \rangle, \Delta c)\]

Similar arguments hold for limits. Proving universality is an easy way of showing that adjoints exist.

Part (v) describes all adjunctions by two simple identities:

\[ \begin{xy} \xymatrix{ F\ar[r]^{F \eta} & FGF\ar[d]^{\epsilon F} \\ & F\ar@{.}[ul]|{=} } \end{xy} \begin{xy} \xymatrix{ GFG\ar[d]^{G \epsilon} & G\ar[l]_{\eta G} \\ G\ar@{.}[ur]|{=} } \end{xy} \]

Any two left adjoints of the \(G : A \rightarrow X\) are naturally isomorphic. This follows immediately from the fact that universal arrows are unique upto isomorphism.

A functor \(G : A \rightarrow X\) is said to have a left adjoint iff for every \(x \in X\), the functor \(X(x, Ga)\) is representable as a functor of \(a \in A\). If \(\varphi : A(F_0 x, a) \cong X(x, Ga)\) is a representation of this functor, then \(F_0\) is the object function of the left adjoint of \(G\), for which \(\varphi\) is natural in \(a\) and gives the adjunction. This is simply a restatement of (ii).

If additive functor \(G : A \rightarrow M\) between \(\text{Ab}\)-categories \(A, M\) has left adjoint \(F : M \rightarrow A\), then \(F\) is additive, and the adjunction bijections \[\varphi : A(Fm, a) \cong M(m, Ga)\]

are isomorphisms of abelian groups for all \(m \in M, a \in A\). This can be shown as follows. If \(\eta : I \overset{\bullet}{\rightarrow} GF\) is the unit of the adjunction, then \(\varphi\) may be written as \(\varphi f = Gf \circ \eta_m\) for any \(f : Fm \rightarrow a\). If also \(f' : Fm \rightarrow a\), additivity of \(G\) gives: \[\varphi(f + f') = (Gf + Gf')\eta_m = \varphi f + \varphi f'\]

Therefore \(\varphi\) is a morphism of abelian groups. Next, take \(g, g' : m \rightarrow n\) in \(M\). Since \(\eta\) is nautural, \[GF(g + g') \circ \eta_m = \eta_n(g + g') = \eta_n g + \eta_n g'\]

On the other hand, since \(G\) is additive, \[G(Fg + Fg') \circ \eta_m = \eta_n g + \eta_n g'\]

The equality of these two results, along with the universal property of \(\eta_m\) show that \(F(g + g') = Fg + Fg'\). Hence \(F\) is additive. Dually, right adjoint of an additive functor is additive.

Reflective subcategories

Let \(f^* : A(a, -) \overset{\bullet}{\rightarrow} A(b, -)\) be the NT induced by the arrow \(f : b \rightarrow a\) of \(A\). Then \(f^*\) is monic iff \(f\) is epi, and \(f^*\) is epi iff \(f\) is a split monic. Note that \(f^* \mapsto f\) is the bijection \(Nat(A(a, -), A(b, -)) \cong A(b, a)\) given by the Yoneda lemma. Observe that for functors \(S, T : C \rightarrow B\), the NT \(\tau : S \overset{\bullet}{\rightarrow} T\) is epi in \(B^C\) iff every component \(\tau_c : S_c \rightarrow T_c\) is epi in \(B\) for \(B = \textbf{Set}\). To show this, notice that for \(h \in A\), \(f^*h = hf\). Hence the first result is just the definition of an epi \(f\). If \(f^*\) is epi, there is an \(h_0 : a \rightarrow b\) such that \(f^* h_0 = h_0 f^* = 1 : b \rightarrow b\), so \(f\) has a left inverse. The converse is immediate. Now apply Yoneda lemma to the NT: \[A(a, c) \xrightarrow{G_{a, c}} X(Ga, Gc) \xrightarrow{\varphi^{-1}} A(FGa, c)\]

It is determined by the image of \(1 : a \rightarrow a\), which is exactly the definition of counit \(\epsilon_a : FGa \rightarrow a\). But \(\varphi^{-1}\) is an isomorphism, hence this NT is monic or epi, respectively, whenver \(G_{a, c}\) is injective or surjective; i.e. when \(G_{a, c}\) is full or faithful.

For an adjunction \(\langle F, G, \eta, \epsilon \rangle : X \rightharpoonup A\), \(G\) is faithful iff every component \(\epsilon_a\) of the counit \(\epsilon\) is epi, and \(G\) is full iff every \(\epsilon_a\) is split monic. Hence, \(G\) is full and faithful iff each \(\epsilon_a\) is an isomorphism \(FGa \cong a\). This follows immediately from the last result.

A subcategory \(A\) of \(B\) is `reflective` in \(B\) when the inclusion function \(K : A \rightarrow B\) has left adjoint \(F : B \rightarrow A\). The functor \(F\) may be called a `reflector`, and the adjunction \(\langle F, K, \varphi \rangle = \langle F, \varphi \rangle : B \rightharpoonup A\) a `reflection` of \(B\) in subcategory \(A\). Since the inclusion functor \(K\) is always faithful, the counit \(\epsilon\) of the reflection is always epi. A reflection can be described in terms of the composite functor \(R = KF : b \rightarrow b\); indeed \(A \subset B\) is reflective in \(B\) iff there is a functor \(R : B \rightarrow B\) with values in the subcategory \(A\) and a bijection of sets: \[A(Rb, a) \cong B(b, a)\]

natural in \(b \in B, a \in A\). A reflection can also be described in terms of universal arrows: \(A \subset B\) is reflective iff to each \(b \in B\), there is an object \(Rb\) of the subcategory \(A\), and the arrow \(\eta_b : b \rightarrow Rb\) such that every arrow \(g : b \rightarrow a \in A\) has the form \(g = f \circ \eta_b\) for \(f : Rb \rightarrow a\) of \(A\). \(R\) is then the object function of a functor \(B \rightarrow B\) with values in \(A\). If a full subcategory \(A \subset B\) is reflective in \(B\), then each object \(a \in A\) is isommorphic to \(FKa\), and hence \(Ra \cong a\) for all \(a\). Dually, \(A \subset B\) is `coreflective` in \(B\) when the inclusion functor \(A \rightarrow B\) has right adjoint.

As an example, \(\textbf{Ab}\) is reflective in \(\textbf{Grp}\), for if \(G/[G, G]\) is the usual factor-commutator group of group \(G\), then \(\text{Hom}(G/[G, G], A) \cong \text{Hom}(G, A)\) for \(A\) abelian, and \(\textbf{Ab}\) is full in \(\textbf{Grp}\). As another example, consider the category of metric spaces \(X\) with arrows uniformly continuous functions. The full subcategory of complete metric spaces is reflective; the reflector sends each metric space to its completion. As a third example, consider the category of all completely regular Hausdorff spaces with arrows continuous functions. The full subcategory of this category is reflective; the reflector sends each completely regular space to its `Stone-Čech compatification`.

A coreflective subcategory of \(\textbf{Ab}\) is the full subcategory of all torsion abelian groups; the coreflector sends each abelian group \(A\) to the subgroup \(TA\) of all elements of finite order in \(A\).

Equivalence of categories

A functor \(S : A \rightarrow C\) is an isomorphism of categories when there is a functor \(T : C \rightarrow A\) such that \(ST = I : C \rightarrow C\) and \(TS = I : A \rightarrow A\). In this case, the identity NTs \(\eta : I \overset{\bullet}{\rightarrow} ST\) and \(\epsilon : TS \overset{\bullet}{\rightarrow} I\) make \(\langle T, S, \eta, \epsilon \rangle : C \rightharpoonup A\) into an adjunction. In other words, the two-sided inverse \(T\) of a functor \(S\) is a left-adjoint of \(S\); \(T\) is also a right-adjoint of \(S\).

In any category \(C\), the `skeleton` of \(C\) is any full subcategory \(A\), such that every object of \(C\) is isomorphic to exactly one object in \(A\). Then \(A\) is equivalent to \(C\), and any functor \(K : A \rightarrow C\) is an equivalence of categories, for we can select to each \(c \in C\) an isomorphism \(\theta_c : c \cong Tc\), with \(Tc\) an object of \(A\). We can then make \(T : C \rightarrow A\) a functor in exactly one way, so that \(\theta\) will become a natural isomorphism \(\theta : I \cong KT\). Moreover, \(TK \cong I\), so \(K\) is indeed an equivalence. This discussion can be summarized as: A category is equivalent to any of its skeletons. As an example, the category of all finite sets has as a skeleton the full subcategory with objects all finite ordinals. A category is called `skeletal` when any two isomorphic objects are identical; i.e. when a category is its own skeleton.

An `adjoint equivalence` of categories is an adjoint \(\langle T, S, \eta, \epsilon \rangle : C \rightharpoonup A\) such that both units \(\eta : I \overset{\bullet}{\rightarrow} ST\) and counits \(\epsilon : TS \overset{\bullet}{\rightarrow} I\) are the natural isomorphisms \(I \cong ST, TS \cong I\). Then \(\eta^{-1}, \epsilon^{-1}\) are also identities, and the triangular identities \(\epsilon T \bullet T \eta = 1\) and \(S \epsilon \bullet \eta S = 1\) can be written as \(T \epsilon^{-1} \bullet \eta^{-1} T = 1\) and \(\epsilon^{-1} S \bullet S \eta^{-1} = 1\). These state that \(\langle T, S, \epsilon^{-1}, \eta^{-1} \rangle : A \rightharpoonup C\) are adjunctions with unit \(\epsilon^{-1} : I \overset{\bullet}{\rightarrow} TS\) and counit \(\eta^{-1} : ST \overset{\bullet}{\rightarrow} I\). Thus, in an adjoint equivalence \(\langle T, S, -, - \rangle\), the functor \(T : C \rightarrow A\) is left adjoint of \(S : A \rightarrow C\) with unit \(\eta\), and \(T\) is right adjoint of \(S\) at the same time, with unit \(\epsilon^{-1}\).

The following properties about functor \(S : A \rightarrow C\) are equivalent:

  1. \(S\) is an equivalence of categories.
  2. \(S\) is part of the adjoint equivalence \(\langle T, S, \eta, \epsilon \rangle : C \rightharpoonup A\).
  3. \(S\) is full and faithful, and each object \(c \in C\) is isomorphic to \(Sa\) for some object \(a \in A\).

Trivially, (b) implies (a). To prove that (a) implies (c), note that \(ST \cong I\) shows that each \(c \in C\) has the form \(c \cong S(Tc)\) for an \(a = Tc \in A\). The natural isomorphism \(\theta : TS \cong I\) gives for each \(f : a \rightarrow a'\) the commutative diagram:

\[ \begin{xy} \xymatrix{ TSa\ar[r]^{\theta_a}\ar[d]_{TSf} & a\ar[d]^f \\ TSa'\ar[r]^{\theta_{a'}} & a' } \end{xy} \]

It follows that \(S\) is faithful. Symmetrically, \(ST \cong I\) proves that \(T\) is faithful. To show that \(S\) is full, consider any \(h : Sa \rightarrow Sa'\), and set \(f = \theta_a \circ Th \circ \theta_a^{-1}\). Then the above square commutes when \(Sf\) is replaced by \(h\), so \(TSf = Th\). Since \(T\) is faithful, and \(Sf = h\), it implies that \(S\) is full. To prove that (c) implies (b), we must construct \(S\) from a left adjoint \(T\). For each \(c \in C\), choose some object \(a_0 = T_0 c \in A\) and the isomorphism \(\eta_c\):

\[ \begin{xy} \xymatrix{ \eta_c : c\ar@{}[r]|{\cong}\ar[dr]_f & S(T_0 c)\ar[d]^{S_g} \\ & Sa } \end{xy} \]

For every arrow \(f : c \rightarrow Sa\), the composite \(f \circ \eta_c^{-1}\) has the form \(Sg\) because \(S\) is full; this \(g\) is unique because \(S\) is faithful. In other words, \(f = Sg \circ \eta_c\), for unique \(G\), so \(\eta_c\) is universal from \(c\) to \(S\). Therefore, \(T_0\) can be made a functor \(T : C \rightarrow A\) in exactly one way so \(\eta : I \overset{\bullet}{\rightarrow} ST\) is natural, and then \(T\) is left adjoint of \(S\) with unit the isomorphism \(\eta\). As with any adjunction, \(S \epsilon_a \bullet \eta_{S_a} = 1\) by putting \(c = Sa, f = 1\) in the above diagram. Thus, \(S \epsilon_a = (\eta_{S_a})^{-1}\) is invertible. Since \(S\) is full and faithful, the counit \(\epsilon_a\) is also invertible. Therefore, \(\langle S, T, \eta, \epsilon \rangle : C \rightharpoonup A\) is an adjunction equivalence.

If \(A\) is a full subcategory of \(C\) and every \(c \in C\) is isomorphic to some object of \(A\), then the insertion \(K : A \rightarrow C\) is an equivalence and is part of the adjoint equivalence \(\langle T, K, \eta, 1 \rangle : C \rightharpoonup A\) with counit identity. Therefore \(A\) is reflective in \(C\). To show this, in the previous result, let \(A\) be a full subcategory of \(C\) and \(S = K : A \rightarrow C\) is the insertion. For objects \(a \in A \subset C\), we can choose \(a_0 = a = Ka\), and \(\eta_{Ka}\) the identity. Then \(K \epsilon_a = 1\) and hence \(\epsilon_a = 1\) for all \(a\), completing the proof.

Duality theorems in functional analysis are often instances of equivalences. For example, let \(\textbf{CAb}\) be the category of compact topological abelian groups, and let \(P\) assign to every such group \(G\) its character group \(PG\), consisting of all continuous homomorphisms \(G \rightarrow \textbf{R}/\mathbb{Z}\). The `Pontrjagin duality theorem` asserts that \(P : \textbf{CAb} \rightarrow \textbf{Ab}^{op}\) is an equivalence of categories. Similarly, the `Gelfand-Naimark theorem` states that the functor \(C\) that assigns to each compact Hausdorff space \(X\) its abelian \(C^*\)-algebra of continuous complex-valued functions is an equivalence of categories.

Adjunctions for preorders

Preorders may be regarded as categories, with functors all order-preserving functions. Then order-reversing function \(\bar{L}\) from \(P\) to \(Q\) is the functor \(\bar{L} : P \rightarrow Q^{op}\).

Let \(P, Q\) be two preorders and \(L : P \rightarrow Q^{op}\) and \(R : Q^{op} \rightarrow P\) be two order-preserving functions. Then \(L\), regarded as a functor, is left-adjoint to \(R\) iff for all \(p \in P, q \in Q\): \[Lp \geq q \text{ in Q } \iff p \leq Rq \text{ in P}\]

A pair of order-preserving functions \(L, R\) satisfying this is called the `Galios connection` from \(P\) to \(Q\). When this is the case, there is exactly one adjunction \(\varphi\) making \(L\) the left adjoint of \(R\). For all \(p, q\), \(p \leq RLp\) and \(LRq \geq q\); hence also: \[Lp \geq LRLp \geq Lp \quad Rq \leq RLRq \leq Rq\]

To prove this, notice that \(P\) becomes a category when there is exactly one arrow \(p \rightarrow p'\) whenver \(p \leq p'\). Thus, the first condition states that there is a bijection \(\text{Hom}_{Q^{op}}(Lp, q) \cong \text{Hom}_P(p, Rq)\). Since each hom-set has exactly one element, this bijection is natural. The unit of the adjunction is the inequality \(p \leq RLp\) and the counit is \(LRq \geq q\). Thus, the second condition is the triangular identity connecting unit and counit. In the convenient case when \(P, Q\) are posets, these conditions become \(L = LRL, R = RLR\).

As a fundamental example, consider the group \(G\) acting on a set \(U\), by \(\langle \sigma, x \rangle \rightarrow \sigma \bullet x\) for all \(\sigma \in G, x \in U\). Take \(P = \mathscr{P}(U), Q = \mathscr{P}(G)\), the powersets. Let \(LX = \{\sigma \mid x \in X \implies \sigma \bullet x = x\}\), \(RS = \{\sigma \mid x \in S \implies \sigma \bullet x = x\}\); in other words, \(LX\) is the subgroup of \(G\) which fixes all points \(x \in X\) and \(RS\) is the set of fixed points of automorphisms of \(S\). Then, \(LX \geq S\) in \(Q\), iff \(\sigma \bullet x = x\) for all \(\sigma \in S, x \in X\), which in turn only holds if \(X \leq RS\) in \(P\). Therefore, \(L, S\) form an adjoint pair or Galios connection.

As another example, consider sets \(U, V\) and powersets \(\mathscr{P}(U), \mathscr{P}(V)\). For each function \(f : U \rightarrow V\), the direct image \(f_*(X) = \{f(x) | x \in X\}\) is order-preserving, and is hence \(f_* : \mathscr{P}(U) \rightarrow \mathscr{P}(V)\) is the corresponding functor. The inverse image \(f^*(Y) = \{x | \exists y : f(x) = y\}\) is also order preserving, and hence \(f^* : \mathscr{P}(V) \rightarrow \mathscr{P}(U)\) is the corresponding functor. Hence, the direct image \(f_*\) is left-adjoint to the inverse image \(f^*\).

As yet another example, consider Boolean algebras. Let \(\mathscr{P}(U)\) be a category. The diagonal functor \(\Delta : \mathscr{P}(U) \rightarrow \mathscr{P}(U) \times \mathscr{P}(U)\) has right adjoint \(\cap\), with \(\langle X, Y \rangle \mapsto X \cap Y\), and left adjoint \(\cup\), with \(\langle X, Y \rangle \mapsto X \cup Y\). If \(X\) is a fixed subset of \(U\), intersection with \(X\) is the functor \(X \cap - : \mathscr{P}(U) \rightarrow \mathscr{P}(U)\). Since \(X \cap Y \leq Z\) if \(Y \leq Z \cup X'\), where \(X'\) is the complement of \(X\) in \(U\), right adjoint of \(X \cap -\) is \(X' \cup -\). Thus, construction of suitable adjoints leads to \(\cap, \cup, '\). Now, let \(P : U \times V \rightarrow U\) be a projection from sets \(U, V\). Each subset \(S \in U \times V\) determines subsets of \(U\) by:

\[P_* S = \{x \mid \exists y \in V \text{ and } \langle x, y \rangle \in S\} \\ P_\# S = \{x \mid \forall y \in V \implies \langle x, y \rangle \in S\}\]

They arise from \(\langle x, y \rangle\) by applying universal and existential quantifiers. Also, \(P_* S\) is the direct image of \(S\) under projection \(P\). Now, for all subsets \(X \subset U\), we have: \[S \leq P^* X \iff P_* S \leq X \quad P^* X \leq S \iff X \leq P_* S\]

This states that inverse image operation \(P^*\) has left adjoint \(P_*\) and right adjoint \(P_\#\). In this sense, both quantifiers \(\exists\) and \(\forall\) can be interpreted as adjoints. This also has the following geometric interpretation: \(P^* X\) is the cylinder \(X \times Y \subset U \times V\) over the base \(X \in U\), \(P_* S\) is the projection of \(S \subset U \times V\) onto base \(U\), \(P_\# S\) is the largest subset \(X \subset U\) such that the cylinder is contained wholly within \(S\).

Cartesian closed categories

To assert that a category has finite products and coproducts is to say that the category has products, terminal, initial, and coproducts; thus the functors \(C \rightarrow \textbf{1}\) and \(\Delta: C \rightarrow C \times C\) have both left and right adjoints. Indeed, left adjoints give initial object and coproduct, while right adjoints give terminal object and product.

A category is termed `cartesian closed` if the following functors have specified right adjoints:

\[C \rightarrow \textbf{1} \quad C \rightarrow C \times C \quad C \xrightarrow{- \times b} C \\ c \mapsto 0 \quad c \mapsto \langle c, c \rangle \quad a \mapsto a \times b\]

These right adjoints are:

\[t \leftarrow\!\shortmid 0 \quad a \times b \leftarrow\!\shortmid \langle a, b \rangle \quad c^b \leftarrow\!\shortmid c\]

To specify the first is to specify the terminal object \(t \in C\). To specify the second is to specify, for each pair of objects \(a, b \in C\), the product object \(a \times b\) along with projections \(a \leftarrow a \times b \rightarrow b\): the projections consistite the counit of the adjunction, and \(\times\) is a bifunctor. The third specifies \(- \times b : C \rightarrow C\), a right adjoint with bijection: \[\text{Hom}(a \times b, c) \cong \text{Hom}(a, c^b)\]

natural in \(a\) and \(c\). By the `parameter theorem`, \(\langle b, c \rangle \rightarrow c^b\) is the object functor of bifunctor \(C^{op} \times C \rightarrow C\). Specifying the adjunction amounts to specifying specifying for all \(c, b\), the arrow: \[e : c^b \times b \rightarrow c\]

which is natural in \(c\), and universal from \(- \times b\) to \(c\). We call this \(e = e_{c, b}\) the `evaluation map`. It amounts to ordinary evaluation \(\langle f, x \rangle \mapsto fx\) in the following cases:

  1. \(\textbf{Set}\) is a cartesian closed category with \(b^c = \text{Hom}(b, c)\).
  2. \(\textbf{Cat}\) is a cartesian closed category with \(B^C\) the functor category.

A closely related example of adjunctions is the functor: \[- \otimes_K B : \text{K-Mod} \rightarrow \text{K-Mod}\]

which has right adjoint \(\text{Hom}_K(B, -)\); the adjunct is determined by counit \(\text{Hom}_K(B, A) \otimes_K B \rightarrow A\) given by the evaluation.

Transformations of adjoints

Next, we turn our attention to maps between adjunctions. Given two adjunctions:

\[\langle F, G, \eta, \epsilon \rangle : X \rightharpoonup A \\ \langle F', G', \eta', \epsilon' \rangle, X' \rightharpoonup A\]

we define the map between the two adjunctions by two functors \(K : A \rightarrow A'\) and \(L : X \rightarrow X'\) such that the following squares commute:

\[ \begin{xy} \xymatrix{ A\ar[r]^G\ar[d]^K & X\ar[r]^F\ar[d]^L & A\ar[d]^K \\ A'\ar[r]^G & X'\ar[r]^F & A' } \end{xy} \]

and such that the diagram of adjunctions and hom-sets commutes for all \(x \in X, a \in A\):

\[ \begin{xy} \xymatrix{ A(x, Fa)\ar[r]^\varphi\ar[d]_{K = K_{Fx, a}} & X(Gx, a)\ar[d]^{L = L_{x, Ga}} \\ A'(KFx, Ka)\ar@{}[d]|{=} & X'(Lx, LGa)\ar@{}[d]|{=} \\ A'(F'Lx, Ka)\ar[r]^{\varphi'} & X'(Lx, G'Ka) } \end{xy} \]

Here, \(K_{Fx, a}\) is the map \(f \mapsto Kf\) given by the functor \(K\) applied to each \(f : Fx \rightarrow a\).

The above condition is equivalent to \(L \eta = \eta' L\) and \(\epsilon' K = K \epsilon\). To prove this, set \(a = Fx\) and chase \(1 : Fx \rightarrow Fx\) around the commutative diagram to get the units \(\eta, \eta'\), and the equality:

\[\langle L, \eta : L \rightarrow LGF \rangle = \langle \eta', L : L \rightarrow G'F'L \rangle\]

where \(LGF = G'F'L\). Conversely, given the identity \(L \eta = \eta' L\) of the NTs, the definition of adjunctions \(\varphi, \varphi'\) by their units gives the required result. The case of counits is dual to this case.

Next, consider two adjunctions between the same two categories:

\[\langle F, G, \eta, \epsilon \rangle, \langle F', G', \eta', \epsilon' \rangle : X \rightharpoonup A\]

The following two NTs are said to be `conjugate` when the diagram commutes for every pair of objects \(x \in X, a \in A\):

\[ \begin{xy} \xymatrix{ A(F'x, a)\ar@{}[r]|{\overset{\varphi'}{\cong}}\ar[d]_{(\sigma_x)^* = A(\sigma_x, a)} & X(x, G'a)\ar[d]^{X(x, \tau_a) = (\tau_a)_*} \\ A(Fx, a)\ar@{}[r]|{\overset{\varphi}{\cong}} & X(x, Ga) } \end{xy}\tag{1}\label{conj} \]

Given the above two adjunctions, the NTs \(\sigma, \tau\) are said to be `conjugate` iff the following diagrams commute:

\[ \begin{xy} \xymatrix{ G'\ar[r]^\tau\ar[d]_{\eta G'} & G \\ GF'G\ar[r]_{G \sigma G'} & GF'G'\ar[u]^{G \epsilon'} } \end{xy} \begin{xy} \xymatrix{ F\ar[r]^\sigma\ar[d]_{F \eta'} & F' \\ FG'F'\ar[r]_{F \tau F'} & FGF'\ar[u]^{\epsilon F'} } \end{xy}\tag{2}\label{conj1} \]

\[ \begin{xy} \xymatrix{ FG'\ar[r]^{F \tau}\ar[d]^{\sigma G'} & FG\ar[d]^c \\ F'G'\ar[r]^{c'} & I_A } \end{xy} \begin{xy} \xymatrix{ I_X\ar[r]^\eta\ar[d]^{\eta'} & GF\ar[d]^{G \sigma} \\ G'F'\ar[r]^{\tau F'} & GF' } \end{xy}\tag{3}\label{conj2} \]

Also, given the NT \(\sigma : F \overset{\bullet}{\rightarrow} F'\), there is a unique \(\tau : G' \overset{\bullet}{\rightarrow} G\) such that \(\langle \sigma, \tau \rangle\) is conjugate. To prove this, consider \(\eqref{conj}\) with \(x = G'a\):

\[ \begin{xy} \xymatrix{ A(F'G'a, a)\ar@{}[r]|{\overset{\varphi'}{\cong}}\ar[d]_{(\sigma_x)^* = A(\sigma_x, a)} & X(G'a, G'a)\ar[d]^{X(G'a, \tau_a) = (\tau_a)_*} \\ A(FG'a, a)\ar@{}[r]|{\overset{\varphi}{\cong}} & X(G'a, Ga) } \end{xy} \]

Start with the identity arrow \(1 : G'a \rightarrow G'a\) on the top right, use the description of \(\varphi, \varphi'\) by unit and counit, and chase the diagram around \(1\) as follows:

\[ \begin{xy} \xymatrix{ \epsilon'_a\ar@{|->}[d] & 1 = 1_{G'a}\ar@{|->}[l]\ar@{|->}[d] \\ \epsilon'_a \circ \sigma_{G'a} \ar@{|->}[r] & G \epsilon'_a \circ G \sigma_{G'a} \circ \eta_{G'a} = \tau_a } \end{xy} \]

This yields \(\eqref{conj1}\) and its dual. A slightly different chase yields \(\eqref{conj2}\) and its dual:

\[ \begin{xy} \xymatrix{ \epsilon'_a\ar@{|->}[d] & 1\ar@{|->}[l]\ar@{|->}[d] \\ \epsilon'_a \circ \sigma_{G'a} = \epsilon_a \circ \tau_{Fa} & \tau_a\ar@{|->}[l] } \end{xy} \]

Next, suppose \(\sigma, \tau\) are not given. Then, applying Yoneda lemma to \(\varphi \circ (\sigma_x)^* \circ \varphi^{-1}\) yields a unique family of arrows \(\tau'_a\) for which \(\eqref{conj}\) commutes, and this family is an NT. Since each \(\epsilon_a : FGa \rightarrow a\) is universal from \(F\) to \(a\), there is also a unique family of arrows \(\tau''_a : G'a \rightarrow Ga\) such that \(\eqref{conj2}\) commutes. Since \(\eqref{conj}\) implies \(\eqref{conj2}\), \(\tau'_a = \tau''_a\); in other words, if \(\tau'' = \tau\) makes \(\eqref{conj2}\) commute, it also makes \(\eqref{conj}\) commute. Therefore \(\eqref{conj2}\) implies \(\eqref{conj}\). Given \(\sigma\), there is immediately a unique NT \(\tau : G' \rightarrow G\) for which \(\eqref{conj1}\) commutes; since \(\eqref{conj}\) implies \(\eqref{conj1}\), \(\tau_a = \tau'_a\). Hence solutions of \(\tau'_a\) of \(\eqref{conj}\) are necessarily natural; moreover \(\eqref{conj1}\) implies \(\eqref{conj}\), completing the proof.

The vertical compositions of:

\[\langle F, G, \eta, \epsilon \rangle \xrightarrow{\langle \sigma, \tau \rangle} \langle F', G', \eta' \epsilon' \rangle \xrightarrow{\langle \sigma', \tau' \rangle} \langle F'', G'', \eta'', \epsilon'' \rangle\]

are given by \(\langle \sigma, \tau \rangle \circ \langle \sigma', \tau' \rangle = \langle \sigma \bullet \sigma', \tau \bullet \tau' \rangle\)

For two given categories \(X, A\), we have a new category \(A^{(\text(adj)X)}\), the `category of adjunctions` from \(X\) to \(A\); its objects are adjunctions \(\langle F, G, \eta, \epsilon \rangle\) and arrows are conjugate pairs \(\langle \sigma, \tau \rangle\) with composition just noted. There are also two forgetful functors to the ordinary functor categories:

\[ \begin{xy} \xymatrix{ A^X \leftarrow A^{(\text{adj})X} & & [A^{(\text{adj}X)}]^{\text{op}} \rightarrow X^A \\ F\ar[d]^\sigma & \langle F, G, \eta, \epsilon \rangle\ar[d]^{\langle \sigma, \tau \rangle}\ar@{|->}[l]\ar@{|->}[r] & G\ar[d]^\tau \\ F' & \langle F', G', \eta', \epsilon' \rangle\ar@{|->}[l]\ar@{|->}[r] & G' } \end{xy} \]

A typical example is for \(\textbf{Set}\): \[\text{Hom}(S \times T, R) \cong \text{Hom}(S, \text{Hom}(T, R))\]

If \(t : T \rightarrow T'\) is a function between the two sets, then \(- \times t\) is a NT of functors \(- \times T \overset{\bullet}{\rightarrow} T'\). Its conjugate is the NT \(\text{Hom}(t \times -) : \text{Hom}(T', -) \rightarrow \text{Hom}(T, -)\); this is in the reverse direction as \(S \times T\) is covariant in \(\text{Hom}(T, R)\) and contravariant in \(T\). We may call the above an `adjuction with parameter` \(T \in \textbf{Set}\).

Given a bifunctor \(F : X \times P \rightarrow A\), assume for each \(p \in P\), that \(F(-, p) : X \rightarrow A\) has a right adjoint \(G(p, -) : A \rightarrow X\) via the adjunction: \[\text{Hom}(F(x, p), a) \cong \text{Hom}(x, G(p, a))\]

natural in \(x\) and \(a\). Then, there is a unique way to assign to each arrow \(h : p' \rightarrow p\) of \(P\), and each object \(a \in A\), an arrow \(G(h, p') \rightarrow G(h, p)\) of \(X\) so that \(G\) becomes a bifunctor \(P^{\text{op}} \times A \rightarrow X\) for which the bijection of the adjunction is natural in \(x, p, a\). This assignment of arrows \(G(h, a)\) to \(\langle h, a \rangle\) may also be described as the unique way to make \(G(h, -)\) an NT conjugate to \(F(-, h)\). To prove this, first notice that the bijection implies the following commutative diagram:

\[ \begin{xy} \xymatrix{ \text{Hom}(F(x, p), a)\ar@{}[r]|{\cong} & \text{Hom}(x, G(p, a)) \\ \text{Hom}(F(x, p'), a)\ar[u]^{F(x, h)_*}\ar@{}[r]|{\cong} & \text{Hom}(x, G(p', a))\ar[u]_{G(h, a)_*} } \end{xy} \]

This states precisely that \(G(h, -) : G(p', -) \overset{\bullet}{\rightarrow} G(p, -)\) must be chosen as the conjugate to \(F(-, h) : F(-, p) \rightarrow F(-, p')\). By the previous result, there is a unique choice of \(G(h, -)\) to realize this - the condition for conjugacy may be expressed in any of the five ways previously stated. For a second arrow \(h' : p' \rightarrow p''\), the uniqueness of choice of conjugates shows for \(h'h\) that \(G(h'h, -) = G(h, -) \circ G(h', -)\), so \(G(-, a)\) is a functor and \(G\) is a bifunctor, as required. Dually, given a bifunctor \(P^{\text{op}} \times A \rightarrow X\), where each \(G(p, -)\) has right adjoint \(F(-, p)\), there is a unique way to make \(F\) a bifunctor \(X \times P \rightarrow A\).

Composition of adjoints

Two adjunctions compose to give a single adjunction as follows. Given two adjunctions:

\[\langle F, G, \eta, \epsilon \rangle : X \rightharpoonup A \\ \langle \bar{F}, \bar{G}, \bar{\eta}, \bar{\epsilon} \rangle : A \rightharpoonup D\]

the composite functors yield the adjunction: \[\langle \bar{F}F, G\bar{G}, G\bar{\eta}F . \eta, \bar{\epsilon} . \bar{F}\epsilon\bar{G} \rangle : X \rightharpoonup D\]

We prove it by noticing that, with hom-sets, the two given adjunctions yield a composite isomorphism, natural for all \(x \in X, d \in D\): \[D(\bar{F}Fx, d) \cong D(Fx, \bar{G}d) \cong X(x, G\bar{G}d)\]

This makes the composite \(\bar{F}F\) left adjoint to \(G\bar{G}\). Setting \(d = \bar{F}Fx\), and applying these two isomorphisms to the identity \(1 : \bar{F}Fx \rightarrow \bar{F}Fx\), we find that the unit of composite adjunction is \(x \xrightarrow{\eta x} GFx \xrightarrow{G\bar{\eta}Fx} G\bar{F}\bar{F}Fx\), so is \(G\bar{\eta}F . \eta\), as asserted. The dual argument yields counit \(\bar{\epsilon} . \bar{G}\epsilon\bar{F}\), as required.

Using this composition, we may form a category \(\textbf{Adj}\), whose objects are small categories \(X, A, D\), and whose arrows are adjunctions \(\langle F, G, \eta, \epsilon \rangle : X \rightharpoonup A\) composed as above; the identity arrow is \(A \rightharpoonup A\). This category has additional structure; each hom-set \(\textbf{Adj}(X, A)\) may be regarded as a category; the category of adjunctions \(A^{(\text{adj})X}\) has already been described. Its objects are these adjunctions, and arrows are conjugate pairs \(\langle \sigma, \tau \rangle\) under "vertical" composition.

Given two conjugate pairs:

\[\langle \sigma, \tau \rangle : \langle F, G, \eta, \epsilon \rangle \overset{\bullet}{\rightarrow} \langle F', G', \eta', \epsilon' \rangle : X \rightharpoonup A \\ \langle \bar{\sigma}, \bar{\tau} \rangle : \langle \bar{F}, \bar{G}, \bar{\eta}, \bar{\epsilon} \rangle \overset{\bullet}{\rightarrow} \langle \bar{F'}, \bar{G'}, \bar{\eta'}, \bar{\epsilon'} \rangle : A \rightharpoonup D\]

The "horizontal" composite NTs yield a conjugate pair \(\bar{\sigma} \sigma : \bar{F}F \overset{\bullet}{\rightarrow} \bar{F'}F'\), \(\tau \bar{\tau} : G'\bar{G'} \overset{\bullet}{\rightarrow} G\bar{G}\) of NTs for the conjugate adjunction. The proof may be visualized by the commutative diagram of hom-sets:

\[ \begin{xy} \xymatrix{ D(\bar{F'}F'x, d)\ar@{}[r]|{\cong}\ar[d]^{(\bar{\sigma} \sigma x)^*} & A(F'x, \bar{G'}d)\ar@{}[r]|{\cong}\ar[d]^{(\sigma x)^* (\bar{\tau} d)_*} & X(x, G'\bar{G'}d)\ar[d]^{(\tau \bar{\tau_d})_*} \\ D(\bar{F}Fx, d)\ar@{}[r]|{\cong} & A(Fx, \bar{G}d)\ar@{}[r]|{\cong} & X(x, G\bar{G}d) } \end{xy} \]

Moreover, this operation of horizontal composition is a bifunctor: \[\textbf{Adj}(A, D) \times \textbf{Adj}(X, A) \cong \textbf{Adj}(X, D)\]

This means that \(\textbf{Adj}\) is a `two-dimensional category` as is \(\textbf{Cat}\).

Subsets and characteristic functions

The characteristic function of a subset \(S \subset X\) is the two-valued function \(\psi_S : X \rightarrow \{0, 1\}\) on \(X\) with values: \[\psi_S x = 0 \text{ if } x \in S \quad \psi_S x = 1 \text { if } x \in X, x \notin S\]

Put differently, \(\{0\} \subset \{0, 1\}\) is the simplest non-trivial subset. An arbitrary subset \(S \subset X\) can be mapped into this simple subset by \(\psi_S\), as defined. This produces the pullback map:

\[ \begin{xy} \xymatrix{ S\ar[r]\ar[d] & \{0\}\ar[d] \\ X\ar[r]^{\psi_S} & \{0, 1\} } \end{xy} \]

These appear in probability theory; in logic, \(\{0, 1\}\) are "truth values", and "truth" is represented by \(\{0\}\). The monomorphism \(t : \{0\} \rightarrow \{0, 1\}\) is termed `subobject classifier` for the category of sets. A subobject classifier for the category \(C\) with terminal object \(1\) is defined to be \(t : 1 \rightarrow \Omega\), such that every monomorphism \(m\) in \(C\) is a pullback of \(t\) in a unique way. In other words, for each \(m\), there exists a pullback square:

\[ \newdir{ >}{{}*!/-7pt/\dir{>}} \begin{xy} \xymatrix{ S\ar@{ >->}[d]^m\ar[r] & 1\ar@{ >->}[d]^t \\ X\ar[r]^\psi & \Omega } \end{xy} \]

The top horizontal arrow is the unique map to terminal object \(1\), and the lower horizontal arrow acts as the `characteristic function` of subobject \(S\), while the universal morphism \(t : 1 \rightarrow \Omega\) may be called "truth".

For example, take \(C\) to be a category of functions \(f : X \rightarrow Y\). Here a monomorphism \(g \rightarrowtail f\) is a function \(S \rightarrow T\) between a pair of subsets \(S \subset X\) and \(T \subset Y\), such that \(g(s) = f(s)\) for all \(s \in S\). This means that the following diagram commutes:

\[ \begin{xy} \xymatrix{ S\ar[r]^g\ar[d] & T\ar[d] \\ X\ar[r]^f & Y } \end{xy} \]

In this case, there are three types of elements in \(X\): those \(x \in S\), those \(x \notin S\), but with \(gx \in T\), and those \(x \notin S, gx \notin T\). We may then define a characteristic function with three values by setting:

\[\psi_S x = \begin{cases} 0 \quad x \in S \\ 1 \quad x \notin S, fx \in T \\ 2 \quad fx \notin T \end{cases}\]

Again, this prescription provides a pullback map:

\[ \begin{xy} \xymatrix{ X\ar[rr]\ar@{ >->}[dd]\ar[dr]^g & & \{0\}\ar[dd]\ar[dr] & \\ & T\ar@{ >->}[dd]|{\hole}\ar[rr] & & \{0\}\ar@{ >->}[dd] \\ X\ar[dr]^f\ar[rr]^{\psi_S} & & \{0, 1, 2\}\ar[dr]^j & \\ & Y\ar[rr]^{\psi_T} & & \{0, 2\} } \end{xy} \]

of objects \(X \rightarrow Y\) and \(j : \{0, 1, 2\} \rightarrow \{0, 1\}\) in the category of functions, whose function \(j\) is given by \(j0 = 0, j1 = 1, j2 = 2\). Thus, the inclusion \(j\) is the subobject classifier for the category of functions.

As an example, consider the arrow category \(\textbf{2}\) as a category with two objects \(0\) and \(1\), and only one non-identity arrow \(a : 0 \rightarrow 1\). Thus, an ordinary function \(f\) is the same thing as a functor \(\textbf{2} \rightarrow \textbf{Sets}\). Hence, we have constructed above the functor category for \(\textbf{Sets}^2\).

Categories like sets

An elementary `topos` is defined to be a category \(E\) with the following properties:

  1. \(E\) has all finite limits.
  2. \(E\) has a subobject classifier.
  3. \(E\) is cartesian closed.

Requiring \(E\) to be cartesian closed means requring each functor "product with b" (i.e. \(a \mapsto a \times b\)) has for each \(b \in E\) a right adjoint \(c \mapsto c^b\) so that: \[\text{Hom}(a \times b, c) \cong \text{Hom}(a, c^b)\]

In other words, \(E\) has exponentials.

The category \(\text{Sets}\) of all small sets is a topos, as is \(\textbf{Sets}^{C^\text{op}}\), the set of all contravariant functors on small category \(C\). Such a functor \(F : C^{\text{op}} \rightarrow \textbf{Sets}\) is called a [presheaf](/ag/1#definition-of-presheaf-and-sheaf). This is a reference to topology where \(C\) is the set of all open subsets \(U\) of topological space \(X\); in this case, presheaf \(F\) assigns to each \(U\) a set \(F(U)\), with functorial properties for continuous maps \(U \rightarrow V\). If \(F\) is the set of continuous real-valued functions on \(U\), it is said to be a [sheaf](/ag/1#definition-of-presheaf-and-sheaf). A topological structure is essentially described by its topos of sheaves of \(\textbf{Sets}\). Various logical properties are reflected in subobject classifiers \(\Omega\) of a topos. Suitable toposes can replace the category of sets as a foundation for mathematics.