离散数学笔记（8）——群论

wzf2000
2019年11月8日

代数结构（代数系统）

代数系统的概念

可消去性

设 $\star$ 是 $X$ 上的二元运算， $a \in X$ ，如果对任何 $x,y \in X$ ，有：
$a \star x = a \star y$
或者：
$x \star a = y \star a$
则必有 $x = y$ ，则称 $a$ 在 $X$ 上可消去。

可消去判定法：如果 $X$ 上存在单位元 $e$ ，且 $a$ 存在逆元 $a^{-1}$ ，则 $a$ 在 $X$ 上可消去。

（证明略）

分配律

设 $\star$ 和 $\circ$ 都是 $X$ 上的二元运算，若对任何 $x,y,z \in X$ ，有：
$x \star (y \circ z) = (x \star y) \circ (x \star z) \\ (x \circ y) \star z = (x \star z) \circ (y \star z)$
则称 $\star$ 对 $\circ$ 可分配。

吸收律

设 $\star$ 和 $\circ$ 都是 $X$ 上的二元运算，若对任何 $x,y \in X$ ，有：
$x \star (x \circ y) = x \\ x \circ (x \star y) = x$
则 $\star$ 和 $\circ$ 满足吸收律。

半群和独异点（幺群）

半群

$S$ 是个非空集合， $\star$ 是 $S$ 上的二元运算，如果：

运算 $\star$ 是封闭的；
运算 $\star$ 在 $S$ 上满足结合律；

则称 $\langle S,\star \rangle$ 是半群。

可交换的半群称为交换半群。

如果 $\star$ 在半群某子集上封闭，则称该子集为子半群。

定理：设 $\langle S,\star \rangle$ 是半群，如果 $S$ 是有限集合，则必存在 $a \in S$ ，使得 $a \star a = a$ 。

独异点（幺群）

设 $\langle M,\star \rangle$ 是个半群，如果对 $\star$ 有单位元，则称 $\langle M,\star \rangle$ 是个独异点，也称它是幺群。

定理：设 $\langle S,\star,e \rangle$ 是独异点，且 $S$ 有限，则在关于 $\star$ 的运算表中，任何两行或两列都不相同。

群

群的定义

设 $\langle G,\star \rangle$ 是个代数系统，如果 $\star$ 满足封闭性、可结合、有单位元且每个元素可逆，则称它是个群。

有限群：令 $\langle G,\star \rangle$ 是群， $G$ 是有限集，则称它是有限群。

群的性质

群满足可消去性：由前述可消去判定法（定理 1）可知。
群方程可解性：
定理 2：设 $\langle G,\star \rangle$ 是个群，则对任何 $a,b \in G$ ：
1. 存在唯一元素 $x \in G$ ，使得 $a \star x = b$ ；
2. 存在唯一元素 $y \in G$ ，使得 $y \star a = b$ 。
群中无零元：
定理 3：设 $\langle G,\star,e \rangle$ 是个群，如果 $|G| \ge 2$ ，则 $G$ 中无零元。
群中除单位元外，无其他等幂元：
定理 4：设 $\langle G,\star,e \rangle$ 是个群， $G$ 中除单位元外，无其他等幂元。
定理 5：设 $\langle G,\star,e \rangle$ 是个群，对任何 $a,b \in G$ ，有：
1. $(a^{-1})^{-1} = a$
2. $(a \star b)^{-1} = b^{-1} \star a^{-1}$
推论：设 $\langle G,\star,e \rangle$ 是个群，对任何 $a \in G$ ，有 $(a^n)^{-1} = (a^{-1})^n$ 。此外， $a^0 = e$ 。
有限群的运算表的特征：
定理 6：设 $\langle G,\star,e \rangle$ 是个有限群，则 $G$ 中每个元素在 $\star$ 运算表中的每一行（列）必出线且仅出现一次。

子群

设 $\langle G,\cdot \rangle$ 是群， $S$ 是 $G$ 的非空子集，如果 $\langle S,\cdot \rangle$ 满足：

任何 $a,b \in S$ ， $a \cdot b \in S$ ；（封闭）
单位元 $e \in S$ ；（有单位元）
任何 $a \in S$ ， $a^{-1} \in S$ 。（可逆）

