풍부화된 범주: 거리를 범주로(Enriched category)

마을 A에서 B까지 길이 2km, B에서 C까지 2km라면 A에서 C까지는 많아야 4km입니다. B를 거쳐 가면 되니까요. $d(A, C)\le d(A, B) + d(B, C)$라는 거리의 삼각부등식은 '두 길을 이어 붙이면 길이 된다'는 말입니다. 그리고 제자리에 있는 데는 0km가 듭니다. 이 두 문장을 범주의 두 조건과 나란히 놓아 봅시다. 범주에서는 A → B와 B → C 화살표를 이어 붙인 A → C 화살표가 있고(합성), 대상마다 아무것도 하지 않는 화살표가 있습니다(항등). 1973년 로베어는 논문 「거리 공간⁠(metric space)⁠, 일반화된 논리, 닫힌 범주」에서 이것이 비유가 아니라 같은 구조라는 것을 보였습니다. 두 대상 사이에 '화살표들의 집합'을 두는 대신 '수 하나' $d(a, b)$를 두면, 합성은 삼각부등식이고 항등은 $d(a, a) = 0$입니다.

이것을 정확히 하는 틀이 풍부화된 범주(enriched category)입니다. 모노이드 범주 V를 하나 정하고, 대상 a, b마다 '화살표 모음' $\mathcal C(a, b)$를 집합 대신 V의 대상으로 둡니다. 합성은 V의 화살표 $\mathcal C(b, c)\otimes\mathcal C(a, b)\to\mathcal C(a, c)$, 항등은 V의 화살표 $I\to\mathcal C(a, a)$이고, 결합법칙⁠(associativity)⁠과 단위 법칙은 V 안의 가환 그림으로 적습니다. V를 무엇으로 고르느냐에 따라 익숙한 것들이 나옵니다.

• V = 집합과 곱집합. 보통의 범주입니다.
• V = {거짓, 참}과 '그리고'. 화살표 모음이 'a ≤ b인가'라는 참·거짓 하나이고, 합성은 'a ≤ b이고 b ≤ c이면 a ≤ c'라는 추이성⁠(transitivity)⁠, 항등은 a ≤ a입니다. 곧 순서(준순서⁠, preorder⁠)입니다.
• V = 음이 아닌 실수⁠(real number)⁠와 ∞, 순서는 ≥, ⊗는 덧셈, 단위는 0. 화살표 모음이 수 d(a, b)이고, V의 화살표가 부등식 ≥이므로 합성은 $d(a, b) + d(b, c)\ge d(a, c)$, 항등은 $0\ge d(a, a)$입니다. 이것이 로베어 거리 공간입니다.
• V = 벡터 공간과 텐서곱⁠(tensor product)⁠. 화살표 모음이 벡터 공간이고 합성이 쌍선형인 범주(선형 범주)입니다. 대상이 자연수⁠(natural number)⁠이고 화살표가 행렬인 범주가 그 예입니다.

결합법칙과 단위 법칙은 거리의 경우 따로 확인할 것이 없습니다. V의 두 대상 사이에 화살표가 많아야 하나(부등식은 성립하거나 안 하거나)라서 그림은 저절로 가환합니다. 흥미로운 것은 로베어의 정의가 보통의 거리보다 느슨하다는 점입니다. 대칭 $d(a, b) = d(b, a)$도, '$d(a, b) = 0$이면 a = b'도, 거리가 유한하다는 것도 요구하지 않습니다. 이것은 결함이 아니라 쓸모입니다. 일방통행 길이나 오르막길의 걸리는 시간은 대칭이 아니고, 다리가 없는 두 섬 사이의 거리는 ∞입니다. 거리가 0 또는 ∞뿐인 로베어 거리 공간은 정확히 준순서입니다(0은 '≤이다', ∞는 '아니다'). 순서와 거리가 한 틀 안에서 이어지는 것입니다.

거리를 표로 적으면 계산이 행렬처럼 됩니다. 아래 다섯 마을의 도로 지도에서, 도로 하나로 바로 가는 거리를 표 W로 적습니다(도로가 없으면 ∞, 자기 자신은 0). 두 표 A, B의 '곱'을

