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.
Tuesday, May 8, 2012
"Boolean algebras are to powersets as complete Heyting algebras are to topologies", or topology from logic (part 3)
In the last post I gave the definition of a Heyting algebra and stated and proved many properties about Heyting algebras and Boolean algebras, a proper subclass of Heyting algebras. Moreover I showed how the implication and negations operations on a Heyting algebra can be interpreted ("proof" and "information" interpretation) as logical operations within a lattice of propositions. We also had the important result that, when considered as spaces alone, frames and complete Heyting algebras are equivalent. In a later post we shall add yet another class of space that is equivalent when considered as a space alone to the former two. Eventually we shall be able to distinguish them, however, when considered in the context of category theory. Specifically we shall see later that they each have different "morphisms".
Let us return to our "lattice of observations" approach to a topology $\Omega X$ on an abstract space $X$ that we began to develop in part 1. We know that $\Omega X$ is a frame, hence it is also a complete Heyting algebra (cHa). Now recall for $x \in X$ that $x \in U \in \Omega X \implies x \in \mathscr{N}(x)$. Conversely if $U \in \mathscr{N}(x)$ then $x \in U$, which recall that by $x\in U$, under the lattice of observations interpretation we mean that we have observed (know empirically, have a "proof" that $x \in U$) $x$ to be in the "region" $U$ of the abstract space $X$. So let $y \in U$. Then by definition (different defintion of $\in$ here than is usual) we have a proof that $y \in U$ so $U \in \mathscr{N}(y)$. So $U$ is a (intuitionistic) neighborhood of each of its points, hence $U \in \Omega X$. (Caution: This is not classically true! It depends entirely of the particular interpretation of $\in$ I was using. This type of reasoning was used at the end of my second post, however I never mentioned that it forces us to have that neighborhoods are (intuitionistically) open (only due to interpretation!). Really, as I remarked in a similar paragraph in the second post, I am using a different definition of set containment than is standard in classical logic for the above reasoning. Therefore let us use an alternate symbol for when we mean this type of containment rather than the standard usage so it is no longer necessary to remind the reader for which paragraphs to "suspend disbelief". From now on in the lattice of observations interpretation, for $x \in X$ and $U\subset X$ we shall write \[definition: \qquad x\vdash U \iff U \in \mathscr{N}(x)\] and say $x$ inhabits $U$ when we mean this type of membership. Note that by definition $x$ can only inhabit a neighborhood. So this definition depends entirely on $\Omega X$. To emphasize this dependence on $\Omega X$ we may write $\vdash_{\Omega}$. For instance if one were speaking of another topology $\Gamma X$ on $X$ distinct from $\Omega X$ then distinction must be made between $\vdash _{\Omega}$ and $\vdash_{\Gamma}$.
We have not yet considered $\vdash_{\mathscr{P}}$ where $\mathscr{P}(X)$ is the classical lattice of observations. Well if $A \subset X$ and $x \in A$ then $x\ \in A \in \mathscr{P}(x)$. So $A$ is a n-hood of $x$ (relative to $\mathscr{P}(X)$. Hence $x \vdash_{\mathscr{P}} A$. Therefore $\in$ = $\mathscr{P}$. So when we deviate from the classical lattice of observations we also deviate from classical inclusion if we keep the internalized logic of the lattice.
Now we can see in the claim earlier than neighborhoods are forced to be open, what was really meant using our new notation is that neighborhoods are open in the internal logic of $\Omega$ because the classical
\[U \in \Omega X \iff \{\forall x \in U\:[\:x\vdash_\Omega U]\}\]
becomes a trivial statement when we replace $\in$ with $\vdash_{\Omega}$ (that is n-hoods are open under $\vdash$ (internal logic of $\Omega$ but not necessarily under $\in$). On the other hand $x \vdash U$ can also have the interpretation $x$ is known empirically to be in $U$ (a type of metalogic) and can be used to recover $\mathscr{N}(x)$ for each $x \in X$. In this latter sense only topologies "coarser" than $\Omega X$ ($\Gamma X \subset \Omega X$) may be produced.
Now that we have two concepts of membership we get two distinct concepts of set inclusion: the standard one induced by $\in$ and a now one induced by $\vdash$. For the latter we shall define
\[definition: \qquad \forall A, B \in \Omega X \:[\:A\sqsubset B \iff \{\forall x\in X \:[\:x\vdash A \implies x\vdash B]\}]\] and sometimes write $A \sqsubset_{\Omega} B$ to show dependence on $\Omega X$.
Now $\Omega X$ is a cHa. Let us examine implication and negation in this case. Recall from part 1 that the partial order on $\Omega X$ is subset inclusion $\subset$ and that we have \[\forall \alpha \subset \Omega X \:[\bigvee \alpha = \bigcup \alpha \: \: \&\:\: \bigwedge \alpha = (\bigcap \alpha)^{\circ}]\]
So arbitrary joins are unions but in general arbitrary meets are equal to the interior of the intersection. Since $\Omega X$ is a topology, the condition that $\Omega X$ is closed under finite intersections translates to finite meets are the same as finite intersections.
Note that if we have $A, B \in \Omega X$ and $A \subset B$ then we may consider the proposition $x \vdash A$. Then we also have $x \vdash B$ because $\mathscr{N}(x)$ is a filter. So any observation that can be made in $A$ can also be made in $B$. This follows the "proof interpretation" model that I mentioned in the last post because a proof of $x$ being contained in $A$ is $x \vdash A$ which implies that we have a proof of $x$ being contained in $B$ or $x\vdash B$.
Let's see what $A \rightarrow B$ looks like for $A, B \in \Omega X$. Since $\Omega X$ is complete, we must have $A \rightarrow B = \bigvee\{C \in\Omega X \: | \:A \wedge C \leq B\} = \bigcup \{ C\in \Omega X \:|\:A \cap C \subset B\}$. Then $\sim A =A \rightarrow \emptyset = \bigcup \{C\in \Omega X\:|\:A \cap C = \emptyset\} = \bigcup \{C\in \Omega X\:|\: C \subset A^c\} = (A^c)^{\circ}$. So the negation of $A$ is the interior of its complement. But from property (5) from the last post we know that a Heyting algebra is boolean $\iff \sim \sim a = a$ for each $a \in L$. So $\Omega X$ is boolean $\iff \forall A \in \Omega X \:[\sim \sim A = ((A^c)^{{\circ}})^c)^{\circ}=A]$.
Let's try to simplify $\sim \sim A = ((A^c)^{{\circ}})^c)^{\circ}$ using that $(A^c)^{{\circ}} = (\bar{A})^c$. Plugging this in we get $\sim \sim A = (((\bar{A})^c)^c)^{\circ} = (\bar{A})^{\circ}$. Hence $\sim \sim A$ is the interior of the closure of $A$. So we have that a topology is Boolean $\iff$ for all $A \in \Omega X$ we have that $(\bar{A})^{\circ} = A$. In general topology open sets $A$ that satisfy the condition $(\bar{A})^{\circ} = A$ are called normal open sets. So for our characterization an open set $A$ is normal when $\sim \sim A = A$ and a topology is Boolean $\iff$ every open set is normal.
Therefore we now have a multitude of examples of Heyting algebras that are not Boolean. Take any topology $\Omega X$ on $X$ that is not closed under complementation. Then it will be Heyting but not Boolean. This is because if $A \in \Omega X$ but $A^c \notin \Omega X$ then $\sim A \subsetneq A^c$. So $A \vee \sim A = A \cup \sim A \subsetneq A \cup A^c = X$. So $\sim A$ is not the Boolean negation of $A$. So $\Omega X$ is not Boolean. The proceeding argument also shows that if we have that $\Omega X$ is not Boolean then excluded middle does not hold internally on $\Omega X$. To see this note that if $\Omega X$ is not Boolean then $\exists A \in \Omega X \:[A^c \notin \Omega X]$. Then apply the proceeding argument to show that $\sim A \cup A \neq X$ which shows excluded middle does not hold internally.
For an example take $\mathbb{R}$ with its standard topology. Then it clearly is not Boolean because $\sim (0, 1) = (\infty,0) \cup (1,\infty) \neq (0,1)^c$. So that means there must exist open sets that are not normal. Let's try to find one. $(0, 1)$ is normal because $\sim ((\infty,0) \cup (1,\infty))= (0, 1)$. Let's try $(0, \frac{1}{2}) \cup (\frac{1}{2}, 1)$. Well $\sim ((0, \frac{1}{2}) \cup (\frac{1}{2}, 1)) = (\infty,0) \cup (1,\infty)$ and $\sim ((\infty,0) \cup (1,\infty) = (0,1) \neq (0, \frac{1}{2}) \cup (\frac{1}{2}, 1)$. So $(0, \frac{1}{2}) \cup (\frac{1}{2}, 1)$ is an open set that is not normal.
Let us return to our "lattice of observations" approach to a topology $\Omega X$ on an abstract space $X$ that we began to develop in part 1. We know that $\Omega X$ is a frame, hence it is also a complete Heyting algebra (cHa). Now recall for $x \in X$ that $x \in U \in \Omega X \implies x \in \mathscr{N}(x)$. Conversely if $U \in \mathscr{N}(x)$ then $x \in U$, which recall that by $x\in U$, under the lattice of observations interpretation we mean that we have observed (know empirically, have a "proof" that $x \in U$) $x$ to be in the "region" $U$ of the abstract space $X$. So let $y \in U$. Then by definition (different defintion of $\in$ here than is usual) we have a proof that $y \in U$ so $U \in \mathscr{N}(y)$. So $U$ is a (intuitionistic) neighborhood of each of its points, hence $U \in \Omega X$. (Caution: This is not classically true! It depends entirely of the particular interpretation of $\in$ I was using. This type of reasoning was used at the end of my second post, however I never mentioned that it forces us to have that neighborhoods are (intuitionistically) open (only due to interpretation!). Really, as I remarked in a similar paragraph in the second post, I am using a different definition of set containment than is standard in classical logic for the above reasoning. Therefore let us use an alternate symbol for when we mean this type of containment rather than the standard usage so it is no longer necessary to remind the reader for which paragraphs to "suspend disbelief". From now on in the lattice of observations interpretation, for $x \in X$ and $U\subset X$ we shall write \[definition: \qquad x\vdash U \iff U \in \mathscr{N}(x)\] and say $x$ inhabits $U$ when we mean this type of membership. Note that by definition $x$ can only inhabit a neighborhood. So this definition depends entirely on $\Omega X$. To emphasize this dependence on $\Omega X$ we may write $\vdash_{\Omega}$. For instance if one were speaking of another topology $\Gamma X$ on $X$ distinct from $\Omega X$ then distinction must be made between $\vdash _{\Omega}$ and $\vdash_{\Gamma}$.
We have not yet considered $\vdash_{\mathscr{P}}$ where $\mathscr{P}(X)$ is the classical lattice of observations. Well if $A \subset X$ and $x \in A$ then $x\ \in A \in \mathscr{P}(x)$. So $A$ is a n-hood of $x$ (relative to $\mathscr{P}(X)$. Hence $x \vdash_{\mathscr{P}} A$. Therefore $\in$ = $\mathscr{P}$. So when we deviate from the classical lattice of observations we also deviate from classical inclusion if we keep the internalized logic of the lattice.
Now we can see in the claim earlier than neighborhoods are forced to be open, what was really meant using our new notation is that neighborhoods are open in the internal logic of $\Omega$ because the classical
\[U \in \Omega X \iff \{\forall x \in U\:[\:x\vdash_\Omega U]\}\]
becomes a trivial statement when we replace $\in$ with $\vdash_{\Omega}$ (that is n-hoods are open under $\vdash$ (internal logic of $\Omega$ but not necessarily under $\in$). On the other hand $x \vdash U$ can also have the interpretation $x$ is known empirically to be in $U$ (a type of metalogic) and can be used to recover $\mathscr{N}(x)$ for each $x \in X$. In this latter sense only topologies "coarser" than $\Omega X$ ($\Gamma X \subset \Omega X$) may be produced.
Now that we have two concepts of membership we get two distinct concepts of set inclusion: the standard one induced by $\in$ and a now one induced by $\vdash$. For the latter we shall define
\[definition: \qquad \forall A, B \in \Omega X \:[\:A\sqsubset B \iff \{\forall x\in X \:[\:x\vdash A \implies x\vdash B]\}]\] and sometimes write $A \sqsubset_{\Omega} B$ to show dependence on $\Omega X$.
Now $\Omega X$ is a cHa. Let us examine implication and negation in this case. Recall from part 1 that the partial order on $\Omega X$ is subset inclusion $\subset$ and that we have \[\forall \alpha \subset \Omega X \:[\bigvee \alpha = \bigcup \alpha \: \: \&\:\: \bigwedge \alpha = (\bigcap \alpha)^{\circ}]\]
So arbitrary joins are unions but in general arbitrary meets are equal to the interior of the intersection. Since $\Omega X$ is a topology, the condition that $\Omega X$ is closed under finite intersections translates to finite meets are the same as finite intersections.
Note that if we have $A, B \in \Omega X$ and $A \subset B$ then we may consider the proposition $x \vdash A$. Then we also have $x \vdash B$ because $\mathscr{N}(x)$ is a filter. So any observation that can be made in $A$ can also be made in $B$. This follows the "proof interpretation" model that I mentioned in the last post because a proof of $x$ being contained in $A$ is $x \vdash A$ which implies that we have a proof of $x$ being contained in $B$ or $x\vdash B$.
Let's see what $A \rightarrow B$ looks like for $A, B \in \Omega X$. Since $\Omega X$ is complete, we must have $A \rightarrow B = \bigvee\{C \in\Omega X \: | \:A \wedge C \leq B\} = \bigcup \{ C\in \Omega X \:|\:A \cap C \subset B\}$. Then $\sim A =A \rightarrow \emptyset = \bigcup \{C\in \Omega X\:|\:A \cap C = \emptyset\} = \bigcup \{C\in \Omega X\:|\: C \subset A^c\} = (A^c)^{\circ}$. So the negation of $A$ is the interior of its complement. But from property (5) from the last post we know that a Heyting algebra is boolean $\iff \sim \sim a = a$ for each $a \in L$. So $\Omega X$ is boolean $\iff \forall A \in \Omega X \:[\sim \sim A = ((A^c)^{{\circ}})^c)^{\circ}=A]$.
Let's try to simplify $\sim \sim A = ((A^c)^{{\circ}})^c)^{\circ}$ using that $(A^c)^{{\circ}} = (\bar{A})^c$. Plugging this in we get $\sim \sim A = (((\bar{A})^c)^c)^{\circ} = (\bar{A})^{\circ}$. Hence $\sim \sim A$ is the interior of the closure of $A$. So we have that a topology is Boolean $\iff$ for all $A \in \Omega X$ we have that $(\bar{A})^{\circ} = A$. In general topology open sets $A$ that satisfy the condition $(\bar{A})^{\circ} = A$ are called normal open sets. So for our characterization an open set $A$ is normal when $\sim \sim A = A$ and a topology is Boolean $\iff$ every open set is normal.
Therefore we now have a multitude of examples of Heyting algebras that are not Boolean. Take any topology $\Omega X$ on $X$ that is not closed under complementation. Then it will be Heyting but not Boolean. This is because if $A \in \Omega X$ but $A^c \notin \Omega X$ then $\sim A \subsetneq A^c$. So $A \vee \sim A = A \cup \sim A \subsetneq A \cup A^c = X$. So $\sim A$ is not the Boolean negation of $A$. So $\Omega X$ is not Boolean. The proceeding argument also shows that if we have that $\Omega X$ is not Boolean then excluded middle does not hold internally on $\Omega X$. To see this note that if $\Omega X$ is not Boolean then $\exists A \in \Omega X \:[A^c \notin \Omega X]$. Then apply the proceeding argument to show that $\sim A \cup A \neq X$ which shows excluded middle does not hold internally.
For an example take $\mathbb{R}$ with its standard topology. Then it clearly is not Boolean because $\sim (0, 1) = (\infty,0) \cup (1,\infty) \neq (0,1)^c$. So that means there must exist open sets that are not normal. Let's try to find one. $(0, 1)$ is normal because $\sim ((\infty,0) \cup (1,\infty))= (0, 1)$. Let's try $(0, \frac{1}{2}) \cup (\frac{1}{2}, 1)$. Well $\sim ((0, \frac{1}{2}) \cup (\frac{1}{2}, 1)) = (\infty,0) \cup (1,\infty)$ and $\sim ((\infty,0) \cup (1,\infty) = (0,1) \neq (0, \frac{1}{2}) \cup (\frac{1}{2}, 1)$. So $(0, \frac{1}{2}) \cup (\frac{1}{2}, 1)$ is an open set that is not normal.
Subscribe to:
Comments (Atom)