代数系统笔记

离散数学——代数系统

[TOC]

代数系统

二元运算及其性质

定义 设$S$是一个非空集合，映射$f:S^n\rightarrow S$称为$S$上的一个n元运算。

n元运算可以看作n+1元关系。

定义

设"$\cdot$"是定义在集合$S$上的二元运算，如果

$\forall x, y \in S$, $x\cdot y \in S$,则称"$\cdot$"在S上是封闭的

$\forall x, y\in S$, $x\cdot y=y\cdot x$,则称"$\cdot$"在S上是可交换的

$\forall x, y, z\in S$, $x\cdot (y\cdot z)=(x\cdot y)\cdot z$,则称"$\cdot$"在S上是可结合的

$\forall x\in S$, $x\cdot x=x$,则称"$\cdot$"是幂等的。

定义

设$\cdot$和$*$是同时定义在$S$上的两个二元运算。如果

$\forall x, y, z\in S, x*(y\cdot z)=(x*y)\cdot(x*z)且(y\cdot z)*x=(y*x)\cdot(z*x)$，则称运算*关于·是可分配的。

*和$\cdot$ 是可换运算，且$\forall x, y\in S, x*(x\cdot y)=x及x\cdot(x*y)=x$，则称运算*和·满足吸收律

代数系统的定义与特异元

定义 一个==非空集合==S连同若干个定义在S上的运算$f_1, f_2, ...,f_k$所组成的系统称为一个==代数系统==，记为$<S,f_1,f_2,...,f_k>$

判断集合S及其上的代数运算是否是代数系统的关键是
1. 集合S非空
2. 这些运算是否满足封闭性

定义

设$<S, \cdot>$是一个代数系统，则

如果$\exist e\in S$使$\forall x\in S, e\cdot x=x\cdot e=x$，则称e为代数系统的==幺元（单位元）==

如果存在$\theta \in S$，使$\forall x\in S, \theta \cdot x=x\cdot \theta=\theta$，则称$\theta$为代数系统的==零元==

$a\in S$，如果$a\cdot a=a$，则称$a$时系统的==幂等元==

定义 设在代数系统$<S, $$~~\cdot~$>中，$e$是幺元，$a$是S中的一个元素。如果存在$b\in S$使得$a\cdot b=b\cdot a=e$，则称$b$是$a$的==逆元==，记为$b=a^{-1}$

在一个代数系统中，不是每个元都存在着逆元。

定理设$<S, \cdot>$是一个代数系统。如果存在幺元，则幺元是==唯一的==；如果存在零元，则零元是==唯一的==；如果元a有逆元，且"$~\cdot~$"==可结合==，则逆元是==唯一的==。

证明：反证法即可（设不唯一）。

根据运算满足的条件，可以把含单个二元运算的代数系统进行分层。

定义

设$<S, \cdot>$是一个代数系统，则

当"$\cdot$"是封闭的，称$<S, \cdot>$为==广群==

如果$<S, \cdot>$是广群，且"$\cdot$"是==可结合运算==，则称$<S, \cdot>$是==半群==

如果$<S, \cdot>$是半群，且存在幺元，则称$<S, \cdot>$为==含幺半群==

如果$<S, \cdot>$是含幺半群，且每个元素都有逆元，则称$<S, \cdot>$为==群==

群的条件：闭，结，幺，逆

（没必要在代数系统是否要求有封闭性上花费太大心思，不同教材不同，在这里要求代数系统要有封闭性）

半群与群

半群

例：

$<S, \cdot>$满足封闭、可结合、有幺元0，所以是含幺半群。还满足可换性，每个元都有逆元，因此也是可换群

$<S, \times>$满足封闭、可结合、有幺元1，因此是含幺半群。但0无逆元，所以不是群。

定义

设$<S, \cdot>$是半群，$a\in S$，n是正整数，约定符号$a^n$表示n个a在运算"$\cdot$"下的结果，可递归定义如下：

$a^1=a$

$a^{n+1}=a^n\cdot a$

