수반 함자(Adjoint functors)

실수⁠(real number)⁠ x의 올림 ⌈x⌉은 x 이상인 가장 작은 정수입니다. 올림에는 이런 성질이 있습니다. 모든 정수⁠(integer)⁠ n에 대해

$$\lceil x\rceil \le n \iff x \le n.$$

x = 2.3이면 ⌈x⌉ = 3이고, '3 ≤ n'과 '2.3 ≤ n'은 n = 2일 때 둘 다 거짓, n = 3일 때 둘 다 참입니다. 실수 x에 대한 질문이 정수 ⌈x⌉에 대한 질문으로 정확히 옮겨지는 것입니다. 내림도 짝을 이룹니다. 모든 정수 n에 대해 $n\le x \iff n \le \lfloor x\rfloor$입니다. 정수를 실수로 보는 포함 i: ℤ → ℝ을 가운데 두고, 올림은 그 왼쪽에, 내림은 그 오른쪽에 붙는 짝입니다. 순서는 범주⁠(category)⁠이고 단조 함수⁠(function)⁠는 함자이므로, 이것이 가장 작은 수반(adjunction)의 예입니다. 순서 사이의 이런 짝을, 1944년 오이스테인 오레가 갈루아가 찾은 체와 군의 대응에서 이름을 따 '갈루아 연결⁠(Galois connection)⁠'이라 불렀습니다.

일반적으로, 함자 $L: \mathcal C\to\mathcal D$와 $R: \mathcal D\to\mathcal C$가 모든 X, Y에 대해

$$\mathrm{Hom}_{\mathcal D}(LX,\,Y)\;\cong\;\mathrm{Hom}_{\mathcal C}(X,\,RY)$$

를 만족하고 이 일대일 대응⁠(one-to-one correspondence)⁠이 X와 Y에 대해 자연스러우면(자연 변환⁠(natural transformation)⁠) L을 R의 왼쪽 수반, R을 L의 오른쪽 수반이라 하고 $L\dashv R$로 적습니다. Hom(X, Y)는 X에서 Y로 가는 화살표들의 집합입니다. 순서에서는 화살표가 있거나 없거나이므로 이 식이 $LX\le Y\iff X\le RY$로 줄어듭니다. 그래서 올림 ⊣ 포함 ⊣ 내림입니다. Y = LX로 두면 왼쪽의 항등 화살표⁠(identity arrow)⁠가 오른쪽의 화살표 $\eta_X: X\to RLX$로 옮겨지는데, 이것을 단위라 합니다. 올림에서는 $x\le\lceil x\rceil$입니다. 반대로 X = RY로 두면 쌍대 단위⁠(counit)⁠ $\varepsilon_Y: LRY\to Y$가 나오고, 올림에서는 정수 n의 올림이 n 자신이라는 사실입니다.

수반은 '가장 자유로운 것'을 정확히 말해 줍니다. 집합⁠(set)⁠ S의 글자로 만든 문자열의 모노이드⁠(monoid)⁠ $S^*$에서 모노이드 M으로 가는 준동형⁠(homomorphism)⁠은, S에서 M으로 가는 아무 함수와 정확히 하나씩 대응합니다. 글자가 가는 곳만 정하면 나머지는 곱으로 정해지기 때문입니다. 이것이 '자유 모노이드⁠(free monoid)⁠ ⊣ 잊는 함자⁠(forgetful functor)⁠'입니다. 선형대수⁠(linear algebra)⁠에서 더 익숙한 모습도 있습니다. 기저가 $e_1, \dots, e_n$인 벡터 공간⁠(vector space)⁠에서 W로 가는 선형변환⁠(linear transformation)⁠은, 기저 벡터⁠(basis vector)⁠ n개를 W의 아무 벡터⁠(vector)⁠로 보내는 방법과 정확히 하나씩 대응합니다. 행렬⁠(matrix)⁠의 j번째 열이 $e_j$가 가는 곳이라는 사실이 바로 '자유 벡터 공간 ⊣ 잊는 함자'입니다. 집합 위의 자유군과 이산 위상 공간⁠(topological space)⁠도 같은 모양입니다. 각각 군에서, 위상 공간에서 집합으로 가는 잊는 함자의 왼쪽 수반입니다.

