추상대수학, 그 세 번째 이야기 | 모노이드의 정의 ( Definition of Monoid )

저번 글에서 반군 (Semigroup)에 대해서 다루었다. 이제 반군에 새로운 조건을 추가하여 모노이드를 정의할 것이다. 모노이드를 정의하기에 앞서, 항등원에 대해 알아보자. 어떤 이항구조 $\left<G,*\right>$의 원소 $e$가 다음을 만족한다면 $e$를 $\left<G,*\right>$의 항등원 (Identity Element; Identity)이라고 부른다.

 

$$\forall a\in G,\;a*e=e*a=a$$

 

모노이드의 정의는 다음과 같다.

 

반군 $\left<G,\cdot\right>$에 항등원 $e\in G$가 존재하면 반군 $\left<G,\cdot\right>$를 모노이드 (Monoid)라고 부른다.

 

그러면 다음 정리가 성립한다.

 

Theorem 1.

이항구조 $\left<G,\cdot\right>$가 모노이드라면, $G$의 항등원은 유일하다.

 

Proof:

$e\in G$와 $e'\in G$ 둘 모두가 $G$의 항등원이라고 하자.

그러면 항등원의 정의에 의해 다음이 성립한다.

$$e=ee'=e'$$

따라서 $e=e'$이며 $G$의 항등원은 유일하다.

$\blacksquare$

 

이때, 모노이드 $\left<G,\cdot\right>$의 임의의 두 원소 $a$, $b$에 대해 편의상 $a\cdot b$를 $ab$로 축약하여 서술한다. 즉, 곱셈처럼 취급한다. 이때 주의할 점은 교환법칙이 성립할 것이라고 보장할 수 없기 때문에 $ab\neq ba$일 수 있다는 점이다. 즉, 실수의 곱셈처럼 취급해서는 안 된다. 이때, 어떤 이항구조 $\left<G,\cdot\right>$가 다음을 만족하면 이항구조 $\left<G,\cdot\right>$가 교환법칙 (Commutative Law; Commutative Property; Commutativity)을 만족한다고 한다.

 

$$\forall a,b\in G,\;ab=ba$$

 

또한, 교환법칙을 만족하는 모노이드를 가환 모노이드 (Commutative Monoid)라고 한다.

 

이제 새로운 연산자를 정의하자. 연산자 $\prod$는 다음과 같이 귀납적으로 정의된다. 단, $e$는 곱셈 연산의 항등원이다.

 

$$\prod_{k=1}^0 a_k = e$$ $$\forall n\in\mathbb{N},\;\prod_{k=1}^{n+1} a_k = \left(\prod_{k=1}^n a_k\right)a_{n+1}$$ $$\forall m,n\in\mathbb{N},\;\prod_{k=m}^{n+m-1} a_k = \prod_{k=1}^n a_{k+m-1}$$

 

또한, 위 정의에서 첨수가 정수 범위가 되도록 매우 자연스러운 확장을 할 수 있다. 

위의 정의에 의해 다음의 정리가 성립한다.

 

Theorem 2.

 

$$\forall u,v\in\mathbb{N}\text{ with } 1 \leq u \leq v,\;\left(\prod_{i=1}^{u} a_i \right) \left(\prod_{i=u+1}^v a_i \right) = \prod_{i=1}^v a_i$$

 

Proof:

이 표기법의 정의에 의해 다음이 성립한다.

$$\left(\prod_{i=1}^{u} a_i \right) \left(\prod_{i=u+1}^v a_i \right) = \left(\prod_{i=1}^{u} a_i \right) \left(\prod_{i=1}^{v-u} a_{i+u} \right)=\prod_{i=1}^v a_i$$

$\blacksquare$

 

또한, 다음과 같은 표기법을 정의할 수 있다.

 

$$\forall n\in\mathbb{N},\;\forall a\in G.\;a^n := \prod_{k=1}^n a$$

 

위와 같이 거듭제곱을 정의하면 다음 정리가 성립한다.

 

Theorem 3.

모노이드 $\left<G,\cdot\right>$의 임의의 원소 $a$와 임의의 두 자연수 $n$, $m$에 대해 다음 두 명제가 성립한다. $$a^{n+m}=a^n a^m \\ a^{nm}=(a^n)^m$$

 

위 명제의 증명은 자연수의 거듭제곱의 지수법칙의 증명과 유사하다.

또한, 다음의 정리 역시 성립한다.

 

Theorem 4.