当$<S, \cdot>$是含幺半群，e是幺元时，可以把归纳基础改为$a^0=e$

定理

设$<S, \cdot>$是半群，$a\in S$，m和m是正整数，则

$a^m\cdot a^n=a^{n+m}$

$(a^m)^n=a^{mn}$

当$<S, \cdot>$是含幺半群时，上述结论对任意非负整数m和n都成立

定理

设$<S, \cdot>$是一个半群，如果S是==有限集==，则必有$a\in S$使得$a^2=a$。

证明:

任取$b\in S$，因为S是有限集，则元素$b^1, b^2,...$中必定有两个一样的，设为$b^i, b^j$，设$i<j$，所以$b^i=b^{j-i}\cdot b^i$，所以对于任意的$t \ge i$，都有$b^t=b^{j-i}\cdot b^t$，反复迭代可以得到$b^t=b^{k(j-i)}\cdot b^t$，取$k$使得$k(j-i)\ge i$，同时令$t=k(j-i)$，则$b^t$是幂等元。

含幺半群至少有一个幂等元，即幺元。

定义

设$<S, \cdot>$是一个半群，==非空集合==$A \subseteq S$，并且$<A, \cdot>$也是半群，则称$<A, \cdot>$是$<S, \cdot>$的==子半群==。

设$<S, \cdot>$是一个含幺半群，==非空集合==$A \subseteq S$，并且$<A, \cdot>$也是含幺半群，则称$<A, \cdot>$是$<S, \cdot>$的==含幺子半群==。

要证明$<A, \cdot>$是半群$<S, \cdot>$的子半群时，只需证明$A$非空，$A\subseteq S$并且运算"$\cdot$"在集合A内是封闭的。

群和子群

例：

$<Z,+>$整数加群，$<R,+>$实数加群，$<Q,+>$有理数加群。

$<Z,\times>$不是群，$<R-\{0\},\times>$是实数乘群。

设$Z_k$表示整数集Z上的模k剩余类集合，即$Z_k=\{[0],[1],[2],..,[k-1]\}$

$<Z_k,\bigoplus>$是剩余类加群，[0]是幺元，每元[i]的逆元是[k-i]

$<Z_k,\bigotimes>$不是群，因为[0]无逆元。

而$<Z_k-\{[0]\},\bigotimes>$，也不一定是群。如$<Z_4-\{[0]\}，\bigotimes>$不是群（不封闭），但$<Z_5-\{[0]\}，\bigotimes>$是群。

当k是素数的时候，$<Z_k-\{[0]\},\bigotimes>$一定是群。
设n个元素的集合A上的全体置换构成集合$S_n$。则$<S_n,\circ>$构成群，称为n次对称群

==群中元素的个数称为群的阶==

群也可以用别的形式等价定义

定理

如果$<G, \cdot>$是==半群==，并且对于任意$a, b\in G$，都存在$x, y\in G$，使$x\cdot a=b,a\cdot y=b$，则$<G,\cdot>$是群。

证明：先证明有幺元，再证明每元都有逆。

设$a\in G$，方程$x\cdot a=a$的解为$e_1$，那么对于任何$t\in G$，都有$e_1\cdot t=t$

证明：设方程$a\cdot y=t$的解为$y_0$

于是有$e_1\cdot t=e_1\cdot (a\cdot y_0)=(e_1\cdot a)\cdot y_0=a\cdot y_0=t$

所以$e_1$是$G$中的左幺元，同理$G$中的右幺元是$e_2$

所以$G$中有幺元$e$。（一个代数系统中幺元是唯一的）
同理，对任意$b\in G$，方程$x\cdot b=e$有解$x_0$，则$x_0$是b的左逆元。

$b\cdot y=t$有解$y_0$，是b的右逆元。从而b有逆元。（可结合的运算的代数系统每元的逆是唯一的）

这个定理说明：在群的定义中，幺元的条件可以用存在左幺元（或右幺元）替代，逆元的条件可以用存在左逆元（右逆元）替代。