논리의 양화사⁠(quantifier)⁠도 수반입니다. 학생들의 집합 X, 반들의 집합 Y, 학생을 그 학생의 반으로 보내는 함수 f: X → Y를 생각합시다. 반들의 부분집합⁠(subset)⁠ T(예: '1반 또는 2반')를 학생의 부분집합으로 되돌리는 역상 $f^*T = \{x : f(x)\in T\}$는 '반이 T에 속한다'는 조건을 학생에 대한 조건으로 바꾸는 대입입니다. 학생의 부분집합 S(예: '안경을 쓴 학생')에서는 두 가지 방법으로 반의 부분집합을 만들 수 있습니다. $\exists_f S$는 'S에 속한 학생이 한 명이라도 있는 반'이고, $\forall_f S$는 '학생이 모두 S에 속하는 반'입니다. 그러면 $\exists_f\dashv f^*\dashv\forall_f$, 곧

$$\exists_f S\subseteq T\iff S\subseteq f^*T,\qquad f^*T\subseteq S\iff T\subseteq\forall_f S$$

가 늘 성립합니다. 학생(작은 점)을 눌러 S를, 반(큰 점)을 눌러 T를 바꿔 보세요.

학생이 없는 4반은 언제나 ∀S에 들어 있습니다. '4반의 모든 학생이 S에 속한다'는, 확인할 학생이 없으니 참이기 때문입니다. 이 수반은 익숙한 논리 규칙을 그대로 적은 것입니다. 조건 ψ(y)에 x가 나오지 않으면 '(어떤 x에 대해 φ(x, y)이다) ⇒ ψ(y)'와 '모든 x에 대해 (φ(x, y) ⇒ ψ(y))'가 같다는 규칙입니다. 1969년 로베어는 「기초⁠(basics)⁠에서의 수반성」(Adjointness in Foundations)에서 ∃와 ∀를 대입의 왼쪽·오른쪽 수반으로 보자고 제안했습니다. 프로그래밍의 커링도 수반입니다. 두 인자를 받는 함수 A × B → C는, A를 받아 'B를 받아 C를 돌려주는 함수'를 돌려주는 함수 $A\to C^B$와 정확히 하나씩 대응합니다. 곧 $(-\times B)\dashv(-)^B$이고, 이 수반이 있는 범주가 데카르트 닫힌 범주⁠(cartesian closed category)⁠입니다.

수반의 가장 쓸모 있는 정리는 이것입니다. 오른쪽 수반은 극한을 보존하고, 왼쪽 수반은 쌍대극한⁠(colimit)⁠을 보존한다. 곧 L ⊣ R이고 그림 D의 극한 lim D가 있으면, R(lim D)는 그림 RD의 극한입니다. 증명의 뼈대는 한 줄입니다. 아무 X에 대해

$$\mathrm{Hom}(X, R(\lim D))\cong\mathrm{Hom}(LX, \lim D)\cong\lim_i\mathrm{Hom}(LX, D_i)\cong\lim_i\mathrm{Hom}(X, RD_i)$$

