모노이드

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

모노이드는 집합과 이항 연산으로 구성된 대수 구조로, 결합 법칙과 항등원 존재라는 두 가지 공리를 만족한다. 즉, 모노이드는 항등원을 가진 반군이며, 하나의 객체를 가진 범주와 동일하다. 모노이드는 부분 모노이드, 모노이드 준동형, 가역원, 영원, 멱등원, 아이디얼 등의 개념을 가지며, 반대 모노이드, 직접곱, 자유곱, 멱집합 등의 연산을 통해 새로운 모노이드를 생성할 수 있다. 모노이드는 컴퓨터 과학에서 추상 자료형, MapReduce 프로그래밍 모델 등에 응용되며, 범주론의 개념과 밀접한 관련을 맺고 있다.

더 읽어볼만한 페이지

대수 구조 - 환 (수학)
환은 덧셈에 대해 아벨 군, 곱셈에 대해 모노이드를 이루며 분배 법칙이 성립하는 대수 구조로, 가환환과 비가환환으로 나뉘고 모든 비영 원소가 곱셈 역원을 갖는 비영 가환환을 체라고 한다.
대수 구조 - 계수
계수는 수학에서 다항식, 급수, 또는 식의 항에 곱해지는 곱셈 인자를 의미하며, 다항식에서는 숫자, 매개변수 등으로 나타낼 수 있고, 선형대수학, 푸리에 급수, 이항정리 등 다양한 분야에서 활용된다.
반군론 - 멱등원
멱등원은 연산을 통해 자기 자신을 결과로 반환하는 원소로, 환이나 모노이드에서는 $e^2 = e$ 를 만족하는 원소 $e$ 를 의미하며, 환의 구조 분석에 중요한 역할을 하고 범주론에서는 자기 사상 $e$ 가 $e \circ e = e$ 를 만족시킬 때 멱등 사상이라고 정의한다.
반군론 - 화환곱
화환곱은 군론에서 두 군의 구조를 결합하여 더 큰 군을 만드는 연산으로, 반군 작용을 통해 정의되며 다양한 종류가 존재하고 결합 법칙을 따르며 여러 분야에 응용된다.
범주론 - 작은 범주
그로텐디크 전체 $\mathcal{U}$ 가 주어졌을 때, $\mathcal{U}$ -작은 범주는 대상과 사상의 모임이 모두 $\mathcal{U}$ 의 원소인 범주를 의미하며, 이는 함자와 자연 변환과 함께 완비 범주이자 쌍대 완비 범주인 2-범주를 이룬다.
범주론 - 토포스
토포스는 유한 완비 범주이자 데카르트 닫힌 범주이며 부분 대상 분류자를 갖는 특정한 조건을 만족하는 범주로서, 일계 논리 또는 일계 정의가 있는 대상의 부분 대상 개념을 갖는 데카르트 닫힌 범주로 이해될 수 있고, 위상 공간의 일반화이자 집합론에 대한 범주론적 일반화로서 수학의 공리적 기초를 제공한다.

모노이드
개요
종류	대수 구조
정의	결합 법칙을 만족하는 이항 연산과 항등원을 갖는 대수 구조
정의
정의	집합 M과 이항 연산 * : M × M → M로 구성된 대수 구조 (M, *) 다음 공리를 만족해야 함
결합 법칙	임의의 a, b, c ∈ M에 대해 (a * b) * c = a * (b * c)
항등원	M 안에 다음 조건을 만족하는 원소 e가 존재
항등원 조건
좌항등원	임의의 a ∈ M에 대해 e * a = a
우항등원	임의의 a ∈ M에 대해 a * e = a
양쪽 항등원	좌항등원이자 우항등원
예시
예시	자연수의 집합 N (0을 포함)과 덧셈 연산 + 문자열의 집합과 문자열 연결 연산 행렬의 집합과 행렬 곱셈 연산
성질
항등원의 유일성	모노이드 안에는 단 하나의 항등원만 존재
가역원	모노이드의 원소 중에는 역원을 갖는 원소가 있을 수 있으며, 이들을 가역원이라고 함
군	모든 원소가 가역원인 모노이드는 군이 됨
관련 개념
반군	결합 법칙을 만족하는 이항 연산을 갖는 대수 구조 (항등원 존재 여부는 불필요)
군	모든 원소가 역원을 갖는 모노이드
환	덧셈에 대해 아벨 군, 곱셈에 대해 모노이드인 대수 구조
모노이드 준동형 사상	두 모노이드 사이의 구조를 보존하는 함수
모노이드 범주	대상이 모노이드이고 사상이 모노이드 준동형 사상인 범주
참고 문헌
참고 문헌	(영어) John M. Howie, Fundamentals of Semigroup Theory, Clarendon Press, 1995, ISBN 0-19-851194-9. (영어) Pierre Antoine Grillet, Semigroups: An Introduction to the Structure Theory, Marcel Dekker, 1995, ISBN 0-8247-9662-4.
외부 링크
외부 링크	MathWorld: Monoid PlanetMath: Monoid

