离散数学补充 群论（三）

离散数学 群论

Homomorphism 同态

1. Definition： Let $(S,*)$ and $(T,*')$ be two groupoids， $f$ be a function from $S$ to $T$. If for all $a$ and $b$ in $S$, $\space f(a*b) = f(a) *' f(b)$， then:
   
   • $f$ is called a homomorphism from $(S,*)$ to $(T,*')$
   • $S$ is homomorphic to $T$, denoted by $S\sim T$.
     $f(S)$ is the homomorphic image（同态像） of $S$.
     简单来说，就是映射之后的元素依然满足二元关系的对应。
     
     
2. Definition： Let $f$ be a homomorphism from $(S,*)$ to $(T,*')$
   
   • If $f$ is an onto（满射，即陪域中任意元素 $y$ 必有 $f(x) = y$ 存在) from $S$ to $T$， that is $f(S) = T$， $f$ is called an onto homomorphism from $(S,*)$ to $(T,*')$.
   • If $f$ is a bijection(双射，又叫一一对应,one-to-one correspondence) from $S$ to $T$，
   • $f$ is called a isomorphism(同构） from $(S,*)$ to $(T,*')$
   • $S$ is isomorphic to $T$, or $S$ and $T$ are isomorphic, denoted by $S \cong T$
3. Example:
   
   如上图，$f$ 的作用是奇偶校验， 二元操作 $·$ 将两个01串连接在一起。容易看出 $f$ 是一个同态。
   Tips: 要证明是否同态：
   
   • STEP 1. 找到对应关系 $f$
   • STEP 2. 证明 $f(a*b) = f(a)*'f(b)$
     若要证明是否同构，还需判断 $f$ 是否为双射.(先判断是否单射，再判断是否满射)
4. 对于满射同态，单位元和逆元也是对应的。如果 $G$ 是 广群/半群/独异点/群（或在其基础上加上交换的性质，即Abelian), $G'$ 与之相同。
5. Remember: 同构会保留群的所有性质,只要有性质不同，那么便不是同构。

Fundamental Homomorphism Theorem

1. Theorem(Natural Homomorphism 自然同态）:
   
   • Let $R$ be a congruence relation（即$aRa',\space bRb'$，则有$(a*b)R(a'*b')$） on a groupoid $(G,*)$）
   • $(G/R,\otimes)$ be the corresponding quotient groupoid（即满足$[a]\otimes [b] = [a*b]$)
     Then：
     the function $f_R: G \rightarrow G/R$ defined by
     $f_R(a) = [a]$
     ($a$ 对应其等价类)
     is an onto homomorphism, called the natural homomorphism.
   • 证明非常容易。
     对任意的$[a] \in G/R$, 在 $G$ 中必存在$a$,则$f_R(a)=[a]$，故 $f$ 为满射。
     $f_R(a)\otimes f_R(b) = [a] \otimes [b] = [a*b] = f_R(a*b)$， 故为同态。
2. Theorem(Fundamental Homomorphism Theorem):
   
   • $f: G \rightarrow G'$ 是广群 $(G.*)$ 到另一个广群 $(G',*')$ 上的一个同态，且是满射。
   • $R$ 是 $G$ 上满足如下定理的关系：
     $\forall a,b \in G$，$aRb$ iff $f(a)=f(b)$
     那么，
   • $R$ 是同余关系.
   • $(G',*')$ 和 商广群 $(G/R, \otimes)$ （商广群： $\otimes([a],[b]) = [a]\otimes[b] = [a*b]$） 同构.
   • 证明如下：
     1.证明 $R$ 为同余关系： 首先 $R$ 显然是等价关系。若 $aRa',bRb'$, 则$f(a)=f(a'),f(b)=f(b')$。而 $f$ 是同态,故满足$f(a)*'f(b)=f(a*b)=f(a')*'f(b')=f(a'*b')$, 则$(a*b)R(a*'b)$, $R$ 为同余关系.
     2.证明 $(G',*')$ 和 $(G/R,\otimes)$ 是同构的：定义$\overline f = \{([a],f(a)|[a] \in G/R\}$,
     容易判断 $\overline f$ 是函数，并且满足单射，（单射是指不同的变量对应不同的值。如果有$\overline f([a]) = \overline f([a'])$, 根据定义，$f(a) = f(a')$, 则 $aRa'$，我们已经证明 $R$ 是等价关系，因此 $[a] = [a']$）也满足满射，（由于 $f$ 是 $G'$中的满射函数，容易知道$\overline f$ 也是满射函数）。故 $\overline f$ 是双射。
     又因为 $\overline f([a]\otimes [b]) = \overline f([a*b]) = f(a*b) = f(a)*'f(b) = \overline f([a]) *'\overline f([b])$.
     综上所述，二者同构。
   • 此定理可以用下图表示：
     
     $f_R$ 是自然同态，$\overline f\circ f_R = f$，因为 $(\overline f \circ f_R)(a)=\overline f(f_R(a)) = \overline f([a]) = f(a)$

Normal subgroup

• Definition: $H$ 是 群 $G$ 的子群，$a\in G$，$G$ 中， $H$ 的由 $a$ 决定的左右陪集(The left and right coset of $H$ in $G$) 分别是如下集合：
  $aH = \{ah|h \in H\}\\ Ha = \{ha|h \in H\}$
  如果 $aH = Ha$ 对$\forall a \in G$ 都成立，那么子群 $H$ 是正规子群(Normal subgroup)。
  Note: $aH=Ha$，并不意味着对于$h \in H$ 以及 $a \in G$ 就有 $ah=ha$, 而应该是存在一个 $h' \in H$, 使得 $ha=ah'$。
  
  
• Theorem 1：如果 $K$ 是 群 $G$ 的一个有限子群, 那么 $K$ 在 $G$ 中的每个左陪集的元素个数都和 $K$ 相同。
  
  

• Theorem 2(拉格朗日定理）：设 $H$ 是 有限群 $G$ 的子群，则$H$ 的阶(order,即元素个数) 整除G的阶。
  
  

  同余关系和正规子群:

• 等价类和陪集：
  
  以下定理说明，群 $G$ 上的同余关系中 $e$ 的等价类是正规子群：

• Theorem 3： $R$ 是群 $G$ 上的同余关系, $H = [e]$ （即 $H$ 这个等价类中包含单位元）, 那么 $H$ 是 $G$ 的一个正规子群, 并且对于 $\forall a \in G, [a] = aH = Ha$。
  Notice： 商群 $G/R$ 是由 $N = [e]$ 的所有左陪集构成的。商群上的操作$\otimes$ 定义为： $(aN)(bN) = [a] \otimes [b] = [ab] = abN$
  $f_R: G \rightarrow G/R$ 定义为： $f_R(a) = aN$。 $f_R$ 是从$G$ 到 $G/R$ 上的一个同态。($G/R$ 也写作 $G/N$)
  
  以下的定理说明，任何一个正规子群，都是某一个同余关系上 $e$ 的等价类：
• Theorem 4： $N$ 是群 $G$ 的一个正规子群， 关系$R$： $aRb$ iff $a^{-1}b \in N$。 那么 $R$ 是群 $G$ 上的同余关系, $N$ 是 $R$ 中的等价类 $[e]$。
• Corollary： $f$ 是从群 $(G,*)$ 到群 $(G',*')$ 的一个同态并且是满射, $f$ 的核(kernel), $ker(f)$， 定义为 $ker(f) = \{a\in G|f(a) = e'\}$, 那么 $ker(f)$ 是 $G$ 的一个正规子群， 商群 $G/ker(f)$ 与 $G'$ 同构。（根据Fundamental homomorphism theorem 2., 可定义同余关系 $R$: $aRb \Leftrightarrow f(a)=f(b)$, 容易知道 $ker(f)=[e]$；根据Theorem 3, $ker(f)$ 是正规子群，$G/ker(f)$ 与 $G'$ 同构。）