[ct/3] Adjunctions

Paris, Chennai


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 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:
$$\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. 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. 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.