9 群论

半群

二元运算

二元运算是指在两个元素之间定义的一种运算。设 $ S $ 是一个集合，如果对于 $ S $ 中的任意两个元素 $ a, b $，都能得到一个 $ c \in S $，使得 $ c = a \star b $（这里的 $ \star $ 是运算符），则称 $ \star $ 是在集合 $ S $ 上的一个二元运算。

半群（Semigroup）

半群是一个包含集合和二元运算的代数结构，满足以下条件：

封闭性：对于集合 $ S $ 中的任意 $ a, b $，运算 $ a \star b $ 仍然在 $ S $ 中。
结合律：对于任意 $ a, b, c \in S $，都有 $ (a \star b) \star c = a \star (b \star c) $。

如果一个集合 $ S $ 在某种运算下满足上述两个条件，则 $ (S, \star) $ 是一个半群。

自由半群（Free Semigroup）

自由半群是基于某个集合 $ A $ 生成的。设 $ A $ 是一个非空集合，则其自由半群 $ F(A) $ 是由 $ A $ 中元素的所有有限串（字符串）构成的集合，运算为字符串的连接。

例如，如果 $ A = {a, b} $，则 $ F(A) $ 包含 $ {a, b, aa, ab, ba, bb, aaa, aab, ...} $，并且运算为字符串的连接。

定理 1

如果 $a_1, a_2, \ldots, a_n, n \geq 3$ 是半群中的任意元素，那么通过任意插入有意义的括号形成的所有元素 $a_1, a_2, \ldots, a_n$ 的乘积都是相等的。

例如，$ ((a_1 * a_2) * a_3) * a_4, \quad a_1 * (a_2 * (a_3 * a_4)), \quad (a_1 * (a_2 * a_3)) * a_4$ 是相等的。

幺半群（Monoid）

单元半群（或称为单子）是一个特殊的半群，除了满足半群的所有条件外，还必须有单位元（identity element）。即存在一个元素 $ e \in M $，满足对于任意 $ a \in M $，都有 $ e \star a = a \star e = a $。

例如，自然数加法的集合 $ (\mathbb{N}, +) $ 是一个单元半群，单位元为 0。

子半群

子半群：如果 $(S, \star)$ 是一个半群，且 $T \subseteq S$，如果 $T$ 也是一个半群（即对于 $T$ 中任意 $a, b$，$a \star b \in T$），则称 $T$ 为 $S$ 的子半群。
子单元半群：如果 $(M, \star)$ 是一个单元半群，且 $T \subseteq M$，如果 $T$ 是一个单元半群，且包含 $M$ 的单位元，则称 $T$ 为 $M$ 的子单元半群。

同构（Isomorphism）

同构是描述两个代数结构之间一种特定关系的概念。若 $ (S_1, \star_1) $ 和 $ (S_2, \star_2) $ 是两个半群，如果存在一个双射 $ f: S_1 \to S_2 $，使得对于任意 $ a, b \in S_1 $ 都有： $$ f(a \star_1 b) = f(a) \star_2 f(b) $$ 则称 $ f $ 是一个同构，且 $ S_1 $ 和 $ S_2 $ 是同构的。

同构表明两个半群在结构上是相同的，虽然它们的元素和运算可能不同。

$f^{-1}$ 也是同构的（证明见 9-2 PPT 第 26 页）。

证明步骤

构造 $f$ 函数，$Dom(f) = S$
证明 $f$ 是单射
证明 $f$ 是满射
证明 $f(a \star^1 b) = f(a) \star^2 f(b)$

定理 2

