모노이드
추상대수학에서, 모노이드()는 항등원을 갖는, 결합 법칙을 따르는 이항 연산을 갖춘 대수 구조이다. 군의 정의에서 역원의 존재를 생략하거나, 반군의 정의에서 항등원의 존재를 추가하여 얻는다.
모노이드 formula_1는 다음과 같은 데이터로 구성되는 대수 구조이다.
이 데이터는 다음과 같은 두 공리를 만족시켜야 한다.
두 번째 공리를 생략하면 반군의 개념을 얻는다. 즉, 모노이드와 반군의 관계는 환과 유사환의 관계와 같다. 보통, 편의상 이항 연산을 (곱셈과 같이) 생략하는 경우가 많다.
즉, 다음과 같은 포함 관계가 성립한다.
범주론적으로, 모노이드는 집합과 함수의 범주 formula_9 속의 모노이드 대상이다. 또한, 하나의 대상만을 갖는 작은 범주는 모노이드와 같은 개념이다. 이 경우, 모든 사상은 자기 사상이며, 모노이드 이항 연산은 자기 사상의 합성이다.
두 모노이드 formula_2, formula_11 사이의 모노이드 준동형(monoid準同型, )은 다음 조건을 만족시키는 함수 formula_12이다.
둘째 조건은 생략할 수 없다. 첫째 조건을 만족시키지만 둘째 조건을 만족시키지 않는 함수는 모노이드 준동형이 아닌 반군 준동형이다.
모노이드를 하나의 대상을 갖는 범주로 간주할 때, 모노이드 준동형은 두 범주 사이의 함자와 같다.
모노이드 formula_2의 부분 집합 formula_17가 다음 조건을 만족시킨다면, formula_18를 formula_2의 부분 모노이드(部分monoid, )라고 한다.
둘째 조건은 첫째로부터 함의되지 않는다. 첫째 조건을 만족시키지만 둘째 조건을 만족시키지 않는 부분 집합은 부분 반군을 이루지만, 부분 모노이드를 이루지 않는다.
모노이드 formula_2의 원소 formula_24의 왼쪽 역원()은 (만약 존재한다면) 다음 조건을 만족시키는 원소 formula_25이다.
모노이드 formula_2의 원소 formula_24의 오른쪽 역원()은 (만약 존재한다면) 다음 조건을 만족시키는 원소 formula_25이다.
formula_24의 왼쪽 역원이자 오른쪽 역원인 원소는 역원()이라고 하고, formula_32로 쓴다. 주어진 원소의 왼쪽 역원 및 오른쪽 역원은 유일하지 않을 수 있지만, 주어진 원소의 역원은 (만약 존재한다면) 유일하다. 역원을 갖는 원소를 가역원(, )이라고 한다.
모노이드 formula_2의 가역원들의 부분 집합은 부분 모노이드를 이루며, 또한 군을 이룬다. 이를 formula_2의 가역원군() formula_35이라고 한다.
모노이드 formula_2 속에서, 다음과 같은 원소 formula_37이 존재한다면, 이를 formula_2의 영원()이라고 한다.
이러한 원소는 만약 존재한다면 유일하다.
모노이드 formula_2 속에서 formula_41을 만족시키는 원소 formula_24을 멱등원()이라고 한다. 항등원 formula_8은 정의에 따라 멱등원이다.
모노이드 formula_2 속에서, 다음 조건을 만족시키는 부분 반군 formula_45을 formula_2의 왼쪽 아이디얼()이라고 한다.
모노이드 formula_2 속에서, 다음 조건을 만족시키는 부분 반군 formula_45을 formula_2의 오른쪽 아이디얼()이라고 한다.
왼쪽 아이디얼이자 오른쪽 아이디얼인 부분 반군을 아이디얼()이라고 한다.
아이디얼은 부분 모노이드를 이룰 필요가 없다 (즉, 1을 포함하지 않을 수 있다). 모노이드 formula_2의 부분 모노이드를 이루는 아이디얼은 formula_2 전체 밖에 없다.
모노이드 formula_2 위에 다음과 같이 5개의 표준적인 동치 관계가 존재하며, 이를 그린 관계라고 한다.
즉, formula_60 · formula_61 · formula_62는 각각 두 원소가 생성하는 왼쪽 · 오른쪽 · 양쪽 아이디얼이 같은지 여부이다. formula_63는 formula_60과 formula_61가 동시에 성립하는 것이며, formula_66는 첫째가 생성하는 왼쪽 아이디얼이 둘째가 생성하는 오른쪽 아이디얼과 교차하는지 여부이다.
모노이드 formula_2이 다음 조건을 만족시킨다면, 가환 모노이드(可換monoid, )라고 한다.
가환 모노이드인 군은 아벨 군이다. 즉, 다음과 같은 포함 관계가 성립한다.
모노이드 formula_2이 다음 조건을 만족시킨다면, 멱등 모노이드(冪等monoid, )라고 한다.
자명 모노이드가 아닌 멱등 모노이드는 군이 될 수 없다.
모노이드 formula_1이 주어졌을 때, 집합 formula_2 위에 다음과 같은 다른 이항 연산 formula_75을 줄 수 있다.
그렇다면 formula_78은 모노이드를 이룬다. 이를 formula_1의 반대 모노이드(反對monoid, )라고 하고, formula_80으로 쓴다.
군론의 반대군이나, 환론의 반대환은 반대 모노이드의 특수한 경우이다. 모노이드를 하나의 대상을 갖는 범주로 간주한다면, 반대 모노이드는 반대 범주의 특수한 경우이다.
군의 경우 모든 군은 스스로의 반대군과 역원 함수를 통해 표준적으로 동형이지만, 모노이드의 경우 일반적으로 스스로의 반대 모노이드와 동형이 아니다. (가환 모노이드는 물론 스스로의 반대 모노이드와 같다.)
모노이드의 모임은 대수 구조 다양체이므로, 여러 개의 모노이드들의 직접곱을 정의할 수 있다. 구체적으로, 모노이드들의 집합 formula_81의 직접곱 formula_82은 집합으로서 곱집합과 같으며, 그 위의 이항 연산은 다음과 같다.
만약 모든 formula_84가 가환 모노이드라면, 이들의 직접곱 formula_85 역시 가환 모노이드이다. 모노이드의 직접곱은 모노이드의 범주에서의 범주론적 곱이다.
모노이드의 모임은 대수 구조 다양체이므로, 여러 개의 모노이드들의 자유곱을 정의할 수 있으며, 이는 모노이드의 범주의 쌍대곱이다. 구체적으로, 모노이드들의 집합 formula_81이 주어졌을 때, 자유곱 formula_87의 원소는 다음과 같은 문자열이다.
즉, 각 모노이드의 항등원이 아닌 원소들로 구성된 문자열이며, 문자열에서 서로 마주하는 문자들은 서로 다른 모노이드에 속하여야 한다.
모노이드 formula_2이 주어졌을 때, formula_90에 다음과 같은 이항 연산을 주자.
그렇다면 formula_90은 모노이드를 이룬다.
모노이드 formula_2이 주어졌을 때, 그 멱집합 formula_94 위에 다음과 같은 이항 연산을 주자.
그렇다면 formula_94은 모노이드를 이루며, 이항 연산의 항등원은 한원소 집합 formula_97이다.
모든 군은 모노이드를 이룬다. 모든 (곱셈 항등원을 갖는) 환 formula_98은 덧셈 연산을 잊으면 formula_99은 모노이드를 이룬다. (곱셈 연산을 잊으면 formula_100 역시 아벨 군이므로 가환 모노이드를 이룬다.)
유계 격자 formula_101의 경우, formula_102 및 formula_103 둘 다 가환 멱등 모노이드를 이룬다. formula_103의 항등원은 formula_105 (최소 원소)이며, formula_102의 항등원은 formula_107 (최대 원소)이다.
자연수(음이 아닌 정수)의 집합 formula_108은 덧셈에 대하여 가환 모노이드를 이룬다. (그러나 양의 정수의 집합 formula_109은 덧셈에 대하여 가환 반군을 이루지만 가환 모노이드를 이루지 않는다.)
정수 집합의 다음과 같은 부분 집합들은 곱셈에 대하여 가환 모노이드를 이룬다.
다른 대수 구조 다양체와 마찬가지로, 모노이드의 경우 자명 모노이드(自明monoid, )를 정의할 수 있다. 이는 한원소 집합 위에 정의할 수 있는 유일한 이항 연산이다. 이는 사실 아벨 군을 이루며, 이를 자명군이라고 한다.
임의의 국소적으로 작은 범주 formula_117 속의 대상 formula_118에 대하여, formula_119 위의 자기 사상 집합 formula_120은 사상 합성에 대하여 모노이드를 이룬다. 이를 자기 사상 모노이드() formula_121라고 한다. 자기 사상 모노이드 formula_121의 가역원군은 자기 동형군 formula_123이다.
예를 들어, 집합의 범주 formula_9에서, 집합 formula_18의 자기 사상 모노이드 formula_126는 완전 변환 모노이드()라고 하고, 그 가역원군은 formula_18의 대칭군 formula_128이다.
모노이드의 모임은 대수 구조 다양체를 이루므로, 자유 대수를 정의할 수 있다. 이를 자유 모노이드(自由monoid, )라고 한다. 집합 formula_18로부터 생성되는 자유 모노이드는 그 클레이니 스타 formula_130와 같다. 즉, formula_130의 원소는 formula_18를 알파벳으로 하는 문자열이며, 모노이드 연산은 문자열의 이음이다. 모노이드 연산의 항등원은 길이가 0인 유일한 문자열이다.
공집합으로 생성되는 자유 모노이드는 자명 모노이드이다. 한원소 집합으로 생성되는 자유 모노이드는 자연수의 덧셈 모노이드 formula_133와 동형이다. 두 개 이상의 원소를 갖는 집합으로 생성되는 자유 모노이드는 비가환 모노이드이며 무한 집합이다.
가환 모노이드의 모임은 대수 구조 다양체를 이루므로, 자유 대수를 정의할 수 있다. 이를 자유 가환 모노이드(自由可換monoid, )라고 한다. 집합 formula_18로부터 생성되는 자유 가환 모노이드 formula_135는 formula_18의 원소만을 포함하는 유한 중복집합들의 집합이다. 즉, formula_135의 원소는 formula_18의 각 원소에 자연수를 대응시키는 함수
로 생각할 수 있다. 이 위의 이항 연산은 함수의 점별 합이다.
공집합으로 생성되는 자유 가환 모노이드는 자명 모노이드이다. 한원소 집합으로 생성되는 자유 가환 모노이드는 한원소 집합 위의 자유 모노이드와 같으며, 자연수의 덧셈 모노이드 formula_133와 동형이다. 산술의 기본 정리에 따르면, 양의 정수 집합의 곱셈 모노이드 formula_142는 소수 집합 위의 자유 가환 모노이드와 표준적으로 동형이다.
크기가 1인 모노이드는 자명 모노이드 밖에 없다. 크기가 2인 모노이드는 다음 2개가 있으며, 둘 다 가환 모노이드이다.
크기가 3인 모노이드는 다음 7개가 있으며, 7개 가운데 5개는 가환 모노이드이다.
마지막 두 개의, 크기 3의 비가환 모노이드를 플립플롭 모노이드()라고 한다. 이는 크론-로즈 정리에 등장한다.
크기가 formula_159인 모노이드의 동형류의 수는 다음과 같다. (formula_160)
모노이드와 그 반대 모노이드를 동치로 간주할 때, 크기가 formula_159인 모노이드의 동치류의 수는 다음과 같다. (formula_160)
크기가 formula_159인 가환 모노이드의 동형류의 수는 다음과 같다. (formula_160)
주어진 차원의 콤팩트 매끄러운 다양체들의 미분 동형류들의 집합을 생각하자. 이 집합은 연결합을 통해 가환 모노이드를 이루며, 항등원은 해당 차원의 초구이다. 매끄러운 다양체 대신 (위상) 다양체를 사용하여도 가환 모노이드를 얻는다.
주어진 매끄러운 다양체 위의 실수 벡터 다발들의 동형류의 집합을 생각하자. 이는 직합을 통해, 또는 텐서곱을 통해 가환 모노이드를 이룬다.
알파벳 formula_165에 대한, 상태 집합이 formula_18인 유한 상태 기계 formula_167는 formula_165 위의 문자열 모노이드(자유 모노이드)에서 formula_18의 완전 변환 모노이드로 가는 모노이드 준동형
을 정의한다. 즉, 이는 formula_18 위에 작용하는 모노이드를 정의한다. 모노이드 이론, 특히 크론-로즈 정리 등을 사용하여 유한 상태 기계를 분석할 수 있다.