ᕕ ( ᐛ ) ᕗ collision's blog

离散数学笔记-近世代数

6.1 群

6.1.1 半群和独异点

定义

6.1.2 群

定义

一些性质

特殊的群

6.1.3 群中元素的阶

定义

q：如果$G$是有限群，那么$G$包括无限阶元吗？ a：若$G$为有限群，$\forall a\in G$为无限阶元，则 $$ \lbrace a^{-\infty}...a^{-1},a^{0},a^{1},a^{2}...a^{\infty}\rbrace \subset G $$ 且$a^{-\infty}\not = ... \not = a^{-1} \not = a^{0} \not = a^{1} \not = a^{2} \not = ...\not = a^{\infty}$ (若$\exists n,m\in Z$，且$n\not = m$，有$a^{n}=a^{m}\Rightarrow a^{|n-m|}=e$，与已知矛盾) 即，无限阶元会产生无穷个元素，显然$G$不可能是有限群

一些性质

6.1.4 子群

定义

子群的判定定理

下面给出判断子群的三条定理：

充分性：
已知$H\le G$，则$\forall a,b \in H$，有$a\cdot b\in H 且b^{-1} \in H \Rightarrow a\cdot b^{-1}\in H$
必要性：
由$\forall a,b\in H有a\cdot b^{-1}\in H$
$1.$令$b=a$，则$a\cdot a^{-1}=e\in H$，即$H$中单位元存在
$2.$令$a=e$，则$e\cdot b^{-1}=b^{-1}\in H$，即$H$中元素均有逆元
$3.\forall a,b \in H$，则$b^{-1}\in H$，则$a\cdot (b^{-1})^{-1} \in H \Rightarrow a\cdot b \in H$，即$H$对$\cdot$运算封闭
充分性易证，下证必要性
$1.$由于$\forall a,b \in H$，有$a\cdot b\in H$，即$H$对$\cdot$运算封闭
$2.$由于$H$是有穷集，故$\forall a\in H$，有$|a|=r\Rightarrow a^{r}=e\in H$，即$H$中存在单位元
$3.$由$a^{r-1}\cdot a=e \Rightarrow a^{-1}=a^{r-1}$，即$H$中任意元素均有逆元

特殊子群

$1.$设$a,b\in C$，则$a\in G,b\in G \Rightarrow b^{-1} \in G$，且对$\forall x \in G$，有$ax=xa$ $$ bx=xb\Rightarrow x=b^{-1}xb \Rightarrow xb^{-1}=b^{-1}x $$ 因此$b^{-1}\in C$，故$ab^{-1}x=axb^{-1}=xab^{-1}$

共轭子群：
设$H\le G,x\in G$，证明：$xHx^{-1}=\lbrace xhx^{-1}|h\in H\rbrace$是$G$的子群，称为$H$的共轭子群

$1.$设$xax^{-1},xbx^{-1}\in xHx^{-1}$，则$a\in H,b\in H,b^{-1}\in H\Rightarrow ab^{-1}\in H$ $2.$$xax^{-1}(xbx^{-1})^{-1}=xax^{-1}xb^{-1}x^{-1}=xab^{-1}x^{-1}\in xHx^{-1}$，由子群判定定理，原式得证
$\forall a,b\in H\cap K$，则$a\in H 且 a\in K,b^{-1}\in H 且 b^{-1}\in K$，由于$H\le G且K\le G$，因此$ab^{-1}\in H且ab^{-1}\in K$，因此$ab^{-1} \in H\cap K\Rightarrow H\cap K\le G$

（2）$H\cup K\le G\iff H\subseteq K \vee K\subseteq H$

充分性$\Leftarrow$显然成立
下证必要性$\Rightarrow$：假设$H\not \subseteq K\wedge K\not \subseteq H$，则$\exists h\in H \wedge h \notin K,\exists k\in K \wedge k \notin H$，则$hk\notin H$（否则$k=h^{-1}(hk)\in H$，矛盾）,同理$hk\notin K$，因此$hk\notin H\cup K$.但$h,k\in H\cup K$，与$H \cup K \le G$矛盾 因此$H\subseteq K\vee K\subseteq H$

