抽象代数 Abstract Algebra.

Presentation on theme: "抽象代数 Abstract Algebra."— Presentation transcript:

1 抽象代数 Abstract Algebra

2 本部分所要探讨的数学结构是由集合上定义若干运算而组成的系统——称为代数系统(代数结构)。

3 几个问题 1.项链问题：用n种颜色的珠子做成有m颗珠子的项链，问可做成多少种不同类型的项链?
3.图的构造与计数问题 4.开关线路的构造与计数问题：用n个开关可以构造出多少种不同的开关线路? 5.数字通信的可靠性：如何设计高效的检错码与纠错码？ 6.代数方程根式求解问题：五次方程有根吗？ 7.网络规划 8.信息安全 9.语言：某语言L的语法语义？程序的结构（数据表示？算法构造？），根据L编写的程序是正确的吗？ 10.计算复杂性：该问题可计算吗？计算机能/不能计算吗？计算复杂性如何？

4 关于抽象代数 “…时至今日，数学家们还在忙于发展简单的计算方法，也就是在一切数学领域中的所谓算法。一旦我们有了算法，所有的其他事都留给了计算机。计算机所作的不再是数学了，但为了使用计算机，需要数学和数学家。”  ——H.Freudenthal “模型化是数学中的一个基本概念，它处于所有的数学应用之心脏，也处于某些最抽象的纯数学核心之中。” ——R.C.Buck 数学之所以重要，其中心原因就在于它提供的数学系统丰富多彩；此外的原因是，数学给出了一个系统，以便于使用这些模型对物理现实和技术领域提出问题、回答问题，并且也就探索了模型的行为。 ——R.C.Buck &.E.F.Buck

5 关于抽象代数 古典代数 代数系统(系统化：模型及其性质)； 纯数学结合计算机应用。
计算机科学：计算？ 计算过程？——能行性计算模型：抽象与具体化。 组合学 计算机科学中的代数方法： 形式语言与自动机理论、可计算理论、语义学（模型论）——模型/语言。 集合代数、逻辑代数 密码学、数据表示理论、数字逻辑 未来的计算机 其他：代数方程求解、物理、化学 思维训练 有关科学家：Von Neumann、Abel、Galois

6 Niels Abel A statue of Abel in Oslo

7 Evariste Galois A drawing done in 1848 from memory by Evariste's brother. This is taken from a French stamp

8 主要内容 第6讲 代数结构 第7讲 群代数 第8讲 格与布尔代数

9 第6讲 代数结构 6.0 研究代数结构的方法？ 6.1 什么是代数结构？ 6.2 代数结构间的关系？ 6.3 同余关系 1.研究集合的方法？
2.研究数理逻辑的方法？ 3.研究代数结构的思路？ 6.1 什么是代数结构？ 1. 初等代数？ 2. 高等代数？ 6.2 代数结构间的关系？ 6.3 同余关系 重点： 代数结构的判定与构造 代数结构关系：同态、同构 特殊关系：同余关系 难点： 同余关系、同态基本定理

10 6.1 什么是代数结构？ 代数结构？〈S;O〉 6.1.1 集合运算代数结构 集合S？ 运算O？
例1 〈Z;+,*,-〉, 〈Z;-,*,_〉,〈N,-〉, 〈{T,F}; ┐,∧,∨〉, 〈P(A); ∪,∩〉，〈∑*; *〉 需要满足的条件？ 法则，运算，运算的阶？ （n-ary operation） 运算的在某个集合下的封闭性？ 设o是集合A上的一个n元运算，非空集合S  A，如果对于每一个(a1，a2，…，an)∈S，都有o(a1，a2，…，an)∈S，则称S在运算o下是封闭的，或o在集合S上是封闭的。 集合S？ 运算O？ 代数结构？〈S;O〉