定理 在群$<G, \cdot>$中==消去律成立==，即如果$a\cdot b=a\cdot c$，必有$b=c$

证明：$a^{-1}\cdot a\cdot b=a^{-1}\cdot a\cdot c\\b=c$

推论1 群$<G, \cdot>$的运算表中每行和每列都没有重复元素

推论2 群$<G, \cdot>$除幺元外无其他幂等元

定理设$<G, \cdot>$是群，$a\in G$，构造映射$\varphi_a:G\to G$，使得对任意$x\in G$，$\varphi _a(x)=a\cdot x$，令$H = \{\varphi _a|a \in G\}$，则对于函数的复合运算"$\circ$"，$<H,\circ>$是群。

按闭结幺逆证明即可。

定义

设$<G, \cdot>$是群，$S$是$G$的==非空子集==。如果$<G, \cdot>$也是群，则称$<S, \cdot>$是$<G, \cdot>$的子群。

任意群$<G, \cdot>$都有两个天然子群，即它本身和幺元子群$<\{e\},\cdot>$，被称为平凡子群，其他情况的子群称为真子群。

此外，由群中一个元素，也可生成一个子群，为此，需要把群中元素的幂扩充到负指数的情形，即定义$a^{-k}=(a^k)^{-1}$

定理

设$<G, \cdot>$是群，$\forall x\in G$，记$S=\{a^n|n\in Z\}$，则$<S, \cdot>$是$<G, \cdot>$的子群。

把由群的一个元素$a$生成的子群记为$(a)$

定理 子群的幺元与群的幺元相同；对任意$a\in S$，$a$在$S$中的逆元就是$a$在$G$中的逆元

判别子群的方法：

定理设$<G, \cdot>$是群，$S$是$G$的==非空子集==。$<S,\cdot>$是$<G, \cdot>$的子群，当且仅当对于任何$a, b\in S$，$a\cdot b^{-1}\in S$

证明：

充分性：显然（闭，结，幺，逆）
必要性：

当$a=b$时，由题意知$a\cdot a^{-1}=e\in S$，所以S中存在幺元。

令$a=e$，那么当$b\in S$时，必有$e\cdot b^{-1}=b^{-1}\in S$，所以S中每元都有逆。

当$a,b\in S$时，由于$b^{-1}\in S$，就有$a\cdot b = a\cdot (b^{-1})^{-1} \in S$，所以满足封闭性。

可以证明：当$G$是有限集的时候，判别$<S, \cdot>$是否是$<G, \cdot>$的子群，只判别在$S$中是否封闭就行了。

交换群和循环群

定义 如果群$<G, \cdot>$的运算==满足交换率==，则称群$G$为==交换群（Abel群）==。

交换群又常被成为加群

定理 群$<G, \cdot>$为交换群的==充要条件==是：对任意$a,b\in G$，$(a\cdot b)^2=a^2\cdot b^2$

在交换群中，循环群有特殊地位

（循环群都是交换群）

定义 如果群$<G, \cdot>$中存在一个元$a$，是的$G$能由$a$生成，即$G=(a)$，则称$G$为==循环群==，称$a$是$G$的一个==生成元==。

$G = \{a^k|k \in G\}$

定义 设$<G, \cdot>$是群，$a\in G$，使得$a^n=e$的==最小正整数$n$==为元素$a$的周期。如果不存在这种最小正整数，则称$a$的周期为$\infty$

定理

设群$<G, \cdot>$中元素$a$的周期为正整数$n$，则：

$a^m=e$，当且仅当$n|m$

$a^i=a^j$，当且仅当$n|(i-j)$

由$a$生成的子群恰好有n个元素。

有限群的每个元素周期都是有限数。

循环群的任何子群都是循环群。

陪集与拉格朗日定理

定义