2. 정의

'''모노이드'''(monoid^영어)는 다음의 데이터를 갖는 대수 구조이다.

집합 $M$
이항 연산 $\cdot\colon M\times M\to M$

이 데이터는 다음 두 공리를 만족시켜야 한다.

(결합 법칙) $M$ 의 임의의 원소 $a,b,c$ 에 대하여, $(a\cdot b)\cdot c=a\cdot(b\cdot c)$
(항등원의 존재) $M$ 의 임의의 원소 $a$ 에 대하여 $1\cdot a=a\cdot1=a$ 를 만족시키는 원소 $1\in M$ 이 존재한다. (이러한 항등원은 유일하다.)

모노이드는 항등원을 갖는 반군이자, 결합 법칙과 항등원을 갖는 마그마이다. 이항 연산 기호는 생략되는 경우가 많으며, 예를 들어 위의 공리들은

(ab)c = a(bc)

,

ea = ae = a

와 같이 표기된다.

2. 1. 부분 모노이드

모노이드

M

의 부분 집합

S\subseteq M

가 다음 조건을 만족시킨다면,

S

를

M

의 '''부분 모노이드'''(submonoid^영어)라고 한다.

임의의 $s,t\in S$ 에 대하여, $st\in S$
$1\in S$

둘째 조건은 첫째로부터 함의되지 않는다. 첫째 조건을 만족시키지만 둘째 조건을 만족시키지 않는 부분 집합은 부분 반군을 이루지만, 부분 모노이드를 이루지 않는다.

모노이드

(M, \bullet)

의 '''부분 모노이드'''는 모노이드 연산에 닫혀있고,

M

의 항등원

e

를 포함하는

M

의 부분 집합

N

이다. 기호로 나타내면,

e \in N \subseteq M

이고,

x, y \in N

일 때마다

x \bullet y \in N

이면

N

은

M

의 부분 모노이드이다. 이 경우,

N

은

M

에서 상속된 이진 연산 하에서 모노이드이다.

반면에,

N

이 모노이드 연산에 대해 닫혀 있고, 이 상속된 연산에 대해 모노이드인 모노이드의 부분 집합인 경우,

N

은 항상 부분 모노이드가 아닌데, 항등원이 다를 수 있기 때문이다. 예를 들어, 싱글톤 집합

\{0\}

은 곱셈에 대해 닫혀 있으며, 음이 아닌 정수의 (곱셈) 모노이드의 부분 모노이드가 아니다.

모노이드

M

의 부분 집합

N

이

M

의 '''부분 모노이드'''는

M

의 항등원을 포함하고, 닫혀있는 성질:

x, y \in N

이면

xy \in N

이 되는 것을 말한다. 이것은

M

의 모노이드 연산의 제한

\bullet_{N}: N \times N \rightarrow M

의 상이

im(\bullet_{N}) \subseteq N

을 만족하는 것이고, 따라서

\bullet_{N}

는

N

위의 이항 연산을 정의하며, 부분 모노이드

N

