Let $F:\mathbf{C}\rightarrow \mathbf{D}$ be left adjoint to $G:\mathbf{D}\rightarrow \mathbf{C}$. Let $\eta:1_\mathbf{C}\rightarrow GF, \varepsilon:FG \rightarrow 1_\mathbf{D}$ be the unit and co-unit, respectively, of the adjunction (see earlier post). Then we know that the triangle identities hold: $\varepsilon F \circ F\eta = 1_F, G\varepsilon \circ \eta G = 1_G$. Let $\mathbf{C_0}$ be the full subcategory of $\mathbf{C}$ generated by the objects $X$ of $\mathbf{C}$ for which $\eta_X:X\rightarrow GFX$ is an isomorphism, $\mathbf{D_0}$ be the full subcategory of $\mathbf{D}$ generated by the
objects $Y$ of $\mathbf{D}$ for which $\varepsilon_Y:FG Y\rightarrow Y$ is an
isomorphism (full means that for any two objects of the subcategory, all arrows in the ambient category are arrows of the subcategory). Then $F$ restricts to an equivalence between $\mathbf{C_0}$ and $\mathbf{D_0} $.
Indeed, let $F_0: = F|_{\mathbf{C_0}}, G_0:=G|_{\mathbf{D_0}}$. We show $G_0F_0 \cong 1_\mathbf{C_0}, F_0G_0\cong 1_\mathbf{D_0}$. But that will be obvious from the definition of $\mathbf{C_0}$ and $\mathbf{D_0}$ if we know that for $X\in \mathbf{C_0}, FX\in \mathbf{D_0}$ and for $Y\in \mathbf{D_0}, GY\in \mathbf{C_0}$. We prove the claim for $X\in \mathbf{C_0}$. The other may be proven analogously (using the other triangle identity). Let $X\in \mathbf{C_0}$. Then $\eta_X$ is iso. So $F\eta_X$ is iso. But by the first triangle identity, $\varepsilon_{FX}F\eta_X=1_{FX}$. Multiplying on the right of both sides by $(F\eta_X)^{-1}$ (since it is iso), yields $\varepsilon_{FX} = (F\eta_X)^{-1}$. So $\varepsilon_{FX}$ is iso as well. Hence $FX$ is in $\mathbf{D_0}$.
We now apply this result to the particular adjunction between $\mathbf{Top}$ and $\mathbf{Loc}$ from the previous post. Recall that in the adjunction $\Omega \dashv pt$, we had that the transpose under the adjunction of a locale morphism $h:\Omega X \rightarrow A$ is $\bar{h}:X\rightarrow ptA$, where $\bar{h}(x)=h\Omega(x)$, and the transpose under the adjunction of a continuous map $h:X\rightarrow ptA$ is $\hat{h}=\phi_A^{op}\Omega(h)$, where, recall, $\phi_A$ is a frame morphism defined by $\phi_A(a)=\{p\;|\;p^\star(a)=1\}$ and $\Omega ptA$ is defined by the requirement that $\phi_A$ is surjective.
Hence for $X \in \mathbf{Top}, \eta_X=\bar{1_FX}$ and so $\eta_X(x) = \Omega(x)$. What does it mean for $\eta_X$ to be surjective? It means every point of the locale $\Omega X$ (recall a point $p$ of a locale $A$ is a locale morphism $2\rightarrow A$ and $p$ is the opposite of a frame morphism $p^\star$) is of the form $\Omega(x)$ for some $x\in X$. What does it mean for $\eta_X$ to be injective? It means that if a point of $\Omega(X)$ is of the form $\Omega(x)$ for some $x\in X$ then that $x$ is unique. So $\eta_X$ is a bijection when every point of $\Omega(X)$ is of the form $\Omega(x)$ for a unique $x\in X$. Suppose $\eta_X$ is a bijection. Then is it an isomorphism? Clearly, the inverse, if it exists will be the map $p=\Omega(x)\mapsto x$, where we have used the assumption that we can write any point uniquely as $\Omega(x)$ . For definiteness let's call the proposed inverse $\lambda_X$. Clearly it's a function and the inverse of $\eta_X$ in $\mathbf{Set}$. We just need to show it's continuous. So let $U \in \Omega X$. Then $\lambda_X^{-1}(U)=\{\Omega(x)\;|\;x\in U\} = \{\Omega(x)\;|\;\Omega(x)^\star(U)=x^{-1}(U)=1\} = \{p\;|\;p^\star(U) = 1\} = \phi_{\Omega X}(U)\in \Omega PtX$. Hence $\eta_X$ is iso iff it is bijective iff every point of $\Omega X$ is of the form $\Omega(x)$ for a unique $x\in X$. We call such spaces $X$ sober.
Similarly, for $Y\in \mathbf{Loc}, \varepsilon_Y = \hat{1_{GY}}=\phi_A^{op}$. Hence $\varepsilon_Y$ is iso iff $\varepsilon_Y^\star = \phi_A$ is a frame isomorphism. But clearly if $\phi_A$ has an inverse in $\mathbf{Set}$ then the inverse also preserves meets and finite joins since $\phi_A$ does. So it will be a frame homomorphism as well. Hence $\phi_A$ will be invertible iff it is bijective. But $\phi_A$ is onto $\Omega pt A$ by definition of $\Omega pt A$. So $\phi_A$ will be invertible iff it is injective. When is $\phi_A$ injective? When elements of $A$ are uniquely determined by the points that they "contain", where we might say that $a$ "contains" a point $p:2\rightarrow A$ if $p^\star(a)=1$ (for intuition think of the case that $A$ is of the form $\Omega(X)$. Then $U\in \Omega (X)$ "contains" a point of the form $\Omega(x)$ if and only if $x\in U$ and $U$ is certainly determined by those "representable points".). Locales whose elements are uniquely determined by the points that they "contain" (a.k.a. $\phi_A$ injective) are called spatial.
Then by the theorem we proved at the beginning of the post, $\Omega$ restricts to an equivalence between the full subcategories of sober topological spaces and spatial locales.
Tuesday, October 15, 2013
Saturday, October 12, 2013
Locales and spaces: generalized points
We have already essentially introduced locales in a previous post. Locales, as objects, are just complete Heyting algebras. However, the morphisms are different.
Before we begin in earnest, a good reference for more information about the contents of this post is the excellent book Stone Spaces by Johnstone.
First we start by defining another category whose objects are complete Heyting algebras, $\mathbf{Frm}$, the category of frames. Since we already know that the objects are complete Heyting algebras, it suffices to define a frame homomorphism. This will be defined by abstracting the properties of the inverse image map $f^{-1}:\Omega(Y)\rightarrow \Omega(X)$ of a continuous function $f:X\rightarrow Y$, where $\Omega(X)$ means the topology on $X$ (which we know is a complete Heyting algebra (joins are unions, meets interior of intersection, etc.)). What properties does $f^{-1}$ satisfy? Well, it preserves arbitrary joins and finite meets. So we define a frame homomorphism $f:A\rightarrow B$ between frames to be a map preserving arbitrary joins and finite meets. Then we define the category of locales, $\mathbf{Loc}:=\mathbf{Frm}^{op}$. We must remember that the morphisms of locales are not functions, for instance if we ever need to check whether two locale morphisms are equal we often have to pass to the opposite category of frames for the computation.
Then almost by definition we have a functor: $\Omega:\mathbf{Top}\rightarrow \mathbf{Loc}$ given on objects by $X\mapsto \Omega(X)$, (where again $\Omega(X)$ is the topology of $X$ considered as a complete Heyting albegra) and on arrows by $f:X\rightarrow Y \mapsto \Omega(f):\Omega(X)\rightarrow \Omega(Y)$ where $\Omega(f)^{op}:=f^{-1}$.
How can we abstract the notion of point in a space to a locale? Well, first a point, as an element of a space $X$, is a morphism $x:1\rightarrow X$, where $1$ is the one-point space. Then the induced locale map is $\Omega(x):\Omega(1)=2\rightarrow \Omega(X)$, where $2$ is the lattice $0\rightarrow 1$. Hence, we define a point of a locale $A$ to be a locale morphism $2\rightarrow A$. Hence a point of a locale is the opposite of a frame morphism $A\rightarrow 2$, and if $p:2\rightarrow A$ is a point, we write $f^\star:A\rightarrow 2$ for the induced frame map (rather than $f^{op}$, since we would like to emphasize that $f^\star$ is actually a function). As a working definition, we define $pt(A)$ to be the set of all points of $A$.
If this notion of point is to be a suitable generalization of the notion of element of a space, then we should at least have that the points of $A$ form a space in a natural way. To this end, if $A$ is a locale, define a frame map $\phi_A: A\rightarrow P(pt(A)$ (where $P$ is the power-set functor) by $a\mapsto \phi(a):=\{p\;|\;p^\star(a)=1\}$. Note that since each $p^\star$ preserves finite meets and arbitrary joins, being a frame morphism, and since each $p^\star$ can only take values $0$ or $1$, we have $\phi_A(a\wedge b):=\{p\;|\;p^\star(a)\wedge p^\star(b)=1\}=\{p\;|\;p^\star(a)=1\}\cap\{p\;|\;p^\star(b)=1\}
= \phi_A(a)\wedge \phi_A(b)$ and
$\phi_A(\bigvee a_i) = \{p\;|\;\bigvee p^\star (a_i)=1\}=\bigcup\{p\;|\;p^\star(a_i)=1\} = \bigvee \phi_A(a_i)$. Hence, $\phi_A$ is indeed a frame homomorphism. In particular, $\phi_A(pt(A))$ is a topology. So we set $\Omega(pt(A)):= \phi_A(pt(A))$ and now consider $\phi_A:A\rightarrow \Omega(pt(A))$ to have co-domain $\Omega(pt(A))$. Hence $pt(A)$ is a space for each locale $A$. Hence we may revise our working definition of $pt(A)$ to reflect this fact.
Before we continue, a bit of notation: if $C$ is a category, we will replace the tedious notation hom$_C(\_,\_)$ for the hom functor, by $<\_,\_>_C$, reflecting the analogy with the inner product, often dropping the subscript $C$ when the context is obvious.
Note that $pt(A)$ is essentially $<2,A>_{\mathbf{Loc}}$ with the proviso that $pt(A)$ is a space and not just a set. Hence we should seek to define $pt:\mathbf{Loc}\rightarrow \mathbf{Top}$ using the representable functor $<2,\_>$ as a guide. So $pt$, on objects, $A\mapsto pt(A)$, has already been defined. And on arrows, we define $pt(f:A\rightarrow B):pt(A)\rightarrow pt(B)$ by $pt(f)(p):=fp$. That this is a functor is straightforward.
Hence we have functors $\Omega:\mathbf{Top}\rightarrow \mathbf{Loc}$ and $pt:\mathbf{Loc}\rightarrow \mathbf{Top}$. We conclude this post by showing that $\Omega \dashv pt$.
There's a sort of "shortcut theorem" for showing that a functor has an adjoint which says that solutions to a certain universal mapping problem for one functor is the same as an adjoint functor pair with another functor. I may cover this theorem in a later post. Johnstone uses this theorem in his proof that $\Omega \dashv pt$, and as a result obtains a much shorter proof than ours. We will use the "hom functor definition" of adjoint, i.e. we will show $<\Omega(\_),\_>\cong<\_,pt(\_)>$.
If $X$ is a space and $A$ a locale and $h:\Omega(X)\rightarrow A$, how can we define the proposed transpose $\bar{h}:X\rightarrow pt(A)$? Well, if $x:1\rightarrow X$ is an element of $X$ then $\Omega(x)=2\rightarrow \Omega(X)$ is a locale map. Hence $h\Omega(x)$ is a locale map from $2$ to $A$, a.k.a. a point of $A$, precisely the form that $\bar{h}(x)$ should take. So set $\bar{h}(x):h\Omega(x)$. We must check $\bar{h}$ is continuous. But $\bar{h}^{-1}(\phi_A)(a)=\{x\;|\;(h\Omega(x))^\star(a)=1\}$. But $(h\Omega(x))^\star(a) = \Omega(x)^\star h^\star(a)=x^{-1}(h^\star(a))=1 \iff x\in h^\star(a)$. So $\bar{h}^{-1}(\phi_A)(a)=h^\star(a)\in\Omega(X)$. Hence $\bar{h}$ is continuous. We show that this transpose operation defines a natural transformation.
Let $f:Y\rightarrow X$ be a space morphism (continuous map) and $g:A\rightarrow B$ be a locale homomorphism (opposite of a frame homomorphism). Then we must show that the "naturality square" commutes, i.e. if $h:\Omega(X)\rightarrow A$ then $<f,pt(g)>(\bar{h})= pt(g)\bar{h}f= \bar{(<\Omega(f),g>(h))}=\bar{(gh\Omega(f))}$. But for $y\in Y$, $\bar{(gh\Omega(f))}(y)=gh\Omega(f)\Omega(y)=gh\Omega(fy)$, and $pt(g)\bar{h}f(y)=pt(g)h\Omega(f(y))=gh\Omega(fy)$.
Hence the naturality square commutes, as desired.
Now we define the inverse of $\bar{()}$, completing the proof (since then $\bar{()}$ will be a natural equivalence). So for each $h:X\rightarrow pt(A)$, we seek to define a proposed transpose under the adjunction $\hat{h}:\Omega(X)\rightarrow A$. Note that $\phi_A:A\rightarrow \Omega(pt(A))$ is a frame map. Hence $\phi_A^{op}:\Omega(pt(A))\rightarrow A$ is a locale morphism. Hence, set $\hat{h}:=\phi_A^{op} \Omega(h)$. Note that for $a\in A$, $\hat{h}^\star(a) = (\phi_A^{op}\Omega(h))^\star(a) = h^{-1}(\phi_A(a))=\{x\;|\:h(x)^\star(a)=1\}.$
Then if $h:X\rightarrow pt(A)$ is continuous,$x\in X, \bar{\hat{h}}(x)=\hat{h}\Omega(x)=\phi_A^{op}\Omega(h)\Omega(x)=\phi_A^{op}\Omega(hx)=\hat{(hx)}$. But for $a\in A$, $\hat{(hx)}^\star(a) = \{t\in 1\;|\;hx(t)^\star(a)=1\} = 1$ when $h(x)(a)=1$ and $=\emptyset = 0$ when $h(x)(a)=0$ (since $x(1)=x$). Hence $\hat{(hx)}^\star = h(x)^\star.$ So $\hat{(hx)}=h(x)$. Then $\bar{\hat{h}}=h$.
If $h:\Omega(X)\rightarrow A$ is a locale morphism, $a\in A$, then $\hat{\bar{h}}^\star(a) = \{x\;|\;(\bar{h}(x))^\star(a)=1\}=\{x\;|\;(h\Omega(x))^\star(a)=1\} = \{x\;|\;x\in h^\star(a)\} = h^\star(a).$ Hence $\hat{\bar{h}}=h$. Therefore the proof is complete. We have shown $\Omega \dashv pt$.
In the next post we examine the unit and co-unit of the adjuntion and deduce a Stone-type duality between so called spatial locales and sober spaces.
Before we begin in earnest, a good reference for more information about the contents of this post is the excellent book Stone Spaces by Johnstone.
First we start by defining another category whose objects are complete Heyting algebras, $\mathbf{Frm}$, the category of frames. Since we already know that the objects are complete Heyting algebras, it suffices to define a frame homomorphism. This will be defined by abstracting the properties of the inverse image map $f^{-1}:\Omega(Y)\rightarrow \Omega(X)$ of a continuous function $f:X\rightarrow Y$, where $\Omega(X)$ means the topology on $X$ (which we know is a complete Heyting algebra (joins are unions, meets interior of intersection, etc.)). What properties does $f^{-1}$ satisfy? Well, it preserves arbitrary joins and finite meets. So we define a frame homomorphism $f:A\rightarrow B$ between frames to be a map preserving arbitrary joins and finite meets. Then we define the category of locales, $\mathbf{Loc}:=\mathbf{Frm}^{op}$. We must remember that the morphisms of locales are not functions, for instance if we ever need to check whether two locale morphisms are equal we often have to pass to the opposite category of frames for the computation.
Then almost by definition we have a functor: $\Omega:\mathbf{Top}\rightarrow \mathbf{Loc}$ given on objects by $X\mapsto \Omega(X)$, (where again $\Omega(X)$ is the topology of $X$ considered as a complete Heyting albegra) and on arrows by $f:X\rightarrow Y \mapsto \Omega(f):\Omega(X)\rightarrow \Omega(Y)$ where $\Omega(f)^{op}:=f^{-1}$.
How can we abstract the notion of point in a space to a locale? Well, first a point, as an element of a space $X$, is a morphism $x:1\rightarrow X$, where $1$ is the one-point space. Then the induced locale map is $\Omega(x):\Omega(1)=2\rightarrow \Omega(X)$, where $2$ is the lattice $0\rightarrow 1$. Hence, we define a point of a locale $A$ to be a locale morphism $2\rightarrow A$. Hence a point of a locale is the opposite of a frame morphism $A\rightarrow 2$, and if $p:2\rightarrow A$ is a point, we write $f^\star:A\rightarrow 2$ for the induced frame map (rather than $f^{op}$, since we would like to emphasize that $f^\star$ is actually a function). As a working definition, we define $pt(A)$ to be the set of all points of $A$.
If this notion of point is to be a suitable generalization of the notion of element of a space, then we should at least have that the points of $A$ form a space in a natural way. To this end, if $A$ is a locale, define a frame map $\phi_A: A\rightarrow P(pt(A)$ (where $P$ is the power-set functor) by $a\mapsto \phi(a):=\{p\;|\;p^\star(a)=1\}$. Note that since each $p^\star$ preserves finite meets and arbitrary joins, being a frame morphism, and since each $p^\star$ can only take values $0$ or $1$, we have $\phi_A(a\wedge b):=\{p\;|\;p^\star(a)\wedge p^\star(b)=1\}=\{p\;|\;p^\star(a)=1\}\cap\{p\;|\;p^\star(b)=1\}
= \phi_A(a)\wedge \phi_A(b)$ and
$\phi_A(\bigvee a_i) = \{p\;|\;\bigvee p^\star (a_i)=1\}=\bigcup\{p\;|\;p^\star(a_i)=1\} = \bigvee \phi_A(a_i)$. Hence, $\phi_A$ is indeed a frame homomorphism. In particular, $\phi_A(pt(A))$ is a topology. So we set $\Omega(pt(A)):= \phi_A(pt(A))$ and now consider $\phi_A:A\rightarrow \Omega(pt(A))$ to have co-domain $\Omega(pt(A))$. Hence $pt(A)$ is a space for each locale $A$. Hence we may revise our working definition of $pt(A)$ to reflect this fact.
Before we continue, a bit of notation: if $C$ is a category, we will replace the tedious notation hom$_C(\_,\_)$ for the hom functor, by $<\_,\_>_C$, reflecting the analogy with the inner product, often dropping the subscript $C$ when the context is obvious.
Note that $pt(A)$ is essentially $<2,A>_{\mathbf{Loc}}$ with the proviso that $pt(A)$ is a space and not just a set. Hence we should seek to define $pt:\mathbf{Loc}\rightarrow \mathbf{Top}$ using the representable functor $<2,\_>$ as a guide. So $pt$, on objects, $A\mapsto pt(A)$, has already been defined. And on arrows, we define $pt(f:A\rightarrow B):pt(A)\rightarrow pt(B)$ by $pt(f)(p):=fp$. That this is a functor is straightforward.
Hence we have functors $\Omega:\mathbf{Top}\rightarrow \mathbf{Loc}$ and $pt:\mathbf{Loc}\rightarrow \mathbf{Top}$. We conclude this post by showing that $\Omega \dashv pt$.
There's a sort of "shortcut theorem" for showing that a functor has an adjoint which says that solutions to a certain universal mapping problem for one functor is the same as an adjoint functor pair with another functor. I may cover this theorem in a later post. Johnstone uses this theorem in his proof that $\Omega \dashv pt$, and as a result obtains a much shorter proof than ours. We will use the "hom functor definition" of adjoint, i.e. we will show $<\Omega(\_),\_>\cong<\_,pt(\_)>$.
If $X$ is a space and $A$ a locale and $h:\Omega(X)\rightarrow A$, how can we define the proposed transpose $\bar{h}:X\rightarrow pt(A)$? Well, if $x:1\rightarrow X$ is an element of $X$ then $\Omega(x)=2\rightarrow \Omega(X)$ is a locale map. Hence $h\Omega(x)$ is a locale map from $2$ to $A$, a.k.a. a point of $A$, precisely the form that $\bar{h}(x)$ should take. So set $\bar{h}(x):h\Omega(x)$. We must check $\bar{h}$ is continuous. But $\bar{h}^{-1}(\phi_A)(a)=\{x\;|\;(h\Omega(x))^\star(a)=1\}$. But $(h\Omega(x))^\star(a) = \Omega(x)^\star h^\star(a)=x^{-1}(h^\star(a))=1 \iff x\in h^\star(a)$. So $\bar{h}^{-1}(\phi_A)(a)=h^\star(a)\in\Omega(X)$. Hence $\bar{h}$ is continuous. We show that this transpose operation defines a natural transformation.
Let $f:Y\rightarrow X$ be a space morphism (continuous map) and $g:A\rightarrow B$ be a locale homomorphism (opposite of a frame homomorphism). Then we must show that the "naturality square" commutes, i.e. if $h:\Omega(X)\rightarrow A$ then $<f,pt(g)>(\bar{h})= pt(g)\bar{h}f= \bar{(<\Omega(f),g>(h))}=\bar{(gh\Omega(f))}$. But for $y\in Y$, $\bar{(gh\Omega(f))}(y)=gh\Omega(f)\Omega(y)=gh\Omega(fy)$, and $pt(g)\bar{h}f(y)=pt(g)h\Omega(f(y))=gh\Omega(fy)$.
Hence the naturality square commutes, as desired.
Now we define the inverse of $\bar{()}$, completing the proof (since then $\bar{()}$ will be a natural equivalence). So for each $h:X\rightarrow pt(A)$, we seek to define a proposed transpose under the adjunction $\hat{h}:\Omega(X)\rightarrow A$. Note that $\phi_A:A\rightarrow \Omega(pt(A))$ is a frame map. Hence $\phi_A^{op}:\Omega(pt(A))\rightarrow A$ is a locale morphism. Hence, set $\hat{h}:=\phi_A^{op} \Omega(h)$. Note that for $a\in A$, $\hat{h}^\star(a) = (\phi_A^{op}\Omega(h))^\star(a) = h^{-1}(\phi_A(a))=\{x\;|\:h(x)^\star(a)=1\}.$
Then if $h:X\rightarrow pt(A)$ is continuous,$x\in X, \bar{\hat{h}}(x)=\hat{h}\Omega(x)=\phi_A^{op}\Omega(h)\Omega(x)=\phi_A^{op}\Omega(hx)=\hat{(hx)}$. But for $a\in A$, $\hat{(hx)}^\star(a) = \{t\in 1\;|\;hx(t)^\star(a)=1\} = 1$ when $h(x)(a)=1$ and $=\emptyset = 0$ when $h(x)(a)=0$ (since $x(1)=x$). Hence $\hat{(hx)}^\star = h(x)^\star.$ So $\hat{(hx)}=h(x)$. Then $\bar{\hat{h}}=h$.
If $h:\Omega(X)\rightarrow A$ is a locale morphism, $a\in A$, then $\hat{\bar{h}}^\star(a) = \{x\;|\;(\bar{h}(x))^\star(a)=1\}=\{x\;|\;(h\Omega(x))^\star(a)=1\} = \{x\;|\;x\in h^\star(a)\} = h^\star(a).$ Hence $\hat{\bar{h}}=h$. Therefore the proof is complete. We have shown $\Omega \dashv pt$.
In the next post we examine the unit and co-unit of the adjuntion and deduce a Stone-type duality between so called spatial locales and sober spaces.
Saturday, June 29, 2013
Adjunction : two definitions and their equivalence
Let $\mathbf{C}, \mathbf{D}$ be locally small categories and let $F:\mathbf{C} \rightarrow \mathbf{D}, G:\mathbf{D}\rightarrow \mathbf{C}$ functors.
I will give what, in my view, is the more intuitive definition of an adjunction first.
We say that $F$ is left adjoint to $G$, written $F\dashv G$, when we have a natural isomorphism between the (bi)functors $\hom_\mathbf{D}(F\_,\_)$ and $\hom_{\mathbf{D}}(\_,G\_)$. Recall that these were defined in an earlier post.
This definition is easy to remember if you use the analogy between the inner product on a Hilbert space and representable functors as mentioned in an earlier post. If $F$ is a bounded linear map between Hilbert spaces and $G$ its adjoint, then $<F\_,\_>=<\_,G\_>$ is the defining property of the adjoint.
Now let's return to our our original setting with (locally small) categories $\mathbf{C}, \mathbf{D}$ and $F\dashv G$.
Let $\phi: \hom_\mathbf{D}(F\_,\_) \rightarrow \hom_{\mathbf{D}}(\_,G\_)$ be a natural isomorphism (which exists since $F\dashv G$).
Note that $\phi$ is a natural isomorphism in each variable separately. That is we have natural isomorphisms $\phi_{A,\_}: \hom_\mathbf{D}(FA,\_) \rightarrow \hom_{\mathbf{C}}(A,G\_)$
and $\phi_{\_,C}: \hom_\mathbf{D}(F\_,C) \rightarrow \hom_{\mathbf{C}}(\_,GC)$ for each $\mathbf{C}$ object $A$ and each $\mathbf{D}$ object $C$. Moreover, as the notation suggests, the two agree with $\phi$ when defined on the same set, i.e.
\[ \phi_{A,\_}(C) = \phi_{A,C} = \phi_{\_,C}(A).\]
Conversely, given such a pair with the above agreement property we can use them to define a natural isomorphism $\hom_\mathbf{D}(F\_,\_) \rightarrow \hom_{\mathbf{C}}(\_,G\_)$ using the agreement property.
Note that for each $\mathbf{C}$ object $A$ and each $\mathbf{D}$ object $C, \phi_{A,C}:\mathbf{C}(FA,C) \overset{\sim}{\rightarrow}\hom_{\mathbf{C}}(A,GC)$. Hence to greatly simplify notation, for $f:FA\rightarrow C$ and $g:A\rightarrow GC$ define the transpose of $f$ under $\phi: \bar{f}: = \phi_{A,C}(f)\in \mathbf{C}(A,GC)$ and the transpose of $g$ under $\phi^{-1}: \hat{g}:= \phi^{-1}_{A,C} (g)= (\phi_{A,C})^{-1}(g) \in \mathbf{D}(FA,C)$. Then clearly we have $\bar{\hat{g}} = g$ and $\hat{\bar{f}}=f$.
For each $\mathbf{C}$ object $A$, define $\eta_A:= \phi_{A,FA}(1_ A) = \bar{1_A}:A\rightarrow GFA$ and for each $\mathbf{D}$ object $C$, define $\varepsilon_C: = \phi^{-1}_{FGA,C}(1_{GA}) = \hat{1_{GA}}.$
Let $g:C\rightarrow D, f^{op}:B\rightarrow A$ be arrows in $\mathbf{D}, \mathbf{C}^{op}$, respectively. Then naturality of $\phi_{A,\_}$ implies \begin{equation}Gg\bar{(\_)} = \bar{(g\_)} \end{equation} and naturality of $\phi^{-1}_{A,\_}$ implies \begin{equation} \hat{(Gg\_)} = g\hat{(\_)}. \end{equation}
Then taking $C=FA$ in the first equation and evaluating at $1_{FA}$, recalling $\bar{1_{FA}} = \eta_A$, yields
\[ (eq.1) \;\;\;\;\; Gg\eta_A = \bar{g} ,\]
and taking $A=GC$ in the second equation and evaluating at $1_{GC}$, recalling $\hat{1_{GC}} = \epsilon_C$, yields
\[(eq.2) \;\;\;\;\; \hat{Gg} = g\varepsilon_C.\]
Similarly, naturality of $\phi_{\_,C}$ implies \begin{equation}\bar{(\_)}f = \bar{(\_Ff)} \end{equation} and naturality of $\phi^{-1}_{\_,C}$ implies \begin{equation} \hat{(\_f)} = \hat{(\_)}Ff. \end{equation}
Then taking $C=FA$ in the first equation and evaluating at $1_{FA}$, recalling $\bar{1_{FA}} = \eta_A$, yields
\[ (eq.3) \;\;\;\;\; \eta_Af = \bar{Ff},\]
and taking $A=GC$ in the second equation and evaluating at $1_{GC}$, recalling $\hat{1_{GC}} = \varepsilon_C$, yields
\[(eq.4) \;\;\;\;\; \hat{f} = \epsilon_CFf.\]
We may define natural transformations $\eta: 1_\mathbf{C} \rightarrow GF$ and $\varepsilon :FG \rightarrow 1_\mathbf{D}$ by defining them on components by $\eta(A) = \eta_A$ and $\varepsilon(C) = \epsilon_C$. We must check that these assignments do indeed define natural transformations.
First let's check $\eta:1_{\mathbf{C}} \rightarrow GF$. Let $f:A\rightarrow B$ be a $\mathbf{C}$ arrow. Then we must show that the naturality square commutes, i.e. that $(GFf)\eta_A = \eta_Bf$. But using $Ff$ in (eq.1) yields $G(Ff)\eta_A = \hat{Ff}$. Similarly using $f$ in (eq. 3) yields $\eta_Bf=\bar{Ff}.$ So $(GFf)\eta_A = \eta_Bf$, as desired.
Now let's check $\varepsilon: FG\rightarrow 1_\mathbf{D}$. Let $g:C\rightarrow D$ be a $\mathbf{D}$ arrow. Then we must show that the naturality square commutes, i.e. that $g\varepsilon_C = \varepsilon_D(FGg)$. However, by (eq. 2) $g\varepsilon_C = \hat{(Gg)}$ and using $Gg$ in (eq. 4) gives $\varepsilon_DF(Gg) = \hat{(Gg)}$. So $g\varepsilon_C = \varepsilon_D(FGg)$, as desired. Hence $\eta, \varepsilon$ are natural transformations. See the Catster's video Adjunctions 4 for a similar argument (with the diagrams drawn).
The natural transformations $\eta:1_{\mathbf{C}} \rightarrow GF, \varepsilon: FG\rightarrow 1_\mathbf{D}$ are called the unit and co-unit, respectively, of the adjunction.
Next we show that $\eta$ and $\varepsilon$ satisfy the so-called triangle identities:
\[(\varepsilon F)\circ(F\eta) = 1_F \;\;\;\;\;\;\;\;\; (G\varepsilon)\circ (\eta G) = 1_G,\]
where the $\circ$ has only been written as a reminder that composition of natural transformations is involved.
Let $A$ a $\mathbf{C}$ object, $C$ a $\mathbf{D}$ object. Then \[((\varepsilon F)\circ(F\eta) )(A) = (\varepsilon F)_A(F\eta)_A =
\varepsilon_{FA}(F\eta_A) = \hat{\eta_A} = 1_{FA} = 1_F(A)\] by (eq. 4) and
\[((G\varepsilon)\circ (\eta G))(C) = (G\varepsilon)_C(\eta G)_C = (G\varepsilon_C)\eta_{GC} = \bar{\epsilon_C} = 1_{GC} = 1_G(C)\] by (eq. 1). Therefore the triangle identities hold.
This leads us to the second, more abstract, defintion of adjunction. Let $F:\mathbf{C} \rightarrow \mathbf{D}, G:\mathbf{D} \rightarrow \mathbf{C}$ be functors. Then we say $F$ is left adjoint to $G$ ($F\dashv G$) if there exist natural transformation $\eta:1_\mathbf{C} \rightarrow GF, \varepsilon : FG\rightarrow 1_\mathbf{D}$ called the unit and co-unit, respectively, satisfying the triangle identities. Note that for this definition it is not necessary for the categories involved to be locally small.
We have shown already that if $\mathbf{C}, \mathbf{D}$ are locally small categories then the first definition implies the second. Now let's show that in the case that if $\mathbf{C}, \mathbf{D}$ are locally small then also the second definition implies the first, so that in that case the two definitions are equivalent.
Let $F,G, \eta, \varepsilon$ as in the second definition of adjunction, with $\mathbf{C}, \mathbf{D}$ locally small. Moreover assume $\eta, \varepsilon$ satisfy the triangle identities. Let's show that the first definition of adjunction is satisfied.
We will use an argument completely analogous to that used in the proof of the Yoneda Lemma to define the natural isomorphism $\phi$. Essentially $\phi$ will be completely determined by its action on the identity.
For any $\mathbf{C}$ object $A$ set $\phi_{A,FA}(1_{FA}) = \eta_A$. Then in order for $\phi$ to be a natural transformation, for any $g:FA\rightarrow C$ we must have $\phi_{A,C}(g) = \phi_{A,C}(g1_{FA}) = (Gg)(\phi_{A,FA}(1_{FA}) = (Gg)(\eta_A)$. Hence we must define $\phi_{A,C}$ by
\[\phi_{A,C}(g) = (Gg)(\eta_A)\].
Let's show that $\phi_{A,\_}$ is a natural transformation. Let $g: C\rightarrow D$, $h\in \mathbf{D}(FA,C)$. Then $Gg(\phi_{A,C})(h) = Gg(Gh\eta_A) = G(gh)\eta_A = \phi_{A,D}(gh)$. Hence
\[Gg(\phi_{A,C}\_) = \phi_{A,D}(g\_),\] which is the naturality condition.
Now for any $\mathbf{D}$ object $C$ set $\psi_{GC,C}(1_{GC}) = \varepsilon_C$. We wish to define $\psi$ in such a way that $\psi = \phi^{-1}$. In order for $\psi$ to be a natural transformation, for any $f: A\rightarrow GC (f^{op}:GC\rightarrow A)$ we must have $\psi_{A,C}(f) = \psi_{A,C}(1_{GC}f) = \psi_{GC,C}(1_{GC})Ff = \varepsilon_C(Ff)$. Hence we must define $\psi_{A,C}$ by
\[\psi_{A,C}(f) = \varepsilon_C(Ff)\].
Let's show that $\psi_{\_,C}$ is a natural transformation. Let $f^{op}:A\rightarrow B$, $h\in \mathbf{C}(A,GC)$. $\psi_{A,C}(h)Ff = \varepsilon_CFhFf= \varepsilon_CF(hf) = \psi_{B,C}(hf)$. Hence
\[\psi_{B,C}(\_f) = (\psi_{A,C}(\_Ff),\] which is the naturality condition.
Finally, we must show that $(\phi_{A,C})^{-1} = \psi_{A,C}$. From that it will follow that $\phi_{\_,C}$ is also a natural transformation (since $\psi_{\_,C} = \phi^{-1}_{\_,C}$ is a natural transformation). Then since $\phi_{A,\_}$ and $\phi_{\_,C}$ agree when defined on the same set, they will induce a natural isomorphism $\phi: \hom_\mathbf{D}(F\_,\_) \rightarrow \hom_\mathbf{C}(\_,G\_)$.
Note that since $\eta: 1_{\mathbf{C}} \rightarrow GF, \varepsilon: FG\rightarrow 1_\mathbf{C}$ are natural transformations, by naturality, we have for any $f:A\rightarrow B, g:C\rightarrow D$,
\[(eq. a) \;\;\;\;\;\;\; GFf\eta_A = \eta_Bf\] and
\[(eq. b) \;\;\;\;\;\;\; g\varepsilon_C =\varepsilon_DFGg.\]
Moreover, we have the triangle identities \[ (\varepsilon F)\circ(F\eta) = 1_F \;\;\;\;\;\;\;\;\; (G\varepsilon)\circ (\eta G) = 1_G.\]
Hence if $h:A\rightarrow GC$ then
\begin{equation}
\begin{split}
\phi_{A,C}\psi_{A,C}(h) &= \phi_{A,C}\varepsilon_CFh = G(\varepsilon_CFh)\eta_A = G\varepsilon_C(GFh)\eta_A \\ &= G\varepsilon_C\eta_{GC}(h) = (G\varepsilon\circ \eta G)(C)(h)=1_{GC}(h)=h
\end{split}
\end{equation} where the first equalities hold by definition of $\phi$ and $\psi$, the third equality holds by functoriality of $G$, the fourth holds by (eq. b) and the last holds by the second triangle identity.
Similarly if $h:FA\rightarrow C$ then
\begin{equation}
\begin{split}
\psi_{A,C}\phi_{A,C}(h) &= \psi_{A,C}(Gh\eta_A) = \varepsilon_CF(Gh\eta_A) = \varepsilon_C(FGh)F\eta_A\\ &= h\varepsilon_{FA}F\eta_A = h(\varepsilon F\circ F\eta)(A) =h 1_{FA}=h,
\end{split}
\end{equation}
where the first equalities hold by definition of $\phi$ and $\psi$, the third equality holds by functoriality of $F$, the fourth holds by (eq. a) and the last holds by the first triangle identity.
Therefore $(\phi_{A,C})^{-1} = \psi_{A,C}$, from which our desired conclusion follows: the two definitions of adjunction are equivalent for locally small categories.
I will give what, in my view, is the more intuitive definition of an adjunction first.
We say that $F$ is left adjoint to $G$, written $F\dashv G$, when we have a natural isomorphism between the (bi)functors $\hom_\mathbf{D}(F\_,\_)$ and $\hom_{\mathbf{D}}(\_,G\_)$. Recall that these were defined in an earlier post.
This definition is easy to remember if you use the analogy between the inner product on a Hilbert space and representable functors as mentioned in an earlier post. If $F$ is a bounded linear map between Hilbert spaces and $G$ its adjoint, then $<F\_,\_>=<\_,G\_>$ is the defining property of the adjoint.
Now let's return to our our original setting with (locally small) categories $\mathbf{C}, \mathbf{D}$ and $F\dashv G$.
Let $\phi: \hom_\mathbf{D}(F\_,\_) \rightarrow \hom_{\mathbf{D}}(\_,G\_)$ be a natural isomorphism (which exists since $F\dashv G$).
Note that $\phi$ is a natural isomorphism in each variable separately. That is we have natural isomorphisms $\phi_{A,\_}: \hom_\mathbf{D}(FA,\_) \rightarrow \hom_{\mathbf{C}}(A,G\_)$
and $\phi_{\_,C}: \hom_\mathbf{D}(F\_,C) \rightarrow \hom_{\mathbf{C}}(\_,GC)$ for each $\mathbf{C}$ object $A$ and each $\mathbf{D}$ object $C$. Moreover, as the notation suggests, the two agree with $\phi$ when defined on the same set, i.e.
\[ \phi_{A,\_}(C) = \phi_{A,C} = \phi_{\_,C}(A).\]
Conversely, given such a pair with the above agreement property we can use them to define a natural isomorphism $\hom_\mathbf{D}(F\_,\_) \rightarrow \hom_{\mathbf{C}}(\_,G\_)$ using the agreement property.
Note that for each $\mathbf{C}$ object $A$ and each $\mathbf{D}$ object $C, \phi_{A,C}:\mathbf{C}(FA,C) \overset{\sim}{\rightarrow}\hom_{\mathbf{C}}(A,GC)$. Hence to greatly simplify notation, for $f:FA\rightarrow C$ and $g:A\rightarrow GC$ define the transpose of $f$ under $\phi: \bar{f}: = \phi_{A,C}(f)\in \mathbf{C}(A,GC)$ and the transpose of $g$ under $\phi^{-1}: \hat{g}:= \phi^{-1}_{A,C} (g)= (\phi_{A,C})^{-1}(g) \in \mathbf{D}(FA,C)$. Then clearly we have $\bar{\hat{g}} = g$ and $\hat{\bar{f}}=f$.
For each $\mathbf{C}$ object $A$, define $\eta_A:= \phi_{A,FA}(1_ A) = \bar{1_A}:A\rightarrow GFA$ and for each $\mathbf{D}$ object $C$, define $\varepsilon_C: = \phi^{-1}_{FGA,C}(1_{GA}) = \hat{1_{GA}}.$
Let $g:C\rightarrow D, f^{op}:B\rightarrow A$ be arrows in $\mathbf{D}, \mathbf{C}^{op}$, respectively. Then naturality of $\phi_{A,\_}$ implies \begin{equation}Gg\bar{(\_)} = \bar{(g\_)} \end{equation} and naturality of $\phi^{-1}_{A,\_}$ implies \begin{equation} \hat{(Gg\_)} = g\hat{(\_)}. \end{equation}
Then taking $C=FA$ in the first equation and evaluating at $1_{FA}$, recalling $\bar{1_{FA}} = \eta_A$, yields
\[ (eq.1) \;\;\;\;\; Gg\eta_A = \bar{g} ,\]
and taking $A=GC$ in the second equation and evaluating at $1_{GC}$, recalling $\hat{1_{GC}} = \epsilon_C$, yields
\[(eq.2) \;\;\;\;\; \hat{Gg} = g\varepsilon_C.\]
Similarly, naturality of $\phi_{\_,C}$ implies \begin{equation}\bar{(\_)}f = \bar{(\_Ff)} \end{equation} and naturality of $\phi^{-1}_{\_,C}$ implies \begin{equation} \hat{(\_f)} = \hat{(\_)}Ff. \end{equation}
Then taking $C=FA$ in the first equation and evaluating at $1_{FA}$, recalling $\bar{1_{FA}} = \eta_A$, yields
\[ (eq.3) \;\;\;\;\; \eta_Af = \bar{Ff},\]
and taking $A=GC$ in the second equation and evaluating at $1_{GC}$, recalling $\hat{1_{GC}} = \varepsilon_C$, yields
\[(eq.4) \;\;\;\;\; \hat{f} = \epsilon_CFf.\]
We may define natural transformations $\eta: 1_\mathbf{C} \rightarrow GF$ and $\varepsilon :FG \rightarrow 1_\mathbf{D}$ by defining them on components by $\eta(A) = \eta_A$ and $\varepsilon(C) = \epsilon_C$. We must check that these assignments do indeed define natural transformations.
First let's check $\eta:1_{\mathbf{C}} \rightarrow GF$. Let $f:A\rightarrow B$ be a $\mathbf{C}$ arrow. Then we must show that the naturality square commutes, i.e. that $(GFf)\eta_A = \eta_Bf$. But using $Ff$ in (eq.1) yields $G(Ff)\eta_A = \hat{Ff}$. Similarly using $f$ in (eq. 3) yields $\eta_Bf=\bar{Ff}.$ So $(GFf)\eta_A = \eta_Bf$, as desired.
Now let's check $\varepsilon: FG\rightarrow 1_\mathbf{D}$. Let $g:C\rightarrow D$ be a $\mathbf{D}$ arrow. Then we must show that the naturality square commutes, i.e. that $g\varepsilon_C = \varepsilon_D(FGg)$. However, by (eq. 2) $g\varepsilon_C = \hat{(Gg)}$ and using $Gg$ in (eq. 4) gives $\varepsilon_DF(Gg) = \hat{(Gg)}$. So $g\varepsilon_C = \varepsilon_D(FGg)$, as desired. Hence $\eta, \varepsilon$ are natural transformations. See the Catster's video Adjunctions 4 for a similar argument (with the diagrams drawn).
The natural transformations $\eta:1_{\mathbf{C}} \rightarrow GF, \varepsilon: FG\rightarrow 1_\mathbf{D}$ are called the unit and co-unit, respectively, of the adjunction.
Next we show that $\eta$ and $\varepsilon$ satisfy the so-called triangle identities:
\[(\varepsilon F)\circ(F\eta) = 1_F \;\;\;\;\;\;\;\;\; (G\varepsilon)\circ (\eta G) = 1_G,\]
where the $\circ$ has only been written as a reminder that composition of natural transformations is involved.
Let $A$ a $\mathbf{C}$ object, $C$ a $\mathbf{D}$ object. Then \[((\varepsilon F)\circ(F\eta) )(A) = (\varepsilon F)_A(F\eta)_A =
\varepsilon_{FA}(F\eta_A) = \hat{\eta_A} = 1_{FA} = 1_F(A)\] by (eq. 4) and
\[((G\varepsilon)\circ (\eta G))(C) = (G\varepsilon)_C(\eta G)_C = (G\varepsilon_C)\eta_{GC} = \bar{\epsilon_C} = 1_{GC} = 1_G(C)\] by (eq. 1). Therefore the triangle identities hold.
This leads us to the second, more abstract, defintion of adjunction. Let $F:\mathbf{C} \rightarrow \mathbf{D}, G:\mathbf{D} \rightarrow \mathbf{C}$ be functors. Then we say $F$ is left adjoint to $G$ ($F\dashv G$) if there exist natural transformation $\eta:1_\mathbf{C} \rightarrow GF, \varepsilon : FG\rightarrow 1_\mathbf{D}$ called the unit and co-unit, respectively, satisfying the triangle identities. Note that for this definition it is not necessary for the categories involved to be locally small.
We have shown already that if $\mathbf{C}, \mathbf{D}$ are locally small categories then the first definition implies the second. Now let's show that in the case that if $\mathbf{C}, \mathbf{D}$ are locally small then also the second definition implies the first, so that in that case the two definitions are equivalent.
Let $F,G, \eta, \varepsilon$ as in the second definition of adjunction, with $\mathbf{C}, \mathbf{D}$ locally small. Moreover assume $\eta, \varepsilon$ satisfy the triangle identities. Let's show that the first definition of adjunction is satisfied.
We will use an argument completely analogous to that used in the proof of the Yoneda Lemma to define the natural isomorphism $\phi$. Essentially $\phi$ will be completely determined by its action on the identity.
For any $\mathbf{C}$ object $A$ set $\phi_{A,FA}(1_{FA}) = \eta_A$. Then in order for $\phi$ to be a natural transformation, for any $g:FA\rightarrow C$ we must have $\phi_{A,C}(g) = \phi_{A,C}(g1_{FA}) = (Gg)(\phi_{A,FA}(1_{FA}) = (Gg)(\eta_A)$. Hence we must define $\phi_{A,C}$ by
\[\phi_{A,C}(g) = (Gg)(\eta_A)\].
Let's show that $\phi_{A,\_}$ is a natural transformation. Let $g: C\rightarrow D$, $h\in \mathbf{D}(FA,C)$. Then $Gg(\phi_{A,C})(h) = Gg(Gh\eta_A) = G(gh)\eta_A = \phi_{A,D}(gh)$. Hence
\[Gg(\phi_{A,C}\_) = \phi_{A,D}(g\_),\] which is the naturality condition.
Now for any $\mathbf{D}$ object $C$ set $\psi_{GC,C}(1_{GC}) = \varepsilon_C$. We wish to define $\psi$ in such a way that $\psi = \phi^{-1}$. In order for $\psi$ to be a natural transformation, for any $f: A\rightarrow GC (f^{op}:GC\rightarrow A)$ we must have $\psi_{A,C}(f) = \psi_{A,C}(1_{GC}f) = \psi_{GC,C}(1_{GC})Ff = \varepsilon_C(Ff)$. Hence we must define $\psi_{A,C}$ by
\[\psi_{A,C}(f) = \varepsilon_C(Ff)\].
Let's show that $\psi_{\_,C}$ is a natural transformation. Let $f^{op}:A\rightarrow B$, $h\in \mathbf{C}(A,GC)$. $\psi_{A,C}(h)Ff = \varepsilon_CFhFf= \varepsilon_CF(hf) = \psi_{B,C}(hf)$. Hence
\[\psi_{B,C}(\_f) = (\psi_{A,C}(\_Ff),\] which is the naturality condition.
Finally, we must show that $(\phi_{A,C})^{-1} = \psi_{A,C}$. From that it will follow that $\phi_{\_,C}$ is also a natural transformation (since $\psi_{\_,C} = \phi^{-1}_{\_,C}$ is a natural transformation). Then since $\phi_{A,\_}$ and $\phi_{\_,C}$ agree when defined on the same set, they will induce a natural isomorphism $\phi: \hom_\mathbf{D}(F\_,\_) \rightarrow \hom_\mathbf{C}(\_,G\_)$.
Note that since $\eta: 1_{\mathbf{C}} \rightarrow GF, \varepsilon: FG\rightarrow 1_\mathbf{C}$ are natural transformations, by naturality, we have for any $f:A\rightarrow B, g:C\rightarrow D$,
\[(eq. a) \;\;\;\;\;\;\; GFf\eta_A = \eta_Bf\] and
\[(eq. b) \;\;\;\;\;\;\; g\varepsilon_C =\varepsilon_DFGg.\]
Moreover, we have the triangle identities \[ (\varepsilon F)\circ(F\eta) = 1_F \;\;\;\;\;\;\;\;\; (G\varepsilon)\circ (\eta G) = 1_G.\]
Hence if $h:A\rightarrow GC$ then
\begin{equation}
\begin{split}
\phi_{A,C}\psi_{A,C}(h) &= \phi_{A,C}\varepsilon_CFh = G(\varepsilon_CFh)\eta_A = G\varepsilon_C(GFh)\eta_A \\ &= G\varepsilon_C\eta_{GC}(h) = (G\varepsilon\circ \eta G)(C)(h)=1_{GC}(h)=h
\end{split}
\end{equation} where the first equalities hold by definition of $\phi$ and $\psi$, the third equality holds by functoriality of $G$, the fourth holds by (eq. b) and the last holds by the second triangle identity.
Similarly if $h:FA\rightarrow C$ then
\begin{equation}
\begin{split}
\psi_{A,C}\phi_{A,C}(h) &= \psi_{A,C}(Gh\eta_A) = \varepsilon_CF(Gh\eta_A) = \varepsilon_C(FGh)F\eta_A\\ &= h\varepsilon_{FA}F\eta_A = h(\varepsilon F\circ F\eta)(A) =h 1_{FA}=h,
\end{split}
\end{equation}
where the first equalities hold by definition of $\phi$ and $\psi$, the third equality holds by functoriality of $F$, the fourth holds by (eq. a) and the last holds by the first triangle identity.
Therefore $(\phi_{A,C})^{-1} = \psi_{A,C}$, from which our desired conclusion follows: the two definitions of adjunction are equivalent for locally small categories.
The Yoneda Embedding Theorem
Let $\mathbf{C}$ be a locally small category. Then for each object $A$ of $\mathbf{C}$ we define the contravariant representable functor $H^A:=hom_{\mathbf{C}}(\_,A):\mathbf{C}^{op}\rightarrow \mathbf{Set}$. Then by the Yoneda Lemma of the previous post we know that for any presheaf $F$ (functor from $\mathbf{C}^{op}$ to $\mathbf{Set}$) we have $Nat(H^A,F)\cong FA$ as sets under the map $Nat(H^A,F)\ni \eta \mapsto \eta_A(1_A)$. Thus, in particular, if we take $F=H^B$ then $Nat(H^A,H^B)\cong H^B(A) = \mathbf{C}(A,B)$.
A fuctor $F$ between categories $\mathbf{C}$ and $\mathbf{D}$ is called an embedding if it is injective on objects and full and faithful; where it is full when it induces a surjective maps from $\mathbf{C}(A,B)$ to $\mathbf{D}(FA,FB)$ for every $A,B$, is faithful when it induces an injective map from $\mathbf{C}(A,B)$ to $\mathbf{D}(FA,FB)$ for every $A,B$, and hence is full and faithful when it induces a bijection between $\mathbf{C}(A,B)$ to $\mathbf{D}(FA,FB)$ for every $\mathbf{C}$ objects $A$ and $B$.
Again letting $\mathbf{C}$ be a small category, define the Yoneda Embedding $H: \mathbf{C} \rightarrow \mathbf{Set}^{\mathbf{C}^{op}}$ by the assignments
\[A\mapsto H^A,\;\;\;\;\;\;(f:A\rightarrow B)\mapsto Hf :: Hf_C = f\_.\]
That is $H(A) = H^A$ on objects and if $f:A\rightarrow B$ is an arrow, then $Hf$ is the natural transformation $H^A\rightarrow H^B$ with components $(Hf)_C = f\_$ for each object $C$.
We have two things that we need to check for this assignment; first, that $H$ is a functor, which includes checking that $Hf$ is a natural transformation, and, second, that $H$ is an embedding.
Let's check that $H$ is a functor. We begin by showing $Hf$ is actually a natural transformation. Let $C,D$ be two $\mathbf{C}$ objects and $g^{op}:C\rightarrow D$ an arrow in $\mathbf{C}^{op}$ (opposite of the arrow $g:D\rightarrow C$ in $\mathbf{C}$). We must then check that the naturality square commutes, i.e. $(H^Bg)(Hf)_C=((Hf)_D)H^Ag)$. So let $h\in H^AC = \mathbf{C}(C,A)$. Then \[(H^Bg)(Hf)_C(h) = (H^Bg)(fh) =fhg = ((Hf)_D)(hg) = ((Hf)_D)H^Ag)(h).\] Hence the square commutes as desired.
Clearly to show that $H$ respects function composition it suffices to show that for any $f:A\rightarrow B, g:B\rightarrow C$ and any $\mathbf{C}$ object $D$ we have $((Hg)_D)(Hf)_D = (H(gf))_D.$ So let $h\in H^AD = \mathbf{C}(D,A)$. Then
\[((Hg)_D)(Hf)_D(h) = gfh = H(gf))_D(h).\] So $H$ respects composition. Lastly, clearly we have $(H1_A)_C = 1_A\_ = \_ = 1_{H^AC} = (1_{H(A)})(C)$. Therefore $H$ is a functor.
Now let's complete the proof of the Yoneda Embedding Theorem by showing that $H$ is an embedding.
Well, clearly $H$ is 1-1 on objects since $H^A = H^B$ implies $H^AA = \mathbf{C}(A,A) = \mathbf{C}(B,A) = H^BA$. So, in particular, $1_A \in \mathbf{C}(B,A)$, which implies (by uniqueness on domain and codomain) that $A=B$.
For the rest, let $A,B$ be $\mathbf{C}$ objects. Then from the conclusion we drew from the Yoneda Lemma above, we have $Nat(H^A,H^B)\cong H^B(A) = \mathbf{C}(A,B)$.
But then $Nat(H^A,H^B) = \mathbf{Set}^{\mathbf{C}^{op}}(H^A,H^B) = \mathbf{Set}^{\mathbf{C}^{op}}(HA,HB)\cong \mathbf{C}(A,B)$ in set, i.e. $H$ is full and faithful. Hence $H$ is an embedding and the proof is complete.
A fuctor $F$ between categories $\mathbf{C}$ and $\mathbf{D}$ is called an embedding if it is injective on objects and full and faithful; where it is full when it induces a surjective maps from $\mathbf{C}(A,B)$ to $\mathbf{D}(FA,FB)$ for every $A,B$, is faithful when it induces an injective map from $\mathbf{C}(A,B)$ to $\mathbf{D}(FA,FB)$ for every $A,B$, and hence is full and faithful when it induces a bijection between $\mathbf{C}(A,B)$ to $\mathbf{D}(FA,FB)$ for every $\mathbf{C}$ objects $A$ and $B$.
Again letting $\mathbf{C}$ be a small category, define the Yoneda Embedding $H: \mathbf{C} \rightarrow \mathbf{Set}^{\mathbf{C}^{op}}$ by the assignments
\[A\mapsto H^A,\;\;\;\;\;\;(f:A\rightarrow B)\mapsto Hf :: Hf_C = f\_.\]
That is $H(A) = H^A$ on objects and if $f:A\rightarrow B$ is an arrow, then $Hf$ is the natural transformation $H^A\rightarrow H^B$ with components $(Hf)_C = f\_$ for each object $C$.
We have two things that we need to check for this assignment; first, that $H$ is a functor, which includes checking that $Hf$ is a natural transformation, and, second, that $H$ is an embedding.
Let's check that $H$ is a functor. We begin by showing $Hf$ is actually a natural transformation. Let $C,D$ be two $\mathbf{C}$ objects and $g^{op}:C\rightarrow D$ an arrow in $\mathbf{C}^{op}$ (opposite of the arrow $g:D\rightarrow C$ in $\mathbf{C}$). We must then check that the naturality square commutes, i.e. $(H^Bg)(Hf)_C=((Hf)_D)H^Ag)$. So let $h\in H^AC = \mathbf{C}(C,A)$. Then \[(H^Bg)(Hf)_C(h) = (H^Bg)(fh) =fhg = ((Hf)_D)(hg) = ((Hf)_D)H^Ag)(h).\] Hence the square commutes as desired.
Clearly to show that $H$ respects function composition it suffices to show that for any $f:A\rightarrow B, g:B\rightarrow C$ and any $\mathbf{C}$ object $D$ we have $((Hg)_D)(Hf)_D = (H(gf))_D.$ So let $h\in H^AD = \mathbf{C}(D,A)$. Then
\[((Hg)_D)(Hf)_D(h) = gfh = H(gf))_D(h).\] So $H$ respects composition. Lastly, clearly we have $(H1_A)_C = 1_A\_ = \_ = 1_{H^AC} = (1_{H(A)})(C)$. Therefore $H$ is a functor.
Now let's complete the proof of the Yoneda Embedding Theorem by showing that $H$ is an embedding.
Well, clearly $H$ is 1-1 on objects since $H^A = H^B$ implies $H^AA = \mathbf{C}(A,A) = \mathbf{C}(B,A) = H^BA$. So, in particular, $1_A \in \mathbf{C}(B,A)$, which implies (by uniqueness on domain and codomain) that $A=B$.
For the rest, let $A,B$ be $\mathbf{C}$ objects. Then from the conclusion we drew from the Yoneda Lemma above, we have $Nat(H^A,H^B)\cong H^B(A) = \mathbf{C}(A,B)$.
But then $Nat(H^A,H^B) = \mathbf{Set}^{\mathbf{C}^{op}}(H^A,H^B) = \mathbf{Set}^{\mathbf{C}^{op}}(HA,HB)\cong \mathbf{C}(A,B)$ in set, i.e. $H$ is full and faithful. Hence $H$ is an embedding and the proof is complete.
Thursday, May 16, 2013
Yoneda Lemma: Statement and Proof
Yoneda Lemma: Let $\mathbf{C}$ be a category, $F: \mathbf{C}^{op} \rightarrow \mathbf{Set}$ a functor (contravariant from $\mathbf{C}$ to $\mathbf{Set}$), and $A \in Ob(\mathbf{C})$. Then $\theta: Nat(H^A,F) \rightarrow F(A)$ defined by $\theta :\eta \mapsto \eta_A(1_A)$ is a bijection.
Proof: (Following Bell in Toposes and Local Set Theories)
We first show $\theta$ is injective by showing that any $\eta$ is uniquely determined by its image under $\theta$. To this end, let $B \in Ob(\mathbf{C})$. Then for $\eta \in Nat(H^A,F), \eta_B:H^A(B)=\mathbf{C}(B,A)\rightarrow F(B).$ We may assume $\mathbf{C}(B,A)\neq \emptyset$ for otherwise the $\eta_B$ is the empty map with codomain $F(B)$. Let $g \in \mathbf{C}(B,A)$. Then $g^{op}:A\rightarrow B \implies $(by contravariance of $H^A$ and $F$) $ H^A:\mathbf{C}(A,A)\rightarrow \mathbf{C}(B,A), F(g):F(A)\rightarrow F(B)$.
Then by naturality, $F(g)\eta_A = \eta_BH^A(g)$. Hence, evaluating at $1_A$, we get
\[\eta_B(H^A(g)1_A) = \eta_B(1_Ag)=\eta_B(g) = F(g)(\eta_A(1_A)).\]
In particular, $\eta_B(g) = F(g)(\eta_A(1_A)) = F(g)(\theta(\eta))$, so that $\eta$ is completely determined by its image under $\theta$. Hence $\theta$ is injective.
Now we prove $\theta$ is surjective. Let $a \in F(a)$. We know that if $a$ is the image of some $\eta$ that $\eta$ will satisfy the above formula. So we would have
$\eta_B(g) = F(g)(\eta_A(1_A)) = F(g)(a)$ if we had $\theta(\eta)=a$.
Hence we should define $\eta$ on objects $B$ and arrows $g \in \mathbf{C}(B,A)$
by $\eta_B(g) = F(g)(a)$. We show this defines a natural transformation.
Let $B_1, B_2 \in Ob(C), f^{op}:B_1 \rightarrow B_2$. Then for
$h \in \mathbf{C}(B_1, A)$, \[\eta_{B_2}(H^A(f)(h)) = \eta_{B_2}(hf) = F(hf)(a) = F(f)(F(h)(a)),\]
where the last equality holds because $F$ is contravariant.
However, we also have \[F(f)\eta_{B_1}(h) = F(f)(F(h)(a)).\]
Therefore \[\eta_{B_2}H^A(f) = F(f)\eta_{B_1},\] which is the naturality condition.
Hence $\eta \in Nat(H^A,F)$. But \[\theta(\eta) = \eta_A(1_A) = F(1_A)(a) = 1_{F(A)}(a) = a.\]
So $\theta$ is also surjective. Hence $\theta$ is a bijection, completing the proof.
If we let $F = H^B$ for another $\mathbf{C}$-object $B$, we get the immediate corollary $Nat(H^A,H^B)\cong \mathbf{C}(A,B)$ for any objects $A,B \in Ob(\mathbf{C})$.
Proof: (Following Bell in Toposes and Local Set Theories)
We first show $\theta$ is injective by showing that any $\eta$ is uniquely determined by its image under $\theta$. To this end, let $B \in Ob(\mathbf{C})$. Then for $\eta \in Nat(H^A,F), \eta_B:H^A(B)=\mathbf{C}(B,A)\rightarrow F(B).$ We may assume $\mathbf{C}(B,A)\neq \emptyset$ for otherwise the $\eta_B$ is the empty map with codomain $F(B)$. Let $g \in \mathbf{C}(B,A)$. Then $g^{op}:A\rightarrow B \implies $(by contravariance of $H^A$ and $F$) $ H^A:\mathbf{C}(A,A)\rightarrow \mathbf{C}(B,A), F(g):F(A)\rightarrow F(B)$.
Then by naturality, $F(g)\eta_A = \eta_BH^A(g)$. Hence, evaluating at $1_A$, we get
\[\eta_B(H^A(g)1_A) = \eta_B(1_Ag)=\eta_B(g) = F(g)(\eta_A(1_A)).\]
In particular, $\eta_B(g) = F(g)(\eta_A(1_A)) = F(g)(\theta(\eta))$, so that $\eta$ is completely determined by its image under $\theta$. Hence $\theta$ is injective.
Now we prove $\theta$ is surjective. Let $a \in F(a)$. We know that if $a$ is the image of some $\eta$ that $\eta$ will satisfy the above formula. So we would have
$\eta_B(g) = F(g)(\eta_A(1_A)) = F(g)(a)$ if we had $\theta(\eta)=a$.
Hence we should define $\eta$ on objects $B$ and arrows $g \in \mathbf{C}(B,A)$
by $\eta_B(g) = F(g)(a)$. We show this defines a natural transformation.
Let $B_1, B_2 \in Ob(C), f^{op}:B_1 \rightarrow B_2$. Then for
$h \in \mathbf{C}(B_1, A)$, \[\eta_{B_2}(H^A(f)(h)) = \eta_{B_2}(hf) = F(hf)(a) = F(f)(F(h)(a)),\]
where the last equality holds because $F$ is contravariant.
However, we also have \[F(f)\eta_{B_1}(h) = F(f)(F(h)(a)).\]
Therefore \[\eta_{B_2}H^A(f) = F(f)\eta_{B_1},\] which is the naturality condition.
Hence $\eta \in Nat(H^A,F)$. But \[\theta(\eta) = \eta_A(1_A) = F(1_A)(a) = 1_{F(A)}(a) = a.\]
So $\theta$ is also surjective. Hence $\theta$ is a bijection, completing the proof.
If we let $F = H^B$ for another $\mathbf{C}$-object $B$, we get the immediate corollary $Nat(H^A,H^B)\cong \mathbf{C}(A,B)$ for any objects $A,B \in Ob(\mathbf{C})$.
Thursday, April 11, 2013
The Yoneda Embedding Theorem I, Introduction
This series of posts will assume some knowledge of Category Theory. For a great overview of Category Theory watch the "TheCatsters" lectures on Youtube. Here is a link aggregate to the videos.
The content of the series will loosely follow a section of Toposes and Local Set Theories by John Lane Bell.
Let $\mathbf{C}$ be a category. For $A, B \in Ob(\mathbf{C})$, let $\mathscr{C}(A,B)$ be the set of arrows between $A$ and $B$. Define the functor (also called a bifunctor since it's leaving a product of two categories) $hom_\mathbf{C} : \mathbf{C}^{op} \times \mathbf{C} \rightarrow \mathbf{Set}$ by $hom_{\mathbf{C}}(A,B) = \mathscr{C}(A,B)$ on objects and $hom_{\mathbf{C}}(f^{op}:A_1\rightarrow A_2, g:B_1\rightarrow B_2):\mathscr{C}(A_1,B_1) \rightarrow \mathscr{C}(A_2, B_2)$ by $hom_{\mathbf{C}}(f^{op}, g) = g\_f$, where $f:A_2\rightarrow A_1, g:B_1 \rightarrow B_2$ are arrows in $\mathbf{C}$ and the $\_$ is where the argument would go. Then for fixed $A \in Ob(\mathbf{C})$ we may define functors $H^A: \mathbf{C}^{op} \rightarrow \mathbf{Set}, H_A:\mathbf{C} \rightarrow \mathbf{Set}$ by $H^A = hom_{\mathbf{C}}(\_,A), H_A = hom_{\mathbf{C}}(A,\_)$ on objects and $H^A = hom_{\mathbf{C}}(\_,1_A), H_A = hom_{\mathbf{C}}(1_A,\_)$ on arrows. Then $H^A, H_A$ are members of the functor categories $\mathbf{Set}^{\mathbf{C}^{op}}, \mathbf{Set}^{\mathbf{C}}$, respectively. The arrows in functor categories are natural transformations.
It's useful to think of $hom_\mathbf{C}$ as an "inner product on $\mathbf{C}$" in the sense that "conjugate linear in first argument" $\leftrightarrow$ covariant in first argument and "linear in second argument" $\leftrightarrow$ covariant in second argument. That is $hom_\mathbf{C} : \mathbf{C}^{op} \times \mathbf{C} \rightarrow \mathbf{Set} \leftrightarrow <\_,\_>:\mathbf{H}^* \times \mathbf{H} \rightarrow \mathbb{C}$. Moreover to continue the Hilbert space analogy, $H^A \leftrightarrow <\_,x>:\mathbf{H}^*\cong \mathbf{H}^{op} \rightarrow \mathbf{C}$ and $H_A:\leftrightarrow <x,\_>:\mathbf{H} \rightarrow \mathbb{C}$. So, in particular, under this dictionary, $H^A \leftrightarrow <\_,x>$. In Hilbert space theory, we have by the Riesz theorem that $\mathbf{H} \cong \mathbb{C}^{{\mathbf{H}}^*}$ under the map $x\mapsto <\_,x>$ that, in particular, embeds $\mathbf{H}\hookrightarrow \mathbb{C}^{{\mathbf{H}}^*} \cong \mathbb{C}^{{\mathbf{H}}^{op}}$. Analogously, the Yoneda Embedding Theorem is the result that $\mathbf{C} \hookrightarrow \mathbf{Set}^{\mathbf{C}^{op}}$. This statement will be made precise in the next post and the prerequisite Yoneda Lemma will be proven.
The content of the series will loosely follow a section of Toposes and Local Set Theories by John Lane Bell.
Let $\mathbf{C}$ be a category. For $A, B \in Ob(\mathbf{C})$, let $\mathscr{C}(A,B)$ be the set of arrows between $A$ and $B$. Define the functor (also called a bifunctor since it's leaving a product of two categories) $hom_\mathbf{C} : \mathbf{C}^{op} \times \mathbf{C} \rightarrow \mathbf{Set}$ by $hom_{\mathbf{C}}(A,B) = \mathscr{C}(A,B)$ on objects and $hom_{\mathbf{C}}(f^{op}:A_1\rightarrow A_2, g:B_1\rightarrow B_2):\mathscr{C}(A_1,B_1) \rightarrow \mathscr{C}(A_2, B_2)$ by $hom_{\mathbf{C}}(f^{op}, g) = g\_f$, where $f:A_2\rightarrow A_1, g:B_1 \rightarrow B_2$ are arrows in $\mathbf{C}$ and the $\_$ is where the argument would go. Then for fixed $A \in Ob(\mathbf{C})$ we may define functors $H^A: \mathbf{C}^{op} \rightarrow \mathbf{Set}, H_A:\mathbf{C} \rightarrow \mathbf{Set}$ by $H^A = hom_{\mathbf{C}}(\_,A), H_A = hom_{\mathbf{C}}(A,\_)$ on objects and $H^A = hom_{\mathbf{C}}(\_,1_A), H_A = hom_{\mathbf{C}}(1_A,\_)$ on arrows. Then $H^A, H_A$ are members of the functor categories $\mathbf{Set}^{\mathbf{C}^{op}}, \mathbf{Set}^{\mathbf{C}}$, respectively. The arrows in functor categories are natural transformations.
It's useful to think of $hom_\mathbf{C}$ as an "inner product on $\mathbf{C}$" in the sense that "conjugate linear in first argument" $\leftrightarrow$ covariant in first argument and "linear in second argument" $\leftrightarrow$ covariant in second argument. That is $hom_\mathbf{C} : \mathbf{C}^{op} \times \mathbf{C} \rightarrow \mathbf{Set} \leftrightarrow <\_,\_>:\mathbf{H}^* \times \mathbf{H} \rightarrow \mathbb{C}$. Moreover to continue the Hilbert space analogy, $H^A \leftrightarrow <\_,x>:\mathbf{H}^*\cong \mathbf{H}^{op} \rightarrow \mathbf{C}$ and $H_A:\leftrightarrow <x,\_>:\mathbf{H} \rightarrow \mathbb{C}$. So, in particular, under this dictionary, $H^A \leftrightarrow <\_,x>$. In Hilbert space theory, we have by the Riesz theorem that $\mathbf{H} \cong \mathbb{C}^{{\mathbf{H}}^*}$ under the map $x\mapsto <\_,x>$ that, in particular, embeds $\mathbf{H}\hookrightarrow \mathbb{C}^{{\mathbf{H}}^*} \cong \mathbb{C}^{{\mathbf{H}}^{op}}$. Analogously, the Yoneda Embedding Theorem is the result that $\mathbf{C} \hookrightarrow \mathbf{Set}^{\mathbf{C}^{op}}$. This statement will be made precise in the next post and the prerequisite Yoneda Lemma will be proven.
Subscribe to:
Comments (Atom)