设$<H, \cdot>$是群$<G, \cdot>$的一个子群，$a\in G$，记$aH=\{a\cdot h|h\in H\}$，称$aH$是$H$在$G$中关于元$a$的==左陪集==。称$Ha=\{h\cdot a|h\in H\}$是$H$在$G$中关于元$a$的==右陪集==。由左（右）陪集构成的集合的基数称为==子群的指数==。

$eH=He=H$

$\forall x \in G,a\in Ha$

$H$关于同一元素的左陪集和右陪集可能不相同
凡是同属某个左（右）陪集的元素，它们对应的左（右）陪集也相同

定理设H是G的子群，$a\in Hb \Leftrightarrow a\cdot b^{-1}\in H \Leftrightarrow Ha=Hb$

证明：
1. 先证明$a\in Hb \Leftrightarrow a\cdot b^{-1}\in H$
  1. $a\in Hb,~\therefore a=h\cdot b(h\in H)$
    
    $\therefore a\cdot b^{-1}=h\in H$（h有逆元）
    
    $\therefore a\in Hb \Rightarrow a\cdot b^{-1}\in H$
  2. $a\cdot b^{-1}\in H$
    
    $\therefore a\cdot b^{-1}=h\in H$
    
    $\therefore a = h\cdot b\in Hb$
    
    $\therefore a\cdot b^{-1}\in H \Rightarrow a\in Hb$
  所以$a\in Hb \Leftrightarrow a\cdot b^{-1}\in H$
2. 再证明$a\cdot b^{-1}\in H \Leftrightarrow Ha=Hb$
  1. 证明$a\cdot b^{-1}\in H \Rightarrow Ha=Hb$
    1. $\forall x\in Ha,x=h_1\cdot a(h_1 \in H)$
      
      又$a\cdot b^{-1}=h_2\in H$
      
      $\therefore x=h_1\cdot h_2 \cdot b=(h_1\cdot h_2)\cdot b \in Hb$
      
      $\therefore Ha \subseteq Hb$
    2. 类似可证明$Hb\subseteq Ha$
    $\therefore Hb=Ha$
  2. 证明：$ Ha=Hbab^{-1}H $
    
    显然
任何两个左（右）陪集要么相同，要么无公共元素
所有左（右）陪集的元素数目相同

定理

设$H$是群$G$的子群，$a, b\in G$。在$G$中建立二元关系$aRb\Leftrightarrow b\in aH$，则$R$是$G$上的一个等价关系。

证明：

自反的：$a\in aH$，所以$aRb$
对称的：如果$aRb$，即$b\in aH$，则$bH=aH$，又因为$a\in aH$所以$a\in bH$，即$bRa$，对称性得证
可传递的：设$aRb,bRc$，根据定义存在$h_1,h_2\in H$，使$b=a\cdot h_1,c=b\cdot h_2$，于是$c=b\cdot h_2=a\cdot h_1\cdot h_2\in aH$，所以$aRc$成立

定理 R是上述等价关系，则$[a]_R=aH$

等价关系R可以确定群G的一个分划，每个左陪集就是分划中的一个块。$G=H\cup a_1H\cup a_2H\cup ...$称为G的左陪集分解式。

同时可以确定G的右陪集分解式$G=H\cup Ha_1\cup Ha_2\cup ...$

定理 群G中子群H的所有左（右）陪集都是等势的。

证明：只需证明任何$aH\sim H$。

构造映射$f:H\to aH$，对任何$h\in H,f(h)=a\cdot h$。这是双射函数。

定理拉格朗日定理

$n$阶群$<G, \cdot>$的任何子群$<H, \cdot>$的阶必定是$n$的因子。

由上述陪集分解式，显然。

推论 $n$元群$G$中任何元素的周期必是$n$的因子。

证明：

设$a\in G$，则$(a)=\{e, a, a^2, ..., a^{m-1}\}$是G的一个子群，故$m|n$,而$m$是元素$a$的周期，所以每个元素的周期必是$n$的因子。

正规子群与商群

定义 设$<H, \cdot>$是群$<G, \cdot>$的一个子群。如果对于任何$a\in G,aH=Ha$，则称$H$是$G$的==正规子群（不变子群）==。

