모노이드 범주와 끈 그림(Monoidal categories and string diagrams)

날씨와 램프라는 서로 무관한 두 가지를 하루 단위로 관찰한다고 합시다. 날씨 X는 맑음(0)과 비(1) 사이를 오가고, 오늘 맑으면 내일도 맑을 확률이 0.9, 오늘 비가 오면 내일 맑을 확률이 0.2입니다. 램프 Y는 꺼짐(0)과 켜짐(1) 가운데 하나이고, 켜진 램프는 하루 사이에 0.3의 확률로 나갑니다. 각각을 열이 오늘, 행이 내일인 마르코프 연쇄⁠(Markov chain)⁠의 전이 행렬로 적으면

$$F = \begin{pmatrix}0.9 & 0.2\\ 0.1 & 0.8\end{pmatrix},\qquad G = \begin{pmatrix}1 & 0.3\\ 0 & 0.7\end{pmatrix}$$

이고, 열마다 합이 1입니다. 두 가지를 한꺼번에 보면 상태는 (날씨, 램프)의 네 가지이고 전이 행렬은 4×4입니다. 둘이 서로 영향을 주지 않으니 '오늘 맑음·켜짐에서 내일 맑음·꺼짐'의 확률은 두 확률의 곱 0.9 × 0.3 = 0.27입니다(조건부 확률⁠(conditional probability)⁠과 독립). 이렇게 한 행렬⁠(matrix)⁠의 각 칸에 다른 행렬 전체를 곱해 붙인 4×4 행렬을 크로네커 곱 $F\otimes G$라 합니다. 곱하기 기호처럼 생겼지만 $2\times 2$ 둘에서 $4\times 4$를 만드는, 행렬의 곱⁠(matrix multiplication)⁠과는 다른 연산입니다.

이제 둘 사이를 잇는 일을 하나 넣습니다. h는 '비가 오면 램프 스위치를 한 번 누른다', 곧 (x, y)를 (x, x XOR y)로 보내는 일입니다. 아래 그림은 이 계산을 선과 상자로 그린 것입니다. 선은 대상(날씨, 램프), 상자는 화살표이고, 아래에서 위로 시간이 흐릅니다. 서로 다른 선 위에 나란히 놓인 것이 ⊗, 같은 선을 따라 위아래로 이어진 것이 합성입니다. 상자의 흰검은 점을 끌어 위아래로 옮겨 보세요. h: .

f와 g를 어떻게 엇갈려 놓아도 표는 바뀌지 않습니다. 다른 선 위의 상자는 서로 미끄러져 지나갈 수 있다는 뜻이고, 식으로는

$$(F\otimes I)(I\otimes G) = F\otimes G = (I\otimes G)(F\otimes I)$$

입니다. 더 일반적으로 크기가 맞으면 $(A\otimes B)(C\otimes D) = (AC)\otimes(BD)$가 성립합니다. '나란히 놓은 뒤 이어 붙이든, 이어 붙인 뒤 나란히 놓든 같다'는 이 교환 법칙(interchange law)이 끈 그림을 믿을 수 있게 하는 핵심입니다. 반면 f를 h의 반대편으로 옮기면 표가 바뀝니다(g도 마찬가지입니다). 같은 선 위에서 한 상자가 다른 상자를 뚫고 지나가는 것은 그림의 변형이 아니라 다른 그림이기 때문입니다. 실제로 '스위치를 누른 뒤 날씨가 바뀌는 것'과 '날씨가 바뀐 뒤 그 날씨를 보고 스위치를 누르는 것'은 다른 과정입니다.

모노이드⁠(monoid)⁠ 범주(monoidal category)는 이 구조를 갖춘 범주입니다. 범주 𝒞에 두 대상 A, B를 나란히 놓은 대상 $A\otimes B$와 두 화살표를 나란히 놓은 화살표 $f\otimes g$를 정하는 함자⁠(functor)⁠ $\otimes: \mathcal C\times\mathcal C\to\mathcal C$가 있고, '아무것도 없음'을 뜻하는 단위 대상 I가 있으며, 괄호를 바꾸는 동형⁠(isomorphism)⁠ $(A\otimes B)\otimes C\cong A\otimes(B\otimes C)$와 단위를 떼는 동형 $I\otimes A\cong A\cong A\otimes I$가 자연 변환⁠(natural transformation)⁠으로 주어져, 네 대상의 괄호를 바꾸는 두 길이 같다는 오각형 등식과 단위에 관한 삼각형 등식을 만족하는 것입니다. ⊗가 함자라는 조건, 곧 $(g\otimes g')\circ(f\otimes f') = (g\circ f)\otimes(g'\circ f')$가 바로 위의 교환 법칙입니다. 1963년 매클레인은 오각형과 삼각형만 확인하면 괄호와 단위를 옮기는 모든 그림이 저절로 가환한다는 정합성 정리⁠(coherence theorem)⁠를 증명했습니다. 그래서 모노이드에서 괄호를 생략하듯 $A\otimes B\otimes C$라 써도 됩니다. '모노이드 범주'라는 이름은 대상들이 ⊗와 I로 모노이드처럼 곱해진다는 데서 왔습니다(같은 해 장 베나부도 같은 구조를 따로 정의했습니다).