6.1.5 循环群

定义

设$G$是群，若$\exists a \in G$使得$G=\lbrace a^{k}|k\in Z \rbrace $，则称$G$是循环群，记作$G=\langle a \rangle$，称$a$为$G$的生成元

分类

$G=\langle a \rangle$，根据$|a|$分为两类：

由$a$生成的循环群只有一个生成元吗?

$$ <Z,+>=\langle 1 \rangle=\langle -1 \rangle $$

$$ <Z_{4},\oplus_{4}>=\langle 1 \rangle=\langle 3 \rangle $$

循环群的生成元求法

设$G=\langle a \rangle$是循环群

循环群的子群求法

设$G=\langle a \rangle$是循环群

例:求出下列$G$的子群
（1）$G=\langle a \rangle$为无限循环群
$\langle e\rangle=\lbrace e\rbrace $
$\langle a\rangle=\langle a^{-1}\rangle=G$ $\langle a^{2}\rangle=\langle a^{-2}\rangle=\lbrace e,a^{\pm2},a^{\pm4},a^{\pm6},…\rbrace $
…
（2）$G$为12阶循环群$\langle a \rangle$
12的正因子有1,2,3,4,6,12.$G$有6个子群
$\langle e\rangle=\lbrace e\rbrace $
$\langle a\rangle=\lbrace G\rbrace $
$\langle a^{2}\rangle=\lbrace e,a^{2},a^{4},a^{6},a^{8},a^{10}\rbrace $
$\langle a^{3}\rangle=\lbrace e,a^{3},a^{6},a^{9}\rbrace $
$\langle a^{4}\rangle=\lbrace e,a^{4},a^{8}\rbrace $
$\langle a^{6}\rangle=\lbrace e,a^{6}\rbrace $

6.1.6 n元置换群

循环群都是Abel群，置换群一般不是

定义

设$S=\lbrace 1,2,…,n\rbrace $，$s$上的任何双射函数$\sigma：S\rightarrow S$称为$S$上的$n$元置换，$(1)$表示恒等置换。即： $$ \sigma= \begin{pmatrix} 1 & 2 & … & n\ \sigma(1) & \sigma(2) & … & \sigma(n) \end{pmatrix} $$ 所有的$n$元置换构成的集合$S_{n}$，其关于置换的乘法封闭，置换的乘法满足结合律，恒等置换(1)是$S_{n}$中的单位元，对于任何$n$元置换$\sigma \in S_{n}$，逆置换$\sigma^{-1}$是$\sigma$的逆元。因此$S_{n}$关于置换的乘法构成一个群，称为n元对称群，其子群称为n元置换群。

乘法与逆

两个$n$元置换的乘法就是函数的符合运算，$n$元置换的求逆就是求反函数 $$ \begin{aligned} \sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 3 & 2 & 1 & 4 \end{pmatrix},\tau=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 3 & 1 & 2 & 5 \end{pmatrix} \\ \sigma^{-1}= \begin{pmatrix} 5 & 3 & 2 & 1 & 4\\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \\ \sigma\tau=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 2 & 5 & 3 & 4 \end{pmatrix} \end{aligned} $$

轮换与对换

设$\sigma$是$S=\lbrace 1,2,…,n\rbrace $上的$n$元置换，若$\sigma(i_{1})=i_{2},\sigma(i_{2})=i_{3},…,\sigma(i_{k-1})=i_{k},\sigma(i_{k})=i_{1}$，且保持$S$中其他元素不变，则称$\sigma$为$S$上的$k$阶轮换，记作$(i_{1}i_{2}…i_{k})$。若$k=2$，则称$\sigma$为$S$上的对换。 如 $$ \sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\ 5 & 3 & 2 & 1 & 4 \end{pmatrix}=(1\space 5\space 4)(2\space 3)=(1\space 4)(1\space 5)(2\space 3) $$