11 6.1 什么是代数结构？ 运算封闭性：若x，y∈A，有x * y∈A，称*在A上是封闭的
例2 ： A={x｜x=2n，n∈N}， 问<A，*>运算封闭否，<A，+>，<A，/>呢？ 解：2r，2s∈A， 2r x 2s=2r+s∈A （ｒ＋ｓ∈Ｎ） ∴<A，x>运算封闭 2，4∈A，2+4A，∴<A，+>运算不封闭 2，4∈A，2/4A， ∴<A，/>运算不封闭

12 6.1 什么是代数结构？ 6.1.2 运算性质、特殊元素 请思考：如何应用运算表 （矩阵）来判断右述性质？ 满足封闭性 结合律 交换律
(左/右)分配律、消去律、吸收律 幂等元(Identity lement) (左/右)单位元(Idempotent element) (左/右)零元 (Zero element) (左/右)逆元 (Inverse)

13 6.1 什么是代数结构？ 6.1.2 运算性质、特殊元素 满足封闭性：运算表中每一个元素a∈S 结合律：构造表来判断
交换律：关于主对角线对称 (左/右)分配律、消去律、吸收律 等幂律(幂等元)：主对角线上元素与其所在表头元素同 (左/右)单位元:某元素x其相应行/列与表列/行头元素同 (左/右)零元:某元素x与其所在的行/列元素全相同 (左/右)逆元:首先,是否存在单位元？元素x所在的列/行的单位元相应的行/列头元素即其逆元

14 6.1 什么是代数结构？ 例3 a）〈P（S）；∪,∩〉 对运算∪，是单位元， S是零元， 对运算∩，S是单位元 ，是零元。
b）〈N；+〉 　　有单位元0，无零元。

15 6.1 什么是代数结构？ c) 代数A=〈{a，b，c}； 。 〉用下表定义：
从运算表可以看出，b是左单位元，无右单位元；a是右零元，b是右零元，无左零元; 。 a b c 运算：不满足交换律？

16 6.1 什么是代数结构？ * a b c d) 代数〈R，*〉中，除零元0外所有元素均有逆元 e) A=〈{a，b，c}，*〉由下表定义：
a的右逆元为c，无左逆元，b的逆元为b， c的右逆元为空，左逆元为a * a b c

17 6.1 什么是代数结构？ f）代数结构：A=<{0，1，2，…，k-1}，*k>
*k称为模k乘法求余（x*ky或记为resk(x*y))。 零元？单位元？关于逆元？ g) 实数集R上的二元运算*：a*b=a+b-ab是否有单位元、零元与幂等元，如果有单位元，哪些元素有逆元？

18 6.1 什么是代数结构？ 示例4 关于逆元的性质（教材定理7.2）
对于可结合运算ο ，如果元素X有 左逆元ｌ， 右逆元r，则l=r=x-1 。 推论：逆元若存在，则唯一 分析：设e为单位元， l=ｌοｅ＝ｌο(xοr)=(ｌοx)οｒ＝ｅοｒ＝ｒ ∴逆元存在为r. 若存在X的另一个逆元r’; 则: r’＝r’οｅ=r’ο(xοr)=(r’οx)οr=ｅοr ＝r

19 6.1 什么是代数结构？ 思考 是否存在零元可逆的代数结构？

20 6.1 什么是代数结构？ 6.1.3 子代数(Subalgebra)
同余类代数{0,2}；+4是{0,1,2,3}；+4的子代数吗?

21 6.1 什么是代数结构？ 6.1.4 半群(Semigroup)、单位半群(独异点,Monoid) 结合性、单位元

22 6.1 什么是代数结构？ 例5 a) 代数结构〈N；*〉,〈{0，1}；*〉 是半群，是独异点吗？ 是〈R，*〉的子半群,子独异点吗？代数结构〈R，-〉是半群吗？ b) 设s={a，b}，*定义如右表，<S；*>是半群吗? 注意到a，b都是右零元 ∵x,y,zs ① x*ys ∴运算封闭 ② x*（y*z）=x*z=z （x*y）*z=z ∴结合律成立 ∴<S；*>是一半群，该半群称为二元素右零半群 * a b

