모노이드

expanded=군 추상대수학에서 **모노이드**(monoid)는 항등원을 갖는, 결합 법칙을 따르는 이항 연산을 갖춘 대수 구조이다. 군의 정의에서 역원의 존재를 생략하거나, 반군의 정의에서 항등원의 존재를 추가하여 얻는다.
# 정의
**모노이드** (M,\cdot)는 다음과 같은 데이터로 구성되는 대수 구조이다. * M은 집합이다. * \cdot\colon M\times M\to M은 이항 연산이다. 이 데이터는 다음과 같은 두 공리를 만족시켜야 한다. * (결합 법칙) 임의의 a,b,c\in M에 대하여, (a\cdot b)\cdot c=a\cdot(b\cdot c) * (항등원의 존재) 임의의 a\in M에 대하여 1\cdot a=a\cdot1=a가 성립하는 원소 1\in M이 존재한다. (만약 이러한 항등원이 존재한다면, 이는 유일하다는 것을 쉽게 보일 수 있다.) 두 번째 공리를 생략하면 **반군**의 개념을 얻는다. 즉, 모노이드와 반군의 관계는 환과 유사환의 관계와 같다. 보통, 편의상 이항 연산을 (곱셈과 같이) 생략하는 경우가 많다. 즉, 다음과 같은 포함 관계가 성립한다. :마그마 ⊋ 반군 ⊋ 모노이드 ⊋ 군 범주론적으로, 모노이드는 집합과 함수의 범주 \operatorname{Set} 속의 모노이드 대상이다. 또한, 하나의 대상만을 갖는 작은 범주는 모노이드와 같은 개념이다. 이 경우, 모든 사상은 자기 사상이며, 모노이드 이항 연산은 자기 사상의 합성이다.
## 모노이드 준동형
두 모노이드 M, N 사이의 **모노이드 준동형**(monoid準同型, monoid homomorphism)은 다음 조건을 만족시키는 함수 f\colon M\to N이다. * (이항 연산의 보존) 임의의 m,n\in M에 대하여, f(mn)=f(m)f(n) * (항등원의 보존) f(1_M)=1_N 둘째 조건은 생략할 수 없다. 첫째 조건을 만족시키지만 둘째 조건을 만족시키지 않는 함수는 모노이드 준동형이 아닌 반군 준동형이다. 모노이드를 하나의 대상을 갖는 범주로 간주할 때, 모노이드 준동형은 두 범주 사이의 함자와 같다.
## 부분 모노이드
모노이드 M의 부분 집합 S\subseteq M가 다음 조건을 만족시킨다면, S를 M의 **부분 모노이드**(部分monoid, submonoid)라고 한다. * 임의의 s,t\in S에 대하여, st\in S * 1\in S 둘째 조건은 첫째로부터 함의되지 않는다. 첫째 조건을 만족시키지만 둘째 조건을 만족시키지 않는 부분 집합은 부분 반군을 이루지만, 부분 모노이드를 이루지 않는다.
## 가역원군
모노이드 M의 원소 m\in M의 **왼쪽 역원**(left inverse)은 (만약 존재한다면) 다음 조건을 만족시키는 원소 n\in M이다. :nm=1 모노이드 M의 원소 m\in M의 **오른쪽 역원**(right inverse)은 (만약 존재한다면) 다음 조건을 만족시키는 원소 n\in M이다. :mn=1 m\in M의 왼쪽 역원이자 오른쪽 역원인 원소는 **역원**(inverse)이라고 하고, m^{-1}로 쓴다. 주어진 원소의 왼쪽 역원 및 오른쪽 역원은 유일하지 않을 수 있지만, 주어진 원소의 역원은 (만약 존재한다면) 유일하다. 역원을 갖는 원소를 **가역원**(invertible element, unit)이라고 한다. 모노이드 M의 가역원들의 부분 집합은 부분 모노이드를 이루며, 또한 군을 이룬다. 이를 M의 **가역원군**(unit group) \operatorname{Unit}(M)이라고 한다.
## 영원과 멱등원
모노이드 M 속에서, 다음과 같은 원소 0\in M이 존재한다면, 이를 M의 **영원**(zero element)이라고 한다. :0m=m0=0\qquad\forall m\in M 이러한 원소는 만약 존재한다면 유일하다. 모노이드 M 속에서 m^2=m을 만족시키는 원소 m\in M을 **멱등원**(idempotent element)이라고 한다. 항등원 1\in M은 정의에 따라 멱등원이다.
## 아이디얼
모노이드 M 속에서, 다음 조건을 만족시키는 부분 반군 I\subseteq M을 M의 **왼쪽 아이디얼**(left ideal)이라고 한다. :mi\in I\qquad\forall m\in M,i\in I 모노이드 M 속에서, 다음 조건을 만족시키는 부분 반군 I\subseteq M을 M의 **오른쪽 아이디얼**(left ideal)이라고 한다. :im\in I\qquad\forall m\in M,i\in I 왼쪽 아이디얼이자 오른쪽 아이디얼인 부분 반군을 **아이디얼**(ideal)이라고 한다. 아이디얼은 부분 모노이드를 이룰 필요가 없다 (즉, 1을 포함하지 않을 수 있다). 모노이드 M의 부분 모노이드를 이루는 아이디얼은 M 전체 밖에 없다.
## 그린 관계
그린 관계 모노이드 M 위에 다음과 같이 5개의 표준적인 동치 관계가 존재하며, 이를 **그린 관계**라고 한다.언어=en :m \;\mathcal L\; n\iff Mm=Mn :m \;\mathcal R\; n\iff mM=nM :m \;\mathcal J\; n\iff MmM=MnM :m \;\mathcal H\; n\iff (m \;\mathcal{L}\; n)\land(m \;\mathcal{R}\; n) :m \;\mathcal D\; n\iff\exists p\in M\colon m\;\mathcal L\;p\;\mathcal R\;n\iff \exists q\in M\colon m\;\mathcal R\;q\;\mathcal L\;n 즉, \mathcal L · \mathcal R · \mathcal J는 각각 두 원소가 생성하는 왼쪽 · 오른쪽 · 양쪽 아이디얼이 같은지 여부이다. \mathcal H는 \mathcal L과 \mathcal R가 동시에 성립하는 것이며, \mathcal D는 첫째가 생성하는 왼쪽 아이디얼이 둘째가 생성하는 오른쪽 아이디얼과 교차하는지 여부이다.
# 종류