은 분명히 그 자체가 하나의 모노이드가 된다.

2. 2. 모노이드 준동형

두 모노이드

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$

둘째 조건은 생략할 수 없다. 첫째 조건을 만족시키지만 둘째 조건을 만족시키지 않는 함수는 모노이드 준동형이 아닌 반군 준동형이다.

예시 모노이드 준동형사상 from to . 이것은 단사 함수이지만 전사 함수는 아니다.

모노이드를 하나의 대상을 갖는 범주로 간주할 때, 모노이드 준동형은 두 범주 사이의 함자와 같다.

두 모노이드

(M, \ast)

와

(N, \bullet)

사이의 준동형사상은 다음과 같은 함수

f : M \rightarrow N

이다.

모든 $M$ 의 $x$ , $y$ 에 대해 $f(x \ast y) = f(x) \bullet f(y)$
$f(e_M) = e_N$

여기서

e_M

과

e_N

은 각각

M

과

N

의 항등원이다. 모노이드 준동형사상은 때때로 단순히 '''모노이드 사상'''이라고 불린다.

모노이드 사이의 모든 반군 준동형사상이 모노이드 준동형사상은 아니다. 왜냐하면 준동형사상은 항등원을 목표 모노이드의 항등원에 대응시키지 못할 수 있기 때문이다.

반대로, 군 사이의 반군 준동형사상은 항상 군 준동형사상인데, 이는 필연적으로 항등원을 보존하기 때문이다.

전단사 모노이드 준동형사상은 모노이드 동형사상이라고 불린다. 두 모노이드가 그 사이에 모노이드 동형사상이 있으면 동형이라고 말한다.

2. 3. 가역원군

모노이드

M

의 가역원들의 부분 집합은 부분 모노이드를 이루며, 군을 이룬다. 이를

M

의 '''가역원군'''(unit group^영어)

\operatorname{Unit}(M)

이라고 한다.^[1] 모노이드 내의 모든 가역원 집합은 연산과 함께 군을 형성한다.^[1]

2. 4. 영원과 멱등원

모노이드

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

은 정의에 따라 멱등원이다.

2. 5. 아이디얼

모노이드

M

에서, 다음 조건을 만족시키는 부분 반군

I\subseteq M

을

M

의 '''왼쪽 아이디얼'''(left ideal^영어)이라고 한다.

:

mi\in I\qquad\forall m\in M,i\in I

모노이드

M

에서, 다음 조건을 만족시키는 부분 반군

I\subseteq M

을

M

의 '''오른쪽 아이디얼'''(right ideal^영어)이라고 한다.

:

im\in I\qquad\forall m\in M,i\in I

왼쪽 아이디얼이자 오른쪽 아이디얼인 부분 반군을 '''아이디얼'''(ideal^영어)이라고 한다.

아이디얼은 부분 모노이드를 이룰 필요가 없다 (즉, 1을 포함하지 않을 수 있다). 모노이드

M

의 부분 모노이드를 이루는 아이디얼은

M

전체 밖에 없다.

2. 6. 그린 관계

모노이드

M

위에는 다음과 같이 5개의 표준적인 동치 관계가 존재하며, 이를 '''그린 관계'''라고 한다.^[2]

관계	정의
$m \;\mathcal L\; n$	$Mm=Mn$
$m \;\mathcal R\; n$	$mM=nM$
$m \;\mathcal J\; n$	$MmM=MnM$
$m \;\mathcal H\; n$	$(m \;\mathcal{L}\; n)\land(m \;\mathcal{R}\; n)$
$m \;\mathcal D\; n$	$\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$ 는 첫째가 생성하는 왼쪽 아이디얼이 둘째가 생성하는 오른쪽 아이디얼과 교차하는지 여부이다.

3. 종류

모노이드에는 여러 종류가 있다.

