教材: 抽象代数基础-丘维声, 抽象代数学-姚慕生
半群
半群的定义(Semigroup)
若运算封闭, 满足结合律, 则称[S,*]是一个半群
- 运算封闭: \forall a,b\in S, a*b\in S
- 结合律: \forall a,b,c\in S, (a*b)*c=a*(b*c)
递归地定义x_1x_2\cdots x_n=(x_1x_2\cdots x_{n-1})(x_n)
其中规定x^n=\underbrace{x\cdots x}_{n\text{个}}(n\ge1)
半群满足广义结合律, 可以任意添加括号
\forall n,m\in \mathbb{N^+},x_1\cdots x_n\cdot y_1\cdots y_m=(x_1\cdots x_n)(y_1\cdots y_m)
通过对m进行归纳来证明:
当m=1时, 由定义知x_1\cdots x_ny_1=(x_1\cdots x_n)(y_1)
现假设当m=k时结论成立, 则当m=k+1时
x_1\cdots x_n\cdot y_1\cdots y_k\cdot y_{k+1} \\
=(x_1\cdots x_n\cdot y_1\cdots y_k)\cdot y_{k+1} \\
=[(x_1\cdots x_n)(y_1\cdots y_k)]\cdot y_{k+1} \\
=(x_1\cdots x_n)[(y_1\cdots y_k)\cdot (y_{k+1})] \\
=(x_1\cdots x_n)(y_1\cdots y_k\cdot y_{k+1})
[半群且非幺半群]
示例1: 正偶数加法半群: \{2,4,6,\cdots\}
示例2: 二元左零半群: 运算结果始终是左元素
- 满足结合律: (a*b)*c=a\land a*(b*c)=a
- 没有单位元: x*e=x\neq e
幺半群
幺半群的定义(Monoid)
若运算封闭, 满足结合律, 存在单位元, 则称[S,*]是一个幺半群
- 运算封闭: \forall a,b\in S, a*b\in S
- 结合律: \forall a,b,c\in S, (a*b)*c=a*(b*c)
- 单位元: \exists e\in S, \forall a\in S, a*e=e*a=a
单位元唯一: e_1=e_1e_2=e_2
定义零指数: x^0=e
[幺半群且非群]
示例1: n阶方阵的乘法幺半群
示例2: 自然数加法幺半群: \{0,1,2,3,\cdots\}
示例3: 整数乘法幺半群: \{\cdots,-1,0,1,\cdots\}
示例4: 集合到自身的所有映射关于复合运算的幺半群 \{f|\ f:\Omega\to\Omega\}
子幺半群的定义(Submonoid)
已知幺半群[S,*], 且T\subseteq S
若运算封闭,单位元保持, 则称[T,*]是一个子幺半群
- 运算封闭: \forall a,b\in T, a*b\in T
- 单位元: e_S\in T
[所有包含A的子幺半群的交]
生成子幺半群的定义一: \langle A\rangle=\bigcap\{T|A\subseteq T\land T是子幺半群\}
- 运算封闭: \forall a,b\in \langle A\rangle\implies a,b\in\forall T_i\implies a*b\in\forall T_i\implies a*b\in \langle A\rangle
- 结合律: \forall a,b,c\in \langle A\rangle\implies a,b,c\in\forall T_i\implies (a*b)*c=a*(b*c)
- 单位元: e_S\in\forall T_i\implies e_S\in\langle A\rangle
[将A中元素进行有限次自然数幂的乘积]
生成子幺半群的定义二: \langle A\rangle=\{x_1^{m_1}x_2^{m_2}\cdots x_k^{m_k}|x_i\in A,m_i\in\mathbb{N},k\in\mathbb{N^+}\}
- 运算封闭: \forall a,b\in \langle A\rangle\implies ab=x_1^{m_1}x_2^{m_2}\cdots x_s^{m_s}y_1^{n_1}y_2^{n_2}\cdots y_t^{n_t}\in \langle A\rangle
- 结合律: \forall a,b,c\in \langle A\rangle\implies (ab)c=a(bc)
- 单位元: e=x^0\in \langle A\rangle
[定义等价性证明]
定义一: \langle A\rangle_1=\bigcap\{T|A\subseteq T\land T是子幺半群\}
定义二: \langle A\rangle_2=\{x_1^{m_1}x_2^{m_2}\cdots x_k^{m_k}|x_i\in A,m_i\in\mathbb{N},k\in\mathbb{N^+}\}
- \langle A\rangle_1\subseteq\langle A\rangle_2: 因为\langle A\rangle_2是包含A的子幺半群, 所以\langle A\rangle_1\subseteq\langle A\rangle_2
- \langle A\rangle_2\subseteq\langle A\rangle_1: 由运算封闭性可知, 对于任意包含A的子幺半群H
都有 x_1^{m_1}x_2^{m_2}\cdots x_k^{m_k}\in H\implies \langle A\rangle_2\subseteq\langle A\rangle_1
幺半群同态的定义(Monoid Homomorphism)
已知幺半群间的映射 f:[S,\cdot]\to[T,*]
若保持运算, 且保持单位元, 则称其为幺半群同态
如果还满足双射, 那么可称其为幺半群同构
- 运算保持: \forall a,b\in S, f(a\cdot b)=f(a)*f(b)
- 单位元保持: f(e_S)=e_T