离散数学补充 群论（二）

离散数学 群论

New Algebra from Old Ones:

Subalgebra 子代数

1. Definition:
   
   • Let $(G,*)$ be a semigroup(半群： 满足封闭性，结合律），$T$ is a nonempty subset of $G$ ; $（T,*）$ is called subsemigroup(子半群） of $(G,*)$ if $T$ is closed under the operation *.
     
     
   • Let $(G,*)$ be a monoid (独异点： 满足封闭性，结合律，存在单位元），$T$ is a nonempty subset of $G$ ; $(T,*)$ is called submonoid(子独异点/子幺半群） of $(G,*)$ if $T$ is a subsemigroup and $e \in T$.
     
     
   • Let $(G,*)$ be a group (群： 满足封闭性，结合律,存在单位元，逆元），$T$ is a nonempty subset of $G$ ; $（T,*）$ is called subgroup(子群） of $(G,*)$ if $T$ is a submonoid and if $a \in T$ , then $a^{-1} \in T.$
     
     
   • 事实上，对于上述定义，简单的理解就是： 对于1) 封闭性 2) 单位元 3) 逆元 这四个性质，a) 子半群 b) 子独异点 c) 子群 每个依次比前者多一项性质。 （半群的任何子集都满足结合性）
2. Examples: $(Z,\times)\space\space and \space\space(E,\times)$
        $\space(Z,+)\space\space and \space\space(E,+)$
   
   
3. Trivial Subgroup: Let $G$ be a group then $G$ and $H = \{e\}$ are subgroups of $G$, the trivial subgroups of $G$.(有点疑问）
   
   
   • an example of Subgroup:
     
     可以看出，$H$ 满足封闭性，并且具有单位元$f_1$,每个元素都有其逆元（$f_1^{-1} = f_1,f_2^{-1} = f_3,f_3^{-1}=f_2$), 故$H$是 $S_3$ 的子群。
     
     
4. Powers of $a$
   
   • Definition: Let $G$ be a semigroup, monoid, or group, $a \in G$; Define $a^n$ as $aa...a\space$(n factors) for $\space n \in \mathbb{Z}^+$,$a^0$ as $e$, in case of monoid(因为幺半群具有单位元），$a^{-n}$ as $a^{-1}a^{-1}...a^{-1}$(n factors), in case of group(因为群具有逆元）
     
     
   • Theorem: If $n$ and $m$ are any integers, then $a^na^m = a^{n+m}$
     
     
   • Examples: $H = \{a^i|i \in \mathbb{Z}^+\}$ is a subsemigroup of $G$.(显然具有封闭性）
     
          $\space H = \{a^i|i \in \mathbb{Z}^+ \space or\space\space i = 0\}$
     is a submonoid of $G$.(显然具有单位元，即$a^0$)
     
          $\space H = \{a^i|i \in \mathbb{Z}\}$ is a subgroup of $G$.(显然具有逆元，因为$i$包括了负整数）
     
     
   • Theorem: Let $(G,*)$ be a group, $H$ be a nonempty subset of $G$. If $\forall a,b\in H$ implies $a^{-1}*b \in H$, then $H$ is a subgroup of $G$.（对于 $\forall a \in H$, 有 $a^{-1}a = e \in H$, 故 $H$ 中含有 单位元；因而，对于 $\forall a$ 和单位元 $e \in H$, 有 $a^{-1}e = a^{-1} \in H$, 故 $H$ 中含有 逆元；至于封闭性，只需要证明对于 $\forall a,b \in H$, 有 $ab \in H$, 而我们已经知道 $a \in H \rightarrow a^{-1} \in H$，则对 $\forall a^{-1} \in H$, $(a^{-1})^{-1}b = ab \in H$。综上所述，$H$ 是 $G$ 的一个子群。)

Product Algebra 积代数

1. Theorem: If $(S,*)$ and $(T,*')$ are semigroups(-monoid,-group), then $(S \times T,*'')$ is a semigroup(-monoid,-group). (Note: $(s_1,t_1)*''(s_2,t_2) = (s_1*s_2,t_1*'t_2)$)

Quotient Algebra 商代数

1. Congruence Relation:
   
   • Definition: An equivalence relation(满足自反，对称，传递） $R$ on the groupoid（广群，满足封闭性） is called a congruence relation if $aRa'$ and $bRb'$ imply $(a*b)R(a'*b')$ 即一个对某二元操作封闭的等价关系叫做同余关系（即原本等价的元素经过二元操作后依然等价）。
     
     
   • Example: Given the group $(\mathbb{Z},+)$ and the equivalence relation $R$ on $\mathbb{Z}$ defined by $aRb$ iff $a\equiv b\space(mod \space\space 2)$. This relation is a congruence relation.(容易知道 $R$ 首先是等价关系，整数集$\mathbb{Z}$是广群，若$a$和$a'$等价，$b$和$b'$等价，它们模2同余，那么 $a+b$ 和 $a'+b'$ 模2也同余。）
     
     
2. Theorem(Quotient Groupoid 商广群 ):
   
   • Let $R$ be a congruence relation on the groupoid $(G,*)$ $R$ 是广群 $(G,*)$ 上的同余关系
   • $\otimes$ be a relation from $G/R \times G/R\space$ to $\space G/R\space$ in which the ordered pair $([a],[b])$ is related to $[a*b]$ for $a,b \in G$, $\otimes$ 是从 $G/R \times G/R\space$ 到 $\space G/R\space$ 的二元关系，在此关系上，对于 $a,b \in G$，序偶 $([a],[b])$ 对应 $[a*b]$。
     then
   • $\otimes([a],[b]) = [a]\otimes[b] = [a*b]$, is a function from $G/R \times G/R\space$ to $\space G/R$,
   • so $(G/R,\otimes)$ is a groupoid,（因为具有封闭性） called the quotient groupoid or factor groupoid (商广群或因子广群）
     
     
   • $Z_n$ 表示 $S/\equiv (mod\space n)$。
     
     (Note： 记号 $G/R$ 表示 $G$ 上所有等价类的集合，$[a] = R(a)$ 表示 $a$ 的等价类。)
     
     
3. Corollary 1： 若 $R$ 是广群 $(G,*)$ 上的等价关系, $G/R$ 是商广群 ，那么如果 $G$ 是半群/幺半群/群， $(G/R,\otimes)$ 与之相同。
   
   
4. Corollary 2:
   
   • 若 * 满足结合律，那么$\otimes$ 也满足。因为：
     $[a] \otimes ([b] \otimes [c]) = [a] \otimes [b*c] = [a*(b*c)] = [(a*b)*c] = [a*b] \otimes [c] = ([a] \otimes [b]) \otimes [c]$
     
     
   • 若 $e$ 是 $G$ 上的单位元，那么其等价类 $[e]$ 也是 $G/R$ 上的单位元, 因为：
     $[a]\otimes [e] = [a*e] = [a] = [e*a] = [e] \otimes [a]$
     
     
   • 若 $a^{-1}$ 是 $a$ 在 $G$ 上的逆元, 那么 $[a^{-1}]$ 是 $[a]$ 在 $G/R$ 上的逆元, 因为：
     $[a] \otimes [a^{-1}] = [a*a^{-1}] = [e] = [a^{-1}*a] = [a^{-1}] \otimes [a]$