가능한 16개의 이진 불리언 연산자 중 4개는 교환적이고 결합적인 양측 항등원을 가진다. 이 4가지는 각각 집합 를 교환 모노이드로 만든다. 표준 정의에 따르면, AND와 XNOR은 항등원 를 가지는 반면, XOR과 OR은 항등원 를 가진다. AND와 OR에서 파생된 모노이드는 멱등원이지만, XOR과 XNOR에서 파생된 모노이드는 아니다.
자연수 집합 은 덧셈(항등원 ) 또는 곱셈(항등원 )에 대해 교환 모노이드이다. 덧셈에 대한 의 부분 모노이드를 수치 모노이드라고 한다.
양의 정수 집합 는 곱셈(항등원 )에 대해 교환 모노이드이다.
집합 가 주어지면, 의 부분 집합 집합은 교집합에 대해 교환 모노이드이다(항등원은 자체).
집합 가 주어지면, 의 부분 집합 집합은 합집합에 대해 교환 모노이드이다(항등원은 공집합).
모든 경계가 있는 반격자는 멱등원 교환 모노이드이다.
* 특히 모든 경계가 있는 격자는 만남과 결합 모노이드 구조를 모두 부여받을 수 있다. 항등원은 각각 격자의 상한과 하한이다. 격자인 헤이팅 대수와 불 대수는 이러한 모노이드 구조를 부여받는다.
모든 단일 집합 는 이진 연산 에 대해 닫혀 있으며, 이는 자명군이기도 한 자명(1개 요소) 모노이드를 형성한다.
모든 군은 모노이드이고, 모든 아벨 군은 교환 모노이드이다.
모든 반군 는 에 없는 요소 를 단순히 인접시키고 모든 에 대해 를 정의함으로써 모노이드로 바뀔 수 있다.
* 멱등원 모노이드(때로는 ''find-first''라고도 함)는 집합 에 대한 왼쪽 영 반군에 항등원 를 인접시켜 형성될 수 있다. 반대 모노이드(때로는 ''find-last''라고도 함)는 에 대한 오른쪽 영 반군에서 형성된다.
** 두 요소 를 가진 왼쪽 영 반군에 항등원 를 인접시키면 멱등원 모노이드 가 된다.
연산으로 덧셈 또는 곱셈이 있는 모든 환의 기본 집합이다.
* 덧셈 또는 곱셈을 연산으로 하는 정수, 유리수, 실수 또는 복소수.^[2]
* 주어진 환에 대한 모든 × 행렬 집합은 행렬 덧셈 또는 행렬 곱셈을 연산으로 한다.
일부 고정된 알파벳 에 대한 모든 유한 문자열 집합은 문자열 연결을 연산으로 하는 모노이드를 형성한다. 빈 문자열은 항등원 역할을 한다. 이 모노이드는 로 표시되며 에 대한 ''자유 모노이드''라고 한다.
모노이드 이 주어지면, ''반대 모노이드'' 는 과 동일한 캐리어 집합과 항등원을 가지며, 연산은 로 정의된다.
모노이드 구조가 부여된 두 개의 집합 과 이 주어지면, 해당 좌표에서 정의된 이진 연산 및 항등원을 사용하여 데카르트 곱 는 직접곱이라고 하며, 또한 모노이드이다.
모노이드 을 수정하면 주어진 집합에서 으로의 모든 함수의 집합도 모노이드가 된다. 항등원은 모든 값을 의 항등원에 매핑하는 상수 함수이고, 결합 연산은 점별로 정의된다.
연산 과 항등원 를 가진 모노이드 의 멱집합 을 고려하면 이진 연산은 }로 정의될 수 있다. 이것은 을 항등원 를 가진 모노이드로 만든다.
를 집합이라고 하면 모든 함수 집합은 함수 합성에 따라 모노이드를 형성한다. 항등원은 단순히 항등 함수이다. 이것은 또한 의 ''전체 변환 모노이드''라고도 한다.
연결 합이 있는 콤팩트 곡면의 위상 동형 class 집합이다. 그 단위 요소는 일반 2차원 구의 클래스이다.
를 차수 의 순환 모노이드라고 하면, . 그러면 for some 가 된다. 각 는 차수 의 다른 모노이드를 제공하며, 모든 순환 모노이드는 이러한 모노이드 중 하나와 동형이다.

