半群(semigroups), 幺半群(monoids)和群(groups)

  \(G\) 是非空集合, \(G\) 上的二元运算是映射 \(G\times G\to G\).

  设 \(R\) 是 \(A\) 上的一个二元关系, 如果满足

  1. 自反性, \(aRa\ (\forall a\in A)\)
  2. 对称性, \(a_1Ra_2\) 蕴含 \(a_2Ra_1\ (\forall a_1,a_2\in A)\)
  3. 传递性, 即 \(a_1Ra_2\) 且 \(a_2Ra_3\) 蕴含 \(a_1Ra_3\ (\forall a_1,a_2,a_3\in A)\)

则称 \(R\) 为 \(A\) 上的一个等价关系, \(A\) 中互相等价的元素组成的子集称为一个等价类. 任意两个不同等价类的交为空集, 集合 \(A\) 等于所有等价类的无交并. 等价关系用 \(\sim\) 表示, \(A\) 中所有等价类组成的集合记为 \(A/\sim\).

Definition 一个 半群 是一个非空集合 \(G\) 和一个 \(G\) 上的二元运算满足

  (i) 结合律: \(a(bc)=(ab)c\quad\forall\ a,b,c\in G\);

一个 幺半群 是一个半群 \(G\) 包含

  (ii) (双边的) 幺元 \(e\in G\) 满足 \(ae=ea=a\quad\forall a\in G\).

一个 群 是一个幺半群 \(G\) 满足

  (iii) 对于任意 \(a\in G\) 存在一个 (双边的) 逆元 \(a^{-1}\in G\) 满足 \(a^{-1}a=aa^{-1}=e\).

A semigroup \(G\) is said to be abelian or commutative if its binary operation is

  (iv) 交换律: \(ab=ba\quad\forall a,b\in G\).

  The order(阶) of a group \(G\) is the cardinal number(基数) \(|G|\). \(G\) is said to be finite[resp. infinite] if \(|G|\) is finite(\(|G|\lt\infty\))[resp. infinite].

只含单位元的群称为平凡群.