가환 모노이드 $\left<G,\cdot\right>$의 원소 $a_1,a_2,\cdot,a_n$과 일대일 대응 $f:\{1,2,\cdots,n\}\to\{1,2,\cdots,n\}$에 대해 다음이 항상 성립한다. $$\prod_{i=1}^n a_i = \prod_{i=1}^n a_{f(i)}$$

 

Proof:

$n=0$일 때와 $n=1$일 때엔 자명하다.

$n \leq k$에 대해 성립함을 가정하자. 이제 $u = f^{-1}(k+1)$를 생각하자.

그러면 $i < u$일 때 $g(f(i)) = i$이고 $i > u$일 때 $g(f(i))+1 = i$인 일대일 대응 $g:\{1,2,\cdots,k+1\}\setminus\{u\}\to\{1,2,\cdots,k\}$가 존재함을 쉽게 알 수 있다. 그러면 다음이 성립한다.

$$\prod_{i=1}^{k+1} a_{f(i)} = \left( \prod_{i=1}^{u-1} a_{f(i)} \right) a_{k+1} \left( \prod_{i=u+1}^{k+1} a_{f(i)} \right) = \left( \prod_{i=1}^{u-1} a_i \right) \left( \prod_{i=u}^{k} a_i \right) a_{k+1} = \prod_{i=1}^{k+1} a_i$$

따라서 수학적 귀납법에 의해 정리가 증명된다.

$\blacksquare$

 

위 정리에 의해 가환 모노이드에서는 유한한 개수의 원소의 곱의 값은 연산의 순서에 영향을 받지 않는다는 것을 알게 되었다. 따라서 가환 모노이드 $\left<G,\cdot\right>$의 유한 부분집합 $X$에 대해 다음의 표기를 정의할 수 있다.

 

$$\prod_{x\in X} x$$

 

위는 $X$의 모든 원소를 곱한 것을 나타낸다.

 

추가로, 어떤 연산이 가환이라면, 즉, 해당 연산에 대해 교환법칙이 성립한다면, $+$를 사용하여 이항연산을 나타내기도 한다. 관례적으로, 덧셈 기호 $+$는 교환법칙이 성립하는 연산에 대해서만 사용하며, 덧셈이라고 부른다. 덧셈 연산에 대해서는 $\prod$ 대신에 $\sum$을 사용한다.

 

이제 모노이드의 예시를 살펴보자. 다음은 모노이드의 예시이다.

 

Example 1.

임의의 집합 $S$에 대해 반군 $\left<\mathcal{P}\left(S\right),\cup\right>$는 모노이드이다.

 

Proof:

공집합 $\varnothing$은 $S$의 부분집합이므로 $\mathcal{P}\left(S\right)$의 원소이며, 모든 집합 $X$에 대해 $X\cup\varnothing = \varnothing\cup X = X$가 성립하므로 $\varnothing$은 반군 $\left<\mathcal{P}\left(S\right),\cup\right>$의 항등원이다. 따라서 $\left<\mathcal{P}\left(S\right),\cup\right>$는 모노이드이다.

$\blacksquare$

 

Example 2.

자연수 집합 $\mathbb{N}$에 대해 반군 $\left<\mathbb{N},+\right>$은 모노이드이다.

 

Proof:

자연수의 덧셈의 정의에 의해 $0\in\mathbb{N}$은 반군 $\left<\mathbb{N},+\right>$의 항등원이다. 따라서 $\left<\mathbb{N},+\right>$은 모노이드이다.

$\blacksquare$

 

위 예시들로부터 알 수 있는 사실이지만, 상당히 많은 반군이 사실은 모노이드이다. 하지만, 모든 반군이 모노이드인 것은 아니다.

 

Counterexample 1.

공집합 $\varnothing$과 임의의 이항연산 $*$에 대해 반군 $\left<\varnothing,*\right>$은 모노이드가 아니다.

 

Proof:

당연하지만, 공집합은 원소가 없으므로 항등원이 없다. 따라서 공반군은 모노이드가 아니다.

$\blacksquare$

 

Counterexample 2.

공집합이 아닌 임의의 집합 $S\neq\{0\}$에 대해 $S_0 = S\cup\{0\}$를 생각하자. 이항연산 $*$를 $\forall a,b\in S_0,\;a*b=0$을 만족하도록 정의하면 반군 $\left<S_0,*\right>$는 모노이드가 아니다.

 

Proof:

$x\neq0$인 $x\in S_0$가 존재하고, 모든 $y\in S_0$에 대해 $x*y=0\neq x$이므로 반군 $\left<S_0,*\right>$는 항등원을 가지지 않는다. 즉, $\left<S_0,*\right>$는 모노이드가 아니다.

$\blacksquare$