$$(A\odot B)_{ik} = \min_j\,\bigl(A_{ij} + B_{jk}\bigr)$$

로 정하면, $W\odot W$의 (i, k) 칸은 '도로를 둘까지 써서 i에서 k로 가는 가장 짧은 길'입니다. 행렬의 곱⁠(matrix multiplication)⁠ $\sum_j A_{ij}B_{jk}$에서 합을 최솟값으로, 곱을 덧셈으로 바꾼 것이고, 이 산술을 열대(tropical) 산술 또는 (min, +) 대수라 부릅니다. 한 걸음씩 넘겨 보세요. 도로를 누르면 길이가 바뀌고(9 다음은 '도로 없음'), 표의 칸을 누르면 그 거리를 이루는 길이 지도에 표시됩니다. 길 잇기: .

마을이 n개면 도로를 n − 1개보다 많이 쓰는 가장 짧은 길은 필요 없으므로(길이가 음수인 도로가 없는 한), $W^{\odot(n-1)}$이 최종 거리표 D이고 그 뒤로는 곱해도 바뀌지 않습니다. 이 D에서는 모든 i, j, k에 대해 $D_{ik}\le D_{ij} + D_{jk}$이고 $D_{ii} = 0$이므로 $D\odot D = D$입니다. 삼각부등식은 거리표가 (min, +) 곱에 대해 멱등⁠(idempotent)⁠이라는 것입니다. 그림의 단계마다 '삼각부등식이 깨지는 곳'의 수를 세어 두었는데, 중간 단계의 표는 아직 거리 공간(풍부화된 범주)이 아니고 마지막 표에서 비로소 0이 됩니다. 도로 지도에서 이렇게 얻은 D는 '도로 지도가 만드는 가장 자유로운 로베어 거리 공간'으로, 최단 경로는 그래프에서 자유롭게 생성한 풍부화된 범주입니다. 다익스트라 알고리즘(데이크스트라, 1959)은 한 출발점에서의 거리를 가까운 곳부터 확정하고, 1962년 로버트 플로이드가 발표한 방법은 거쳐 갈 마을을 하나씩 늘려 가며 표 전체를 채웁니다. 표를 거듭 제곱하는 방법($W, W^{\odot 2}, W^{\odot 4}, \dots$)도 됩니다. 모두 같은 D를 동적 계획법⁠(dynamic programming)⁠의 서로 다른 순서로 계산하는 것입니다.

V를 바꾸면 '길을 잇는 방법'이 바뀝니다. 그림의 선택지를 'max'로 바꿔 보세요. ⊗를 덧셈 대신 최댓값으로 두면 합성 조건은 $d(a, c)\le\max(d(a, b), d(b, c))$, 곧 초거리(ultrametric)의 강한 삼각부등식이 되고, 도로 지도에서 얻는 거리는 '가장 높은 고개가 가장 낮은 길'의 그 고개 높이입니다. 일방통행이 없는 도로 지도라면 이 거리는 최소 신장 트리⁠(minimum spanning tree)⁠ 위의 길에서 가장 긴 도로의 길이와 같고, 계층적 군집의 나무 그림(덴드로그램)이 바로 이런 초거리입니다. Lp 노름⁠(Lp norm)⁠과의 관계도 여기서 보입니다. $(a^p + b^p)^{1/p}$은 p = 1이면 덧셈, p → ∞이면 최댓값이고, 1과 ∞ 사이의 p도 모두 결합법칙을 만족하고 0을 단위로 가져서 각기 다른 '삼각부등식'을 줍니다(p가 클수록 강한 조건). 또 로베어 거리 공간과 거리를 늘리지 않는 사상(짧은 사상⁠, short map⁠)의 범주에서, 두 공간의 곱에 붙는 거리는 두 좌표 거리의 최댓값($\ell^\infty$)이고, 텐서곱처럼 커링⁠(currying)⁠을 가능하게 하는 곱은 두 좌표 거리의 합($\ell^1$)입니다. 유클리드 거리($\ell^2$)는 둘 다 아닙니다.