\begin{bmatrix}0 & 1 & 2 & \cdots & n-2 & n-1 \\1 & 2 & 3 & \cdots & n-1 & k\end{bmatrix}

또는, 동등하게

f(i) := \begin{cases}i+1, & \text{if }  0 \le i < n-1  \\k,  & \text{if } i = n-1.\end{cases}

요소의 곱셈은 함수 합성으로 제공된다. 이면 함수 는 의 순열이며, 차수 의 고유한 순환군을 제공한다.

각 음이 아닌 정수 에 대해, 모노이드의 개 원소의 시퀀스 의 곱 $p_n = \textstyle \prod_{i=1}^n a_i$ 를 재귀적으로 정의할 수 있다.
모노이드의 원소 의 음이 아닌 정수 거듭제곱을 정의할 수 있다.
'''역 모노이드'''는 모노이드 의 모든 에 대해 및 를 만족하는 유일한 이 에 존재하는 모노이드이다. 역 모노이드가 소거 가능하면 군이 된다.
''영합이 없는 모노이드''는 이 및 을 의미하는 덧셈으로 쓰인 모노이드이다.
고정된 알파벳 집합 위의 유한 문자열 전체 (빈 문자열 포함)는 연결을 이항 연산으로 하고, 단위원을 빈 문자열로 하여 모노이드가 된다. 이 모노이드를 로 표기한다. 이것은 위의 '''자유 모노이드'''라고 부른다.

3. 1. 가환 모노이드

임의의

m,n\in M

에 대하여,

mn=nm

을 만족시키면 '''가환 모노이드'''(commutative monoid^영어)라고 한다. 가환 모노이드인 군은 아벨 군이다. 즉, 다음과 같은 포함 관계가 성립한다.

:마그마 ⊋ 반군 ⊋ 모노이드 ⊋ 가환 모노이드 ⊋ 아벨 군 = 군 ∩ 가환 모노이드

교환 연산을 갖는 모노이드는 '''가환 모노이드''' (또는 덜 흔하게는 '''아벨 모노이드''')라고 한다. 가환 모노이드는 종종 덧셈 표기법으로 표기된다. 모든 가환 모노이드는

x\le y \iff x+z = y\quad \exist z\in M

로 정의되는 ''대수적'' 전순서를 가지며, 여기서

x\le y

는

x+z = y

를 만족하는

z

가 존재하는 경우이다. 가환 모노이드

M

의 ''순서 단위''는

M

의 임의의 원소

x

에 대해,

x\le v

를 만족하는

u

에 의해 생성된 집합 내의

v

가 존재하는

M

의 원소

u

이다. 이는

M

이 양의 부분 아벨 군

G

의 부분 순서인 경우에 자주 사용되며, 이 경우

u

는

G

의 순서 단위라고 말한다.

3. 2. 멱등 모노이드

임의의

m\in M

에 대하여,

m^2=m

을 만족시키면 '''멱등 모노이드'''(idempotent monoid^영어)라고 한다. 자명 모노이드가 아닌 멱등 모노이드는 군이 될 수 없다.

3. 3. 부분 가환 모노이드

일부 원소에 대해서는 교환적이지만, 모든 원소에 대해 교환적인 것은 아닌 모노이드는 트레이스 모노이드라고 한다. 트레이스 모노이드는 병렬 계산 이론에 자주 나타난다.^[1]

4. 연산

모노이드의 원소 $x$ 의 음이 아닌 정수 거듭제곱을 정의할 수 있는데, $x^0 = 1$ 로 두고, $n \ge 1$ 에 대해 $x^n = x^{n-1} \cdot x$ 로 둔다. 그러면 모든 $m, n \ge 0$ 에 대해 $x^{m+n} = x^m \cdot x^n$ 이 된다.

4. 1. 반대 모노이드

모노이드

(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)

의 '''반대 모노이드'''(opposite monoid^영어)라고 하고,

M^{\operatorname{op}}

으로 쓴다.