23 6.1 什么是代数结构？ 练习 1 独异点运算表中任何两行两列均不相同. 2 <Σ∗，>是一个半群吗?
3 若半群〈A，*〉的单位元为e,a，bA，若a，b均有逆元，则 1)（a-1）-1=a; 2)（a*b）-1=b-1*a-1 。 试证明之. 4 有限半群必有幂等元?

24 6.1 什么是代数结构？ 有限半群必有幂等元. 证明 设<S；*>是有限半群，需证 aS，有a*a=a。
对bS，由运算封闭性，有b2=b*bS,进一步利用可结合性可得b3，b4，…S。 又S有限，故存在i，jN，j>ｉ 使得bi=bj。 从而有bi=bj=bj-i*bi。 现令p=j-i，则对任意qN，q≥i时, 有 bq= bq-i*bi=bq-i*bj=bq- i*bj-i*bi=bq-i*bp*bi=bp*bq。 又p≥1，则存在q≥i，qN，且有kN，使 q=kp， 从而有bkp=bp*bkp=bp*(bp*bkp)=…=bkp*bkp， 令a=bkpS 则a*a=a，即a=bkp是<S；*>的幂等元。

25 6.2 代数结构间的关系 为什么需要研究代数结构之间的关系？
在研究代数结构的过程中，所关心的常常是代数结过中运算所满足的性质，不关心具体的运算，而对于遵循相同运算规律的系统只需要研究其中一个就可以了解其它的系统.——抽象代数！ 考察下列代数: A1=I;; A2=Q;+; A3=R+;min;A4=(S);∩; A5=(S);∪. 此5个代数都有相同的构成成分:同样个数的运算且对应运算元数相 (1个二元运算); 满足同样的公理规则(交换律,结合律);存在单位元。 ——称具有上述性质的代数是同一类(代数结构的类) 例 5 教材P129例2：逻辑代数——开关电路

26 6.2 代数结构间的关系 6.2.1 同态关系、同构关系 例6：代数结构〈R+; *〉,〈R;+〉同构吗？
对于两代数结构设V1=<A;O1 , O2 , … , Or>和 V2=<B; *1 , *2 , … , *r > 1)是同型的代数结构 2)存在从A到B的一个映射/满射/单射/双射f 3)运算性质保持（保运算性，满足同态方程）：对于ki元运算Oi(i=1，2，…，r)，若任意(x1，x2…，xki)∈Aki，都有 f(Oi(x1，x2…，xki))= *i(f(x1)，…，f(xki))， 则称f是V1到V2的一个同态/满同态/单同态/同构映射，并称V1与V2 同态(Homomorphic) /满同态/单同态/同构的(Isomorphic) 。 例6：代数结构〈R+; *〉,〈R;+〉同构吗？

27 6.2 代数结构间的关系 证明： 显然， <R+,*>与<R,+>为同型代数结构，
下面证明二者之间存在双射关系且满足同态方程。 i)建立双射关系： 令h:R+R,h(x)=lnx 显然，h是单射 yR,x=ey使y=lney =lnx=h(x) h是满射 h是从R+到R的双射 ii)h满足同态方程： h(a*b)=ln（a*b）=lna+lnb=h(a)+h(b) 综上，<R+,*>同构于<R,+>

28 6.2 代数结构间的关系 这样，利用同态/同构关系，可以转移运算，复杂的代数系统可以压缩为另一简单的代数系统。
A B f * + 思考：请你举例说明上述系统转换思想。

29 6.2 代数结构间的关系

30 6.2 代数结构间的关系 勒让德(法国数学家)的遗憾：
勒让德晚年看到阿贝尔的工作时，曾深感遗憾地说：他在椭圆积分方面的工作几乎耗尽他后半生的精力，但与阿贝尔的工作相比，简直是微不足道的，悔恨他自己为什么始终没有从另一条思路——将反函数复化(逆向思维、扩展思维等)去考虑问题。 Adrien-Marie Legendre

