离散数学-近世代数-代数结构.ppt

离散数学 Discrete Mathematics School of Mathematics and Computing Science 第四篇 代数系统 由集合以及集合上的运算组成的数学结构 称为代数结构（也称为代数系统）. 代数结构是抽象代数的一个主要内容. 研究的中心问题： 集合上的抽象运算及运算的性质和结构 。 什么是代数结构 研究意义：研究抽象代数结构的基本特征和基本 结构，不仅能深化代数结构的理论研究，也能扩 展其应用领域。 应用： 现代数学，如拓扑学、泛函分析，等 计算机科学：如 半群自动机、形式语言 群纠错码的设计 格和布尔代数计算机硬件设计、通讯系统设计 其他其他：代数方程求解、物理、化学 关于代数结构 主要内容 n n 第第1212章章 代数结构的概念代数结构的概念 n n 第第1313章章 半群与群半群与群 n n 第第1414章章 环和域环和域 n n 第第1515章章 格与布尔代数格与布尔代数 第第1212章章 代数结构的概念代数结构的概念 第第1 1节节 代数运算及其性质代数运算及其性质 第第2 2节节 代数结构的同态和同构代数结构的同态和同构 n重点： 代数结构的判定与构造，代数结构关系：同态、同构代数结构的判定与构造，代数结构关系：同态、同构 n难点： 同态基本定理同态基本定理 代数运算、代数结构 S是非空集合，映射 f: SnS称为S上的n元运算。 写法: f(a,b)=c可改写为: a f b=c 例如，在集合R上，对任意两个数所进行的普通加 法和乘法，都是在集合R上的二元运算。 由集合S及S上的封闭运算f1，f2，fk所组成的系统 就称为一个代数系统，记作, 或（ S，f1，f2 ,，fk）. 例1 Z; +, Z; -, ,N, - , T,F; , P(A); , 是否代数系统？ 需要满足的条件？ 对于集合A，称运算f: A B 是封闭的, 如果BA。 一个代数系统需要满足以下三个条件： l 有一个非空集合S； l 有一些建立在集合S上的运算； l 这些运算在S上是封闭的。 代数系统的基本概念 例 在整数集合 I 上定义 如下： 对任何 其中的+， 分别是通常数的加法和乘法 。 那么 是一个从 I 2 到 I 的函数， 易知 在集合 I 上是封闭的， 是 一个代数系统。 如果两个代数系统有相同个数的运算符，每个相 对应的运算符的元数是相同的，则称这两个代数系 统是同类型的。 定义：两个代数系统(U，)与(U，*) ，如果满足 下列条件： lU U； l若a U，bU，则a*b =a b；则称(U ，*)是(U，)的子系统或子代数 。 代数系统的基本概念 设有代数系统(S，*)，对a，b，cS，如果有 (a*b)*c= a*(b*c), 则称此代数系统的运算满足结合律 。 例：设A是一个非空集合， 是A上的二元运算，对于任意a ，bA，有ab=b，证明：是满足结合律的。 证： 对于任意的a，b ，c A， (a b)c= b c= c 而a(bc)=a c= c， (ab)c= a(bc) 是满足结合律的. 代数运算及其性质 交换律 设有代数系统(S，*)，如果对于a，b S，有 a*b = b*a，则称此代数系统的运算“ * ”满足交 换律。 例：在整合集合 I 上定义运算 ： 对任何 其中的 +， 分别是通常数的加法和乘法 。 可以满足交换律吗？ 分配律(左分配，右分配) 设有代数系统(S，*)，对a,b,cS，如果有 a(b*c)=(ab)*(ac)，则称 “”运算对“*”运算满足左分配律。 若“*”对“”满足a*(bc)=(a*b)(a*c)，则称 “*”对 “”满足左分配律 若有(a* b)c=(a* c)(b* c)，则称“” 对“*” 满足右分配律。 若(ab)*c=(a* c)(b* c)，则称“*”运算对“”运算满足右分配律。 例：代数系统(N，+，)。其中+，分别代表通常数的 加法和乘法。 是否满足交换律？ 单位元( 幺元) 一个代数系统(S，*)， 若存在一个元素eU ，使得对 xS，有：e * x =x * e = x，则称 e 为对于运算“ * ”的单位元,也称幺元 。 注意： 单位元是跟运算有关系的，不同的运 算可能单位元是不一样的。 左单位元或右单位元(左幺元或右幺元) 一个代数系统(S，)， 若存在一个元素elS，使得对 xS，有：elx =x，则称 el 为对于运算“ ”的左幺 元 。 若存在一个元素erS，使得对xS，有：x er=x， 则称 er为对于运算“ ”的右幺元 。 例 设代数系统(N，*)，* 的定义为： 对 那么，(N，*)有没有单位元？左幺元？右 幺元？ 解：对任何 因此 1 是右幺元。 但 1 不是左幺元，因为 所以(N，*)没有左幺元，当然也就没有幺元。 定理 n代数系统(U,)的单位元若存在，则唯一。 证：设 e 为运算“ ”的幺元，另有一单位元 e ， e是幺元，对xU，有ex =x，取x= e ，则e e = e 又 e是幺元，对xU，有x e =x，取 x=e，则e e =e 由 式可得： e =e，即幺元唯一。 零元 代数系统(S，)，如果存在一个元素S，使得对 xS有：x =x=，则称为对于运算“ ” 的零 元。 若只满足x =，则称为左零元。 若只满足 x=，则称为右零元。 例: 代数系统(I，)的零元是什么？ 在所有n阶方阵集合M上的代数系统(M，)，零元 是什么？ 在I+上定义一个二元运算取极小“Min”，( I+，Min) 的零元是什么？ 性质、定理 定理 一个代数系统，其零元若存在，则唯一。 定理 一个代数系统(S，)，若集合 A 中元素的个数大 于1，且该代数系统存在幺元 e 和零元，则e。 证明：用反证法，设=e，则对于任意的xA，必有 x = ex = x = e， 即对于A中所有元素都是相同的，这与A中含有多个元 素相矛盾。 逆元 一个存在幺元 e 的代数系统(U，)，如果对 U 中的 元素 x 存在 x-1，使得 x-1 x = x x-1 = e， 则称x-1为x的逆元。 若 x x-1 = e，则称 x-1 为 x 的右逆元。 若 x-1 x = e，则称 x-1 为 x 的左逆元。 既是左逆元，又是右逆元，则称 x-1 为 x 的一个 逆元。 例子 n对代数系统(R，*)，* 为二元运算，定义为通常 数的乘法。R为实数集合。 aR，a 0，a 的逆元是什么? n对代数系统(I，*)， * 为二元运算，定义为通常 数的乘法。I 为整数集合。 哪些元素有逆元？ n(R1，*)， * 为二元运算，定义为通常数的乘 法。 R1为除了 1 之外的实数集合。 哪些元素有逆元？ 注意 因此，关于逆元，下述结论是正确的： n当幺元存在时，才考虑逆元。 n逆元是针对具体元素而定的，有些元素可能有逆 元，有些元素则可能没有逆元。如果 a 和 b 都有逆 元且 a b，则 a-1 和 b-1 也不相同。 n一个元素的逆元必须是代数系统内的元素。 n设 e 幺元，只有当 a b = e 和 b a = e 同时时成立 时时，b才能是 a 的逆元，如果只有一个成立，b 也 不是 a 的逆元。 定理：设代数系统(U，)，运算“ ”满足结合律，且 存在幺元 e，那么对任意固定的 xU，若 x 有逆元，则 逆元是唯一的。 证明： 设 x 有两个逆元 x1-1和x2-1 ，则 x1-1 x x2-1 = x1-1 (x x2-1 )=x1-1 e=x1-1 同理 x1-1 x x2-1= (x1-1 x) x2-1 =e x2-1 = x2-1 所以：x1-1 = x2-1 设 * 是定义在集合A上的一个二元运算，如果对 于任意的xA，都有x * x = x，则称 * 运算是等 幂的。 例: S=1,2,4，在集合 p(S) 定义两个二元运算， ，分别表示集合的“并”运算和集合的“交” 运算，是等幂的？ 解：对于任意的A p(S) ，有AA=A；AA=A 因此运算，都满足等幂律。 等幂律 设集合S=， ，定义在S上的一个 二元运算如下表所示，试指出代数系统(S，)中 各个元素的左、右逆元情况。 解：是幺元， 是 的左逆元 ， 是 的右逆元 ； 是 、 的左 逆元， 、是 右逆元 ； 是 的左逆元 , 是 的右逆元； 是 的左逆元, 是 的右逆元。 例题 有限集合上运算的性质 n*是封闭的表上每个元素都属于S。 n*满足交换律表中元素关于主对角线对称。 n元素x为左零元x对应的行中每个元素都是x。 n元素x为右零元x对应的列中每个元素都是x。 n元素x为零元x对应的行中每个元素都是x且x对应的列中 每个元素都是x。 n元素x为左单位元x对应的行与表头的行完全相同。 n元素x为右单位元x对应的列与表头的列完全相同。 n元素x为单位元x对应的行与表头的行完全相同且x对应 的列与表头的列完全相同。 n元素x为左逆元x对应的行中至少有一个单位元。 n元素x为右逆元x对应的列中至少有一个单位元。 n元素x与元素y互为逆元x所在行与y所在列交叉位置元素 为单位元且x所在列与y所在行交叉位置元素为单位元。 * 代数结构之间的关系 为什么需要研究代数结构之间的关系？ 在研究代数结构的过程中，所关心的常常 是代数结过中运算所满足的性质，不关心具体的 运算，而对于遵循相同运算规律的系统只需要研 究其中一个就可以了解其它的系统. 考察下列代数: I, ; Q, +; R+, min; P(S), ; P(S), 此5个代数都有相同的构成成分:同样个数的运算 且对应运算元数相(1个二元运算); 满足同样的 Y运算律(交换律,结合律);存在单位元。 称具有这些性质的代数是同一类(代数结构的类) 设(U，)和(V，*)是两个同类型的代数系统, 与 * 都是二 元运算,如果存在映射f：UV，使得对x1，x2 U,有 f(x1x2)= f(x1)*f(x2)，称f是一个从(U，)到(V，*) 的同态映 射，或说(U，)与(V，*)是同态的。 若f是满射，则称f是(U，)到(V，*)的满同态映射， (U，) 与(V，*)是满同态。 若f是单射，则称f是(U，)到(V，*)的单同态映射， (U，) 与(V，*)是单同态。 若f是双射，则称f是(U，)到(V，*)的同构映射， (U，)与 (V，*)是同构的。 同态与同构 例 解：作映射 f ：IA， abc aabc bbab cacb 是偶数 是奇数 1. 设集合A=a，b，c，在A上定义运算。如下表， 那么， V1=(I，+)， V1=(A，)，其中 I 是正整数集合 ，+ 运算是普通的加法。V1 和V1是否同态态？ 2. 构造与之间的同态映射.(课堂练习) 例 解： 作双射 f：A1A2，f(1)=b, f(2)=d, f(3)=c, f(4)=a abcd abbbd baadb ccbca daacd *1234 14124 24234 31433 41211 设代数系统V1=(A1，*)，V2=(A2，)， 其中A1=1，2，3，4， A2=a，b，c，d， * 和 的运算分别别如下表，V1 和 V2 是否同构？ 例 n代数结构R+; *,R;+同构吗 ？ 证明：与同构 下面证明二者之间存在双射关系且满足同态方程 。 ni)建立双射关系： n 令f:R+R, f(x)=lnx n 显然，f是单射 n yR, x=ey 使y=lney =lnx=f(x) n f 是满射 n f是从R+到R的双射 nii)f 满足同态方程： n f(a*b)= ln（a*b）=lna+ lnb = f(a) + f(b) n综上，同构于 定理 设代数系统 和 其中*, ,*, ,都是二元运算，是V1到V2的满同态映 射，则 (1)如果*是可交换的，则*也是可交换的； (2)如果*是可结合的，则*也是可结合的； (3)如果*对是可分配的,则* 对也是可分配的； (4) 若e是*的单位元，则(e)是*的单位元; (5)若是*的零元，则()是*的零元; (6)若a关于运算*可逆，且逆元为b,则(a)关于运算* 也可逆，逆元为(b)。 性质保持 n1. 对于同构： 保持结合律、交换律、分配律；单 位元、逆元、零元相应存在. n2. 对于同态 单向保持性质 可以证明, 代数系统间的同构关系是等价关 系。 l自反： 构造映射f：U U, 满足 f(x)=x l对称: f是U到V的同构映射，则f-1是V到U 的同构映射。 l(U，)，(V，*)，(W，)，如果f是U到V 同构映射，g是V到W的同构映射，则可证 gof 是U到W的 同构映射。 代数系统间同构关系是等价关系 同态核 nf是一个从(U，)到(V，*) 的同态映射,e是(V ，*)的单位元。定义集合 K(f)=x xS且f(x) e为同态核，记为K(f)。