Theorem If \(G\) is a monoid, then the identity element e is unique. If \(G\) is a group, then

  (i) \(c\in G\) and \(cc=c\Rightarrow c=e\);

  (ii) for all \(a,b,c\in G\), \(ab=ac\Rightarrow b=c\) and \(ba=ca\Rightarrow b=c\)(left and right cancellation);

  (iii) for each \(a\in G\), 逆元 \(a^{-1}\) 唯一;

  (iv) for each \(a\in G\), \((a^{-1})^{-1}=a\);

  (v) for \(a,b\in G\), \((ab)^{-1}=b^{-1}a^{-1}\);

  (vi) for \(a,b\in G\), the equations \(ax=b\) and \(ya=b\) have unque solutions in \(G:x=a^{-1}b\) and \(y=ba^{-1}\).

  SKETCH OF PROOF. If \(e^{'}\) is also a two-sided identity, then \(e=ee^{'}=e^{'}.\) (i) \(cc=c\Rightarrow c^{-1}(cc)=c^{-1}c\Rightarrow (c^{-1}c)c=c^{-1}c\Rightarrow ec=e\Rightarrow c=e;\) (ii), (iii) and (vi) are proved similarly. (v) \((ab)(b^{-1}a^{-1})=a(bb^{-1})a^{-1}=(ae)a^{-1}=aa^{-1}=e\Rightarrow(ab)^{-1}=b^{-1}a^{-1}\) by (iii); (iv) is proved similarly.


Proposition Let \(G\) be a semigroup. Then \(G\) is a group if and only if the following conditions hold:

  (i) there exists an element \(e\in G\) such that \(ea=a\) for all \(a\in G\) (left identity element(左单位元)) ;

  (ii) for each \(a\in G\), there exists an element \(a^{-1}\in G\) such that \(a^{-1}a=e\) (left inverse(左逆)).


Proposition Let \(G\) be a semigroup. Then \(G\) is a group if and only if for all \(a,b\in G\) the equations \(ax=b\) and \(ya=b\) have solutions in \(G\).

  Let \(G\) and \(H\) be groups with identities \(e_G,e_H\) respectively, and define the direct product(直积) of \(G\) and \(H\) to be the group whose underlying set is \(G\times H\) and whose binary operation is given by:

\[(a,b)(a^{'}b^{'})=(aa^{'},bb^{'}),\quad where\quad a,a^{'}\in G;b,b^{'}\in H.\]

Theorem Let \(R(\sim\)) be an equivalence relation on a monoid \(G\) such that \(a_1\sim a_2\) and \(b_1\sim b_2\) imply \(a_1b_1\sim a_2b_2\) for all \(a_i,b_i\in G\). Then the set \(G/R\) of all equivalence classes of \(G\) under \(R\) is a monoid under the binary operation defined by \((\overline{a})(\overline{b})=\overline{ab}\), where \(\overline{x}\) denotes the equivalence class of \(x\in G\). If \(G\) is an [abelian] group, then so is \(G/R\).

Theorem (Generalized Associative Law) lf \(G\) is a semigroup and \(a_1,\cdots,a_n\in G\), then any two meaningful products of \(a_1,\cdots,a_n\) in this order are equal.

Corollary (Generalized Commutative Law) If \(G\) is a commutative semigroup and \(a_1,\cdots,a_n\in G\), then for any permutation \(i_1,\cdots,i_n\) of \(1,2,\cdots,n\), \(a_1a_2\cdots a_n=a_{i_1}a_{i_2}\cdots a_{i_n}\).

Definition Let \(G\) be a semigroup, \(a\in G\) and \(n\in N^*\). The element \(a^n\in G\) is defined to be the standard n product \(\displaystyle\prod_{i=1}^na_i\) with \(a_i = a\) for \(1<i<n\). If \(G\) is a monoid, \(a^0\) is defined to be the identity element \(e\). lf \(G\) is a group, then for each \(n\in N^*\), \(a^{-n}\) is defined to be \((a^{-1})^n\in G\).

例子

\(\mathbb{Z}_n:=\mathbb{Z}/n\mathbb{Z}=\{\bar{0},\bar{1},\cdots,\overline{n-1}\}\)

  • 全体 \(n\) 阶可逆复方阵形成乘法群, 叫做复数上的 \(n\) 次一般线性群, 表示成 \(GL(n,\mathbb{C})\), 一个子群特殊线性群 \(SL(n,\mathbb{C})\) 表示行列式为 1 的 \(n\) 阶复方阵全体.
  • \(n\) 为正整数, \(\bar{a}\) 为整数 \(a\) 的模 \(n\) 同余类, 则集合

\[\mathbb{Z}_n^*=\{\bar{a}|(a,n)=1\}\]

对于乘法形成阿贝尔群. 这个群有 \(\varphi(n)\) 个元素.

同态(homomorphisms), 子群(subgroups)

Definition Let \(G\) and \(H\) be semigroups. A function \(f:G\to H\) is a homomorphism provided \[f(ab) = f(a)f(b)\quad for\ all\ a,b\in G.\] If \(f\) is injective as a map of sets(单射), \(f\) is said to be a monomorphism(单同态). If \(f\) is surjectice(满射), \(f\) is called an epimorphism(满同态). If \(f\) is bijective(双射), \(f\) is called an isomorphism(同构). In this case \(G\) and \(H\) are said to be isomorphic (written \(G\cong H\)). A homomorphism \(f:G\to G\) is called an endomorphism of \(G\) and an isomorphism \(f : G\to G\) is called an automorphism of \(G\).

\(\mathrm{Aut}(G)\) 表示群 \(G\) 的自同构全体.

Definition Let \(f : G\to H\) be a homomorphism of groups. The kernel(核) of \(f\) (denoted \(\mathrm{Ker}\ f\)) is \(\{a\in G | f(a) = e \in H\}\). If \(A\) is a subset of \(G\), then \(f(A) = \{b\in H | b = f(a)\ for\ some\ a\in A\}\) is the image(象) of \(A\). \(f(G)\) is called the image of \(f\) and denoted \(\mathrm{Im}\ f\). If \(B\) is a subset of \(H\), \(f^{-1}(B) = \{a\in G | f(a)\in B\}\) is the inverse image of B.

Definition 设 \(H\) 为群 \(G\) 的非空子集. 如果 \(H\) 在 \(G\) 的运算下构成群, 则称 \(H\) 为 \(G\) 的子群, 记做 \(H\leqslant G\). 此外, 若 \(H\neq G\), 则称 \(H\) 为 \(G\) 的真子群, 表示成 \(H\lt G\).

Definition 设 \(G\) 是一个群, \(C=\{c\in G|gc=cg\ \forall g\in G\}\), 即 \(C\) 中元素与 \(G\) 中任意一个元素的乘法可交换, 称 \(C\) 是 \(G\) 的中心.

群的中心必是子群.

循环群(cyclic groups)

Definition 设 \(G\) 为一个群，如果存在 \(a\), 使得 \(G\) 可以表示为 \(G=\{a^n|n\in\mathbb{Z}\}\), \(G\) 被称为循环群.

陪集(cosets) 和计数(counting)

\(a\equiv b\pmod m\) if and only if \(m\mid a-b\), that is, if and only if \(a-b\) is an element of the subgroup \(<m>=\{mk|k\in\mathbb{Z}\}\). More generally, we have

Lemma 设 \(G\) 是群, \(H\leqslant G\), 定义 \(G\) 上的关系为: 对于 \(g,h\in G,g\sim h\Leftrightarrow gh^{-1}\in H\), 则 \(\sim\) 是 \(G\) 上的等价关系, 并且元素 \(g\) 对此等价关系的等价类是 \(Hg\).

  由引理知, 群 \(G\) 可以分拆形如 \(Hg\) 的一些集合, 每个等价类 \(Hg\) 叫做 \(G\) 对于子群 \(H\) 的右陪集. 如果 \(R=\{g_i|i\in I\}\) 是 \(G\) 对于上述等价元素的完全代表元素, 则它通常叫做 \(G\) 对 \(H\) 的右陪集代表元素, 有分拆

\[G=\bigcup_{g\in R}Hg\]

Definition 设 \(H\leqslant G, a\in G\), 形如 \(aH(Ha)\) 的子集为 \(H\) 的一个左(右)陪集.

Definition Let \(H\) be a subgroup of a group \(G\). The index of \(H\) in \(G\), denoted \([G: H]\), is the cardinal number of the set of distinct right [resp. left] cosets of \(H\) in \(G\).

Theorem 设 \(H\leqslant G\), 有

  1. \(a\in Hb\Leftrightarrow ab^{-1}\in H\Leftrightarrow Ha=Hb\ (\forall a,b\in G)\)

  2. \(|Ha|=|H|=|aH|\ (\forall a\in G)\)

  3. If \(\mathcal{R}\) is the set of distinct right cosets of \(H\) in \(G\) and \(\mathcal{L}\) is the set of distinct left cosets of \(H\) in \(G\), then \(|\mathcal{R}|=|\mathcal{L}|\)

Theorem \(K,H,G\) are groups with \(K < H < G\), then \([G : K] = [G : H][H : K]\). If any two of these indices are finite, then so is the third.

   PROOF. \(G=\bigcup\limits_{i\in I}Ha_i, H=\bigcup\limits_{j\in J}Kb_j\ (a_i\in G,b_j\in H), |I|=[G: H],|J|=[H: K]\). we must have \([G:K]=|I\times J|=|I||J|\)

Corollary(Lagrange) If \(H\) is a subgroup of a group \(G\), then \(|G| = [G: H]|H|\). In particular if \(G\) is finite, the order \(|a|\) of \(a\in G\) divides \(|G|\).

由拉格朗日定理我们知道, \(1\) 个 \(6\) 阶群中只能有 \(1,2,3,6\) 阶群, 素数阶群只能有平凡子群.

正规子群(normal subgroups), 商群(quotient groups), 和同态定理(homomorphisms)

Definition 群 \(G\) 的子群 \(N\) 叫做 \(G\) 的正规子群, 是指对每个 \(g\in G\), \(g^{-1}Ng=N\). 如果 \(N\) 是 \(G\) 的正规子群, 则表示成 \(N\lhd G\).

Lemma 设 \(N\leqslant G\), 则下列条件等价

  1. \(N\lhd G\)

  2. 对每个 \(g\in G\), \(gN=Ng\)

  3. \(N_G(N)=G\)

  4. \(G\) 对 \(N\) 的每个左陪集均是右陪集

Theorem(同态基本定理) 设 \(f:G\to G^\prime\) 是群的同态. 则 \(\mathrm{Im}f=f(G)\) 是 \(G^\prime\) 的子群, \(\mathrm{Ker}f=f^{-1}(1)=\{g\in G|f(g)=1\}\) 是 \(G\) 的正规子群, 并且有群同构

\[\bar{f}: G/\mathrm{Ker}f\cong\mathrm{Im}f\]

置换群

  集合 \(\Sigma\) 到自身上的每一个一一对应 \(\sigma\) 叫做 \(\Sigma\) 上的一个置换. 如果 \(\Sigma=\{a_1,\cdots,a_n\}\) 是有限集, 置换可表示成

\[\sigma= \begin{pmatrix} a_1&a_2&\cdots&a_n\\ \sigma(a_1)&\sigma(a_2)&\cdots&\sigma(a_n)\end{pmatrix}\]

  若 \(\sigma\) 和 \(\tau\) 是 \(\Sigma\) 上的两个置换, 则置换 \(\sigma\tau\) 定义为

\[(\sigma\tau)(a_i)=\sigma(\tau(a_i))\quad(1\le i\le n)\]

  例如

\[\begin{pmatrix}a_1&a_2&a_3&a_4\\a_1&a_3&a_4&a_2\end{pmatrix} \begin{pmatrix}a_1&a_2&a_3&a_4\\a_4&a_3&a_2&a_1\end{pmatrix}= \begin{pmatrix}a_1&a_2&a_3&a_4\\a_2&a_4&a_3&a_1\end{pmatrix}\]

以 \(S(\Sigma)\) 表示 \(\Sigma\) 上全部置换构成的集合, 这是一个 \(n!\) 元群, \(n=|\Sigma|\), 幺元素是恒等置换

\[1_{\Sigma}=\begin{pmatrix}a_1&a_2&a_3&a_4\\a_1&a_2&a_3&a_4\end{pmatrix}\]

\(S(\Sigma)\) 称为集合 \(\Sigma\) 上的对称群, 它的每个子群均叫做集合 \(\Sigma\) 上的置换群.

任意 \(n\) 元置换都可以表示成不交的轮换之积, 例如

\[\sigma=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 5&3&6&4&2&1&8&7 \end{pmatrix}\]

可表示为 \(\sigma=\begin{pmatrix}1&5&2&3&6\end{pmatrix}\begin{pmatrix}4\end{pmatrix}\begin{pmatrix}7&8\end{pmatrix}\)

群在集合上的作用

  设 \(\Sigma\) 是一个集合, \(S(\Sigma)\) 是 \(\Sigma\) 上的对称群, 群 \(G\) 到 \(S(\Sigma)\) 的每个同态 \(f:G\to S(\Sigma)\) 都叫做群 \(G\) 在集合 \(\Sigma\) 上的一个置换表示. 如果 \(f\) 是单同态, 则称 \(f\) 是忠实表示.

  设 \(\pi:G\to S(\Sigma)\) 是一个置换表示. 在 \(\Sigma\) 上定义如下的关系: 对于 \(a,b\in \Sigma, a\sim b\Leftrightarrow \exists g\in G, ga=b\). 这是一个等价关系. 因为 (1) \(a\sim a\); (2) 若\(a\sim b\), 则\(b\sim a\); (3) 若 \(a\sim b,b\sim c\), 则 \(a\sim c\).

  对上述等价关系, \(\Sigma\) 中元素 \(a\) 所在的等价类是 \([a]=Ga=\{ga|g\in G\}\). 每个等价类叫一个 \(G-\) 轨道, 简称轨道. 如果 \(G\) 在 \(\Sigma\) 上的作用只有一个轨道, 则称 \(G\) 在 \(\Sigma\) 上是传递的.

Theorem(Cayley) 每个群同构于某个置换群.

  设群 \(G\) 作用于集合 \(\Sigma\) 上, 则对每个元素 \(a\in G\), \(G_a=\{g\in G|ga=a\}\) 是 \(G\) 的一个子群, 叫做元素 \(a\) 的固定子群.

Theorem(轨道公式) 设有限群 \(G\) 作用于集合 \(\Sigma\) 上, \(a\in\Sigma\), 则 \(|G|=|G_a||[a]|\).

Theorem(Burnside引理) 设 \(G\) 是一个有限群, \(X\) 是一个有限 \(G-\) 集合, 则

\[|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|\]

其中 \(X^g=\{x\in X|gx=x\}\).

PROOF. 对 \(\sum\limits_{g\in G}|X^g|\) 改变求和方式

\[\sum_{g\in G}|X^g|=|\{(g,x)\in G\times X|gx=x\}|=\sum_{x\in X}|G_x|\]

由轨道公式

\[\sum_{x\in X}=\sum_{x\in X}\frac{|G|}{|[x]|}=|G|\sum_{x\in X}\frac{1}{|Gx|}\]

将 \(x\) 按等价类划分再求和, \(Gx\) 就是 \(x\) 所在等价类

\[\sum_{x\in X}\frac{1}{|Gx|}=\sum_{A\in X/G}\sum_{x\in A}\frac{1}{|A|}=\sum_{A\in X/G}1=|X/G|\]

  对于有 \(m\) 种颜色的染色问题, \(|X^g|=m^{c(g)}\), \(|X^g|\) 表示在置换 \(g\) 的作用下, 保持不变的染色方案数. 将 \(g\) 分解为不相交的 \(c(g)\) 个循环的乘积, 某个染色方案不变, \(g\) 的每个循环对应元素要染相同的颜色. 一共 \(m\) 种颜色, \(c(g)\) 个循环, 故共有 \(m^{c(g)}\) 种方案, \(|X^g|=m^{c(g)}\).

Theorem(Polya计数定理) 设 \(N=\{1,2,\cdots,n\}\) 是被染色物体的集合, \(G=\{\sigma_1,\sigma_2,\cdots,\sigma_n\}\) 是 \(N\) 上的置换群, 用 \(m\) 种颜色对 \(N\) 中的元素进行染色, 在 \(G\) 的作用下不同染色方案数是

\[l=\frac{1}{|G|}\sum_{k=1}^{|G|}m^{c(\sigma_k)}\]

其中 \(c(\sigma_k)\) 是置换 \(\sigma_k\) 的轮换表示式中含 1 阶轮换在内的轮换个数.

  2 种颜色对 4 个方个染色, 允许方格围绕中心旋转, 围绕中心逆时针旋转有 \(4\) 种可能: \(0\degree: \sigma_1=\begin{pmatrix}1\end{pmatrix}\), \(90\degree:\sigma_2=\begin{pmatrix}1&2&3&4\end{pmatrix}\), \(180\degree: \sigma_3=\begin{pmatrix}1&3\end{pmatrix}\begin{pmatrix}2&4\end{pmatrix}\), \(270\degree: \sigma_4=\begin{pmatrix}1&4&3&2\end{pmatrix}\), 由 Polya 定理

\[l=\frac{1}{4}(2^4+2^1+2^2+2^1)=6\]

Sylow 定理

Definition 设 \(G\) 为有限群, \(p\) 为素数, \(p^l\mid|G|\), 则称 \(G\) 的 \(p^l\) 阶子群为 \(G\) 的 Sylow p 子群.

Theorem(第一定理) 设 \(G\) 为有限群, \(p\) 为素数, \(p^k\mid|G|\), 则 \(G\) 有 \(p^k\) 阶子群. 特别地, \(G\) 中存在 Sylow p 子群.

Theorem(第二定理) 设 \(G\) 为有限群, \(p\) 为素数, \(P\) 为 \(G\) 的一个 Sylow p 子群. 又设 \(p^k\mid|G|\), 则 \(G\) 的 \(p^k\) 阶子群必含于 \(P\) 的某个共轭子群中.

Theorem(第三定理) 设 \(G\) 为有限群, \(p\) 为素数, \(|G|=p^lm,(p,m)=1\). 以 \(r\) 记 \(G\) 的 Sylow p 子群个数, 则 \(r\equiv1\pmod p\) 且 \(r|m\).