则称 $\langle S,\cdot \rangle$ 是 $\langle G,\cdot \rangle$ 的子群，记 $S \le G$ 。

平凡子群与真子群

设 $\langle G,\cdot \rangle$ 是群， $\langle \{e\},\cdot \rangle$ 和 $\langle G,\cdot \rangle$ 也是 $\langle G,\cdot \rangle$ 的子群，称之为 $\langle G,\cdot \rangle$ 的平凡子群。其余真子集构成的子群称之为真子群，记 $S < G$ 。

证明子群方法

用子群的定义。
定理：设 $\langle G,\cdot \rangle$ 是群， $S$ 是 $G$ 的非空子集，如果 $\langle S,\cdot \rangle$ 满足：
1. 任何 $a,b \in S$ ，有 $a \cdot b \in S$ ；（封闭）
2. 任何 $a \in S$ ， $a^{-1} \in S$ 。（可逆）
则 $\langle S,\cdot \rangle$ 是 $\langle G,\cdot \rangle$ 的子群。
定理：设 $\langle G,\cdot \rangle$ 是群， $B$ 是 $G$ 的有限子集，如果 $\cdot$ 在 $B$ 上满足封闭性，则 $\langle B,\cdot \rangle$ 是 $\langle G,\cdot \rangle$ 的子群。
设 $\langle G,\cdot \rangle$ 是群， $S$ 是 $G$ 的非空子集，如果任何 $a,b \in S$ ，有 $a \cdot b^{-1} \in S$ ，则 $\langle S,\cdot \rangle$ 是 $\langle G,\cdot \rangle$ 的子群。

例题

群的阶

设 $\langle G,\cdot \rangle$ 是群，如果 $|G| = n$ ，则称 $\langle G,\cdot \rangle$ 是 $n$ 阶群，如果 $|G|$ 是无限的，则称 $\langle G,\cdot \rangle$ 是无限阶群。

所有的一、二、三阶群都同构。

群中元素的阶

设 $\langle G,\cdot \rangle$ 是群， $a \in G$ ，使得 $a^n = e$ 的最小的正整数 $n$ ，称为 $a$ 的阶或周期，记为 $O(a) = n$ 。若没有这样的正整数存在，则称 $a$ 的阶是无限的，并记 $O(a) = \infty$ 。

定理： $\langle G,\cdot \rangle$ 是群， $a \in G$ ，如果 $O(a) = n$ ，则 $a^k = e$ 当且仅当 $k = mn(m \in \mathbb{I})$ 。（ $\mathbb{I}$ 表示整数集）

定理：有限群中，每个元素的阶是有限的。

定理： $O(a) = O(a^{-1})$ 。

特殊群

交换群（阿贝尔群、Abel 群）

设 $\langle G,\cdot \rangle$ 是群，运算 $\cdot$ 是可交换的，则称它是交换群。

定理： $\langle G,\cdot \rangle$ 是交换群，当且仅当对任何 $a,b \in G$ ，有 $(ab)(ab) = (aa)(bb)$ ，即 $(ab)^2=a^2b^2$ 。

定理：设 $\langle G,\cdot,e \rangle$ 是群，若除单位元外其他元素都是 $2$ 阶元，则 $G$ 是 Abel 群。

循环群

设 $\langle G,\cdot \rangle$ 是群，如果存在一个元素 $g \in G$ ，使得对每个 $x \in G$ ，都存在整数 $i$ ，有 $x = g^i$ ，则称 $\langle G,\cdot \rangle$ 是个循环群，并称 $g$ 是 $G$ 的生成元。即 $G = \{g^i|i \in \mathbb{I}\} = \langle g \rangle$ ，其中 $g^0 = e,g^{-i} = (g^{-1})^i$ 。

结论：生成元不唯一。（注，若群的元素个数至少为 $2$ ，则单位元不会是生成元）

定理 1：任何循环群都是 Abel 群。

定理 2：设 $\langle G,\cdot \rangle = \langle g \rangle$ ， $|G| = n$ ，则 $O(g) = n$ ，且 $G = \{g^1,g^2,\cdots,g^n = e\}$ 。

离散数学笔记（8）——群论