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