任意群$<G, \cdot>$的平凡子群都是G的不变子群
交换群$<G, \cdot>$的任意子群$<H, \cdot>$都是G的不变子群
循环群$<G, \cdot>$的任意子群$<H, \cdot>$都是G的不变子群
素数阶群$<G, \cdot>$没有不平凡的不变子群

定理 群$<G, \cdot>$的子群$<H, \cdot>$是不变子群，==当且仅当==对任何$a\in G,aHa^{-1}\subseteq H$

证明：

$H$是$G$的正规子群，所以$aH=Ha$，即对任何$h_1\in H$，必有$h_2\in H$，使$a\cdot h_1=h_2\cdot a$，即$a\cdot h_1\cdot a^{-1}=h_2\in H$，充分性得证
如果对于任何$a\in G,aHa^{-1}\subseteq H$，即对于任何$h_1\in H$，都有$h_2\in H$，是$a\cdot h_1\cdot a^{-1}=h_2$，由此可得$a\cdot h_1=h_2\cdot a$，由$h_1,h_2$的任意性，可得$aH=Ha$，必要性得证。

定义设$<H, *>$是$<G, *>$的一个==正规子群==，$G/H$表示$G$的所有陪集的集合，则$<G/H, \cdot>$是一个群，称为==商群==。其中"$\cdot$"定义为$\forall aH,bH\in G/H,aH\cdot bH=(a*b)H$

群的同态与同构

定义

设$<S, \cdot>$和$<T, \circ>$是两个==代数系统==，其中“$\cdot$”和“$\circ$”分别是$S$和$T$的二元运算。如果存在映射$f:S\to T$使得对任意$a_1,a_2\in S,f(a_1\cdot a_2)=f(a_1)\circ f(a_2)$，则称$f$是$S$到$T$的==同态映射==，或者$S$和$T$==同态==，记为$S\sim T$；称$f(S)\subseteq T$为$S$的==同态像==。

当$f$是满射时，称$f$为==满同态==；当$f$是双射时，称$f$为==同构映射==。代数系统$S$和$T$同构记为$S\cong T$.

同态映射不仅确定了不同集合元素间的对应关系，而且还保持了代数系统的运算性质。

定理

设$f$是从代数系统$<S, \cdot>$到代数系统$<T, \circ>$的==同态映射==，则

如果运算”$\cdot$"在$S$中是封闭的，那么运算“$\circ$”在$f(S)$中也是封闭的。

$<S, \cdot>$满足结合律，则$<f(S), \cdot>$满足结合律

$<S, \cdot>$满足交换律，则$<f(S), \cdot>$满足交换律

$<S, \cdot>$存在幺元，则$<f(S), \cdot>$存在幺元

$S$中每元关于运算“$\cdot$”有逆元，那么$f(S)$中每元关于运算“$\circ$”也有逆元。$\forall x\in S, f(x^{-1})=f^{-1}(x)$

定理 如果$f$是代数系统$<S, \cdot>$到$<T, \cdot>$的满同态，那么

如果$S$是半群，则$T$也是半群

如果$S$是群，则$T$也是群

在同态映射下，像源的代数性质都为像集所具有，但像集所具有的代数性质像源未必能有。

如$<Z_2,> $是群，而$<N, +>$不是群。

$f$实际上是按一定模式把像源的元素进行归类。

定义 设$f$是使$<G, \cdot>$到$<H, \circ>$的同态映射，$e'$是$H$的幺元，记$Ker(f)=\{x|x\in G \and f(x)=e'\}$，则称$Ker(f)$为$f$的==同态核==

定理 设$f$是使$<G, \cdot>$到$<H, \circ>$的同态映射，则$f$的==同态核==$Ker(f)$是$G$的==正规子群==

证明：

先证$Ker(f)$是$<G,\cdot>$的子群

设$e'$是H的幺元

$\forall x, y\in Ker(f),\therefore f(x)=f(y)=e'$