군론의 반대군이나, 환론의 반대환은 반대 모노이드의 특수한 경우이다. 모노이드를 하나의 대상을 갖는 범주로 간주한다면, 반대 모노이드는 반대 범주의 특수한 경우이다.

군의 경우 모든 군은 스스로의 반대군과 역원 함수를 통해 표준적으로 동형이지만, 모노이드의 경우 일반적으로 스스로의 반대 모노이드와 동형이 아니다. (가환 모노이드는 물론 스스로의 반대 모노이드와 같다.)

임의의 모노이드

(M,

•

)

에 대해, 그 '''반대 모노이드''' (opposite monoid^영어)

(M

^op, •^op

)

는, 대집합과 항등원은

M

과 같고, 그 연산을 다음과 같이 정의하여 얻어지는 모노이드이다.

:

x

^op•

y := y

•

x

4. 2. 직접곱

모노이드들의 모임은 대수 구조 다양체이므로, 여러 개의 모노이드들의 '''직접곱'''을 정의할 수 있다. 구체적으로, 모노이드들의 집합

\{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|엠^영어, N|엔^영어에 대해 (더 일반적으로는 유한 개의 모노이드

M_1, \dots, M_k

에 대해, 또는 무한 개의 모노이드

\{M_i\}_{i\in I}

에 대해), 이들의 직적 집합

M \times N

(또는

M_1 \times \dots \times M_k

,

\prod_{i\in I} M_i

\{M_i\}_{i\in S}

의 직적 모노이드와 본질적으로 동일하다.

4. 3. 자유곱

모노이드의 모임은 대수 구조 다양체이므로, 여러 개의 모노이드들의 '''자유곱'''을 정의할 수 있으며, 이는 모노이드의 범주의 쌍대곱이다. 구체적으로, 모노이드들의 집합

\{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)

즉, 각 모노이드의 항등원이 아닌 원소들로 구성된 문자열이며, 문자열에서 서로 마주하는 문자들은 서로 다른 모노이드에 속하여야 한다.

4. 4. 멱집합

모노이드

M

의 멱집합

\mathcal P(M)

위에 다음과 같은 이항 연산을 정의할 수 있다.

:

ST=\{st\colon s\in S,t\in T\}

여기서

S

와

T

는

M

의 부분집합이다. 이 연산에 대해

\mathcal P(M)

은 모노이드를 이루며, 이항 연산의 항등원은 한원소 집합

\{1_M\}

이다.

같은 방법으로, 군

G

의 멱집합은 군 부분집합의 곱에 관한 모노이드가 된다.

5. 예

모든 군은 모노이드를 이룬다. 모든 (곱셈 항등원을 갖는) 환에서 덧셈 연산을 잊으면 곱셈에 대한 모노이드를 얻고, 곱셈 연산을 잊으면 덧셈에 대한 아벨 군이 되므로 가환 모노이드를 이룬다.

유계 격자는 결합과 만남 연산에 대해 각각 가환 멱등 모노이드를 이룬다. 이때 항등원은 각각 격자의 최소 원소와 최대 원소이다.

자연수 집합은 덧셈(항등원 0)에 대하여 가환 모노이드를 이룬다. 하지만 양의 정수 집합은 덧셈에 대해 가환 반군은 되지만 모노이드는 아니다. 양의 정수 집합은 곱셈(항등원 1)에 대해 교환 모노이드이다.

다음은 곱셈에 대하여 가환 모노이드를 이루는 정수 집합의 부분 집합들이다.

양의 정수의 집합
자연수의 집합
{0, 1}
{0}
{1}
임의의 정수 k에 대하여 {1, k, k², k³, ...}

이진 불리언 연산자 중 AND, XNOR, XOR, OR 4개는 교환적이고 결합적인 양측 항등원을 갖는다. 이들은 집합 False, True^영어를 교환 모노이드로 만든다. AND와 XNOR은 항등원 True^영어를, XOR과 OR은 항등원 False^영어를 갖는다. AND와 OR에서 파생된 모노이드는 멱등원이지만, XOR과 XNOR에서 파생된 모노이드는 그렇지 않다.

자연수 집합은 덧셈(항등원 0) 또는 곱셈(항등원 1)에 대해 교환 모노이드이다. 덧셈에 대한 자연수 집합의 부분 모노이드를 수치 모노이드라고 한다.

집합 A가 주어지면, A의 부분 집합들은 교집합(항등원 A) 또는 합집합(항등원 공집합)에 대해 교환 모노이드이다.

모든 단일 집합은 자명군이기도 한 자명 모노이드를 형성한다.

모든 반군은 자유 함자를 통해 모노이드로 변환될 수 있다.

환의 기본 집합은 덧셈 또는 곱셈 연산에 대해 모노이드를 이룬다. 예를 들어, 정수, 유리수, 실수, 복소수는 각각 덧셈 또는 곱셈에 대해 모노이드를 이룬다. 또한, 주어진 환에 대한 모든 정사각 행렬의 집합은 행렬 덧셈 또는 행렬 곱셈 연산에 대해 모노이드를 이룬다.

문자열 연결 연산을 갖는 문자열 집합은 모노이드를 형성하며, 빈 문자열이 항등원 역할을 한다.

모노이드 M이 주어지면, 그 반대 모노이드 M^op는 원래 모노이드와 같은 집합과 항등원을 가지지만, 연산은 반대로 정의된다.

두 모노이드의 직접곱은 데카르트 곱으로 표현되며, 좌표별 연산과 항등원을 가진다.

모노이드 M에 대해, 주어진 집합에서 M으로의 모든 함수 집합은 점별 연산을 통해 모노이드를 이룬다.

모노이드 M의 멱집합은 부분 집합 간의 연산을 통해 모노이드를 이룬다.

집합 S에 대한 모든 함수 S → S는 함수 합성에 따라 모노이드를 형성하며, 항등 함수가 항등원이다. 이를 S의 전체 변환 모노이드라고 한다.

콤팩트 곡면의 위상 동형류 집합은 연결 합 연산에 대해 가환 모노이드를 이룬다.

5. 1. 작은 크기의 모노이드

크기가 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, …

6. 응용

모노이드는 여러 분야에서 응용된다.

6. 1. 컴퓨터 과학에서의 응용

컴퓨터 과학에서 많은 추상 자료형은 모노이드 구조를 가질 수 있다. 일반적인 패턴으로, 모노이드의 요소 시퀀스는 최종 값을 생성하기 위해 "접기" 또는 "누적"된다. 예를 들어, 많은 반복 알고리즘은 각 반복에서 일종의 "합계"를 업데이트해야 하는데, 이 패턴은 모노이드 연산으로 표현될 수 있다. 모노이드 연산의 결합성은 여러 코어 또는 프로세서를 효율적으로 활용하기 위해 접두사 합 또는 유사한 알고리즘을 사용하여 연산을 병렬 처리할 수 있도록 보장한다.

항등원 ε와 결합 연산 •이 있는 M 유형의 값 시퀀스가 주어지면, ''fold'' 연산은 다음과 같이 정의된다.

:

\mathrm{fold}: M^{*} \rarr M = \ell \mapsto \begin{cases} \varepsilon & \mbox{if } \ell = \mathrm{nil} \\ m \bullet \mathrm{fold} \, \ell' & \mbox{if } \ell = \mathrm{cons} \, m \, \ell' \end{cases}

또한, 요소의 직렬화가 주어지면 모든 자료 구조를 유사한 방식으로 '접을' 수 있다. 예를 들어, 이진 트리를 "접는" 결과는 트리 순회 방법에 따라 달라질 수 있다.

컴퓨터 과학에서 모노이드의 한 가지 응용은 MapReduce 프로그래밍 모델이다. MapReduce는 컴퓨팅에서 두세 가지 연산으로 구성된다. 데이터 세트가 주어지면 "Map"은 임의의 데이터를 특정 모노이드의 요소에 매핑하는 것으로 구성된다. "Reduce"는 이러한 요소들을 폴딩하여 하나의 요소만 생성하도록 한다.

예를 들어, 멀티셋이 있는 경우 프로그램에서 요소에서 해당 숫자로의 맵으로 표현된다. 이 경우 요소는 키라고 한다. 고유 키의 수가 너무 많을 수 있으며, 이 경우 멀티셋은 분할된다. 리듀싱을 적절하게 완료하기 위해 "Shuffling" 단계에서 노드 간에 데이터를 재그룹화한다. 이 단계가 필요하지 않은 경우 전체 Map/Reduce는 매핑 및 리듀싱으로 구성되며, 두 연산 모두 병렬화가 가능하다. 전자는 요소별 특성으로 인해, 후자는 모노이드의 결합 법칙으로 인해 병렬화가 가능하다.

'''완비 모노이드'''는 임의의 색인 집합 I에 대한 무한 합 연산

\Sigma_I

가 갖춰진 가환 모노이드이며, 다음을 만족한다.

:

\sum_{i \in \emptyset}{m_i} =0;\quad \sum_{i \in \{j\}}{m_i} = m_j;\quad \sum_{i \in \{j, k\}}{m_i} = m_j+m_k \quad \text{ for } j\neq k

그리고

:

\sum_{j \in J}{\sum_{i \in I_j}{m_i}} = \sum_{i \in I} m_i \quad  \text{ if } \bigcup_{j\in J} I_j=I \text{ and } I_j \cap I_{j'} = \emptyset \quad \text{ for } j\neq j'

.

7. 범주론과의 관계

모노이드는 하나의 대상을 갖는 범주와 본질적으로 같다. 모노이드 준동형은 단일 객체 범주 간의 함자와 같다.

임의의 국소적으로 작은 범주 $\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{Set}}S$ 는 '''완전 변환 모노이드'''(full transformation monoid^영어)라고 하고, 그 가역원군은 $S$ 의 '''대칭군''' $\operatorname{Sym}S$ 이다.

모노이드는 범주의 특별한 종류로 볼 수 있다. 모노이드에서 이항 연산에 적용되는 규칙은, 범주에서 (주어진 단 하나의 대상을 시작과 끝으로 하는 사상의 집합만으로 생각하면) 사상의 합성에 적용되는 규칙과 같다. 즉:

:모노이드는 단 하나의 대상을 갖는 범주(단일 대상 범주)와 본질적으로 동일하다.

더욱 자세히 설명하면, 모노이드 (''M'', •)는 단 하나의 대상을 가지며, ''M''의 원소를 사상으로 하여 작은 범주를 이룬다(사상의 합성은 모노이드 연산 •로 주어진다).

이와 비슷하게, 모노이드 준동형은 단일 대상 범주의 사이의 함자로 볼 수 있다. 그러므로, 지금 생각하고 있는 범주의 구성은 (작은) 모노이드의 범주 '''Mon'''와 (작은) 범주의 범주 '''Cat'''의 어떤 충만 부분 범주 사이의 범주 동치를 제공한다. 마찬가지로, (작은) 군의 범주는, '''Cat'''의 (모노이드의 범주와는 다른) 어떤 충만 부분 범주에 해당한다.

이러한 관점에서, 범주론은 모노이드 개념을 일반화한 것으로 생각할 수 있으며, 모노이드에 관한 정의나 정리의 많은 부분을 (하나 또는 그 이상의 대상을 가진) 작은 범주에 대해 일반화할 수 있다. 예를 들어, 단일 대상 범주의 몫범주는 잉여 모노이드이다.

모노이드 전체는 (다른 대수적 구조처럼), 모노이드를 대상으로 하고 모노이드 준동형을 사상으로 하는 범주 '''Mon'''을 이룬다.

또한, 추상적인 정의에 의해, 각 범주에서의 "모노이드"로서 모노이드 대상의 개념이 정해진다. 통상적인 모노이드는 (작은) 집합의 범주 '''Set'''에서의 모노이드 대상이다.

참조

_[1] 저널 Jacobson, I.5. p. 22
_[2] 저널 On the structure of semigroups 1951-07

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com