입니다. 가운데의 $\lim_i\mathrm{Hom}(-, D_i)$는 '그림의 모든 대상으로 가면서 그림과 가환하는 화살표 묶음'들의 집합입니다. 그러니 이 식은 X에서 R(lim D)로 가는 화살표가 X에서 그림 RD로 가는 가환한 묶음과 자연스럽게 하나씩 대응한다는 뜻이고, 그것이 R(lim D)가 RD의 극한이라는 말 그대로입니다. 대상을 '모든 X에서 오는 화살표'로 알아보는 이 방식이 요네다 보조정리⁠(Yoneda lemma)⁠의 생각입니다. 그림에서 확인할 수 있습니다. ∃는 왼쪽 수반이라 합집합(쌍대곱⁠, coproduct⁠)을 보존합니다. $\exists_f(S\cup S') = \exists_f S\cup\exists_f S'$. 그러나 교집합(곱)은 보존하지 않습니다. 1반의 학생 한 명만 S에, 다른 한 명만 S′에 넣으면 S ∩ S′은 비어 있어 ∃(S ∩ S′)도 비지만, ∃S ∩ ∃S′은 {1반}입니다. 역상 f*는 양쪽에 수반이 있어 둘 다 보존하고, ∀는 교집합⁠(intersection)⁠을 보존합니다. 이 정리는 '수반이 없다'는 판정에도 쓰입니다. ∃는 교집합을 보존하지 않으므로 오른쪽 수반일 수 없고, 따라서 ∃에게는 왼쪽 수반이 없습니다. 군을 원소⁠(element)⁠의 집합으로 보내는 잊는 함자는 곱을 보존합니다(G × H의 원소는 순서쌍⁠(ordered pair)⁠). 자유군 함자의 오른쪽 수반이기 때문입니다. 그러나 쌍대곱은 보존하지 않습니다. ℤ와 ℤ의 쌍대곱인 자유곱⁠(free product)⁠에는 두 생성원 a, b를 번갈아 곱한 ab 같은 원소가 있는데, 이 원소는 두 집합의 서로소 합집합⁠(disjoint union)⁠ 어디에서도 오지 않습니다. 그러니 이 잊는 함자에게는 오른쪽 수반이 없습니다.

한 함자의 수반은 있다면 자연 동형⁠(natural isomorphism)⁠을 빼고 하나뿐입니다. 이것도 요네다에서 나옵니다. 수반 L ⊣ R이 있으면 합성 T = R∘L은 단위 $\eta: \mathrm{Id}\Rightarrow RL$과 $R\varepsilon L: RLRL\Rightarrow RL$을 가진 모나드⁠(monad)⁠가 됩니다. 자유 모노이드의 수반에서는 목록 모나드가, 커링의 수반에서는 상태 모나드가 나옵니다. 순서에서는 모나드가 '닫힘 연산⁠(closure operator)⁠', 곧 $x\le Tx$이고 $TTx = Tx$인 단조 함수가 됩니다. 그림에서 $f^*\exists_f S$는 'S의 학생과 같은 반인 학생 전체'로, 한 번 더 해도 바뀌지 않습니다. 수반 함자⁠(adjoint functor)⁠는 1958년 대니얼 칸이 정의했고, 매클레인은 교과서에서 '수반 함자는 어디에나 있다'고 적었습니다.

이어지는 곳. 수반의 정의는 자연 변환과 보편 성질⁠(universal property)⁠을 함께 씁니다. 단위 $\eta_X: X\to RLX$는 'X에서 R(무엇)으로 가는 화살표가 모두 하나뿐인 방식으로 거쳐 가는' 보편 화살표이고, 곱은 대각 함자의 오른쪽 수반입니다. 수반에서 모나드가 나오는 과정은 프로그래밍의 목록·상태 모나드가 어디서 오는지 설명하고, 커링의 수반은 데카르트 닫힌 범주와 람다 계산⁠(lambda calculus)⁠을 잇습니다. ∃와 ∀가 대입의 수반이라는 사실은 의존 타입⁠(dependent type)⁠에서 Σ 타입⁠(type)⁠과 Π 타입으로 다시 나타나고, '그리고'와 '이면'의 수반 $a\wedge x\le b\iff x\le(a\Rightarrow b)$는 직관주의 논리⁠(intuitionistic logic)⁠의 대수인 헤이팅 대수⁠(Heyting algebra)⁠를 정의합니다. 올림과 내림은 수 체계⁠(number system)⁠에서 정수와 실수 사이를 오가는 가장 흔한 도구이고, 행렬의 열이 기저의 상이라는 것은 선형변환에서 이미 본 수반입니다. 합집합⁠(union)⁠은 보존하지만 교집합은 보존하지 않는 상(image)의 성질은 집합의 연산⁠(set operations)⁠에서 직접 확인할 수 있습니다. 순서 사이의 수반을 따로 갈루아 연결이라 부르며, 프로그램 실행의 최강 후조건⁠(strongest postcondition)⁠과 최약 자유 전조건⁠(weakest liberal precondition)⁠이 그런 짝입니다(호어 논리⁠(Hoare logic)⁠). 텐서곱⁠(tensor product)⁠과 ⊸ 사이의 커링 $\mathrm{Hom}(A\otimes B, C)\cong\mathrm{Hom}(A, B\multimap C)$도 수반이고, 이것이 선형 논리⁠(linear logic)⁠의 모형을 이룹니다. 반올림이나 0 쪽으로 버림은 왜 수반이 아닌지 표로 시험하는 그림과, 수반만으로 ⌊⌊x⌋/m⌋ = ⌊x/m⌋를 증명하는 계산은 「화살표만으로 본 수학」 6절에 있습니다.