$f(x\cdot y^{-1})=f(x)\circ f(y^{-1})=f(x)\circ f^{-1}(y)=e'\circ e'=e'\in Ker(f)$

所以$Ker(f)$是$<G,\cdot>$的子群
再证是正规子群

$\forall x\in G,k\in Ker(f)$

$f(x\cdot k\cdot x^{-1})=f(x)\circ f(k)\circ f(x^{-1})=f(x)\circ f^{-1}(x)=e'\in Ker(f)$

所以$Ker(f)$是$<G,\cdot>$的正规子群

环与域

环的定义及性质

定义

设$<R,+,*>$是含有两个二元运算的代数系统。如果满足

$<R,+>$是==交换群==

$<R,*>$是==半群==

$\forall a, b, c\in R,a*(b+c)=(a*b)+(a*c),(b+c)*a=(b*a)+(c*a)$

则称$<R,+,*>$是==环==

约定加法幺元记为$\theta$。

元$b$的加法记为$-b$，并且$a+(-b)=a-b$。

定理移项法则

设$<R,+,*>$是环，$a,b,c\in R$，则下面两条等价：

$a+b=c$

$a+b-c=\theta$

定理

设$<R,+,*>$是环$a,b,c\in R$，则：

$a*\theta =\theta *a=\theta$（加法幺元是乘法零元）

$a*(-b)=-(a*b)=(-a)*b$

$(-a)*(-b)=a*b$

$a*(b-c)=(a*b)-(a*c)$

$(b-c)*a=(b*a)-(c*a)$

证明：

$a*\theta=a*(\theta +\theta)=(a*\theta)+(a*\theta)$

由移项法则，得到$a*\theta = \theta$
$(a*(-b))+(a*b)=a*(-b+b)=a*\theta =\theta$

$\therefore a*(-b)=-(a*b)$

同理$(-a)*b=-(a*b)$
$(-a)*(-b)-(a*b)=(-a)*(-b)+a*(-b)=(-a+a)*(-b)=\theta *(-b)=\theta$

$\therefore (-a)*(-b)=a*b$

$a*(b-c)=a*(b+(-c))=(a*b)+(a*(-c))=(a*b)-(a*c)$
同4.

定义 设$<R,+,*>$是环，$a,b\in R$。如果$a\ne \theta,b\ne \theta$，而$a*b=\theta$，则称$a$和$b$是$R$中的==零因子==。

例如，当$m$不是素数时，$<Z_m,\bigoplus,\bigotimes>$有零因子，m是素数时有零因子。

n阶矩阵中存在零因子。

整环与域

定义

设$<R,+,*>$是==环==

如果$<R,*>$可交换，则称$<R,+,*>$为==交换环==。

如果$<R,*>$有幺元，则称$<R,+,*>$为==含幺环==。

如果1.2.成立，且无零因子，则称$<R,+,*>$为==整环==。

定理 设$<R,+,*>$是环，则$R$中无零因子，当且仅当对任何$a,x,y\in R$，当$a\ne \theta$时，由$a*x=a*y$，必然得到$x=y$。

定义 设$<R,+,*>$是环，$S$是$R$的==非空子集==，如果$<S,+,*>$也是环，则称$S$是$R$的==子环==。

定义设$<S,+,*>$和$<T,\bigoplus,\bigotimes>$是两个环，$f:S\to T$是映射。如果对于任意$a.b\in S$，都有\[f(a+b)=f(a)\bigoplus f(b),f(a*b)=f(a)\bigotimes f(b)\]，则称$f$是环$<S,+,*>$到$<T,\bigoplus,\bigotimes>$的==同态映射==。$f(S)$称谓$S$的==同态像==。当$f$是满射的时候，称$f$为==满同态==。是双射时，称$f$为==环同构映射==。

定义 设$<R,+,*>$是环，如果$<R,+>$和$<R-\{\theta\},*>$都是==交换群==，则称$<R,+,*>$是==域==。

定理 有限整环$<R,+,*>$必是域