9.2 Semigroups 半群、同态、同构

Semigroups

• Defination

非空集合
结合性（自然满足封闭性）
如果可交换，则为Abel半群

• 自由半群

操作符 · 是指连接运算，显然其具有结合律。
称 $(A^∗, · )$ 为由 A 生成的自由半群 (free semigroup generated by A)。

• Identity 单位元，幺元

单位元若存在必唯一。
Prove:
假设$e, e’$都是单位元，由单位元性质可得$e = e * e’ = e’$。

• Monoid——独异点，幺半群

半群 $(S, *)$ 中存在单位元，则称为独异点。

• 定理 1 半群的卡特兰律（广义结合律）

如果 $a_1,\ a_2,\ …,\ a_n$ 是半群的任意元素（其中 $n ≥ 3$），那么在任意元素的乘积中插入有意义的括号形成的乘积是相等的。
翻译成人话就是，任意加括号都成立
引理1:$(x_1……x_n) * (y_1……y_n) = x_1……x_ny_1……y_n$成立
Prove:（数学归纳法）
取定$n \in N$,对$n$做数学归纳：
1）若$m = 1$
$(x_1……x_n)y_1 = x_1……x_ny_1$
2）由$m \rightarrow m + 1$$$\begin{align}
(x_1……x_n) * (y_1……y_{m+1})\
&= (x_1……x_n) * ((y_1……y_m) * y_{m + 1})\
&= ((x_1……x_n) * (y_1……y_{m})) * y_{m + 1}\
&= (x_1……x_ny_1……y_{m+1}) * y_{m + 1}\
&= x_1……x_ny_1……y_{m+1}
\end{align}$$至于为什么要说这个，就是这个才保证了下面的定义。

• Powers of A 幂

Defination: $x^n = x^{n - 1} * x = x * x * …… *x$，规定$x^0 = e$。
显然，不规定也行，$x^m * x^n = x^{m+n}, \forall m,n \ge 1$是显然的，如果我们希望更完备呢？
$x^m * x^0 = x^m$如果成立，那么$x^0$不就等于单位元吗？
有了这个规定自然又得到了以下性质。

• 生成半群/生成子幺半群

Defination: 设$(S, *)$是幺半群，而$A \subset S$，则$A$生成的子幺半群记作$< A > = \cap T,T \supset A, T < S$
人话，$< A >$是所有$S$中包含了$A$的子幺半群的交集。
子半群和子幺半群可以按照如下方式生成。

Subsemigroup

• Defination

子集
运算封闭（一定满足结合性）

• Submonoid——子独异点

子集
运算封闭
幺元属于T
Note! T的幺元必须和S的幺元相同
T 是 S 的子集，并且 $(T, *)$ 同样满足独异点定义，同时 $e∈T$；
显然，半群$(S, *)$ 本身也是$S$的子半群；独异点$(S, *)$ 本身也是$S$的子独异点；
$T = {e}$一定是群$(S, *)$ 的子独异点。

Homomorphism 同态

Defination: 人话，保持运算，保持特殊元素。
如果$S$和$T$的满足幺半群同态关系，$$
f:(S, ·) \rightarrow (T, *)\leftrightarrow \left{
\begin{aligned}
&保持乘法，即\forall x,y \in S, f(x · y) = f(x) * f(y)\
&保持单位元，即f(e) = e’
\end{aligned}
\right.$$直观理解如下图：人话，两个元素作运算能映射到另一个集合，另一个集合中的元素作运算也能映射回原集合

Isomorphism 同构

Defination: 人话，双射，保持运算，保持特殊元素。
直观理解如下图：
&0 如果$S$和$T$的满足幺半群同构关系，$$
f:(S, ·) \rightarrow (T, )\leftrightarrow \left{
\begin{aligned}
&满足双射，即\forall x,y \in S,x \leftrightarrow f(x),y \leftrightarrow f(y), x · y \leftrightarrow f(x) * f(y)\
&保持乘法，即\forall x,y \in S, f(x * y) = f(x) · f(y)\
&保持单位元，即f(e) = e’
\end{aligned}
\right.$$&1 恒等映射*，即$S$是自己的同构。
&2 如果 $f$ 是从 $S\rightarrow T$ 的同构，即 $f$ 是从 $S\rightarrow T$ 的一一对应的函数，那么 $f^{−1}$ 必定存在，并且 $f^{−1}$ 是从 $S\rightarrow T$ 的一一对应的函数, 且一定是同构。
&3 显然，如果$(S,∗)$有独异点，但$(T,∗)$没有独异点，那么必定不存在从 $S\rightarrow T$ 的同构 (常用于证明不存在同构)
$4 显然，同态和同构均满足像点的乘积等于乘积的像点，区别是，同构需要一一对应。

满同态

定理1 如果$S$和$T$是幺半群，且幺元分别为$e,e’$，$S\rightarrow T$为满同态映射，那么有$f(e) = e’$。
Prove: 由同态定义，$\forall a \in S,f(e · a) = f(a) * f(e) = f(a)$，但是首先需要保证$f(a) \in T$，即满射，才能成立，此时$f(e) = e’$。
定理2 如果$S$和$T$是幺半群，且$S$为可交换半群，$S\rightarrow T$为满同态映射，那么$T$也是可交换半群。

解题法

• Example: $(S, *)$是幺半群吗？

Prove Step:

1. 有没有封闭性？
2. 结合律？
3. 有没有单位元？

• Example: 构造同构/证明是否为同构？

Prove Step:

1. (构造或直接给出)构造一个函数 $f: S\rightarrow T$ , 使得 $f$ 的定义域 $Dom (f) = S$;
2. 证明 $f$ 是单射 (one-to-one)的，可用反证法
3. 证明 $f$ 是满射 (onto)的 $\rightarrow$ 故而是双射的
4. 证明 $f(a · b)=f(a)∗f(b)$
   同态无需证明$Step2,Step3$