Adjoints

Prerequisites: Category, Functor

Adjoints의 정의

어느 두 category $C,D$와 functor $L\in C\Rightarrow D$, $R\in D\Rightarrow C$ 에 대해 다음 두 조건이 성립할 때 $L$이 $R$의 left adjoint 혹은 $R$이 $L$의 right adjoint 라고 하고 $L⊣R$ 이라고 적는다.

(Isomorphism)

$$c\in obC,d\in obD\to (c{\Rightarrow }_{C}R(d))\cong (L(c){\Rightarrow }_{D}d)$$

(Naturality)
$c\in obC,d\in obD$에 대해 $(c{\Rightarrow }_{C}R(d))\to (L(c){\Rightarrow }_{D}d)$ 인 isomorphism ${\alpha }_{c,d}$와 비슷하게 정의되는 ${\alpha }_{c^{\prime },d^{\prime }}$을 가정하자. 이때 왼쪽 그림과 같은 $f,g,h$에 대해 오른쪽의 식이 성립한다.

$$\begin{array}{ccc}\mathcal{C}& & \mathcal{D}\\ c^{\prime }& \stackrel{\in L}{\to }& L(c^{\prime })\\ \downarrow f& & \downarrow L(f)\\ c& \stackrel{\in L}{\to }& L(c)\\ \downarrow h& & \downarrow {\alpha }_{c,d}(h)\\ R(d)& \stackrel{\in R}{\leftarrow }& d\\ \downarrow R(g)& & \downarrow g\\ R(d^{\prime })& \stackrel{\in R}{\leftarrow }& d^{\prime }\end{array}{\alpha }_{c^{\prime },d^{\prime }}(f;h;R(g))=L(f);{\alpha }_{c,d}(h);g$$

Example: Currying

Motivation

Currying은 다음과 같은 직관에서 출발한다. 어떤 이변수함수 $f(x,y)=2x^2+y^2$을 생각해 보자. 이때 다음과 같이 결과값이 함수인 함수를 정의할 수 있다.

$$p(x)=(t\mapsto 2x^2+t^2)$$

(즉, $p(x)=gs.t.g(t)=2x^2+t^2$) 그렇다면 이변수함수는 다음과 같이 함수의 연속된 적용으로 적을 수 있다.

$$f(x,y)=p(x)(y)=2x^2+y^2$$

이와 같이 다변수함수를 함수의 연속된 적용으로 적는 것을 Currying이라고 하고, 그 반대를 Uncurrying 이라고 한다. 이제 Currying과 adjoints의 관계성을 살펴보자.

Isomorphism

일반적으로 집합 $A,B,C$에 대해 일반적으로 다음이 성립한다.

$(A{\Rightarrow }_{\text{Set}}(B{\Rightarrow }_{\text{Set}}C))\cong (A\times B{\Rightarrow }_{\text{Set}}C)$

즉 $A\times B$를 입력으로 받아 $C$를 출력하는 함수와, $A$를 입력으로 받아 $B$에서 $C$로 가는 함수를 출력하는 함수 간에 일대일 대응이 존재한다. 구체적으로 ${\Phi }_{A,C}$ 를 다음과 같이 정의하자.

$$f\in A{\Rightarrow }_{\text{Set}}(B{\Rightarrow }_{\text{Set}}C)\to {\Phi }_{A,C}(f)=((t,t^{\prime })\mapsto f(t)(t^{\prime }))$$

또한 그 inverse ${\Phi }_{A,C}^{-1}$를 다음과 같이 정의하자.

$$g\in A\times B{\Rightarrow }_{\text{Set}}C\to {\Phi }_{A,C}^{-1}(g)=(t\mapsto t^{\prime }\mapsto g(t,t^{\prime }))$$

그러면 둘의 합성은 다음과 같이 된다.

