Моноїд

Моноїд — це алгебрична структура з бінарною операцією, що є асоціативною та має нейтральний елемент. Стисліше, моноїд — це напівгрупа з нейтральним елементом.

Кубічна ґратка алгебричних структур
від магми до групи.

Якщо для всіх елементів моноїда існує обернений елемент тоді це група.

Визначення

Моноїд — це множина ${\displaystyle S}$, разом із двомісною операцією “${\displaystyle \cdot }$”, яка задовольняє трьом наступним аксіомам:

Замкнутість

Для всіх ${\displaystyle a,b\in S}$, результат операції ${\displaystyle a\cdot b}$ також в ${\displaystyle S}$.

Асоціативність

Для всіх ${\displaystyle a,b,c\in S}$, виконується рівність ${\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}$.

Нейтральний елемент (одиниця)

Існує елемент ${\displaystyle e\in S}$ такий, що для всіх елементів ${\displaystyle a\in S}$, вірна рівність ${\displaystyle a\cdot e=e\cdot a=a}$.

І в математичному записі ми можемо записати це так

• Замкнутість: ${\displaystyle \forall a,b\in S\colon a\cdot b\in S}$,
• Асоціативність: ${\displaystyle \forall a,b,c\in S\colon (a\cdot b)\cdot c=a\cdot (b\cdot c)}$,
• Нейтральний елемент: ${\displaystyle \exists e\in S}$ такий, що ${\displaystyle \forall a\in S\colon e\cdot a=a\cdot e=a}$.

Символ двомісної операції часто опускається; наприклад, аксіоми моноїда вимагають ${\displaystyle \ (ab)c=a(bc)}$ і ${\displaystyle \ ea=ae=a}$. Двомісна операція традиційно називається множенням, але може реалізовуватися будь-якою.

Моноїдні структури

Підмоноїди

Підмоноїдом моноїда ${\displaystyle \left(M,\cdot \right)}$ є підмножина N із М, замкнута відносно моноїдної операції і така, що містить нейтральний елемент e із M. В символьному записі, N є підмоноїдом М, якщо ${\displaystyle N\subseteq M}$, ${\displaystyle x\cdot y\in N}$ якщо ${\displaystyle x,y\in N}$, і ${\displaystyle M\ni e\in N}$. В цьому випадку N є моноїдом за двомісною операцією, успадкованою від М.

З іншого боку, якщо N є підмножиною моноїду, замкнутою щодо моноїдної операції, та є моноїдом щодо цієї успадкованої операції, то N не завжди буде підмоноїдом, оскільки нейтральний елемент може бути іншим. Наприклад, синглетон {0} замкнутий щодо алгебраїчного множення, але він не є підмоноїдом (мультиплікативного) моноїду невід’ємних цілих чисел: тут нейтральним елементом буде 1.

Генератори

Підмножина S із М породжує М, якщо найменший підмоноїд М, що містить S, є самим М. Якщо моноїд М може бути породженим скінченною множиною, він називається скінченно породженим моноїдом.

Комутативний моноїд

Моноїд, операція якого комутативна, називається комутативним (або, рідше, за аналогією з групами, абелевим). Операцію комутативного моноїда часто позначають як додавання. Будь-який комутативний моноїд наділений алгебраїчним передпорядком ${\displaystyle \leq }$, визначеним так, що ${\displaystyle x\leq y}$, якщо існує z такий, що ${\displaystyle x+z=y}$. Порядковою одиницею комутативного моноїда М є такий елемент u із М, що для будь-якого елемента х із М у множині, породженій u, існує елемент v такий, що ${\displaystyle x\leq v}$. Це часто має місце, коли М є (додатним конусом) частково впорядкованої абелевої групи G, в цьому випадку u називають порядковою одиницею G.

Частково комутативний моноїд

Моноїд, операція якого є комутативною лише для деяких, але не для всіх елементів, називають слідовим моноїдом. Слідові моноїди часто зустрічаються в теорії паралельних обчислень.

Приклади

• З 16 можливих двомісних булевих операцій чотири, які мають двобічну ідентичність, є комутативними та асоціативними. Таким чином, будь-яка з них перетворює множину {False, True} на комутативний моноїд. Відповідно до стандартних визначень, AND та XNOR мають одиницею True, а XOR та OR мають одиницею False. Моноїди з AND чи OR також ідемпотентні, тоді як моноїди із XOR та XNOR — ні.
• Множина натуральних чисел ${\displaystyle \mathbb {N} =\{0,1,2,\ldots \}}$ є комутативним моноїдом щодо операції алгебраїчного додавання (нейтральний елемент 0) або щодо операції алгебраїчного множення (нейтральний елемент 1). Підмоноїд N щодо додавання називають числовим моноїдом.
• Множина цілих додатних чисел є комутативним моноїдом щодо алгебраїчного множення (нейтральний елемент 1).
• Якщо задано множину A, множина підмножин A є комутативним моноїдом щодо операції перетину (нейтральним елементом є сама множина A).
• Якщо задано множину A, множина підмножин A є комутативним моноїдом щодо операції об'єднання (нейтральним елементом є порожня множина).

Див. також

• Ґратка з діленням