31 6.2 代数结构间的关系 例7 a) 请判断〈{T,F}; ∧〉,〈{T,F}; ∨〉是否同构。
b) 请判断〈∑*; ·〉,〈N;+〉是否同构，运算“·”表示字符串的连接， “+” 为一般的加法运算。 c) 代数结构〈I;+,*〉,〈Nm;+m, *m〉是否同态？其中， 运算+m, *m分别是模m加、乘。 d)〈I;+〉,〈2I;+〉同构吗？ e) 代数结构<R+; *>,<R; +>同构？*、+为一般的乘法、加法运算。 f) 设<I+; *>与<E; *>是代数结构，其中I+为正整数集，E为正偶数 集，*分别为一般的乘法运算，h为R上的映射，对任意x∈I+， h(x)=2x。试证明：h不是<I+; *>到<E; *>的同构映射，并证明<I+; *>与<E; *>不同构。

32 6.2 代数结构间的关系 证明 显然，h是I+到E的双射，对任意x，y∈I+，有h(x*y)=2xy， 但h(x)*h(y)=4xy,
显然h(x*y)≠h(x)*h(y)。 故，h不是<I+; *>到<E; *>的同构映射。 h不是<I+; *>到<E; *>的同构能说明<I+; *>与<E; *> 就一定不同构吗？

33 6.2 代数结构间的关系 6.2.2 性质保持 思考 设代数结构<X；ο>与<Y；*>同构，若<X；ο>存在单位元ex，则 <Y；*>亦存在单位元ey，且有g(ex)=ey。 证明： 对 yY，x Y，使得y=g(x), 于是，由<X；ο>与<Y；*>同构，且<X；ο>有单位元ex， 有 g(ex)*y= g(ex)*g(x)=g(exοx)=g(x), 且y*g(ex)= g(x)*g(ex) =g(xοex)=g(x)， 故g(ex)*y= y*g(ex)。 所以<Y；*>的存在单位元ey且 g(ex)= ey。

34 6.2 代数结构间的关系 6.2.2 性质保持 1 对于同构： 保持结合律、交换律、分配律；单位元、逆元、零元相应存在（教材的证明请自学）
同构关系是一种等价关系？ 2 对于同态 单向保持性质 f X Y

35 6.2 代数结构间的关系 示例8（教材例7.19） 如果f为代数结构<S, *>到<S′,*′>的同态，并且S′中有单位元e′，那么称集合K（f）={x  xS  f（x）＝e′}为同态f的核（kernel），记为Ker（f）。 2)证明：f是单同态充要条件是Ker(f)={e}; 3)证明：如果Ker（f）≠ ，那么< Ker（f）, *>为<S ,*>的子代数。

36 6.3 同余关系 1 为什么研究同余关系？ 2 等价关系同余关系 等价类商集 集合上的等价关系？ 添加运算之后……？
模型转换/压缩之关键：知识（性质）的保持

37 6.3 同余关系 同态三角形 h(满同态) V=<S;o> V’=<S’;*> f (同构) g (自然满同态)
如何寻找一个代数结构的压缩结构？ ——变换 h(满同态) V=<S;o> V’=<S’;*> f (同构) g (自然满同态) V/ρh=<S/ρh;> 集合论： 函数——等价关系——划分 代数结构： 同态——同余关系——可允许划分

38 6.3 同余关系 6.3.1 同余关系 原始含义（示例）： 代数结构<Z;+>在Z上的关系R定义如下：
xRy  x≡y(mod 2)， 且满足如下推理： xRy且 zRw  (x+z)R(y+w)（*） 这样，上述利用余数相等建立的满足（*）推理式的关系R称为同余关系。