任何$n$元置换都可以唯一地表示成不相交的轮换之积，而任何轮换都能表示为对换之积 $$ (i_{1}i_{2}…i_{k})=(i_{1}i_{k})…(i_{1}i_{3})(i_{1}i_{2}) $$

置换的阶

$G$是$n$元置换群

6.1.7 群的分解

拉格朗日定理

设$G$是有限群，$H$是$G$的子群，则$|G|=[G:H]\cdot|H|$ $[G:H]$是$H$在$G$中的指数

推论和应用

6.2 环

6.2.1 环

定义

环是具有两个二元运算的代数系统，分别称为加法和乘法，记作$+$和$\cdot$ 设$\langle R,+,\cdot\rangle$是具有两个二元运算的代数系统，如果

则称该代数系统是环。环中加法和乘法的单位元记作0和1（1可能不存在），环中元素的加法逆元称为负元，记作$-x$；$x$的乘法逆元如果存在称为逆元，记作$x^{-1}$。类似的，将$x+(-y)$记作$x-y$
（1）整数集、有理数集、实数集和复数集关于普通加法和乘法构成环，分别称为整数环$Z$、有理数环$Q$、实数环$R$和复数环$C$
（2）$n(n>2)$阶实矩阵的集合$M_{n}(R)$关于矩阵加法和乘法构成n阶实矩阵环
（3）幂集$P(B)$关于集合的对称差和交运算构成环$\langle P(B),\oplus,\cap\rangle$
（4）$\langle Z_{n},\oplus,\otimes\rangle$构成环，称为模n的整数环
（5）设$\langle G,\circ\rangle$是Abel群，在$G$上定义 $：\forall x,y\in G,x*y=e$，则$\langle G,\circ,*\rangle$构成零环

运算性质

$a0=a(0+0)=a0+a0$，由消去律得$a0=0$ $0a=(0+0)a=0a+0a$，由消去律得$0a=0$ 故$0a=a0=0$

$(-a)b+ab=(-a+a)b=0b=0$ $ab+(-a)b+=(-a+a)b=0b=0$ 因此$(-a)b$是$ab$的加法逆元$\Rightarrow (-a)b=-ab$ 同理，$a(-b)$是$ab$的加法逆元$\Rightarrow a(-b)=-ab$ 由逆元的唯一性，$(-a)b=a(-b)=-ab$

由$(-a)b=a(-b)$，$(-a)(-b)=(-(-a))b=ab$

$(a-b)c=(a+(-b))c=ac+(-b)c=ac-bc$

$c(a-b)=c(a+(-b))=ca+c(-b)=ca-cb$

$$ \begin{aligned} \sum_{i=1}^{m}a_{i}\sum_{j=1}^{n}b_{j}&=(a_1+a_2+…+a_m)(b_1+b_2+…b_n)\\ &=a_1(b_1+b_2+…b_n)+a_2(b_1+b_2+…b_n)+…+a_m(b_1+b_2+…b_n)\\ &=a_1b_1+…a_1b_n+…+a_mb_1+…+a_mb_n \end{aligned} $$

证明略
例：在环中计算$(a+b)^3,(a-b)^2$ $(a+b)^3=a^3+ba^2+aba+b^2a+a^2b+bab+ab^2+b^3$ $(a-b)^2=(a-b)(a-b)=a^2-ba-ab+b^2$

6.2.2 环中的零因子

定义

设$\langle R,+,\cdot\rangle$是环，若$\exists ab=0$，且$a\not =0,b\not =0$，则称$a$为左零因子，$b$为右零因子(此处的0指环中加法的单位元)，即两个非0元素的乘积为0，这样的元素称为左/右零因子 如$\langle Z_{6},\oplus,\otimes\rangle$，其中$2\otimes 3=0$，2和3都是零因子，这个环含有零因子，不是无零因子环
无零因子的条件：$ab=0\rightarrow a=0\lor b=0$

