离散数学补充 群论（一）

离散数学 群论

part 1. Binary operations 二元运算

1. Definition: A binary operation on a set $A$ is an everywhere defined function:
      $f: A \times A \to A$
2. Since a binary operation is a function, only one element of $A$ is assigned to each orderd pair. 每个序偶只对应$A$ 中的唯一一个元素。
   
   • use symbols such as "*" to denote binary operations.
   • $A$ is closed ( 封闭的） under the operation *, if $a$ and $b$ are elements in $A$, $a*b \in A$
   • Example 1: Let $A = \mathbb{Z}$, define $a*b$ as $a+b$. "*" is a binary operation on $\mathbb{Z}$;
   • Example 2: Let $A = \mathbb{R}$, define $a*b$ as $a/b$. "*" is not a binary operation.($3*0$ is not defined.)
3. Properties of Binary Operations（并非说二元运算都具有如下性质，只是可能有的性质）
   
   • Commutative（交换律） $a*b = b*a$
   • Associate（结合律） $a*(b*c) = (a*b)*c$
   • Idempotent（幂等律） $a*a = a$
4. Identity（单位元）:
   
   • An element $e$ in $A$ is called an identity element if $\forall a \in A\space\space e*a = a*e = a$
   • 单位元唯一 An identity element must be unique (if not, except $e$, there exist another $e'$ to be an identity element, so according to the definition, $e * e' = e' = e' * e = e$)
   • Inverse(逆元）: An element in $a' \in A$ is called an inverse of $a$ and written as $a^{-1}$ if      $a*a' = a'*a = e$ or $a*a^{-1} = a^{-1}*a = e$
5. Let * be a binary operation on a set $A$, and suppose that "*" satisfies the following properties for any $a,b,$ and $c$ in $A$:
       $a*a=a$
       $a*b = b*a$
       $a*(b*c) = (a*b)*c$
   
   • Define a relation $\preceq$ on $A$ by
        $a \preceq b$ if and only if $a = a*b$.
     Then $(A,\preceq)$ is a poset, and $\forall a,b \in A, GLB(a,b) = a*b$
   • proof 1：since $a = a*a$, $a \preceq a$ for all $a$ in $A$, $\preceq$ is reflexive.
         suppose $a \preceq b$ and $b \preceq a$, $a = a*b = b*a = b$, so $a=b$,
     thus $\preceq$ is antisymmetric.
         If $a \preceq b$ and $b \preceq c$, then $a = a*b = a*(b*c) = (a*b)*c = a*c$, so $a \preceq c$, $\preceq$ is transitve.
   • proof 2 : $a*b = a*(b*b) = (a*b)*b$, so $a*b \preceq b$; similarly, $a*b \preceq a$.
     $\Rightarrow$ $a*b$ is a lower bound for $a$ and $b$.
         If $c \preceq a$ and $c \preceq b$, then $c \preceq a*b$:
         Since $c\preceq a,\space c = c*a;$ likewise, $c = c*b$; then $c = c*b=(c*a)*b = c*(a*b)$. Hence, $c\preceq a*b$

part 2. Semigroup and Group 半群和群

1. Definition: Given a set $G$ and a binary operation * on G. For any elements $a,b,c$ in $G$:
   
   • 1) Closure(封闭性）: $a*b \in G$
   • 2) Associative(结合律)： $(a*b)*c = a*(b*c)$
   • 3) Identity(单位元)： a unique element $e \in G$, such that $a*e = e*a = a$
   • 4) Inverse(逆元)： an element $a' \in G$ of $a$, written as $a^{-1}$, such that $a*a' = a'*a = e$ or $a*a^{-1} = a^{-1}*a = e$
   • 5) Commutative(交换律)： $a*b = b*a$
     
     Groupoid(广群）： 1） is true 满足封闭性
     Semigroup(半群）： 1)~2) are true 满足封闭性，结合律
     Monoid(幺半群，独异点）： 1)~3) are true 满足封闭性，结合律，存在单位元
     Group(群）： 1)~4) are true 满足封闭性，结合律，存在单位元，逆元
     Abelian groupoid/semigroup/monoid/group: 5) is true 满足交换律以及上述各自性质
2. Theorem (Associativity): 对于$a_{1},a_{2},...,a_{n}$（arbitrary elements of a semigroup 对半群中的任意n元组) 在运算过程中任意添加括号对结果没有影响。
3. $A = \{a_1,a_2,...a_n\}$ is an alphabet. $A^*$ is the set of all finite sequences of elements of $A$. $\alpha,\beta,\gamma$ are elemnts of $A^*$.
   
   • The catenation is a binary operation $\cdot$ on $A^*$ (如 $\alpha \cdot \beta$ 就是将 $\beta$ 接在 $\alpha$ 后）。容易知道，$(\alpha \cdot \beta) \cdot \gamma = \alpha \cdot (\beta \cdot \gamma)$
   • $(A^*,\cdot)$ is a semigroup, called the free semigroup generated by $A$.
4. Abelian Group 阿贝尔群:
   
   • example: $G$ is the set of all nonzero real numbers, and $a*b = ab/2$, then $(G,*)$ is an Abelian group.
         Closure: $a*b = ab/2 \not = 0$,hence $a*b \in A$.
         Associative: $(a*b)*c = (ab/2)*c = abc/4, a*(b*c)= a*(bc/2) = abc/4$, hence $(a*b)*c = a*(b*c)$.
         Identity: $\space 2$ is the identity, because we have $a*2 = 2*a = a$.
         Inverse: $a*a^{-1} = a(a^{-1})/2 = 2,\space\space a^{-1} = 4/a$
         Abelian: $a*b = ab/2 = ba/2 = b*a$.
     So, $(G,*)$ is an abelian group.
5. Theorem(Uniqueness of inverse) 逆元唯一: if both $a'$ and $a''$ are inverses of $a$， then $a' = a'e = a'(aa'') = (a'a)a'' = ea''=a''$.
6. Theorem(Left/Right cacellation) 左右相约: $G$ is a group and $a,b,c \in G$ , then $ab=ac \Rightarrow b=c,\space ba = ca \Rightarrow b=c$.
   
   • $ab = ac \Rightarrow a^{-1}(ab) = a^{-1}(ac) \Rightarrow (a^{-1}a)b = (a^{-1}a)c$ (by associativity) $\Rightarrow eb = ec \Rightarrow b = c$.
7. Theorem(Inverse of inverse) 逆元的逆: $(a^{-1})^{-1} = a$
8. Theorem(Solution to equation) 等式的解: $G$ is a group and $a,b \in G$, then both equation $ax=b$ and $ya =b$ have a unique solution in $G$. 这表明在乘法表中，每一行每一列不可能出现相同的元素。否则就不满足解唯一。
   
   • $ax=b \Rightarrow a^{-1}ax=a^{-1}b \Rightarrow x= a^{-1}b$
9. Finite Groups 有限群:
   
   • Definition: If $G$ is a group that has a finite number of elements, $G$ is called a finite group, and the order of $G$ is the number of elements in $G$. ($|G|$)
   • A finite group can be represented by the form of the multiplication table