모노이드의 정의, 기본 예시, 군과 대칭, 순환군, 곱군, 케일리 정리, 그리고 범주로서의 모노이드를 직관적으로 설명합니다.
이제 범주를 다 보았으니, 역시 흥미로운 다른 구조들인 모노이드를 살펴보자.
범주와 마찬가지로, 모노이드/군은 원소들의 집합과 연산으로 이루어진 추상적인 체계이다. 다만 연산은 범주에서 다루었던 연산과는 조금 다르게 생겼다. 정의는 다음과 같다.
모노이드는 원소들의 모임/집합(이를 모노이드의 _기저 집합_이라고 한다)과, 결합법칙을 만족하는 모노이드 연산 — 두 원소를 결합해 같은 종류의 세 번째 원소를 만들어내는 규칙 — 으로 정의된다. 또한 항등원이 있어야 한다.
익숙한 색깔 공들을 다시 가져와 보자.
이 집합에 대해, 두 공을 “결합”해서 하나의 공으로 만드는 연산을 지정함으로써 모노이드를 정의할 수 있다. 그런 연산의 한 예는 물감을 섞듯이 공의 색을 혼합하는 것이다.
아마 이와 비슷한 연산을 정의하는 다른 방법들도 떠올릴 수 있을 것이다. 이를 통해 주어진 원소 집합으로부터 모노이드를 만드는 방법은 많을 수 있다는 점을 알 수 있다. 즉, 모노이드는 집합 그 자체가 아니라, 집합과 연산을 함께 갖춘 것이다.
모노이드 연산은 함수 합성과 마찬가지로 결합적 이어야 한다. 즉, 연산을 적용할 때 원소들을 어떤 식으로 묶느냐가 결과에 영향을 주어서는 안 된다.
연산이 결합적이라는 것은, 임의의 항들의 열에 대해 다양한 대수적 조작을 할 수 있다는 뜻이다. 다시 말해 식에 대한 추론을 적용할 수 있다는 뜻이다. 예를 들어 어떤 원소를 그것을 이루는 원소들의 집합으로 치환하거나, 등식의 양변에 모두 등장하는 항을 더해도 기존 항들의 동등성은 유지된다.
사실 원소들을 결합하는 임의의 (결합적인) 연산이 곧바로 모노이드를 이루는 것은 아니다. 그런 구조는 반군 이 되는데, 이것도 중요한 개념이지만 별도의 주제다. 모노이드가 되려면 집합에 연산의 항등원 이 있어야 한다. 이 개념은 집합과 범주에서 이미 익숙할 것이다. 항등원은 다른 임의의 원소와 결합했을 때 그 다른 원소를 그대로 돌려주는 원소이다. 또는 간단히, 모든 에 대해 이다.
색 혼합 모노이드의 경우, 항등원은 흰 공이다. 아니면 투명한 공이 있다면 그것일 수도 있다.
지난 장에서 기억하겠지만, 함수 합성도 결합적이고 항등원을 가진다. 그러니 이것도 어떤 의미에서는 모노이드를 이룬다고 짐작할 수 있을 것이다. 실제로 그렇지만, 한 가지 단서가 있으며 그것은 나중에 이야기하겠다.
긴장을 조금 유지하기 위해, 모노이드와 범주의 관계를 논하기 전에 먼저 몇 가지 단순한 모노이드 예시를 살펴보자.
수학은 숫자만을 다루는 학문은 아니지만, 숫자는 대부분의 분야에 등장하는 경향이 있고, 모노이드도 예외는 아니다. 자연수의 집합 ()은 익숙한 덧셈 연산과 결합하면 모노이드를 이룬다. 전통적으로는 덧셈에 대하여 모노이드를 이룬다고 말한다. 이 모노이드는 로 표기한다(일반적으로 모든 모노이드는 집합과 연산을 꺾쇠괄호 안에 적어서 표기한다).
교과서에서 를 본다면, 당신이 아주 고급 내용을 읽고 있거나 아주 쉬운 내용을 읽고 있다는 뜻일 텐데, 현재 경우가 그 둘 중 어느 쪽인지는 나도 잘 모르겠다.
어쨌든 자연수는 곱셈에 대해서도 모노이드를 이룬다.
과제 1: 이 모노이드들의 항등원은 무엇인가?
과제 2: 다른 수학적 연산들도 살펴보고 그것들이 모노이드적인지 확인하라.
과제 3: 자연수는 곱셈에 대해서는 모노이드를 이루지만 군은 아니다. 이유를 찾아보라.
우리가 다루었던 연산들을 떠올리면, 불 연산인 and 와 or 가 있다. 이 둘 모두 단 두 값 으로 이루어진 집합 위에서 작동하는 모노이드를 이룬다.
과제 4: 가능한 모든 값을 대입해 공식을 전개함으로써 AND 가 결합적인지 증명하라. or 에 대해서도 같은 작업을 하라.
과제 5: and 와 or 연산의 항등원은 무엇인가?
이제 우리는 모노이드 연산이 무엇인지 알고, 몇 가지 단순한 예도 보았다. 하지만 그 연산 자체를 형식적으로, 즉 우리가 다른 모든 것을 정의할 때 사용했던 집합론의 언어로는 아직 정의하지 않았다. 그렇게 할 수 있을까? 물론 할 수 있다. 모든 것은 집합으로 정의할 수 있다.
모노이드는 두 가지로 이루어진다고 했다. 하나는 집합(이를 라고 하자), 다른 하나는 그 집합 위에서 작동하는 모노이드 연산이다. 는 이미 집합론 안에서 정의되어 있으므로(왜냐하면 그냥 집합이기 때문이다), 이제 남은 일은 모노이드 연산을 정의하는 것뿐이다.
연산을 정의하는 것은 전혀 어렵지 않다. 사실 우리는 이미 덧셈 연산에 대해 그렇게 했다. 2장에서 우리는 덧셈 이 두 수의 곱을 받아 하나의 수를 돌려주는 함수로 집합론 안에서 표현될 수 있다고 말했다(형식적으로 ).
다른 모든 모노이드 연산도 같은 방식으로 표현할 수 있다. 즉, 모노이드의 집합에서 두 원소의 쌍을 받아 다른 하나의 모노이드 원소를 돌려주는 함수로 표현할 수 있다.
형식적으로, 임의의 집합 에 대해 타입 시그니처 가 있는 (결합적인) 함수를 정의하면 모노이드를 정의할 수 있다. 그게 전부다. 더 정확히 말하면, 그것은 모노이드 연산을 정의하는 한 가지 방법 이다. 그리고 또 다른 방법이 있는데, 곧 보게 될 것이다. 그전에 몇 가지 다른 종류의 구조를 살펴보자.
모노이드 연산은 두 가지 법칙을 따른다. 즉 결합법칙 을 만족하고 항등원 이 존재한다. 어떤 경우에는 이 외에도 흥미로운 다른 법칙들을 만족하는 연산을 만나게 된다. 객체들이 결합되는 방식에 더 많은 규칙을 추가하거나, 반대로 더 적은 규칙만 요구하면, 다른 모노이드 유사 구조들이 정의된다.
모노이드 법칙과 지금까지 본 예들을 살펴보면, 모두 우리가 명시하지 않았던 또 하나의 규칙도 만족한다는 것을 알 수 있다. 바로 연산을 적용하는 순서가 최종 결과에 영향을 주지 않는다는 것이다.
이처럼 주어진 원소들의 집합을 어떤 순서로 결합하든 같은 결과가 나오는 연산을 가환적 연산이라고 한다. 이런 연산을 가진 모노이드를 가환 모노이드 라고 부른다.
앞서 말했듯 덧셈도 가환적이다. 내가 사과 1개를 주고 그다음 2개를 더 주든, 먼저 2개를 주고 그다음 1개를 더 주든 상관없다.
지금까지 살펴본 모든 모노이드는 가환적 이기도 하다. 나중에는 비가환적인 것들도 볼 것이다.
군은, 각 원소마다 그것의 이른바 “역원”이 존재하는 모노이드이다. 원소와 그 역원을 차례대로 적용하면 서로 상쇄된다. 이런 평이한 설명을 들으면 오히려 수식의 소중함이 느껴진다. 형식적으로는 모든 원소 에 대해, 를 만족하는 가 존재해야 한다고 말한다(여기서 는 항등원이다).
모노이드 를 결합법칙을 만족하는 일련의 작용의 효과를 모델링하는 수단으로 본다면, 군 은 그 작용들이 또한 되돌릴 수 있는 경우를 모델링하는 데 사용한다.
우리가 이미 본 모노이드와 관련된 좋은 군의 예는 정수의 집합에 대한 덧셈이다. 연산은 다시 ()이지만, 객체는 자연수 가 아니라 정수 이다(따라서 가 아니라 이다). 자연수에는 역원이 없으므로 음수를 추가해야 한다. 각 수의 역원은 그 부호를 바꾼 수이다(양수의 역원은 음수이고 그 반대도 마찬가지다).
이 경우 위의 공식은 다음과 같이 된다
군의 연구는 모노이드 이론보다 훨씬 더 큰 분야이며, 어쩌면 범주론 자체보다도 더 클 수 있다. 그리고 그 가장 큰 갈래 중 하나가 바로 다음에 볼 “대칭군”의 연구이다.
계속 진행하기 전에, 위에서 본 대수적 구조들은 그것들을 정의하는 법칙에 따라 다음 표처럼 요약할 수 있다.
| 반군 | 모노이드 | 군 | |
|---|---|---|---|
| 결합법칙 | X | X | X |
| 항등원 | X | X | |
| 가역성 | X |
이제 대칭군으로 가 보자.
흥미로운 종류의 군/모노이드로 기하학적 도형의 대칭 으로 이루어진 군이 있다. 어떤 기하학적 도형이 주어졌을 때, 대칭이란 어떤 작용을 한 뒤에도 그 도형이 어긋나지 않는 경우를 말한다. 예를 들어, 작용을 적용하기 전과 같은 틀 안에 그대로 들어맞는다.
이번에는 공을 쓰지 않겠다. 대칭의 관점에서 공은 하나의 위치만 가지며, 따라서 작용도 오직 하나, 즉 항등 작용만 있기 때문이다(게다가 그것은 자기 자신의 역이기도 하다).
대신 이 삼각형을 보자. 우리의 목적상 이것은 다른 어떤 삼각형과도 같다. 우리는 삼각형 자체에는 관심이 없고, 그 회전에만 관심이 있다. 우리가 믿기만 하면 되는 것은 이것이 “회전되지 않은” 삼각형, 즉 항등 회전을 나타내는 삼각형이라는 점이다.
먼저 우리 삼각형을 회전시킬 수 있는 방식들의 군, 즉 그 회전군 을 살펴보자. 기하학적 도형은 변의 수만큼의 위치에서 어긋남 없이 회전할 수 있으므로, 삼각형의 경우 위치는 3개이다.
점들을 연결해 보면(이 경우에는 삼각형들을 연결하는 셈이다), 삼각형의 임의의 상태에서 다른 상태로 가는 가능한 회전은 3가지뿐임을 알 수 있다. 즉 120도 회전 (삼각형을 한 번 뒤집는 것), 240도 회전 (두 번 뒤집는 것, 또는 반대 방향으로 한 번 뒤집는 것과 같다), 그리고 0도 회전의 항등 작용이다.
삼각형의 회전은 모노이드를 이룬다. 회전들이 객체 이고(이 중 0도 회전이 항등원이다), 두 회전을 하나로 결합하는 모노이드 연산은 첫 번째 회전을 수행하고 그다음 두 번째 회전을 수행하는 연산이다.
다시 한 번 강조하지만, 이 군의 원소는 회전 이지 삼각형 자체가 아니다. 사실 나중에 보겠지만 이 군은 삼각형과는 아무 관련이 없다.
더 복잡한 기하학적 도형의 모든 회전을 나열한 도표는 처음 보면 꽤 복잡해 보인다.
하지만 다음 사실을 알아차리면 훨씬 이해하기 쉬워진다. 우리 군에는 많은 회전이 있고, 변이 더 많은 도형에는 더 많은 회전이 있다(내가 틀리지 않았다면 회전의 수는 변의 수와 같다). 그러나 그 모든 회전은 단 하나의 회전을 반복 적용하는 것으로 환원될 수 있다. 예를 들어 삼각형에서는 120도 회전, 정팔각형에서는 45도 회전이 그렇다. 이 회전에 기호를 하나 붙여 보자.
이처럼 “주된” 회전을 가진 대칭군을 순환적이라고 한다.
반복 적용만으로 다른 모든 객체를 생성할 수 있는 객체를 가진 군과 모노이드를 순환군 이라고 한다. 이 “주된” 회전을 그 군의 생성원 이라고 부른다.
모든 회전군/모노이드는 순환군이다. 순환 모노이드의 또 다른 예는, 그렇다, 덧셈에 대한 자연수이며, 이 경우 생성원은 이다.
덧셈에 대한 정수군 도 순환적이다. 여기서는 또는 을 생성원으로 사용할 수 있다. 둘 중 어느 것을 선택하더라도 역원 법칙을 적용하면 다른 하나를 얻을 수 있기 때문이다.
잠깐, 순환군인데 분명히 순환이 없어 보이는데 어떻게 그럴 수 있을까? 이것은 정수가 무한 순환군이기 때문이다.
유한 순환군의 수 기반 예시는 모듈러 산술 (때로는 “시계 산술”이라고도 한다)에서 얻을 수 있다. 모듈러 산술의 연산은 법이라 불리는 수에 기반한다(예를 들어 를 택하자). 이 연산에서는 각 수를 그 수를 법으로 정수 나눗셈했을 때의 나머지 로 대응시킨다.
예를 들어: (왜냐하면 이고 나머지가 이기 때문이다) 등등.
하지만 (왜냐하면 이고 나머지가 이기 때문이다), 등등이다.
결과적으로 수들은 “되감기듯” 돌아가며, 법의 크기만큼의 원소를 가진 군을 이룬다. 예를 들어 법이 인 모듈러 산술의 군 표현은 3개의 원소를 가진다.
원소의 개수가 같은 모든 순환군(즉 위수 가 같은 군)은 서로 동형이다. 눈썰미 좋은 독자라면 아직 군 동형이 무엇인지 정의하지 않았다는 점을 알아챌 것이고, 더 눈썰미 좋은 독자라면 그것이 무엇인지 이미 감을 잡았을지도 모른다.
예를 들어, 삼각형의 회전군은 법 가 있는 덧셈에 대한 정수군과 동형이다.
모든 순환군은 가환적 이다(또는 “아벨 군”이라고도 부른다).
과제 6: 원소가 3개인 군은 외에는 존재하지 않음을 보여라.
순환적이지 않은 가환군도 존재하지만, 아래에서 보겠듯이 순환군과 가환군의 개념은 깊이 관련되어 있다.
우리는 이미 군 동형을 언급했지만 아직 정의하지는 않았다. 지금 해 보자.
두 군 사이의 동형이란, 각 군의 원소 집합 사이의 동형사상 ()으로서, 임의의 와 에 대해 를 만족하는 것이다.
시각적으로 동형인 군들의 도표는 같은 구조를 가진다.
범주론에서와 마찬가지로, 군론에서도 동형인 군은 하나의 같은 군의 다른 사례로 여겨진다. 예를 들어 위의 것은 이라고 불린다.
집합에서와 마찬가지로, 군론에서의 동형 개념은 공통적인 유한군들을 식별하게 해 준다.
가장 작은 군은 단 하나의 원소만 가진 자명군이다.
가장 작은 비자명군은 원소가 두 개인 군이다.
은 불 군 이라고도 하는데, 주어진 값을 부정하는 연산 아래의 집합 과 동형이기 때문이다.
와 마찬가지로, 와 도 순환적이다.
지금까지 순환적이면서 가환적인 군은 많이 보았지만, 순환적이지 않은 가환군은 보지 못했다. 이제 그런 것들을 살펴보자. 여기서는 개별 예를 하나씩 보기보다는, 가환 비순환군이 만들어지는 일반적인 방식을 소개하겠다. 그것은 군의 곱 이라는 개념을 이용해 순환군들을 결합하는 것이다.
임의의 두 군이 주어지면, 우리는 그것들을 결합하여 세 번째 군을 만들 수 있다. 이 군은 두 군의 원소들로 이루어진 모든 가능한 쌍과, 그 작용들의 합으로 이루어진다.
원소가 두 개뿐이고 연산도 하나뿐이어서 둘 다 와 동형인 다음 두 군의 곱을 취했을 때 결과 군이 어떻게 생기는지 보자. 상상하기 쉽게 첫 번째는 도형의 세로 반사, 두 번째는 가로 반사에 대응한다고 생각하자.
(여기서도 항등 회전을 나타낼 원소를 각 군에서 하나 골라야 하므로, 왼쪽 도형들을 “뒤집히지 않은” 버전, 오른쪽을 뒤집힌 버전이라고 생각하자. 물론 반대로 잡아도 된다.)
새 군의 원소 집합은 첫 번째 군의 원소 집합과 두 번째 군의 원소 집합의 데카르트 곱 을 취해 얻는다.
그리고 곱군의 작용 은 첫 번째 군의 작용과 두 번째 군의 작용을 결합한 것으로 이루어지는데, 각 작용은 원래 자신이 속한 군의 원소에만 적용되고 다른 원소는 바꾸지 않는다.
위 두 군의 곱은 클라인 사원군 이라고 하며, 가장 단순한 비순환 가환군 이다.
클라인 사원군을 표현하는 또 다른 방법은 정사각형이 아닌 직사각형의 대칭군 으로 보는 것이다.
과제 7: 이 두 표현이 동형임을 보여라.
다음은 클라인 사원군의 원소들이 결합되는 몇 가지 예이다.
(즉 가로/세로 회전은 각각 자기 자신을 상쇄하지만, 가로 회전은 세로 회전을 상쇄하지는 않는다.)
클라인 사원군은 비순환적 이다(생성원이 하나가 아니라 둘이기 때문이다) — 세로 회전과 가로 회전이 있다. 그러나 여전히 가환적 이다. 작용의 순서가 최종 결과에 영향을 주지 않기 때문이다. 사실 클라인 사원군은 가장 작은 비순환군 이다.
이전 절에서 우리는 하나의 비순환 곱군(클라인 사원군)을 보았다. 이것은 순환군들 의 곱이었다. 대부분의 곱군은(심지어 순환군들의 곱이라 해도) 비순환적이다. 그것은 구성하는 두 군의 생성원을 모두 가지기 때문이다. 즉 원래 두 군이 각각 생성원 1개를 가진 순환군이라 해도, 그 곱은 생성원 2개를 갖게 된다. 하지만 두 순환군의 원소 수(즉 위수)가 1 이외의 공약수를 가지지 않는다면, 그 곱은 여전히 순환적일 수 있다(즉 서로소 일 때).
따라서 위수가 공약수를 가지는 두 군(예를 들어 와 — 둘 다 2로 나누어진다)을 결합하면 그 곱은 순환적이지 않다. 하지만 위수가 서로소인 두 군(예를 들어 와 )을 결합하면 순환군을 얻게 된다.
더 나아가, 서로소인 두 군의 곱은 같은 위수를 가진 순환군과 동형이다. 그 위수는 각 성분 위수의 곱이다. 예를 들어 와 의 곱은 군 ()과 동형이다.
(생성원은 두 군 각각에 1을 더한다.)
이것은 중국인의 나머지 정리 라는 오래된 결과의 귀결이다.
곱군은, 그것을 이루는 군들 자체가 가환적이라면, 가환적 이다. 이것이 참이라는 것은 생성원이 여러 개 있더라도 각 생성원이 자기 부분에만 작용하므로 서로 간섭하지 않는다는 점을 보면 알 수 있다.
곱은 비순환 가환군을 만드는 한 가지 방법을 제공한다. 즉 두 개 이상의 순환군의 곱을 만드는 것이다. 유한 아벨 군의 기본정리(여기서는 유한 가환 군의 기본정리라고 부른다)는 이것이 유일한 방법 이라고 말한다. 즉,
모든 유한 가환군은 순환군이거나, 순환군들의 곱이다.
이 법칙을 사용하면 가환군이 무엇인지 직관적으로 이해할 수 있을 뿐 아니라, 주어진 군이 더 기본적인 군들의 곱으로 분해될 수 있는지도 시험할 수 있다.
이제 마침내 비가환군을 살펴보자. 어떤 기하학적 도형의 회전과 반사 로 이루어진 군이다. 이것은 마지막에 본 것과 같지만, 여기서는 이미 본 회전 작용(및 그 합성 작용들) 외에 도형을 세로로 뒤집는 작용이 있다. 이 연산은 거울상으로 바뀐 도형을 만든다.
이 두 작용과 그 합성은 라는 군을 이루는데, 이 군은 가환적이지 않다. 즉 비가환적 이다(게다가 가장 작은 비가환군이기도 하다).
과제 8: 이 군이 실제로 가환적이지 않음을 증명하라.
과제 9: 두 개의 주된 작용을 가진다는 점 외에, 이 군과 다른 비가환군을 비가환적으로 만드는 결정적 요인은 무엇인가?
임의의 2차원 도형의 회전과 반사의 집합을 나타내는 군을 이면체군 이라고 한다.
이제 대단원의 공개를 할 때가 되었다. 군/모노이드는 범주이다. 더 정확히 말하면 모노이드는 특정한 종류의 범주 이다(군도 마찬가지다).
이 말은 우리가 살펴본, 집합과 이항 연산으로 설명하는 정의가 거짓이라는 뜻이 아니다. 단지 그것과 동등한 대안적 범주론적 정의가 있다는 뜻이다. 들어가 보자.
모노이드를 정의할 때 우리는 그 원소들을 객체 로, 그리고 연산을 두 객체를 세 번째 객체로 바꾸는 함수/사상으로 제시했다. 그런 다음 집합론을 사용해 그러한 연산을 표현하는 방법을 소개했다. 즉, 모노이드의 집합에서 원소 쌍 을 받아 다른 하나의 모노이드 원소를 돌려주는 함수로 표현했다.
이 대응 아래에서, 색 혼합 모노이드의 이 특정한 혼합은…
…위 함수의 이 특정한 점 에 대응한다(점이란 집합의 특정 원소에 대한 대응을 뜻한다).
하지만 이것이 다변수 함수를 집합론적으로 표현하는 유일한 방법은 아니다. 자료구조에 의존하지 않고 함수만으로 표현하는, 또 다른 흥미로운 방법이 있다.
대칭군이나 회전군처럼 일부 군에서는 군의 원소를 객체가 아니라 작용 으로 이해할 수 있다는 것을 보았다. 사실 이것은 다른 모든 군에도 해당한다. 예를 들어 색 혼합 모노이드의 빨간 공 은 혼합물에 빨간색을 더하는 작용으로 볼 수 있고, 덧셈 모노이드의 숫자 도 어떤 연산으로 볼 수 있다.
형식적으로, 두 객체의 쌍을 받는 임의의 함수는 하나의 객체를 받고, 나머지 다른 객체를 받아 결과를 돌려주는 함수 를 반환하는 함수로 변환할 수 있다.
이 변환은 Haskell Curry의 이름을 따서 커링 이라고 불리지만, 실제로는 Moses Schönfinkel이 몇 년 먼저 발명했다(Schönfinkelisation 이라는 이름은 이상하게도 정착하지 않았다). 그래서 Schönfinkel은 다음 두 표현이 동형이라는 것을 발견했다.
한 걸음 물러서서, 지금까지 본 군/모노이드를 이 동치의 관점에서 살펴보자. 예를 들어 대칭군 을 보자.
이 군의 원소들은 하나의 도형을 받아 일정한 각도만큼 회전시키는 함수로 볼 수 있다.
그리고 군 연산 자체는 함수 합성으로 표현할 수 있다.
형식적으로, 의 세 원소는 3개의 원소를 가진 집합에서 자기 자신으로 가는 3개의 전단사(가역) 함수로 볼 수 있다(참고로 군론의 맥락에서는 이런 종류의 함수를 순열 이라고 부른다).
덧셈 모노이드에 대해서도 같은 일을 할 수 있다. 숫자를 양 으로(예를 들어 사과 두 개, 오렌지 두 개 같은) 보는 대신 연산 으로 볼 수 있다(예를 들어 주어진 양에 2를 더하는 작용처럼).
형식적으로, 위에서 본 덧셈 모노이드의 연산은 다음 타입 시그니처를 가진다.
위에서 제시한 동형성 때문에, 이 함수는 다음 함수와 동등하다.
이 함수에 모노이드의 원소 하나를 적용하면(예를 들어 ), 결과는 주어진 수에 2를 더하는 함수가 된다.
그리고 모노이드 연산은 항상 주어진 모노이드의 맥락에서 주어지므로, 그 맥락 안에서는 원소 와 함수를 동등한 것으로 볼 수 있다.
즉, 모노이드의 집합 안의 원소를 함수로 결합되는 객체 로 표현하는 것 외에도, 그것들을 함수 자체 로 표현할 수 있다.
말했듯이, 모노이드 원소를 함수로 표현하면 모노이드 연산은 함수 합성 으로 표현된다. 모노이드 원소를 나타내는 함수들은 같은 집합을 출발점과 도착점으로 가지며, 같은 시그니처 를 가진다(형식적으로 어떤 에 대해 타입 이다). 따라서 이 함수들은 모두 서로 합성할 수 있으며, 그 결과도 같은 시그니처를 가진다.
이것은 모든 모노이드에 대해 참이다. 예를 들어 수를 나타내는 함수들도 함수 합성으로 결합될 수 있다.
그러므로 기본적으로, 모노이드의 원소를 표현하는 함수들도 함수 합성 연산 아래에서 하나의 모노이드를 이룬다(그리고 군의 원소를 표현하는 함수들은 역시 하나의 군을 이룬다).
과제 10: 함수 군의 항등원은 무엇인가?
과제 11: 역원인 군 원소를 나타내는 함수들도 역시 서로 역함수임을 보여라.
정리해 보자. 앞 절에서 우리는 모든 군/모노이드의 원소가 모노이드의 기저 집합에서 자기 자신으로 가는 함수들(즉 순열들)에 대응함을 보였고, 그 순열들이 함수 합성 아래에서 자기 자신의 모노이드를 이룬다고 말했다. 이를 순열의 모노이드 라고 하자.
앞 절에서 말하지 않았던 한 가지는, 그렇게 얻어지는 모든 순열군/모노이드는 원래 그것을 구성한 모노이드와 동형이라는 점이다.
이 결과가 바로 케일리 정리이다. 짧게 말하면,
임의의 군은 그에 대응하는 순열군과 동형이다.
또는 형식적으로, 순열군을 로 표기한다면 케일리 정리는 임의의 에 대해 라고 말한다.
즉 모노이드/군의 원소를 순열로 표현하는 것은 실제로 그 모노이드 자체의 표현을 준다. 이것을 때로 표준 표현 이라고 부른다. 예를 들어 삼각형은 두 번 뒤집으면 원래 위치로 돌아가는 도형이며, 두 번 뒤집어서 원래 위치로 돌아가는 모든 것은 삼각형이다.
케일리 정리는 매우 중요한 결과이다. 여기서 그다지 인상적으로 보이지 않는다는 사실은 오히려 범주론적 틀의 강력함(그리고 우리가 얼마나 많은 것을 배웠는지)을 보여 줄 뿐이다.
모노이드의 원소를 작용/함수로 바꾸면 집합의 관점에서 모노이드를 정확히 표현할 수 있음을 보았다.
하지만 중요한 것은 모노이드의 집합이 아니라 함수들 이라는 점이 분명하다(결국 모노이드에서는 어디서나 같은 집합을 사용한다). 그러니 이것을 범주론적(외적) 도표로 그려 볼 수 있다.
그런데 잠깐, 모노이드의 기저 집합 이 범주론의 객체 에 대응한다면, 그에 대응하는 범주는 객체를 하나만 가지게 된다. 따라서 올바른 표현은 하나의 점에서 모든 화살표가 나오고 다시 그 점으로 들어가는 형태여야 한다.
따라서 임의의 모노이드는 객체가 하나뿐인 범주 로 볼 수 있다.
이제 범주의 정의를 다시 검토하여 그것이 정말 맞는지 확인해 보자.
범주는 객체 들의 모음(점으로 생각할 수 있다)과, 한 객체에서 다른 객체로 가는 사상 들(화살표)로 이루어지며, 다음을 만족한다.
- 각 객체는 항등 사상을 가져야 한다.
- 적절한 타입 시그니처를 가진 두 사상을 세 번째 사상으로 합성하는 방법이 있어야 하며, 이 합성은 결합적이어야 한다.
이 법칙들이 객체가 하나뿐인 범주에 대해 무엇을 뜻하는지 보자.
- 각 객체는 항등 사상을 가져야 한다.
객체가 하나뿐인 범주에서는 항등 사상도 하나뿐이다. 그리고 모노이드는 항등 객체 를 가지며, 이것은 범주론적으로 보면 그 항등 사상에 대응한다.
- 적절한 타입 시그니처를 가진 두 사상을 세 번째 사상으로 합성하는 방법이 있어야 하며, 이 합성은 결합적이어야 한다.
하지만 범주가 객체를 하나만 가진다면, 모든 사상은 같은 타입 시그니처를 가지게 된다(그저 일 뿐이다). 그러므로 모든 사상은 서로 합성 가능 하다. 모노이드 연산은 정확히 그 일을 한다. 임의의 두 객체(또는 범주론 용어를 쓰면 두 사상)를 받아 세 번째를 만든다.
범주론적으로 볼 때 모노이드의 객체가 사상으로 바뀐다 는 조금 혼란스러운 사실만 제외하면, 이것은 모노이드를 정확히 기술하고 있음을 알 수 있다.
임의의 모노이드는 객체가 하나뿐인 범주 로 볼 수 있다. 범주의 사상은 모노이드의 원소들이고, 항등 사상은 항등원이며, 모노이드 연산은 사상의 합성이다. 역도 성립한다. 객체가 하나뿐인 임의의 범주는 모노이드로 볼 수 있다.
철학적으로, 모노이드를 객체 하나를 가진 범주로 정의하는 것은, 어떤 객체에 수행되는 일련의 (결합적인) 작용이 그 객체의 상태를 어떻게 바꾸는가를 모델링하는 것으로 모노이드를 보는 관점에 대응한다. 객체의 상태가 오직 그것에 수행된 작용들에 의해 결정된다면, 우리는 객체 자체를 식에서 생략하고 작용들이 어떻게 결합되는지만 집중할 수 있다. 그리고 늘 그렇듯, 그 작용들(그리고 원소들)은 색을 섞는 것에서부터 어떤 사물의 집합에 양을 더하는 것까지 무엇이든 될 수 있다.
앞 절에서 우리는 모노이드가 실제로 객체 하나를 가진 범주와 동등함을 보였다. 그러나 이 진술의 함의는 아직도 조금 혼란스럽다. 이것이 모든 모노이드와 모노이드가(심지어 기저 집합이 다른 경우에도) 어쩐지 거의 같은 것이라는 뜻일까? 답은, 적어도 동형인 모노이드를 같은 모노이드로 본다면, 실제로 비슷하다는 것이다. 서로의 차이는 다음 두 가지로 추적할 수 있다.
형식적으로, 주어진 모노이드를 정의하는 생성원과 법칙의 집합을 모노이드의 제시 라고 하며, 모든 모노이드는 자신의 제시를 명시함으로써 정의할 수 있다. 그리고 이 관찰은 모노이드/모노이드를 정의하는 완전히 새로운 방식을 이끈다.
객체가 하나뿐일 뿐 아니라, 항등사상을 제외하면 사상도 하나뿐인 어떤 범주들을 상상해 보자.
이 범주들은 정확히 순환 모노이드/군 에 대응한다(그 사상이 생성원이다).
그리고 모든 순환 모노이드/군의 차이는 오직 법칙에 의해 결정된다.
이제 제시의 두 번째 구성 요소, 즉 주어진 두 사상의 합성 결과를 기술하는 법칙에 주목해 보자.
순환 모노이드의 경우, 이것은 모노이드를 이루는 유일한 사상을 자기 자신과 합성한 결과를 말한다.
다음과 같은 법칙을 정의할 수 있다.
생성원을 자기 자신과 3번 합성하면 항등 사상이 된다.
이것을 다음처럼 쓸 수 있다.
그렇다면 이 법칙이 정의하는 모노이드는 무엇일까? 알아보려면, 모노이드 생성원을 계속 자기 자신과 합성하고 법칙을 적용해, 가능한 모든 합성 열을 찾아내면 된다.
(왜냐하면 사상을 한 번 더 자기 자신과 합성하면 다시 항등으로 돌아가기 때문이다.)
이미 짐작했겠지만, 이 모노이드는 바로 익숙한 모노이드, 즉 삼각형 회전의 모노이드 또는 법 3의 모듈러 산술이다.
그렇다면 법칙의 3을 다른 어떤 수 로 바꿔 말하면 어떻게 될까?
생성원을 자기 자신과 번 합성하면 항등 사상이 된다.
이렇게 하면 다른 모든 순환 모노이드가 얻어진다. 등등이다.
곱 모노이드도 이 방식으로 표현할 수 있다. 예로 클라인 사원모노이드를 보자. 클라인 사원모노이드는 그것을 이루는 모노이드들로부터 물려받은 두 생성원을 가지며(우리는 이것들을 정사각형이 아닌 직사각형의 세로 및 가로 회전으로 보았다), 각 생성원에는 하나의 법칙이 따른다.
표현을 완성하기 위해, 두 생성원을 결합하는 법칙도 추가한다.
그다음 두 생성원을 적용하고 법칙들을 계속 적용하기 시작하면, 모노이드의 네 원소를 얻게 된다.
우리는 서로 다른 법칙 집합을 고르면 서로 다른 종류의 모노이드가 생긴다는 것을 보았다. 그렇다면 아무 법칙도 고르지 않으면 무엇을 얻게 될까? 이런 모노이드들(고른 사상 집합에 따라 서로 다른 것이 생긴다)을 자유 모노이드 라고 한다. “법칙으로부터 자유롭다”는 뜻이기도 하고, “생성원 집합을 공짜로 모노이드로 승격시킬 수 있다”는 뜻이기도 하다.
생성원이 하나뿐인 자유 모노이드는 자연수의 모노이드와 동형이다.
색깔 공들의 집합으로도 자유 모노이드를 만들 수 있다. 이 경우 모노이드의 원소는 공들의 가능한 모든 조합으로 이루어진 수열들이다.
자유 모노이드는 특별한데, 같은 생성원 집합을 가진 임의의 다른 모노이드로 보내는 함수를 정의할 수 있기 때문이다. 그 방법은 단지 그 모노이드의 법칙을 적용하는 것이다.
예를 들어 생성원이 하나뿐인 자유 모노이드를 취해 그 원소들에 의 법칙을 적용하면, 우리는… 그것에서 로 가는 함수를 얻게 된다.
그리고 공들의 자유 모노이드를 취해 색 혼합 모노이드의 법칙들을 적용하면, 공들의 자유 모노이드에서 색 혼합 모노이드로 가는 함수를 얻게 된다.
과제 14: 색 혼합 모노이드의 법칙들을 써 보라.
프로그래머의 모자를 쓰고 보면, 생성원 집합 T 위의 자유 모노이드의 타입(이를 FreeMonoid<T> 라고 쓸 수 있다)은 List<T> 타입과 동형이며, 위에서 설명한 특별한 성질의 직관도 사실 아주 단순하다. 객체들을 리스트에 담아 두면 그것들을 어떤 다른 구조로든 변환할 수 있다. 즉, 어떤 객체들의 묶음에 어떤 조작을 수행하고 싶지만 그 조작이 정확히 무엇인지는 아직 모를 때, 우리는 그 조작을 실제로 해야 할 때까지 그 객체들의 리스트를 그냥 보관해 둔다.