같은 범주에 ⊗가 여러 가지일 수 있습니다. 집합⁠(set)⁠의 범주에는 곱집합 ×(단위: 원소⁠(element)⁠ 하나짜리 집합)과 서로소 합집합⁠(disjoint union)⁠ ⊔(단위: 공집합⁠(empty set)⁠)이 모두 모노이드 구조입니다. 벡터 공간에서는 직합⁠(direct sum)⁠ ⊕와 텐서곱 ⊗가 다릅니다. m차원과 n차원 공간의 직합은 m + n차원이고 벡터⁠(vector)⁠의 쌍 (v, w)로 이루어지지만, 텐서곱 $V\otimes W$는 mn차원이고 기저가 $e_i\otimes f_j$들입니다. 두 선형변환⁠(linear transformation)⁠ $f: V\to V'$, $g: W\to W'$의 텐서곱 $f\otimes g$는 $e_i\otimes f_j$를 $f(e_i)\otimes g(f_j)$로 보내는 선형변환이고, 그 행렬이 크로네커 곱입니다. 곧 대상이 자연수⁠(natural number)⁠ n이고 화살표가 행렬인 범주에서 $n\otimes m = nm$이고 화살표의 ⊗가 크로네커 곱이며, 교환 법칙은 크로네커 곱의 잘 알려진 성질 $(A\otimes B)(C\otimes D) = AC\otimes BD$입니다. 텐서곱에는 짝의 합으로만 쓸 수 있는 원소가 있다는 것도 중요합니다. $e_0\otimes f_0 + e_1\otimes f_1$은 어떤 v, w로도 $v\otimes w$ 꼴로 쓸 수 없습니다. 계수들을 2×2 행렬로 늘어놓으면 $v\otimes w$의 계수 행렬은 랭크가 1인데 이것은 단위행렬⁠(identity matrix)⁠이라 랭크가 2이기 때문이고, 일반 원소가 몇 개의 $v\otimes w$의 합인지는 계수 행렬의 특잇값 분해⁠(singular value decomposition)⁠가 알려 줍니다.

확률에서는 유한 집합을 대상으로, 열의 합이 1인 행렬(확률 전이, 마르코프 핵)을 화살표로 하는 범주가 있고, ⊗는 위에서 본 '독립인 두 과정을 나란히 놓기'입니다. 합성은 전이 행렬의 곱, 곧 중간 상태에 대해 확률을 더하는 전확률 공식입니다. 여러 날의 전이를 이렇게 이어 붙이는 규칙이 채프먼–콜모고로프 방정식입니다. 이 범주에는 값을 복사하는 화살표 $A\to A\otimes A$(x를 (x, x)로)와 지우는 화살표 $A\to I$가 있습니다. 결정적인 함수⁠(function)⁠는 복사와 순서를 바꿀 수 있지만 무작위한 과정은 그렇지 않습니다. 공정한 동전을 한 번 던진 결과를 복사하면 (앞, 앞)과 (뒤, 뒤)가 반반이지만, 복사한 뒤 두 번 던지면 네 경우가 1/4씩입니다. 반대로 지우기는 모든 화살표와 순서를 바꿀 수 있는데, 이것이 '열의 합이 1'이라는 조건을 그림으로 적은 것입니다. 결과를 버릴 거라면 과정을 거치든 말든 같다는 뜻이니까요. 이런 성질만으로 조건부 독립과 충분 통계량⁠(sufficient statistic)⁠을 끈 그림으로 다루는 틀을 2019–2020년 켄타 조와 바르트 제이컵스, 토비아스 프리츠가 '마르코프 범주⁠(Markov category)⁠'로 정리했습니다.

양자역학의 범주에서는 복사가 아예 불가능합니다. 상태는 복소 벡터 공간의 벡터이고 두 계를 합친 상태는 텐서곱의 원소이며, 물리적 과정은 선형 사상입니다. 모든 상태 v를 $v\otimes v$로 보내는 선형 사상⁠(linear map)⁠이 있다면, 평행하지 않은 두 상태 a, b의 중첩 a + b에 대해 선형성으로는 $a\otimes a + b\otimes b$가 나와야 하는데 복사라면 $(a+b)\otimes(a+b) = a\otimes a + a\otimes b + b\otimes a + b\otimes b$가 나와야 하므로 모순입니다. 1982년 윌리엄 우터스와 보이치에흐 주렉, 그리고 따로 데니스 디크스가 발표한 복제 불가 정리입니다. 곱집합의 범주에서는 모든 대상에 복사와 지우기가 있고 모든 화살표가 그것과 순서를 바꿀 수 있으며, 거꾸로 대칭 모노이드 범주⁠(symmetric monoidal category)⁠에서 모든 대상에 복사와 지우기가 있고(이들이 '복사한 뒤 하나를 지우면 제자리' 같은 몇 가지 등식을 만족하고) 모든 화살표가 그것과 순서를 바꿀 수 있으면 ⊗는 곱이라는 것이 알려져 있습니다(토머스 폭스, 1976). 그러니 '복사할 수 없음'은 ⊗가 곱이 아니라는 구조적 사실이고, 자원을 한 번씩만 쓰는 논리인 선형 논리⁠(linear logic)⁠가 바로 이 구조의 논리입니다.