39 6.3 同余关系 推广 1 <Z;*>, R: xRy  x ≡ y(mod m), m∈Z+
2 恒等关系是整环上的同余关系吗？ 3 <Z;+>, R={(x, y)|x/y=2m, m∈Z}

40 6.3 同余关系 同余关系(Congruence)
<A, * >是一个代数系统,R是A上的等价关系,若<a,b>R, <c,d>R<a * c , b * d>R，称R是A上的同余关系(R对于运算*满足代换性质). 左同余、右同余 同余关系将A划分得到的等价类称为 可允许划分(同余类)： 对于代数结构<A;*>, ={A1,A2,…,An}是A上的一个划分，若对于任意的划分块Ai, Aj ∈ ,存在Ak ∈,使得：Ai*AjAk,则称为可允许划分。

41 6.3 同余关系 例12：<I,+>，在I上定义R:<x,y>R|x|=|y|,
问R是<I,+>的等价关系吗？是否是同余关系? 解: 1)自反性：xI, |x|=|x| ，从而<x,x>R 2)对称性：x,yI，若<x,y>R则|x|=|y|，从而<y,x>R 3)传递性：x,y,zI，若<x,y>R,<y,z>R 由|x|=|y|=|z| 知<x,z>R 所以 R是一等价关系。 对x1,y1,x2,y2I，若<x1,y1>R,<x2,y2>R， 但<x1+x2,y1+y2>R不一定成立，例如， <1,-1>R,<2,2>R但<1+2,-1+2>R 综上，R是等价关系但不是同余关系

42 6.3 同余关系 6.3.2 同余关系商代数 思考 1 设f是代数结构<A;*>到<B;+>的同态映射，则关系
ρf ={(x,y)|f(x)=f(y),  x,y  A} 是<A;*>上的同余关系。 2 是否可以根据ρf定义一个<A;*>的满同态代数结构？

43 思考1 分析： 推广同余定理 首先， ρh是否为等价关系？ 其次， ρh对ºi都满足代换性质(iZ+ ) ？
设h是一个代数结构，即V=〈S；º1，º2，…，ºn〉到代数结构V*=〈S*；*1,*2,...〉的同态，其中所有ºi都是一元运算，(i=1，2，…，n)是经h传递到的运算。在S上定义一个关系ρh，使得当且仅当h(x)=h(y)时xρhy，则ρh是V上的同余关系。

44 6.3 同余关系 思考2 分析： 等价类之间的运算？ 推广 商集，及其上之运算 商代数 同余关系基集？ 等价关系：等价类（集合）？
基集之上运算？ 等价类之间的运算？ 推广 商集，及其上之运算 商代数

45 6.3 同余关系 同余关系商代数(Quotient algebra) 商代数：V/ρ=<S/ρ;o’> 运算o’的定义？
 o’([x])=[o(x)] 代数结构：V=<S; o> （o为一元运算） V上同余关系：ρ 商代数：V/ρ=<S/ρ;o’> 运算*的定义？  [x] o’ [y]=[xoy] 代数结构：V=<S; o> （o为二元运算） V上同余关系：ρ

46 6.3 同余关系 进一步思考 关于商代数的运算的一般性证明 1)运算o’是否在V/ρ下封闭？
2)针对定义，请问[x] o’ [y]值是否唯一？ 设R是代数结构<S; *>上的等价关系，对于[a]，[b] S/R, 定义 [a] o[b]=[a*b] 则o为S/R上的二元运算当且仅当R为<S; *>上同余关系。