## 가환 모노이드
모노이드 M이 다음 조건을 만족시킨다면, **가환 모노이드**(可換monoid, commutative monoid)라고 한다. :임의의 m,n\in M에 대하여, mn=nm 가환 모노이드인 군은 아벨 군이다. 즉, 다음과 같은 포함 관계가 성립한다. :마그마 ⊋ 반군 ⊋ 모노이드 ⊋ 가환 모노이드 ⊋ 아벨 군 = 군 ∩ 가환 모노이드
## 멱등 모노이드
모노이드 M이 다음 조건을 만족시킨다면, **멱등 모노이드**(冪等monoid, idempotent monoid)라고 한다. :임의의 m\in M에 대하여, m^2=m 자명 모노이드가 아닌 멱등 모노이드는 군이 될 수 없다.
# 연산

## 반대 모노이드
모노이드 (M,\cdot)이 주어졌을 때, 집합 M 위에 다음과 같은 다른 이항 연산 \cdot'을 줄 수 있다. :\cdot'\colon M\times M\to M :a\cdot'b=b\cdot a\qquad\forall a,b\in M 그렇다면 (M,\cdot')은 모노이드를 이룬다. 이를 (M,\cdot)의 **반대 모노이드**(反對monoid, opposite monoid)라고 하고, M^{\operatorname{op으로 쓴다. 군론의 반대군이나, 환론의 반대환은 반대 모노이드의 특수한 경우이다. 모노이드를 하나의 대상을 갖는 범주로 간주한다면, 반대 모노이드는 반대 범주의 특수한 경우이다. 군의 경우 모든 군은 스스로의 반대군과 역원 함수를 통해 표준적으로 동형이지만, 모노이드의 경우 일반적으로 스스로의 반대 모노이드와 동형이 아니다. (가환 모노이드는 물론 스스로의 반대 모노이드와 같다.)
## 직접곱
직접곱 모노이드의 모임은 대수 구조 다양체이므로, 여러 개의 모노이드들의 **직접곱**을 정의할 수 있다. 구체적으로, 모노이드들의 집합 \\{M_i\\}_{i\in I}의 **직접곱** \textstyle\prod_iM_i은 집합으로서 곱집합과 같으며, 그 위의 이항 연산은 다음과 같다. :(a_i)_{i\in I}\cdot(b_i)_{i\in I}=(a\cdot b)_{i\in I}\qquad\forall a_i,b_i\in M_i 만약 모든 M_i가 가환 모노이드라면, 이들의 직접곱 \textstyle\prod_i M_i 역시 가환 모노이드이다. 모노이드의 직접곱은 모노이드의 범주에서의 범주론적 곱이다.
## 자유곱
자유곱 모노이드의 모임은 대수 구조 다양체이므로, 여러 개의 모노이드들의 **자유곱**을 정의할 수 있으며, 이는 모노이드의 범주의 쌍대곱이다. 구체적으로, 모노이드들의 집합 \\{M_i\\}_{i\in I}이 주어졌을 때, 자유곱 \textstyle\coprod_iM_i의 원소는 다음과 같은 문자열이다. :a_{i_1}a_{i_2}\cdots a_{i_k}\qquad(a_{i_1}\in M_{i_1}\setminus\\{1_{M_{i_1\\},\dots,a_{i_k}\in M_{i_k}\setminus\\{1_{M_{i_k\\};\quad i_1\ne i_2\ne\cdots\ne i_k) 즉, 각 모노이드의 항등원이 아닌 원소들로 구성된 문자열이며, 문자열에서 서로 마주하는 문자들은 서로 다른 모노이드에 속하여야 한다.
## 0의 추가
모노이드 M이 주어졌을 때, M\sqcup\\{0\\}에 다음과 같은 이항 연산을 주자. :0m=m0=0^2=0\qquad\forall m\in M 그렇다면 M\sqcup\\{0\\}은 모노이드를 이룬다.
## 멱집합
모노이드 M이 주어졌을 때, 그 멱집합 \mathcal P(M) 위에 다음과 같은 이항 연산을 주자. :ST=\\{st\colon s\in S,t\in T\\} 그렇다면 \mathcal P(M)은 모노이드를 이루며, 이항 연산의 항등원은 한원소 집합 \\{1_M\\}\in\mathcal P(M)이다.
# 예
모든 군은 모노이드를 이룬다. 모든 (곱셈 항등원을 갖는) 환 (R,+,\cdot)은 덧셈 연산을 잊으면 (R,\cdot)은 모노이드를 이룬다. (곱셈 연산을 잊으면 (R,+) 역시 아벨 군이므로 가환 모노이드를 이룬다.) 유계 격자 (L,\vee,\wedge)의 경우, (L,\vee) 및 (L,\wedge) 둘 다 가환 멱등 모노이드를 이룬다. (L,\wedge)의 항등원은 \bot (최소 원소)이며, (L,\vee)의 항등원은 \top (최대 원소)이다. 자연수(음이 아닌 정수)의 집합 \mathbb N은 덧셈에 대하여 가환 모노이드를 이룬다. (그러나 양의 정수의 집합 \mathbb Z^+은 덧셈에 대하여 가환 반군을 이루지만 가환 모노이드를 이루지 않는다.) 정수 집합의 다음과 같은 부분 집합들은 곱셈에 대하여 가환 모노이드를 이룬다. * 양의 정수의 집합 \mathbb Z^+ * 자연수의 집합 \mathbb N=\mathbb Z^+\cup\\{0\\} * \\{0,1\\} * \\{0\\} * \\{1\\} * 임의의 정수 k에 대하여, \\{1,k,k^2,k^3,\dots\\}
## 자명 모노이드
자명군 다른 대수 구조 다양체와 마찬가지로, 모노이드의 경우 **자명 모노이드**(自明monoid, trivial monoid)를 정의할 수 있다. 이는 한원소 집합 위에 정의할 수 있는 유일한 이항 연산이다. 이는 사실 아벨 군을 이루며, 이를 **자명군**이라고 한다.
## 자기 사상 모노이드
임의의 국소적으로 작은 범주 \mathcal C 속의 대상 X\in\mathcal C에 대하여, X 위의 자기 사상 집합 \hom_{\mathcal C}(X,X)은 사상 합성에 대하여 모노이드를 이룬다. 이를 **자기 사상 모노이드**(endomorphism monoid) \operatorname{End}_{\mathcal C}X라고 한다. 자기 사상 모노이드 \operatorname{End}_{\mathcal C}X의 가역원군은 자기 동형군 \operatorname{Aut}_{\mathcal C}X이다. 예를 들어, 집합의 범주 \operatorname{Set}에서, 집합 S의 자기 사상 모노이드 \operatorname{End}_{\operatorname{SetS는 **완전 변환 모노이드**(full transformation monoid)라고 하고, 그 가역원군은 S의 **대칭군** \operatorname{Sym}S이다.
## 자유 모노이드
모노이드의 모임은 대수 구조 다양체를 이루므로, 자유 대수를 정의할 수 있다. 이를 **자유 모노이드**(自由monoid, free monoid)라고 한다. 집합 S로부터 생성되는 자유 모노이드는 그 클레이니 스타 S^*와 같다. 즉, S^*의 원소는 S를 알파벳으로 하는 문자열이며, 모노이드 연산은 문자열의 이음이다. 모노이드 연산의 항등원은 길이가 0인 유일한 문자열이다. 공집합으로 생성되는 자유 모노이드는 자명 모노이드이다. 한원소 집합으로 생성되는 자유 모노이드는 자연수의 덧셈 모노이드 (\mathbb N,+)와 동형이다. 두 개 이상의 원소를 갖는 집합으로 생성되는 자유 모노이드는 비가환 모노이드이며 무한 집합이다.
## 자유 가환 모노이드
가환 모노이드의 모임은 대수 구조 다양체를 이루므로, 자유 대수를 정의할 수 있다. 이를 **자유 가환 모노이드**(自由可換monoid, free commutative monoid)라고 한다. 집합 S로부터 생성되는 자유 가환 모노이드 \mathbb N^S는 S의 원소만을 포함하는 유한 중복집합들의 집합이다. 즉, \mathbb N^S의 원소는 S의 각 원소에 자연수를 대응시키는 함수 :f\colon S\to\mathbb N 로 생각할 수 있다. 이 위의 이항 연산은 함수의 점별 합이다. :f+g\colon s\mapsto (f(s)+g(s)) 공집합으로 생성되는 자유 가환 모노이드는 자명 모노이드이다. 한원소 집합으로 생성되는 자유 가환 모노이드는 한원소 집합 위의 자유 모노이드와 같으며, 자연수의 덧셈 모노이드 (\mathbb N,+)와 동형이다. 산술의 기본 정리에 따르면, 양의 정수 집합의 곱셈 모노이드 (\mathbb Z^+,\cdot)는 소수 집합 위의 자유 가환 모노이드와 표준적으로 동형이다.
## 작은 크기의 모노이드
크기가 1인 모노이드는 자명 모노이드 밖에 없다. 크기가 2인 모노이드는 다음 2개가 있으며, 둘 다 가환 모노이드이다. * 2차 순환군 \operatorname{Cyc}(2) (아벨 군). 표시: \langle x|x^2=1\rangle * \langle 0|0^2=0\rangle (가환 멱등 모노이드). 이는 자명군에 0을 추가한 것이다. 크기가 3인 모노이드는 다음 7개가 있으며, 7개 가운데 5개는 가환 모노이드이다. * 가역원군 크기 3: ** 3차 순환군 \operatorname{Cyc}(3) (아벨 군). 표시: \langle x|x^4=1\rangle. 3차 유한체 \mathbb F_3의 덧셈 아벨 군이다. * 가역원군 크기 2: ** \operatorname{Cyc}(2)\cup\\{0\\} (가환 모노이드). 표시: \langle 0,x|0x=x0=0^2=0,x^2=1\rangle. 이는 2차 순환군 \operatorname{Cyc}(2)에 0을 추가한 것이다. 또한, 3차 유한체 \mathbb F_3의 곱셈 모노이드이다. * 가역원군 크기 1: ** \langle 0,x|0x=x0=0^2=0,x^2=x\rangle (가환 멱등 모노이드). 이는 크기 2의 가환 모노이드 \langle x|x^2=x\rangle에 0을 추가한 것이다. ** \langle 0,x|0x=x0=x^2=0^2=0\rangle (가환 모노이드) ** \langle x|x^3=x\rangle (가환 모노이드) ** \langle x,y|x^2=xy=x,y^2=yx=y\rangle (비가환 멱등 모노이드). ** 위 모노이드의 반대 모노이드. 표시: \langle x,y|x^2=yx=x,y^2=xy=x\rangle 마지막 두 개의, 크기 3의 비가환 모노이드를 **플립플롭 모노이드**(flip-flop monoid)라고 한다. 이는 크론-로즈 정리에 등장한다. 크기가 n인 모노이드의 동형류의 수는 다음과 같다. (n=1,2,3,\dots) :1, 2, 7, 35, 228, 2237, 31559, 1668997, … A058129 모노이드와 그 반대 모노이드를 동치로 간주할 때, 크기가 n인 모노이드의 동치류의 수는 다음과 같다. (n=1,2,3,\dots) :1, 2, 6, 27, 156, 1373, 17730, 858977, 1844075697, 52991253973742, … A058133 크기가 n인 가환 모노이드의 동형류의 수는 다음과 같다. (n=1,2,3,\dots) :1, 2, 5, 19, 78, 421, 2637, … A058131
## 연결합
연결합 주어진 차원의 콤팩트 매끄러운 다양체들의 미분 동형류들의 집합을 생각하자. 이 집합은 연결합을 통해 가환 모노이드를 이루며, 항등원은 해당 차원의 초구이다. 매끄러운 다양체 대신 (위상) 다양체를 사용하여도 가환 모노이드를 얻는다.
## 벡터 다발
위상 K이론 주어진 매끄러운 다양체 위의 실수 벡터 다발들의 동형류의 집합을 생각하자. 이는 직합을 통해, 또는 텐서곱을 통해 가환 모노이드를 이룬다.
## 유한 상태 기계
유한 상태 기계 알파벳 \Sigma에 대한, 상태 집합이 S인 유한 상태 기계 \delta\colon \Sigma\times S\to S는 \Sigma 위의 문자열 모노이드(자유 모노이드)에서 S의 완전 변환 모노이드로 가는 모노이드 준동형 :\Sigma^*\to\operatorname{End}_{\operatorname{SetS 을 정의한다. 즉, 이는 S 위에 작용하는 모노이드를 정의한다. 모노이드 이론, 특히 크론-로즈 정리 등을 사용하여 유한 상태 기계를 분석할 수 있다.