모노이드 (Monoid)

모노이드(Monoid)는 결합 법칙을 만족하는 이항 연산 하나와 항등원을 갖는 대수적 구조입니다. 모노이드는 항등원을 갖는 반군입니다. 형식적으로는 집합 M과 연산 ·가 다음 두 조건을 만족할 때 (M, ·, e)를 모노이드라고 합니다.

• 결합 법칙: M의 모든 a, b, c에 대해 (a · b) · c = a · (b · c)입니다. 연산을 어떤 순서로 묶어 계산해도 결과가 같습니다.
• 항등원: M의 모든 a에 대해 e · a = a · e = a를 만족하는 원소 e가 존재합니다.

교환 법칙(a · b = b · a)은 요구하지 않으며, 역원도 필요 없습니다. 모든 원소에 역원이 있으면 그 모노이드는 군(group)이 됩니다.

대표적인 예

1. (ℕ, +, 0): 0을 포함한 자연수와 덧셈입니다. 0을 더해도 값이 바뀌지 않으므로 0이 항등원입니다. 역원(음수)이 없으므로 군은 아닙니다.
2. (ℤ, ×, 1): 정수와 곱셈이며 항등원은 1입니다.
3. 문자열과 연결: 문자열 집합에서 두 문자열을 이어 붙이는 연산은 결합 법칙을 만족하고, 빈 문자열이 항등원입니다. “ab”+“c”와 “a”+“bc”가 같듯이 묶는 순서는 상관없지만, “ab”와 “ba”는 다르므로 교환 법칙은 성립하지 않습니다.
4. (ℤ_n, ·, 1): n으로 나눈 나머지들의 곱셈입니다. 항등원은 1이지만, n과 서로소가 아닌 원소(예: 0)에는 곱셈 역원이 없으므로 일반적으로 군이 아닌 모노이드입니다. n과 서로소인 원소만 모으면 곱셈군이 됩니다.
5. n×n 행렬과 행렬 곱셈: 단위 행렬이 항등원이며, 교환 법칙은 성립하지 않습니다.

모노이드 사이에서 연산과 항등원을 보존하는 함수를 모노이드 준동형사상이라고 합니다. 예를 들어 문자열의 길이를 구하는 함수는 두 문자열을 이어 붙인 길이가 각 길이의 합과 같고, 빈 문자열의 길이가 0이므로 (문자열, 연결, 빈 문자열)에서 (ℕ, +, 0)으로 가는 준동형사상입니다.

모노이드가 아닌 예

• 정수의 뺄셈은 (5 − 3) − 1 ≠ 5 − (3 − 1)이므로 결합 법칙을 만족하지 않습니다.
• 0을 제외한 양의 정수와 덧셈은 결합 법칙은 만족하지만 항등원이 없으므로 반군일 뿐 모노이드가 아닙니다.

응용

• 병렬 집계: 결합 법칙 덕분에 큰 데이터를 여러 조각으로 나누어 각각 계산한 뒤 결과를 합쳐도 전체를 한 번에 계산한 것과 같습니다. 합계, 최댓값, 개수 같은 집계를 분산 처리하는 맵리듀스(MapReduce)나 블록체인 데이터를 구간별로 집계하는 인덱서가 이 성질에 기대고, 빈 구간에는 항등원을 결과로 씁니다.
• 함수형 프로그래밍: 리스트를 하나의 값으로 줄이는 폴드(fold) 연산은 모노이드의 연산과 항등원만 있으면 정의됩니다.
• 암호학: RSA는 (ℤ_n, ·, 1)에서의 거듭제곱을 씁니다. 제곱과 곱셈을 반복해 큰 지수를 빠르게 계산하는 알고리즘은 곱셈이 결합 법칙을 만족하기 때문에 곱셈을 묶는 방식을 바꿔도 결과가 같다는 점을 이용합니다.