범주와 범주 사이의 구조 보존 사상인 함자를 다양한 예시와 함께 소개하고, 단사범주, 순서, 모노이드, 타입, 다이어그램에서 함자가 어떻게 나타나는지 설명합니다.
이 장부터는 전술을 조금 바꾸겠습니다(여러 주제를 오가느라 여러분도 분명 지쳤을 테니까요). 이제까지 본 구조들을 맥락으로 삼아, 범주의 세계로 전속력으로 뛰어들겠습니다. 이렇게 하면 우리가 그 구조들에서 살펴본 몇몇 개념을 일반화하여, 그것들(그 개념들)을 모든 범주에 대해 유효하게 만들 수 있습니다.
지금까지 우리는 서로 다른 많은 범주와 범주의 종류를 보았습니다. 다시 한 번 정리해 봅시다.
우리는 모든 범주의 어머니인 _집합의 범주_부터 살펴보기 시작했습니다.
또한 그 안에는 타입의 범주처럼 다른 많은 범주들이 들어 있다는 것도 보았습니다(정확히는 여러 종류의 타입 범주가 있지만, 지금은 우리가 배운 것(System F)만 생각합시다).
우리는 또한 다른 대수적 대상들이 사실은 그저 _특별한 종류의 범주_라는 것도 배웠습니다. 예를 들어 _객체_가 하나뿐인 범주(모노이드, 군), 두 객체 사이에 _사상_이 하나만 있는 범주(전순서, 부분순서) 같은 것들입니다.
우리는 또한 _서로 다른 개념에 기반한 범주들_도 많이 정의했습니다. 논리/타입에 기반한 것들뿐 아니라, 색 혼합 부분순서/범주처럼 조금 “덜 진지한” 것들도 있었습니다.
그리고 무엇보다도, 제 축구 선수 위계처럼 완전히 꾸며낸 범주들도 보았습니다. 이런 것들은 형식적으로 _유한 범주_라고 부릅니다.
이 범주들은 그 자체로는 유용하지 않지만, 그 뒤에 있는 생각은 중요합니다. 임의의 점과 화살표 조합을 그려서 그것을 범주라고 부를 수 있으며, 이는 임의의 객체 조합으로 집합을 만들 수 있는 것과 같은 방식입니다.
뒤에서 참고할 수 있도록, 몇 가지 중요한 유한 범주를 봅시다.
가장 단순한 범주는 다음과 같습니다(이 도표의 미니멀리즘을 즐겨 보세요).
그다음으로 단순한 범주는 다음입니다. 객체 하나와, 항등사상 외에는 아무 사상도 없습니다(늘 그렇듯 항등사상은 그리지 않습니다).
객체 수를 둘로 늘리면, 조금 더 흥미로운 범주 몇 가지가 보입니다. 예를 들어 객체 둘과 사상 하나를 가진 범주가 있습니다.
과제 1: 객체가 2개이고, 두 객체 사이에 사상이 많아야 하나만 있는 범주는 이것 말고 정확히 두 개 더 있습니다. 그려 보세요.
마지막으로 객체가 3개이고 사상도 3개인 범주가 있습니다(그중 하나는 나머지 둘의 합성입니다).
우리가 본 많은 범주는 서로 비슷합니다. 예를 들어 색 혼합 순서와 논리를 나타내는 범주는 둘 다 최대 객체와 최소 객체를 가집니다. 이런 유사성을 정확히 짚고, 그것이 무엇을 뜻하는지 이해하려면, 범주들을 서로 연결하는 형식적인 방법이 있으면 유용합니다. 그런 연결의 가장 단순한 형태는 익숙한 동형입니다.
1장에서 우리는 두 집합 사이의 동치를 세워 주는 _집합 동형_에 대해 이야기했습니다. 혹시 잊었다면, 집합 동형은 두 집합 사이의 _양방향 함수_입니다.
또는 이것을 서로 “쌍둥이”인 두 함수로 볼 수도 있습니다. 각각은 다른 하나와 합성했을 때 항등이 됩니다. 형식적으로는 다음과 같습니다.
두 집합 와 가 동형이다(또는 )라는 것은, 함수 와 그 역함수 가 존재하여, 이고 임을 뜻합니다.
그다음 4장에서는 _순서 동형_을 만났고, 이것이 집합 동형과 비슷하지만 한 가지 조건이 더 붙는다는 것을 보았습니다. 즉, 동형을 정의하는 함수들은 단지 존재하기만 해서는 안 되고, 객체들의 순서도 보존해야 합니다.
e.g. 한 순서의 최대 객체는 다른 순서의 최대 객체에 연결되어야 하고, 한 순서의 최소 객체는 다른 순서의 최소 객체에 연결되어야 하며, 그 사이의 모든 객체들에 대해서도 마찬가지입니다. 형식적으로는 다음과 같습니다.
두 순서 사이의 동형은 그 바탕 집합들 사이의 가역 함수이며, 이 함수를( 라고 합시다) 한 집합에서 일정한 순서를 갖는 임의의 두 원소( 와 라고 합시다)에 적용하면, 다른 집합에서도 그에 대응하는 순서를 갖는 두 원소가 나와야 합니다(즉 iff ).
이제 순서 동형의 정의를 일반화하여, 모든 다른 범주(즉 두 객체 사이에 사상이 하나보다 많을 수도 있는 범주)에도 적용되게 하겠습니다.
두 범주가 주어졌을 때, 그들 사이의 동형은 객체들의 바탕 집합 사이의 가역 대응과, 그것들을 잇는 사상들 사이의 가역 대응으로 이루어지며, 각 사상은 같은 시그니처를 가진 사상으로 보내져야 합니다.
이 정의를 자세히 살펴보면, 비록 순서에 대한 정의보다 좀 더 복잡하게 들리고 좀 더 지저분해 보이지만, 실제로는 _같은 것_임을 알 수 있습니다.
두 객체 사이에 사상이 하나밖에 없는 범주에서는 이른바 범주 사이의 “사상 대응”이 자명하므로, 그것을 생략할 수 있을 뿐입니다.
과제 2: 순서에서의 사상 대응은 무엇일까요?
하지만 주어진 두 객체 사이에 사상이 하나보다 많을 수 있다면, 원천 범주의 각 사상이 대상 범주에서 대응하는 사상을 갖는지 확인해야 합니다. 그래서 범주의 객체들 사이의 대응뿐 아니라, 사상들 사이의 대응도 필요합니다.
그런데 우리가 방금 한 일(더 좁은 구조인 순서에 대해 정의된 개념을 더 넓은 구조인 범주에 대해 다시 정의한 것)을 그 개념의 _일반화_라고 부릅니다.
범주적 동형을 자세히 보면, 정의 자체는 그리 어렵지 않다는 걸 알 수 있습니다. 하지만 다른 문제가 하나 있는데, 그것은 이것이 _범주적 동일성이 무엇이어야 하는지의 핵심을 포착하지 못한다_는 점입니다. 왜 그런지에 대해 저는 아주 좋고 직관적인 설명을 고안해 두었지만, 이 여백 절은 그것을 담기에는 너무 좁습니다. 그래서 이것은 다음 장으로 미루겠습니다. 다음 장에서는 범주들 사이의 _양방향 연결_을 더 적절하게 정의하는 방법도 만들 것입니다.
하지만 그전에, 범주들 사이의 단방향 연결, 즉 _함자_를 살펴볼 필요가 있습니다.
추신: 범주적 동형은 실제로도 매우 드뭅니다. 떠오르는 예는 지난 장의 Curry-Howard-Lambek 동형뿐입니다. 왜냐하면 두 범주가 동형이면 그것들을 다른 범주로 취급할 이유가 전혀 없기 때문입니다. 그것들은 사실상 하나이자 같은 것입니다.
논리학자 Rudolf Carnap은 과학에 대해 정확하게 말할 수 있는 방식을 만들기 위해, 영어 같은 자연언어의 구문을 형식화하려는 자신의 프로젝트의 일부로 “functor”라는 용어를 만들었습니다. 원래 functor는 수치값과 결합함으로써 의미가 구체화되는 단어나 구를 뜻했습니다. 예를 들어 “the temperature at o’clock”이라는 구는 의 값에 따라 다른 의미를 가집니다.
즉, functor란 함수처럼 작용하는 구이며, 다만 집합 사이의 함수가 아니라 언어적 개념들 사이의 함수입니다(시간과 온도 같은 것들 말입니다).
이후 범주론의 창시자 중 한 명인 Sanders Mac Lane이 이 단어를 빌려, _범주 사이의 함수처럼 작용하는 것_을 가리키는 데 사용했고, 그것을 다음과 같이 정의했습니다.
두 범주 사이의 함자(그것들을 와 라고 합시다)는 두 개의 대응으로 이루어집니다. 즉 안의 각 _객체_를 안의 객체로 보내는 대응과, 안의 임의의 객체들 사이의 각 _사상_을 안의 객체들 사이의 사상으로 보내는 대응인데, 이때 범주의 _구조를 보존_해야 합니다.
이제 이 정의의 각 요소를 하나씩 살펴보며 풀어 봅시다.
위 정의에서는, 정확히 함수는 아닌 것에 “function”이라는 말을 함부로 쓰지 않기 위해 “mapping”이라는 말을 씁니다. 하지만 이 경우에는 그 대응을 함수라고 불러도 거의 오용이라고 할 수 없습니다. 사상은 잠시 잊고 원천 범주와 대상 범주를 집합으로만 본다면, 객체 대응은 그냥 평범한 함수일 뿐입니다.
객체 대응을 좀 더 형식적으로 정의하려면 범주의 바탕 집합 개념이 필요합니다. 범주 가 주어졌을 때, 의 바탕 집합은 의 객체들을 원소로 갖는 집합입니다. 이 개념을 이용하면, 두 범주 사이의 함자의 객체 대응은 _그 바탕 집합들 사이의 함수_라고 말할 수 있습니다. 그리고 함수의 정의는 여전히 같습니다.
함수란 두 집합 사이의 관계로서, 한 집합의 각 원소(함수의 출발 집합)를 다른 집합(함수의 도착 집합)의 정확히 하나의 원소와 짝짓는 것입니다.
함자를 이루는 두 번째 대응은 범주들의 사상들 사이의 대응입니다. 이것 역시 함수와 비슷하지만, 한 가지 추가 요구사항이 있습니다. 즉 주어진 출발 객체와 도착 객체를 가진 각 사상은, 객체 대응에 따라 안의 대응하는 출발 객체와 도착 객체를 가진 사상으로 보내져야 합니다.
사상 대응을 더 형식적으로 정의하려면 호모모르피즘 집합 개념이 필요합니다. 이것은 어떤 범주에서 주어진 두 객체 사이를 가는 모든 사상을 모아 둔 집합입니다. 이 개념을 이용하면, 두 범주의 사상들 사이의 대응은 _서로 대응하는 호모모르피즘 집합들 사이의 함수들의 집합_으로 이루어진다고 말할 수 있습니다.
_호모모르피즘 집합_과 바탕 집합 개념 덕분에, 범주적 개념을 정의할 때 집합론으로 “빠져나가서” 모든 것을 함수로 정의할 수 있게 된다는 점에 주목하세요.
이렇게 해서 함자를 이루는 두 대응(객체 사이의 대응 하나와 사상 사이의 대응 하나)을 보았습니다. 하지만 이런 두 대응의 임의의 쌍이 함자가 되는 것은 아닙니다. 앞서 말했듯이, 이 대응들은 단지 존재하기만 하는 것이 아니라, 원천 범주의 _구조를 대상 범주 안에서 보존_해야 합니다. 이것이 무슨 뜻인지 보려면 2장에서 본 범주의 정의를 다시 떠올려 봅시다.
범주는 객체들(점이라고 생각할 수 있습니다)과, 한 객체에서 다른 객체로 가는 사상들(화살표)의 모음이며, 다음을 만족합니다.
- 각 객체는 항등사상을 가져야 합니다.
- 적절한 타입 시그니처를 가진 두 사상을 세 번째 사상으로 합성하는 방법이 있어야 하며, 그 합성은 결합적이어야 합니다.
이 정의는 다음 두 가지 _함자 법칙_으로 옮겨집니다.
두 범주 사이의 함자(그것들을 와 라고 합시다)는 두 개의 대응으로 이루어집니다. 즉 안의 각 _객체_를 안의 객체로 보내는 대응과, 안의 임의의 객체들 사이의 각 _사상_을 안의 객체들 사이의 사상으로 보내는 대응인데, 이때 범주의 _구조를 보존_해야 합니다.
사상들 사이의 함수는 _항등을 보존_해야 합니다. 즉 모든 항등사상은 다른 항등사상으로 보내져야 합니다.
함자는 또한 _합성을 보존_해야 합니다. 즉 임의의 두 사상 와 에 대해, 원천 범주에서 그들의 합성에 대응하는 사상은 대상 범주에서 대응하는 사상들의 합성에 대응하는 사상으로 보내져야 하므로, 입니다.
이 두 법칙으로 함자의 정의가 마무리됩니다. 단순하지만, 곧 보겠듯 아주 강력한 개념입니다.
왜 이것이 그토록 강력한지 보려면, 몇 가지 예를 살펴봅시다.
다음과 같은 흔한 비유 표현이 있습니다(이 책에서도 계속 쓰고 있습니다).
가 같다면, 는 같다.
또는 “ 는 와 같은 방식으로 와 관련되어 있다.” 예를 들어 “학교가 기업과 같다면, 교사는 상사와 같다.” 같은 식입니다.
이 비유 표현은 사실 일상 언어로 함자를 설명하는 방식입니다. 이 말이 뜻하는 바는, 학교와 교사 사이에 어떤 연결들의 집합(범주론 용어로는 “사상들”)이 있는데, 그것이 기업과 상사 사이의 연결과 비슷하다는 것입니다. 즉 학교 관련 사물들의 범주를 일 관련 사물들의 범주에 연결하는 어떤 구조 보존 사상이 있어서, 학교()를 기업()에, 교사()를 상사()에 대응시키고, 학교와 교사 사이의 연결()을 기업과 상사 사이의 연결()에 대응시킨다는 뜻입니다.
“기호란, 그것을 앎으로써 우리가 다른 어떤 것을 더 알게 되는 것이다.” — Charles Sanders Peirce
매우 _메타적_인 함자 예시로 시작해 봅시다. 바로 이 책의 도표/그림입니다.
아마 여러분도 눈치챘겠지만, 범주론에서 도표는 특별한 역할을 합니다. 다른 분야에서는 도표의 기능이 어디까지나 보조적이어서, 이미 다른 방식으로 정의된 것을 보여 주기만 하지만, 여기서는 도표 자체가 정의 역할을 합니다.
예를 들어 1장에서 우리는 함수 합성을 다음과 같이 정의했습니다.
두 함수 와 의 합성은, 다음 도표가 가환하도록 정의되는 세 번째 함수입니다.
“객체 세 개 와 와 가 있고 사상 두 개 와 가 있다고 하자…” 같은 긴 정의를 쓰는 대신 도표로 정의하는 것이 얼마나 유익한지는 모두가 압니다.
하지만 이것(도표를 사용해 정의하는 것)에는 문제가 있습니다. 수학의 정의는 형식적이어야 하므로, 도표를 정의로 사용하려면 먼저 _도표 자체의 정의를 형식화_해야 합니다.
그러면 어떻게 해야 할까요? 핵심 관찰 하나는, 도표가 유한 범주처럼 보인다는 점입니다. 예를 들어 위의 정의는 범주 와 같은 모습입니다.
하지만 이것만으로는 충분하지 않습니다. 유한 범주는 그저 구조일 뿐인데, 도표는 _기호_이기도 하기 때문입니다. Peirce가 유명하게 말했듯, 그것은 “그것을 앎으로써 우리가 다른 어떤 것을 더 알게 되는 것”입니다(또는 Umberto Eco의 말로 하면, “거짓말을 하는 데 사용할 수 있는 것”이기도 합니다).
이 때문에, 도표의 구조를 부호화하는 유한 범주 외에도, 도표의 정의에는 이 범주를 다른 맥락에서 “해석”하는 방법도 들어가야 합니다. 즉 _함자_가 포함되어야 합니다.
이렇게 해서 함자 개념은 도표라는 개념을 형식화하게 해 줍니다.
_도표_는 하나의 유한 범주(이를 _색인 범주_라고 부릅니다)와, 그 범주에서 다른 어떤 범주로 가는 함자로 이루어집니다.
기호학을 안다면, 함자의 원천 범주와 대상 범주를 각각 _기표_와 _기의_로 볼 수도 있습니다.
이제 함자 개념이 범주론에서 얼마나 중요한 역할을 하는지 벌써 알 수 있습니다. 함자 덕분에 범주론의 도표는 형식적으로 명시될 수 있으며, 즉 그 자체로 범주적 대상이 됩니다.
오히려 그것들은 범주적 대상 중에서도 _가장 뛰어난 것들_이라고 말할 수도 있겠네요(TODO: 마지막 농담은 지우기).
지도는 그것이 나타내는 영토가 아니지만, 올바르다면 영토와 유사한 구조를 가지며, 바로 그것이 지도의 유용성을 설명한다. — Alfred Korzybski
함자를 종종 “map”이라고 부르는 데에는 이유가 있습니다. 지도는, 다른 모든 도표와 마찬가지로, 함자이기 때문입니다. 우리가 어떤 공간을 생각하고, 그 안에 도시와 우리가 이동하는 도로가 있다고 합시다. 도시를 객체로, 그 사이의 도로를 사상으로 보면, 도로 지도는 그 공간의 어떤 영역을 나타내는 범주와, 그 지도 안의 객체들을 실제 세계의 객체들에 대응시키는 함자로 볼 수 있습니다.
지도에서는 합성의 결과로 생기는 사상들이 자주 그려지지 않지만, 우리는 그것들을 늘 사용합니다. 그것들을 _경로_라고 부릅니다. 그리고 합성을 보존하는 법칙은, 우리가 지도 위에서 만드는 모든 경로가 실제 세계의 경로에 대응함을 말해 줍니다.
함자가 되기 위해 지도는 현실의 모든 도로와 모든 이동 가능성을 나열할 필요가 없다는 점에 주목하세요(“지도는 영토가 아니다”). 유일한 요구사항은 _지도에 나오는 도로가 실제여야 한다_는 것뿐입니다. 이것은 모든 다대일 관계(즉 함수)가 공유하는 특징입니다.
보았듯이, 함자는 범주론뿐 아니라 인간의 정신을 연구하는 많은 분야, 이를테면 논리학, 언어학, 기호학 등에도 등장합니다. 왜 그런지에 대해 저는 블로그 글에서 생각해 본 적이 있습니다. 제 대답은 인간의 지각, 인간의 사고 자체가 함자적이라는 것입니다. 우리는 주변 세계를 지각하기 위해, 더 원초적인 “저수준” 정신 모델에서 더 추상적인 “고수준” 모델로 가는 여러 함자를 거칩니다.
지각은 날것의 감각 데이터에서 시작한다고 말할 수 있습니다. 거기서 우리는 (함자를 이용해) 세계가 어떻게 작동하는지에 대한 어떤 기본 모델을 담은 범주로 갑니다. 우리가 보고 있는 객체들을, 마음속에서 형성한 어떤 개념들에 대응시키는 것입니다.
그다음 우리는 이 모델을 더 추상적인 또 다른 모델(혹은 여러 모델)과 연결합니다. 이 모델들은 우리가 놓인 상황에 대한 더 높은 수준의 개요를 제공합니다. 역시 함자적 연결을 사용합니다(기술적으로는 부분범주에서 오는 함자들입니다).
이것은 더 단순한 것에서 더 추상적인 것으로 가는 연결의 진행으로 볼 수 있습니다(즉 사상이 더 적은 범주에서 사상이 더 많은 범주로 가는 것입니다).
이 연결들이 본질적으로 함자적인 이유는, 그것들이 순전히 _구조_의 관점에서 작동하기 때문입니다. 어떤 객체에 대한 관념은 그 객체 자체와 아무 공통점이 없습니다(e.g. 비스킷에 대한 관념은 둥글지도 달지도 않습니다). 관념이 표현 대상과 공유하는 것은, 그 관념들 사이의 연결이 실제 비스킷이 다른 객체들과 맺는 어떤 연결을 모방한다는 점입니다.
물론 이 모든 것은 그저 추측일 뿐입니다. 하지만 우리의 뇌의 어느 부분도(또는 그것이 만들어 내는 신호도) 사람/자전거/나무와 조금도 닮지 않았는데, 어떻게 우리는 사람이 자전거를 타다가 나무에 부딪히는 장면을 상상하는 따위의 생각을 형성할 수 있을까요?
답은 구조입니다. 생각은 상황의 구조를 가지므로 그것을 가리킬 수 있습니다(비록 각 요소를 그 자체로는 가리킬 수 없더라도).
이 짧은 우회를 마쳤으니, 다시 평소 하던 방식으로 돌아가 봅시다.
혹시 군론에 _군 준동형_이라는 멋진 것이 있다는 걸 아시나요?
군 준동형(_모노이드_에 대해 말할 때는 모노이드 준동형)은 군/모노이드의 바탕 집합들 사이의 함수로서, 군 연산을 보존하는 것입니다. 즉 입니다(여기서 와 는 군의 연산자입니다).
예를 들어, 지금 시간이 00:00시(또는 12 PM)라면, 시간 뒤는 몇 시일까요? 이 질문의 답은 정수 집합을 출발 집합과 도착 집합으로 하는 함수로 표현할 수 있습니다.
이 함수는 흥미롭습니다. 그것은 (모듈러) 덧셈 연산을 보존합니다. 즉 지금부터 13시간 뒤가 1시이고, 14시간 뒤가 2시라면, (13 + 14)시간 뒤의 시간은 (1 + 2)시가 됩니다.
형식적으로 말하면, 이 함수 를 라고 부를 때 다음 식이 성립합니다(우변의 는 모듈러 덧셈입니다). 이 식이 성립하므로, 이 함수는 덧셈에 대한 정수의 군과 밑이 11인 모듈러 산술의 군(여기서 11은 다른 수로 바꿔도 됩니다) 사이의 _군 준동형_입니다.
준동형이 있으려면 두 군이 꼭 이렇게 비슷할 필요는 없습니다. 예를 들어 어떤 수를 2의 제곱으로 보내는 함수, 즉 를 생각해 봅시다(여기서도 2는 다른 수로 바꿔도 됩니다). 이 함수는 덧셈에 대한 정수의 군과 곱셈에 대한 정수, 즉 사이의 군 준동형을 만들어 냅니다.
잠깐, 우리가 원래 무슨 이야기를 하고 있었죠? 아, 맞다.
군 준동형은 함자입니다. 왜 그런지 보려면 군의 범주론적 표현으로 바꿔 보고, 첫 번째 예를 다시 살펴봅시다(도표를 더 단순하게 하기 위해 대신 를 쓰겠습니다).
군/모노이드를 한 객체 범주로 보면, 군/모노이드 준동형은 그 범주들 사이의 함자일 뿐입니다.
정말 그런지 봅시다.
군/모노이드는 범주로 볼 때 객체가 하나뿐입니다. 따라서 임의의 두 군/모노이드 사이의 객체 대응도 하나뿐입니다. 원천 군의 (유일한) 객체를 대상 군의 객체로 보내는 대응입니다(도표에는 그리지 않았습니다).
위 사실 때문에, 사상 대응만이 군 준동형의 유일하게 중요한 성분입니다. 범주론적 관점에서는 군의 원소들( 와 등)이 사상들( , 등)에 대응하므로, 사상 대응은 사실 군의 원소들 사이의 대응일 뿐이며, 도표에서도 이를 볼 수 있습니다.
첫 번째 함자 법칙은 자명합니다. 원천 군의 유일한 항등원(이는 그 유일한 객체의 항등사상에 대응합니다)은 대상 군의 유일한 항등원으로 보내져야 한다는 뜻일 뿐입니다. 군의 경우 이것은 두 번째 법칙에서 바로 따라오고, 모노이드의 경우에는 별도의 조건으로 추가해야 합니다.
그리고 군에서 두 원소를 결합하는 연산이, 군을 범주로 볼 때 _함수 합성_에 대응한다는 것을 기억하면, 군 준동형 방정식은 바로 두 번째 함자 법칙의 진술임을 알 수 있습니다. 즉 입니다.
많은 대수 연산이 이 식을 만족합니다. 예를 들어 사이의 군 준동형에 대한 함자 법칙은 유명한 대수 법칙, 즉 를 말해 주는 식일 뿐입니다.
과제 3: 군의 첫 번째 함자 법칙(항등 보존)이 두 번째 법칙에서 증명될 수 있음을 보이세요. 이것은 군에서는 참이지만 모노이드에서는 성립하지 않음에 유의하세요.
이제 함자와는 전혀 관계없는 개념에 대해 이야기해 봅시다, 넛지넛지(그래도 형편없는 농담도 농담 없는 것보다는 낫겠죠?) 순서 이론에는 순서들 사이의 함수라는 개념이 있고(순서가 모노이드/군처럼 집합에 기반하기 때문이니 놀랍지 않습니다), 그중 미적분과 해석학에 응용되는 매우 흥미로운 종류의 함수로 단조 함수(_monotone map_이라고도 합니다)가 있습니다.
단조 함수는 두 순서 사이의 함수로서, 원천 순서에서 객체들의 순서를 대상 순서에서도 보존합니다. 즉 함수 는 원천 순서의 모든 와 에 대해, 이면 일 때 단조입니다.
예를 들어 현재 시각을 어떤 물체가 이동한 거리로 보내는 함수는 단조입니다. 시간이 증가하면 이동 거리도 증가하거나(혹은 그대로이거나) 하기 때문입니다.
이런 함수나 다른 단조 함수를 선 그래프로 그려 보면, 그래프가 한 방향으로만 간다는 것을 알 수 있습니다(즉 계속 올라가거나 계속 내려갑니다).
이제 단조 함수도 함자임을 보이려 합니다. 준비되셨나요?
순서를 얇은 범주로 보면, 단조 사상은 함자입니다.
범주와 마찬가지로, 순서의 객체 대응은 그 순서들의 바탕 집합들 사이의 함수로 표현됩니다.
모노이드에서는 함자의 객체 대응 성분이 자명했습니다. 여기서는 그 반대입니다. 사상 대응이 자명합니다. 원천 순서의 두 객체 사이에 있는 사상이 주어지면, 그것을 대상 순서에서 대응하는 두 객체 사이의 사상으로 보내면 됩니다. 단조 함수가 원소들의 순서를 존중한다는 사실이, 그 후자의 사상이 실제로 존재함을 보장합니다.
단조 사상이 첫 번째 함자 법칙을 만족한다는 것은 어렵지 않게 알 수 있습니다. 한 객체와 자기 자신 사이에 가는 사상은 항등사상뿐이기 때문입니다.
그리고 두 번째 법칙()도 자명하게 따라옵니다. 함수가 순서를 보존한다는 것, 즉 만약
와
이면 당연히
임을 보이면 되기 때문입니다.
과제 4: 왜 이 법칙이 성립하는지 보이세요.
좋습니다, 이런 추상적인 허튼소리는 충분합니다. 이제 숫자 사이의 “정상적인” 함수에 대해 이야기해 봅시다.
미적분에는 선형 함수(_1차 다항식_이라고도 합니다)라는 개념이 있습니다.
선형 함수는 꼴의 함수로서, 어떤 상수(예시에서는 로 표시됨)로 인자를 곱하는 것 외의 연산을 포함하지 않습니다.
그런데 이런 함수들을 그려 보기 시작하면, 그것을 설명하는 또 다른 방법이 있다는 걸 알게 됩니다. 그 그래프는 언제나 직선으로 이루어집니다.
과제 5: 선형 함수의 그래프가 왜 직선으로 이루어지는지 설명해 보세요.
이 함수들의 또 다른 흥미로운 성질은, 대부분이 덧셈을 _보존_한다는 것입니다. 즉 임의의 와 에 대해 입니다. 우리는 이미 이 식이 두 번째 함자 법칙과 같다는 것을 알고 있습니다. 따라서:
선형 함수는 자연수의 덧셈 모노이드와 자기 자신 사이의 함자일 뿐입니다.
나중에 보겠지만, 이것들은 벡터 공간의 범주에서의 함자 예시이기도 합니다.
과제 6: 선형 함수가 덧셈을 보존함을 보이세요.
또한 자연수를 순서로 보면, 직선으로 그려지는 함수는 분명 모두 단조이므로, 선형 함수는 이 관점에서도 함자입니다.
하지만 직선으로 그려진다고 해서 모두 덧셈을 보존하는 것은 아닙니다. 꼴의 함수에서 가 0이 아닌 경우도 직선이며(그리고 역시 선형이라고 부르기도 합니다), 그러나 덧셈은 보존하지 않습니다.
이 경우 위 공식은 다음과 같이 됩니다. .
타입 이론/타입 시스템은 하나의 범주를 이루며, 그 범주 안에는 프로그래머가 매일 사용하는 함자들이 있습니다. 예를 들어 리스트 함자가 그렇고, 이것을 예시로 사용하겠습니다. 리스트 함자는 단순한(원시적인) 타입과 함수의 세계를 더 복잡한(제네릭한) 타입과 함수의 세계로 보내는 함자의 예입니다.
하지만 기초부터 시작합시다. 타입 이론의 맥락에서 함자 개념을 정의하는 것은, 쓰는 용어 몇 개를 바꾸고, 선택적으로 수식의 글꼴을 “현대적”인 것에서 “고정폭”으로 바꾸는 것만큼이나 간단합니다.
타입의
범주들(그것들을A와B라고 합시다) 사이의 함자는,A의 각객체_타입_을B의 어떤 타입으로 보내는 대응과,A안의 타입들 사이의 각사상_함수_를B안의 타입들 사이의 함수로 보내는 대응으로 이루어지며,범주타입 시스템의 구조를 보존해야 합니다.
이 두 정의를 비교해 보면, 수학자와 프로그래머는 매우 다른 공동체이지만, 둘 다 함자를 사용한다는 점에서(그리고 특이한 글꼴에 대한 애정이라는 점에서도) 하나로 묶인다는 것을 알게 됩니다.
함자의 첫 번째 성분은 각 타입을 다른 타입으로 바꾸는 대응입니다. 즉 _타입 수준 화살표_입니다. 그런데 우리는 이것을 이미 알고 있습니다. 타입 이론 용어로 이것은 _다형 타입_으로 알려져 있습니다(다형 타입은 모든 타입을 다른 타입으로 보내는 화살표일 뿐이기 때문입니다).
도표 모양은 비슷해 보여도, 다형적인 타입 수준 화살표는 다형적인 값 수준 화살표와는 완전히 다르다는 점에 유의하세요. 즉 타입 수준* 화살표 List<A>는 각 _타입_을 _타입_으로 바꾸기 때문에(e.g. 타입 string을 타입 로, 를 로 보내는 식입니다), 이것은 a에서 List<a>로 가는 다형적인 값 수준 화살표, 또는 수학스러운 Haskell식 표기로 와는 다른 것입니다. 후자는 타입 의 값을 타입 의 값으로 바꾸며(값 수준의 다형 함수는 이 장의 뒤에서 배우겠습니다).
그러므로 함자의 타입 대응은 단순히 다형 타입입니다(서로 다른 두 다형 타입 사이의 함자도 있을 수 있지만, 그것은 나중에 보겠습니다). 그렇다면 _함수 대응_은 무엇일까요? 이것은 단순 타입에 작동하는 임의의 함수, 예를 들어 를 그보다 복잡한 대응물들 사이의 함수, e.g. 로 바꾸는 대응입니다.
타입 이론에서 이 대응은 라는 타입 시그니처를 가진 map이라는 고차 함수로 표현됩니다. 여기서 는 제네릭 타입을 나타냅니다.
이 타입 시그니처를 가진 가능한 모든 함수(그리고 함자 법칙을 만족하는 모든 함수)가 함자를 만들어 내기는 하지만, _그런 함자가 모두 유용한 것은 아니다_라는 점에 유의하세요. 보통 주어진 제네릭 타입에 대해 의미가 있는 것은 단 하나뿐이며, 그래서 우리는 그 리스트 함자라고 말하고, map을 제네릭 데이터타입 안에 메서드로 직접 정의합니다.
리스트와 비슷한 구조의 경우, 유용한 map 구현은 원래의(단순한) 함수를 리스트의 모든 원소에 적용하는 것입니다.
class Array<A> {
map (f: A => B): Array<B> {
let result = [];
for (obj of this) {
result.push(f(obj));
}
return result;
}
}
map은 단순 타입의 표준 함수들을 더 복잡한 맥락으로 가져와 코드 재사용을 가능하게 할 뿐 아니라, 프로그래밍 맥락에서는 다음과 같은 함자 법칙 덕분에 예측 가능한 방식으로 작업하게 해 줍니다.
항등 법칙:
a.map(a => a) == a
합성 법칙:
a.map(f).map(g) == a.map((a) => g(f(a)))
과제 7: 예시를 사용해서 이 법칙들이 지켜진다는 것을 스스로 확인해 보세요.
이제 이렇게 많은 함자의 예를 보았으니, 비로소 백만 달러짜리 질문, 즉 함자는 무엇에 쓰이고 왜 유용한가에 답해 볼 수 있습니다(이 질문은 종종 “왜 이런 (추상적인) 허튼소리로 내/네 시간을 낭비하느냐?”라고도 표현됩니다).
우리는 _지도가 함자_라는 것을 보았고, _지도가 유용하다_는 것도 알고 있으니, 거기서부터 시작해 봅시다.
그렇다면 왜 지도가 유용할까요? 분명 그것은 지도 위의 점과 화살표가 여러분이 방문하는 장소의 도시와 도로에 대응한다는 사실, 즉 지도 자체가 함자라는 사실과 관련이 있습니다. 하지만 두 번째 측면도 있습니다. 지도(적어도 유용한 지도)는 자신이 나타내는 실제 대상보다 _다루기 더 단순_합니다. 예를 들어 도로 지도가 유용한 이유는, 그것이 나타내는 영토보다 더 작기 때문이어서, 두 장소 사이의 경로를 찾으려면 실제 세계를 일일이 여행하는 것보다 지도에서 따라가는 편이 훨씬 쉽기 때문입니다.
타입 이론의 함자도 프로그래밍에서 비슷한 이유로 쓰입니다. string, number, boolean 같은 단순 타입을 다루는 함수는 … 단순합니다. 적어도 리스트나 다른 제네릭 타입을 다루는 함수와 비교하면 그렇습니다. map 함수를 사용하면, 그런 타입들에 대해 일일이 생각하지 않고도 그것들 위에서 연산할 수 있고, 단순 값들을 변환하는 함수로부터 그것들을 변환하는 함수를 도출할 수 있습니다. 다시 말해 함자는 _추상화_의 수단입니다.
물론 지도의 모든 경로가, 또 제네릭 데이터타입 사이의 모든 함수가, 그 안에 담긴 타입들 사이의 함수만으로 유도될 수 있는 것은 아닙니다. 이것은 일반적으로 많은 “유용한” 함자에 대해 참입니다. 원천 범주가 대상 범주보다 “더 단순”하기 때문에, 대상의 일부 사상은 원천에 대응물이 없습니다. 즉 모델을 단순하게 만들면 필연적으로 어떤 능력을 잃게 됩니다. 이것은 “지도는 영토가 아니다”라는 원리의 결과입니다(Joel Spolsky의 말로 하면 “모든 추상화는 새는 추상화다”).
이제 마무리하기 전에, 프로그래밍에서 특히 유용한 함자 관련 개념 하나를 더 살펴보겠습니다. 바로 _점찍힌 자기함자_입니다.
점찍힌 자기함자가 무엇인지 이해하려면 먼저 _자기함자_가 무엇인지 알아야 합니다. 사실 지난 절에서 이미 몇 가지 예를 보았습니다. 설명해 보겠습니다. 그 도표들의 모양만 보면, 프로그래밍의 함자가 서로 다른 범주를 연결하는 것처럼 보일 수도 있습니다.
하지만 그렇지 않습니다. 타입 시스템은 하나의 범주이고, 모든 함자는 이 범주에서 자기 자신으로 갑니다.
네, 이것이 바로 우리가 _자기함자_라고 부르는 것입니다.
자기함자는 원천과 대상이 하나이자 같은 범주인 함자입니다.
그렇다면 자기함자의 예로는 무엇이 있을까요? 아마 익숙해 보일 하나에 집중하고 싶습니다. 바로 각 범주의 _항등 함자_입니다. 이 함자는 각 객체와 사상을 자기 자신으로 보냅니다.
그리고 이것이 익숙해 보일 수 있는 이유는, 항등 함자가 항등사상과 비슷하기 때문입니다. 실제 값을 직접 다루지 않고도 값과 관련된 것들에 대해 이야기할 수 있게 해 줍니다.
마지막으로 점찍힌 함자를 정의할 수 있습니다.
항등 함자와, 항등 함자로부터 _자연 변환_될 수 있는 다른 모든 함자를 _점찍힌 함자_라고 부릅니다(즉 어떤 함자가 점찍혀 있다는 것은 항등 함자에서 그 함자로 가는 자연 변환이 존재한다는 뜻입니다).
곧 보겠지만, 리스트 함자는 점찍힌 함자입니다.
우리는 아직 한 함자가 다른 함자로 자연 변환된다는 것이 무엇을 뜻하는지 논의하지 않았습니다(비록 위의 가환 도표가 어느 정도 힌트를 주긴 하지만). 하지만 프로그래밍 언어의 타입 범주에만 집중한다면, _자연 변환은 그저 다형 함수_일 뿐입니다. e.g. 이것은 이며, 타입의 구조를 보존합니다. 즉 다음 도표가 가환하는 함수입니다.
이 함자의 경우, 문제의 함수는 입니다. 즉 모든 값을 “싱글턴” 리스트 안에 넣는 함수입니다.
여기서 멈추겠습니다. 자연 변환은 복잡한 것이고, 그것을 한 장 전체(바로 다음 장)에서 다루고 싶기 때문입니다.
하, 이번엔 제가 여러분을 속였네요(적어도 그러길 바랍니다). 아마 이 장에서 다른 범주를 더 도입하지는 않겠거니 생각했을 텐데, 지금 정확히 그것을 하려고 합니다. 그리고(다시 한 번 놀랍게도) 새 범주는 함자의 범주가 아닙니다(걱정 마세요, 그건 다음 장에서 도입합니다). 대신 (작은) 범주의 범주를 살펴보겠습니다.
작은 범주의 범주는 작은 범주들(예를 들면 집합의 범주 , 모노이드의 범주 , 순서의 범주 등)을 객체로 하고, 함자를 사상으로 하는 범주입니다.
우리는 아직 함자도 합성된다는 사실(그리고 그것이 결합적이라는 사실)을 언급하지 않았지만, 함자는 그저 함수들의 묶음이니 당연한 일입니다.
과제 8: 함자의 정의를 따라가 보며 함자가 어떻게 합성되는지 살펴보세요.
과제 9: 작은 범주의 범주에서 시작 객체와 끝 객체는 무엇인가요?
범주론의 재귀적 성격은 때때로 우리를 혼란스럽게 할 수 있습니다. 우리는 처음에 범주가 _객체와 사상으로 이루어져 있다_고 말했는데, 이제는 범주들 사이의 사상(함자)이 있다고 말하고 있습니다. 게다가 객체가 범주 그 자체인 범주도 있습니다. 그렇다면 범주는… 범주의 한 예라는 뜻일까요? 직관적으로는 조금 이상하게 들립니다(예를 들어 비스킷 안에 다른 비스킷이 들어 있거나, 집을 짓는 재료로 집을 쓰지는 않으니까요). 하지만 실제로 그렇습니다. 예를 들어 모든 모노이드는 객체가 하나뿐인 범주이지만, 동시에 모노이드는 하나의 범주, 즉 모노이드의 범주에 속한다고 볼 수 있고, 그 안에서 모노이드는 모노이드 준동형으로 연결됩니다. 예를 들어 군의 범주도 있고, 이것은 모노이드의 범주를 부분범주로 포함합니다. 모든 모노이드는 군이기 때문입니다 등등.
범주론은 모든 것을 _범주화_합니다. 그래서 범주론의 관점에서 보면, 수학 전체는 _끝없이 이어지는 범주_입니다. 어떤 범주를 우주로 볼지, 혹은 점으로 볼지는 전적으로 맥락에 달려 있습니다. 범주론은 추상적 이론입니다. 즉 실제 사태를 그대로 재현하려는 것이 아니라, 아주 다양한 생각을 표현하는 데 쓸 수 있는 언어를 제공하려는 것입니다.
과제 1: 객체가 2개이고, 두 객체 사이에 사상이 많아야 하나만 있는 범주는 이것 말고 정확히 두 개 더 있습니다. 그려 보세요.
답은 다음과 같습니다.
동형은 범주론에서의 동일성을 뜻하므로, 화살표를 왼쪽에서 오른쪽으로 뒤집는 것은 새로운 범주로 치지 않습니다.
세 번째 범주에 대해서는, 사상을 자기 자신과 합성했을 때 무엇이 나오는지를 지정해야 합니다.
이 법칙은 항등 이외의 사상이 딱 1개만 있게 된다는 것을 보장합니다. 이 법칙이 없으면 사상이 무한히 많은 범주가 생기게 됩니다(모노이드 장의 자유 모노이드를 보세요). 이것을 다른 것으로 바꾸면 사상의 수는 유한할 수는 있지만, 여전히 1개보다 많게 됩니다.
과제 2: 순서에서의 사상 대응은 무엇일까요?
순서의 사상 대응은, 한 순서에서 주어진 한 쌍의 객체 사이에 존재하는 유일한 사상을, 다른 순서에서 그 대응물 사이의 유일한 사상으로 보내는 것뿐입니다. 순서 동형의 “순서 보존” 조건은 이 사상이 존재함을 보장합니다. 즉 한 순서에서 이면, 다른 순서에서도 가 됩니다.
과제 3: 군의 첫 번째 함자 법칙(항등 보존)이 두 번째 법칙에서 증명될 수 있음을 보이세요. 즉 와 가 군이고, 가 군 준동형이면, 임을 보이세요. 이것은 군에서는 참이지만 모노이드에서는 성립하지 않음에 유의하세요.
우리는 다음을 압니다.
그래서
(두 번째 함자 법칙)
하지만 항등 연산은 식의 어디에 넣어도 값을 바꾸지 않으므로,
(식에 항등 추가)
그리고 를 소거하면,
이 마지막 단계는 군에서만 유효합니다. 사상을 소거하는 것은 그 역원을 적용하는 것이고, 모노이드의 사상은 역원을 갖지 않기 때문입니다.
과제 4: 왜 이 법칙이 성립하는지 보이세요.
범주적 언어로 쓰면, 문제는 와 이면 임을 보이라는 것입니다.
증명은 과제 2와 같은 접근을 사용합니다. 순서에서는 주어진 타입 시그니처를 가진 사상이 하나밖에 없으므로, 타입 시그니처가 같은 두 사상은 서로 같아야 합니다.
그러면 대상 순서에서 이 두 사상을 합성하면(), 다음과 같은 사상을 얻습니다.
원천 순서에서 두 사상을 합성한 뒤, 함자 법칙을 써서 대상 순서의 대응 사상을 얻으면, 객체 에서 로 가는 또 다른 사상을 얻습니다.
하지만 순서에서는 시그니처 를 가진 사상은 하나뿐이므로, 이 두 사상은 서로 같아야 합니다.
과제 5: 선형 함수의 그래프가 왜 직선으로 이루어지는지 설명해 보세요.
선형 함수는 항상 일정한 비율로 증가합니다(즉 도함수가 항상 일정합니다).
함수의 기울기는 증가율의 변화를 반영하므로, 선형 함수의 경우 그래프는 직선입니다.
과제 6: 선형 함수가 덧셈을 보존함을 보이세요.
어떤 함수 가 있고, 이것이 어떤 상수 를 곱한다고 합시다. e.g. 다음과 같습니다.
와
이 둘을 더하면
덧셈의 분배법칙에 의해
하지만 의 정의에 의해 다음도 성립합니다.
둘 다 와 같은 두 항을 합치면,
반대 방향으로도 성립함을 보일 수 있지만, 조금 더 복잡합니다.
과제 7: 예시를 사용해서 이 법칙들이 지켜진다는 것을 스스로 확인해 보세요.
핵심은 법칙에 익숙해지도록 조금 직접 가지고 놀아 보는 것입니다. 어떤 집합과 함수들을 써도 좋습니다. 여기 예시가 있습니다.
항등 법칙:
[1, 2, 3].map(a => a) == [1, 2, 3]
합성 법칙:
let f = (a) => a + 1
let g = (a) => a * 2
[1, 2, 3].map(f).map(g) == [1, 2, 3].map((a) => g(f(a)))
과제 8: 함자의 정의를 따라가 보며 함자가 어떻게 합성되는지 살펴보세요.
아마 준비는 간단하지 않았을지 몰라도, 연습 자체는 역시 자명한 편입니다. 핵심은 함자가 무엇으로 이루어져 있는지를 하나씩 따라가며, 두 함자의 성분들이 어떻게 합성되는지를 보는 것입니다.
함자의 두 성분은 객체 대응과 사상 대응입니다.
객체 대응은 두 범주의 바탕 집합을 잇는 함수일 뿐이므로, 적절한 타입 시그니처를 가진 두 함자
와
가 있으면, 이 범주들의 바탕 집합을 잇는 두 함수도 있습니다.
와
.
따라서 객체 대응에 대한 답은, 이 두 함수를 합성해 함수 를 얻는 것입니다(이것이 함자의 기반이 될 수 있습니다).
사상 대응에 대해서도, 각 범주의 hom-set들에 대해 똑같이 하면 됩니다.
과제 9: 작은 범주의 범주에서 시작 객체와 끝 객체는 무엇인가요?
집합의 범주 에서의 시작 객체와 끝 객체 개념을 기억한다면, 범주의 범주 에서도 기본적으로 같다는 것을 알게 될 것입니다.
에서 시작 객체는 공집합이고, 에서 시작 범주는 빈 범주입니다. 빈 범주에서 다른 어떤 범주로 가는 유일한 함자는, 역시 아무것도 아무것에도 보내지 않는 함자입니다.
에서 끝 객체는 원소가 하나인 집합이고, 에서 끝 범주는 범주 입니다. 이 범주는 객체 하나를 가지며, 항등사상 외의 사상은 없습니다. 임의의 객체에서 끝 객체로 가는 유일한 함자는, 모든 객체를 그 유일한 객체로 보내고 모든 사상을 그 유일한 사상으로 보내는 함자입니다.