设 $(S, *)$ 和 $(T, *')$ 为具有单位元 $e$ 和 $e'$ 的幺半群，分别。设 $f: S \rightarrow T$ 为一个同构。那么，$f(e) = e'$。

同态（Homomorphism）

同构是双射（bijective）；

同态是 $ S \rightarrow T$ 的满射，不是单射。

定理 3

和 定理 2 类似，对于同态同样适用。

定理 4

如果 $S'$ 是半群 $S$ 的一个子半群，那么 $S'$ 在同态映射 $f$ 下的像 $f(S')$ 也是半群 $T$ 的一个子半群。这个性质表明同态映射可以保持子半群的结构。

定理 5

如果 $f$ 是从交换半群 $(S, *)$ 到半群 $(T, *')$ 的一个满射同态，那么 $(T, *')$ 也是交换的。

积半群和商半群（Products and Quotients）

定理 1（积半群定义）

如果 $(S, *)$ 和 $(T, *')$ 是两个半群，那么它们的直积 $(S \times T, *'')$ 也是一个半群。其中 $\ast''$ 由 $(s_1, t_1) \ast'' (s_2,t_2)=(s_1 * s_2, t_1 *' t_2)$ 定义。

如果 $S$ 和 $T$ 不仅是半群，而且是幺半群，且分别有单位元 $e_S$ 和 $e_T$，那么 $S \times T$ 也是一个幺半群，其单位元为 $(e_S, e_T)$。

同余关系（Congruence Relation）

如果 $a R a'$ 且 $b R b'$，则 $(a * b) R (a' * b')$。

证明同余关系

先证明 R 是等价关系（自反性、对称性、传递性）
假设 $a R a'$ 且 $b R b'$，推出 $(a * b) R (a' * b')$

定理 2（商半群定义）

设 $R$ 是半群 $(S,*)$ 上的一个同余关系，考虑从 $S/R\times S/R$ 到 S/R 的关系 $\circledast$,它对于 S中的 $a$ 和 $b$,有序对 $([a],[b])$ 与 $[a*b]$ 有关。

$\circledast$ 是从 S/R×S/R 到 S/R 的一个函数，像通常一样用$[a]\circledast[b]$表示$\circledast([a],[b])$。因此，$[a]\circledast[b]{=}[a*b]$。
$\left(S/R,\circledast\right)$ 是一个半群。

$\Z_n$ 指的是表示 mod 4 的商集。

定理 3（自然同态）

Natural Homomorphism。

对于一个同余关系 $R$，对应的商半群 $(S/R), \circledast$ 那么由 $f_R(a)=[a]$ 定义的函数 $f_R:S \rightarrow S/R$ 是同态且是满射，称为自然同态。

定理 4（同态基本定理）

《离散数学结构》P371

有一个同态 $f:S \rightarrow T$，两个半群 $(S, *')$ 和 $(T,*'')$，定义 S 上关系的关系 R，$a R b$ 当且仅当 $f(a)=f(b)$，则：

R 是同余关系。
$(T,*'')$ 和商半群 $(S/R,\circledast)$ 同构。

群

群 $(G, *)$ 包含以下性质：

封闭性：$a * b \in G$
结合律：$(a*b)*c=a*(b*c)$。
单位元：存在唯一元素 e，使得对于任意 a 有 $a*e=e*a$ = a。
逆元：对于每个 a，存在 $a'\in G$，使得 $a *a'=a'*a=e$。

阿贝尔群（Abel）

对于群里所有 a、b 有 ab = ba，则称为阿贝尔群。也叫交换群。

定理 1（逆元唯一）

G 中的每个元素 a 在 G 中仅有一个逆元。

定理 2（左右消去）

ab = ac，推出 b = c（左消去）
ba = ca，推出 b = c（右消去）

群的阶（Order）

用 $|G|$ 表示 G 中元素个数。

n 次对称群（Symmetrics）

所有 n 个元素的排列集合，在复合运算下形成一个阶为 $n!$ 的群。这个群被称为 n 次对称群。

子群

H 是 G 的子群：

G 的单位元 e 属于 H
如果 a、b 属于 H，那么 ab 属于 H
a 属于 H，那么 $a^{-1}$ 属于 H

平凡子群（Trivial Subg）

G 有两种平凡子群：

只包含单位元的子群 {e}
G 自己本身

克莱因 4 元群（Klein 4）

记为 V 或者 $K_4$，是阿贝尔群。含有 e（单位元）、a、b、c。

运算规则：

e 乘以其它元素还得其他元素。
$a \times b = c$、$a \times c =b$ 以此类推。

循环群（Cyclic）

一个循环群 G，如果存在一个 $a \in G$，使得 G 中任意元素 g 都可以用 a 的幂形式表示，即 $g=a^n$，那么 a 称为循环群 G 的生成元（Generator）。

左右陪集（Coset）

H 是 G 的子群，a 关于 H 的陪集：

左陪集：$aH = \{ah ~|~ h \in H \}$
右陪集：$Ha = \{ha~|~ h\in H \}$

正规子群（Normal）

H 是 G 的正规子群，如果 $aH =Ha$，对于所有 $a\in G$。