证明：由于R中没有零因子，因此由$a\not =0$和 $$ ab=ac\rightarrow ab-ac=0\rightarrow a(b-c)=0 $$ 得$b-c=0$，即$b=c$消去律成立 反之，假设消去律成立，因为$ab=0\rightarrow ab=a0$ 由消去律$a\not =0$则$b=0$，因此环$R$中没有零因子

定理：一个环中若有一个消去律成立，则另一个消去律也成立

6.2.3 特殊的环

定义

设$\langle R,+,\cdot\rangle是环$

6.2.4 除环和域

若$R$为环，$|R|>1$，令$R^\lbrace *\rbrace =R-\lbrace 0\rbrace $，且$R^\lbrace *\rbrace $构成群，则称$R$是一个除环 若$R$为交换环，满足以上除环的条件，则称R为域 一个域$F$是具有两个二元运算的代数系统，其中$F$与加法构成Abel群，$F^{*}=F-{0}$与乘法也构成Abel群
（1）整数环$Z$、有理数环$Q$、实数环$R$中的乘法适合交换律、含有单位元1、不含零因子，因此是交换环、含幺环、无零因子环和整环。其中有理数环和实数环是域（除0外均有逆元）
（2）n阶实矩阵环$\langle M_{n}(R),+,*\rangle$不是交换环，是含幺环（单位元是$n$阶单位矩阵），不是无零因子环，因此也不是整环和域
（3）模n的整数环$\langle Z_{n},\oplus,\otimes\rangle$是交换环、含幺环，当$n$为质数时构成无零因子环、整环和域；当$n$为合数时构成不构成整环和域

6.3 格与布尔代数

格与布尔代数均是加载有两个二元运算的代数系统，布尔代数也是一种格

6.3.1 格

定义

设$\langle S,\preccurlyeq \rangle$是偏序集，若$\forall x,y\in S,\lbrace x,y\rbrace $均有上确界和下确界，则称$S$关于$\preccurlyeq$构成格
其中，求上确界记作$\lor$，下确界记作$\land$

对偶原理

设$f$是含有符号$=,\preccurlyeq \succcurlyeq \lor \land$的公式，令$f^{*}$为$f$中的$\lor \rightarrow\land,\preccurlyeq\rightarrow\succcurlyeq…$后的对偶式，若$f$为真，则$f^{*}$也为真

一些性质

$\langle L,\preccurlyeq \rangle$为格

格的等价定义：

证幂等律： $\forall a \in S,a*a=a*(a\cdot(a*a))=a$ 同理有$a\cdot a=a$

子格

设$L$为格，$S$是$L$的非空子集，如果$S$关于$L$中的运算封闭，则称$S$是$L$的子格

特殊的格

1）分配格

2）有界格 如果一个格存在全下界$a$（$\exists a\in L,\forall b\in L\rightarrow a\preccurlyeq b$）和全上界$c$（$\exists c\in L,\forall b\in L\rightarrow b\succcurlyeq c$），则为有界格，记作$\langle L,\land,\lor,0,1\rangle$

3）有补格 设$\langle L,\land,\lor,0,1\rangle$是有界格，$a\in L$，若$\exists b\in L$满足$a\land b=0,a\lor b=1$，则称$b$是$a$的补元。若每个元素都有补元则为有补格

设$L$是分配格，$a\in L$，假设$a$存在补元$b$和$c$，则 $$ a\land b=0=a\land c,a\lor b=1=a\lor c $$ 由分配格性质，$b=c$

4）布尔格 有补分配格称为布尔格（布尔代数）

等价定义： 设$\langle B,*,\cdot\rangle$是代数系统，如果$*$和$\cdot$满足：

则称$\langle B,*,\cdot\rangle$是布尔代数

#离散数学 #近世代数