풍부화해도 범주론⁠(category theory)⁠의 도구는 그대로 일합니다. 풍부화된 함자⁠(functor)⁠는 $d(Fa, Fb)\le d(a, b)$인 사상, 곧 거리를 늘리지 않는 함수⁠(function)⁠이고, 두 함자 사이의 자연 변환⁠(natural transformation)⁠이 이루는 '화살표 모음'은 두 함수의 거리 $\sup_x d(Fx, Gx)$입니다. 요네다 보조정리⁠(Yoneda lemma)⁠는 이렇게 됩니다.

$$d(x, y) = \sup_z\,\max\bigl(d(z, y) - d(z, x),\ 0\bigr)$$

증명은 보통의 요네다와 같은 한 수입니다. z = x를 넣으면 오른쪽이 d(x, y) 이상이고, 삼각부등식 $d(z, y)\le d(z, x) + d(x, y)$에서 모든 z에 대해 오른쪽의 항이 d(x, y) 이하입니다. 대칭인 거리라면 이것은 점 x를 '모든 점까지의 거리의 목록' $(d(x, z))_z$로 보내면 거리가 그대로 보존된다는 뜻입니다(두 목록 사이의 거리는 성분 차의 최댓값). 1910년 모리스 프레셰가 쓴 이 매장이 유한 거리 공간을 $\ell^\infty$ 공간 안에 거리 그대로 넣는 방법이고, 요네다 매장⁠(Yoneda embedding)⁠의 거리판입니다. 로베어는 같은 논문에서 거리 공간의 코시 완비화도 범주론의 일반 구성의 특수한 경우임을 보였습니다.

확률⁠(probability)⁠로도 옮길 수 있습니다. 확률은 곱해지므로 V를 ([0, 1], ≤, ×)로 잡으면 '가장 믿을 만한 길'을 찾는 (max, ×) 계산이 되고, 음의 로그 −log p를 씌우면 곱이 합이 되어 다시 (min, +)로 돌아옵니다. 은닉 마르코프 모델⁠(hidden Markov model)⁠에서 가장 그럴듯한 상태열을 찾는 비터비 알고리즘⁠(Viterbi algorithm)⁠이 이렇게 −log 확률 위의 최단 경로입니다. 풍부화된 범주의 일반 이론은 1965년 학회에서 발표된 에일렌베르크와 맥스 켈리의 논문 「닫힌 범주」(1966년 출판)에서 시작되었고, 켈리의 1982년 책 『풍부화된 범주론의 기본 개념』이 표준 교과서가 되었습니다. 로베어의 1973년 논문은 2002년 저자의 해설을 붙여 다시 출판되었습니다.

이어지는 곳. 화살표 모음이 놓일 곳 V의 구조는 모노이드 범주에서, 합성과 항등의 두 조건은 범주론에서 왔고, 거리의 세 공리⁠(axiom)⁠ 가운데 로베어가 무엇을 남기고 무엇을 버렸는지는 거리 페이지와 견주어 보면 분명해집니다. 거리표의 (min, +) 곱은 행렬의 곱의 열대판이고, 그 거듭제곱이 최단 경로를 주는 동적 계획법입니다. 덧셈 대신 최댓값으로 잇는 초거리는 최소 신장 트리와, 두 공간을 곱으로 묶으면 좌표 거리의 최댓값($\ell^\infty$), 텐서곱으로 묶으면 합($\ell^1$)이 새 거리가 된다는 것은 Lp 노름, 맨해튼 거리⁠(Manhattan distance)⁠, 체비쇼프 거리⁠(Chebyshev distance)⁠와 이어집니다. 거리판 요네다는 요네다 보조정리가 '대상은 관계로 정해진다'고 할 때의 가장 손에 잡히는 예이고, 확률의 −log를 거친 최단 경로는 은닉 마르코프 모델의 비터비 알고리즘입니다. 참·거짓으로 풍부화하면 순서가 되므로, 순서 사이의 수반인 갈루아 연결⁠(Galois connection)⁠도 이 틀의 한 모습입니다.