끈 그림은 1971년 로저 펜로즈가 텐서⁠(tensor)⁠ 계산을 위해 쓴 표기에서 왔습니다. 1991년 앙드레 조얄과 로스 스트리트는 이것이 증명 방법으로 믿을 만하다는 것을 정리했습니다. ⊗와 ∘로 지은 두 식이 모노이드 범주의 공리⁠(axiom)⁠만으로 같음을 보일 수 있을 필요충분조건은, 두 끈 그림이 선을 끊거나 상자끼리 뚫고 지나가지 않고, 선이 늘 아래에서 위로 흐르도록 유지한 채 평면 위에서 연속적으로 변형되어 겹쳐지는 것입니다. 두 선을 맞바꾸는 화살표 $A\otimes B\cong B\otimes A$가 있고 두 번 바꾸면 제자리인 범주(대칭 모노이드 범주)에서는 선이 서로 엇갈려도 되고, 두 번 바꾸어도 제자리가 아닌 꼬임 모노이드 범주에서는 선이 매듭처럼 꼬인 모양까지 셉니다. 그림으로 하는 계산이 식의 계산을 대신할 수 있다는 이 정리 덕분에 양자 회로, 확률 모형, 신호 흐름도 같은 분야에서 끈 그림을 증명 도구로 씁니다.

모노이드 범주 안에서는 '모노이드'를 다시 정의할 수 있습니다. 대상 M과 곱하기 $M\otimes M\to M$, 단위 $I\to M$가 결합법칙⁠(associativity)⁠과 단위 법칙을 그림으로 만족하면 모노이드 대상⁠(monoid object)⁠이라 합니다. 곱집합의 범주에서는 보통의 모노이드이고, 텐서곱의 벡터 공간 범주에서는 행렬 전체처럼 곱셈이 있는 벡터 공간(대수)이며, 함자들을 합성 ∘로 곱하는 범주에서는 모나드⁠(monad)⁠입니다. '모나드는 자기 함자 범주⁠(functor category)⁠의 모노이드'라는 문장의 '범주'가 바로 이 모노이드 범주입니다. 또 텐서곱에는 커링⁠(currying)⁠이 있습니다. 쌍선형 사상 $U\times V\to W$는 선형 사상 $U\otimes V\to W$와 정확히 하나씩 대응하고, 이것이 다시 $U\to\mathrm{Hom}(V, W)$와 대응합니다. 곱 대신 텐서곱으로 커링하는 이런 범주를 닫힌 모노이드 범주라 하며, 데카르트 닫힌 범주⁠(cartesian closed category)⁠가 그 특별한 경우입니다.

두 가지 오해를 짚어 둡니다. 모노이드 범주는 '모노이드인 범주'가 아닙니다. 대상 하나짜리 범주가 모노이드였던 것과 달리, 여기서는 대상들 위에 곱이 하나 더 있는 것입니다. 또 끈 그림은 아무 그림이나 증명이 되는 것이 아니라, 범주가 가진 구조(대칭인지, 꼬임이 있는지, 복사가 있는지)에 맞는 변형만 허용될 때 증명이 됩니다. 확률의 범주에서 '복사한 뒤 과정을 거치는 그림'과 '과정을 거친 뒤 복사하는 그림'을 같다고 놓으면 틀린 결론이 나옵니다.

이어지는 곳. 크로네커 곱의 교환 법칙은 행렬의 곱과 선형변환의 텐서곱에서, 독립인 과정을 나란히 놓는 일은 마르코프 연쇄와 조건부 확률에서 왔습니다. 대상을 곱하는 방식이 모노이드를 닮았다는 것이 이름의 뜻이고, 그 안의 모노이드 대상이 모나드입니다. 복사할 수 없는 세계의 논리는 선형 논리에서, 곱으로 커링하는 특별한 경우는 데카르트 닫힌 범주에서 볼 수 있습니다. 텐서곱의 원소가 몇 개의 짝의 합인지는 특잇값 분해가 알려 주고, 거리에 덧셈이라는 ⊗를 쓰면 풍부화된 범주⁠(enriched category)⁠가 됩니다. 모든 구조의 출발점인 함자와 자연 변환은 범주론⁠(category theory)⁠의 기본 어휘입니다.