$${\Phi }_{A,C}^{-1}({\Phi }_{A,C}(f))(a)(b)={\Phi }_{A,C}(f)(a,b)=f(a)(b)\therefore {\Phi }_{A,C}^{-1}({\Phi }_{A,C}(f))=f$$ $${\Phi }_{A,C}({\Phi }_{A,C}^{-1}(g))(a,b)={\Phi }_{A,C}^{-1}(g)(a)(b)=g(a,b)\therefore {\Phi }_{A,C}({\Phi }_{A,C}^{-1}(g))=g$$

따라서 이 둘은 실제로 inverse 이므로 앞선 두 집합은 isomorphic 하다.

Naturality

이제 $L_B,R_B\in \text{Set}{\Rightarrow }_{\text{Cat}}\text{Set}$을 집합 $X$와 함수 $f\in X^{\prime }{\Rightarrow }_{\text{Set}}X$ 에 대해서 다음과 같이 정의하자.

(Object-wise)

$$L_B(X)=X\times B{R}_B(X)=(B{\Rightarrow }_{\text{Set}}X)$$

(Morphism-wise)

$$L_B(f)\in X^{\prime }\times B{\Rightarrow }_{\text{Set}}X\times Bs.t.L_B(f)(x,b)=(f(x),b)$$ $$R_B(f)\in (B{\Rightarrow }_{\text{Set}}{X}^{\prime }){\Rightarrow }_{\text{Set}}(B{\Rightarrow }_{\text{Set}}X)s.t.R_B(f)(u)=u;f$$

이하에서 아래첨자 $B$는 생략한다. 이제 아래 그림을 생각해 보자.

$$\begin{array}{ccc}\text{Set}& & \text{Set}\\ A^{\prime }& \stackrel{\in L}{\to }& A^{\prime }\times B\\ \downarrow f& & \downarrow L(f)\\ A& \stackrel{\in L}{\to }& A\times B\\ \downarrow h& & \downarrow {\Phi }_{A,C}(h)\\ B{\Rightarrow }_{\text{Set}}C& \stackrel{\in R}{\leftarrow }& C\\ \downarrow R(g)& & \downarrow g\\ B{\Rightarrow }_{\text{Set}}{C}^{\prime }& \stackrel{\in R}{\leftarrow }& C^{\prime }\end{array}$$

이때 ${\Phi }_{A^{\prime },C^{\prime }}(f;h;R(g))=L(f);{\Phi }_{A,C}(h);g$ 인지 살펴보자.

$$\begin{array}{rlrl}{\Phi }_{A^{\prime },C^{\prime }}(f;h;R(g))(a^{\prime },b)& =(f;h;R(g))(a^{\prime })(b)& & \text{(by definition of }\Phi \text{)}\\ & =R(g)((f;h)(a^{\prime }))(b)& & \text{(evaluating the composition at }{a}^{\prime }\text{)}\\ & =R(g)(h(f(a^{\prime })))(b)& & \text{(evaluating }f;h\text{)}\\ & =(h(f(a^{\prime }));g)(b)& & \text{(by definition of }R(g)\text{ acting on a function)}\\ & =g(h(f(a^{\prime }))(b))& & \text{(evaluating the composition at }b\text{)}\end{array}$$ $$\begin{array}{rlrl}(L(f);{\Phi }_{A,C}(h);g)(a^{\prime },b)& =({\Phi }_{A,C}(h);g)(L(f)(a^{\prime },b))& & \text{(evaluating the first composition)}\\ & =({\Phi }_{A,C}(h);g)(f(a^{\prime }),b)& & \text{(by definition of }L(f)\text{)}\\ & =g({\Phi }_{A,C}(h)(f(a^{\prime }),b))& & \text{(evaluating the second composition)}\\ & =g(h(f(a^{\prime }))(b))& & \text{(by definition of }\Phi \text{)}\end{array}$$

따라서 naturality 가 성립한다. 즉, $L_B⊣R_B$ 이다.

References

(1) Brendan Fong, David I. Spivak, Seven Sketches in Compositionality