47 6.3 同余关系 证明 必要性 设o为<S; *>上二元运算。对a, b, c, d S,若aRb，cRd，即[a]=[b],[c]=[d], 则[a] o[c]=[b] o[d], 又有[a] o[c]=[a*c], [b] o[d]=[b*d]。从而[a*c]=[b*d]。 于是a*cRb*d。故R为<S; *>上同余关系。 充分性 设R为<S; *>上同余关系，任意[a],[b] S/R， 显然[a] o[b]=[a*b] S/R，即o在S/R上满足封闭性，还需证对任意[a],[b] S/R，[a] o[b]值惟一。 注意到，[a] o[b]=[a*b]，a*b值是惟一的，[a*b]是惟一的。因此，需要证明若[a]，[b]取其它代表元，如a′,b′，其值[a′*b′]与[a*b]是否相等。 对a′[a], b′[b],有a′Ra, b′Rb, 则a′*b′Ra*b 且有[a′]=[a], [b′]=[b]。于是[a′] o[b′]=[a′*b′] =[a*b]=[a] o[b]。这说明[a] o[b]的运算结果与等价类的代表元无关，值是惟一的。 故o是S/R上的二元运算。 综上，命题得证。

48 6.3 同余关系 6.3.2 同态基本定理 设代数结构V=<S; *>, V′=<S′; *′>, h是从V到V′的满同态映射，则 1) 在S上定义一个关系ρh，使得当且仅当h(x)=h(y)时xρhy，则ρh是V上的同余关系（同余定理）； 2) 由ρh可以得到V的商代数<S/ρh; o>，记为V/ρh，且存在V到V/ρh的满同态映射(自然同态)g； 3) V/ρh与V′同构。

49 6.3 同余关系 同态三角形 h(满同态) V=<S;o> V’=<S’;*> f (同构) g (自然满同态)
如何寻找一个代数结构的压缩结构？ ——变换 h(满同态) V=<S;o> V’=<S’;*> f (同构) g (自然满同态) V/ρh=<S/ρh;> 集合论： 函数——等价关系——划分 代数结构： 同态——同余关系——可允许划分

50 6.3 同余关系 自然同态？ 1 容易证明V与V/ρ同态，可以认为当同余关系ρ确定之后， 该同态g就自然成立； ——自然同态！
2 进一步，可以证明，该同态的“等价核”，就是同余关系ρ 本身 g的等价核： K={(x,y)|x,y  G且g(x)= g(y)} ={(x,y)|x,y  G且[x] ρ =[y] ρ} ={(x,y)|x,y  G且xρy} = ρ

51 6.3 同余关系 同态三角形的同构性的证明： 1 同型：Vρh 与 V’同型？ 2 双射： 定义映射f，并证明其为双射
定义映射f：因为h是一个从S到S’的满射， S/ρh为可允许划分，所以对于每一个[x]ρh∈ S/ρh必存在惟一x’∈S’，使得x’=h(x)，于是可以如下定义函数：f: S/ρh → S’ ，使得f([x]ρh)=x’=h(x)。 f为满射：对于任意x’∈S’ ，必存在 x∈S，使得h(x) =x’，从而存在[x] ρh ∈S/ρh， ，使得f([x]ρh)=h(x)=x’ ，所以f是满射。 f为单射：若h(x)=h(y)，则xρhy，于是[x]ρh=[y]ρh，所以f是单射 3 满足同态方程 由于 f([x]ρh [y]ρh)=f([xoy]ρh)=h(xoy)=h(x)*h(y)=f([x]ρh)*f([y]ρh) 所以，前述运算与双射满足同态方程。 综上， Vρh 与 V’同构。

52 思考 如果上述同构证明过程中，将映射改f改为从S’ 到S/ρh ，则如何描述具体证明过程？

53 小结与作业 小结 作业 本章介绍了抽象代数的基本概念，是后续章节学习的基础，主要知识点有： 1）代数运算的概念及其性质；
2）代数结构的概念； 3）代数结构中特殊元素； 4）半群； 5）同态与同构； 6）同余、商代数，同态基本定理。 其中，运算以及代数结构的概念，特殊元素的判定，同态、同构的证明是学习的重点。 作业 1 反复阅读教材(结合例题、练习) 、思考 2 书面作业：p136——2、6、9、11、12、13、15、19、20、21