《第4章%20代数结构2ppt.ppt》由会员分享,可在线阅读,更多相关《第4章%20代数结构2ppt.ppt(36页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、广东工业大学计算机学院,1,第四章 代数结构,4.1(2) 同构与同态两个代数系统之间的联系,2,回顾:函数的分类,设 f: AB是一个函数,(1) 单射 ai、aj,aiA, ajA, 若 ai aj, 都有: f (ai) f (aj), 则称 f 为从A到B的单射(injection)函数。自变量不同,函数值也不同的函数为单射函数。(2) 满射 若f(A) = B, 则称f 为从A到B的满射(surjection)。(3) 双射 若f 既是单射又是满射, 则称f 为从A到B的双射(bijection)。,3,代数系统的关系,1. 同构同构的定义自同构的定义2. 同态同态的定义同态的性质,
2、4,1. 同构:定义,定义同构设, 是代数系统,如果存在A到B的双射函数f,使得对于A中任意元素a和b都有:f(a * b) = f(a) f(b)则称f为到的同构映射;称同构于或称与同构,记作AB ;称是的同构象如果, 是同构的,集合A和B的元素之间必须存在一一对应关系,并且这种关系能在各自的运算中保持。,5,1. 同构,直观描述同构如果两个代数系统, 具有相同的特征和相同的结构,则称这两个代数系统是同构的。例如, , ,,6,同构举例1,例1:设和是代数系统,其中A = a, b, c, d, e,运算*和5的运算表如下所示,和同构吗?,设双射函数:f(a) = 0; f(b) = 1;
3、f(c) = 2; f(d) = 3; f(e) = 4,f(a * b) = f(a) f(b),7,同构举例2,例2:设N+是正整数集合,A = x | x = 2n, n N+,即 A = 2, 22,23,,对于普通加法+和普通乘法运算, 证明与同构。证明:构造A到N+的映射f:f(2k) = k对于A中任意元素2i, 2j,都有 f(2i2j) = f(2i+j) = i + j = f(2i) + f(2j)又 f(2k) = k是AN+上的双射函数(注意:不能漏这步) f是同构映射,(A, )和(N+, +)同构. 证毕问题: 如何构造N+到A的同构映射f?f(k) = 2k,f
4、(a * b) = f(a) f(b),8,代数系统的关系,1. 同构同构的定义自同构的定义2. 同态同态的定义同态的性质,9,自同构定义,定义自同构设是代数系统,f是到的同构映射, 即对任意a, b, A, 有f(a * b) = f(a) * f(b)则称f为的自同构映射.,10,自同构举例1,例1: 设在代数系统中, 令f是从N4到N4的双射函数, 且有:f(k) = k (k = 0, 1, 2, 3) 问:f是的自同构映射吗?回答:是 再问:是否存在的其它自同构映射? 令g是是从N4到N4的双射函数, 且: g(0) = 0; g(1) = 3; g(2) = 2; g(3) = 1
5、 则g是的自同构映射。,从本题可看出:自同构映射不一定唯一。,11,自同构举例2,例2:设有代数系统,+是普通加法。设定函数f:f(r) = 2r 问:f是不是到的自同构? 解: 对于x, y R, f(x + y) = 2(x + y) = 2x + 2y f(x) + f(y) = 2x + 2y 因此,f(x + y) = f(x) + f(y) 又因为f是双射函数, 所以,f是到的自同构映射。,f(a * b) = f(a) * f(b),12,同构小结,1. 同构判定的关键在于构造恰当的双射函数.2. 当两个代数系统同构时,它们具有完全相同的结构和特征,或者说它们“在本质上是一致的”
6、,只是使用了不同的符号表示。 因此,可以把两个同构的代数系统可作是同一个代数系统。3.设S 是代数系统的集合, 则S上代数系统之间的同构关系是等价关系.将S上的同构关系表示为R: A1RA2当且仅当 A1A2.显然, R具有自反性、对称性和传递性,13,代数系统的关系,1. 同构同构的定义自同构的定义2. 同态同态的定义同态的性质,14,同态,同态是同构概念的推广;同构是同态概念的特例。定义同态设和是代数系统,如果存在A到B的函数f使得对于A中任意元素a和b都有:f(a * b) = f(a) f(b)则称f为到的同态映射;称同态于,简记为AB ;称为的同态象如果f是到的同态映射,则称f为自同
7、态映射。,与同构区别1:同构:双射函数同态:一般函数,与同构区别2:同构的同构象:同态的同态象:, f(A) B,15,同态举例1,例1. 设有代数系统到, +和分别是普通加法和普通乘法。现定义映射f:x R, f(x) = ex 问: f是否到 的同态映射? 解:由x1, x2 R, f(x1+x2) = ex1+x2 f(x1)f(x2) = ex1ex2 = ex1+x2 故f(x1+x2) = f(x1)f(x2) f是到的同态映射。,f(a * b) = f(a) f(b)f(a + b) = f(a) f(b),问题:是否与同构?,f(x) = ex是不是RR+上的双射函数?,16
8、,同态举例2练习,例2. 设有代数系统到, 是普通乘法。现定义映射g:x R, g(x) = ex 问:g是否 到的同态映射? 解:由x1, x2R, g(x1x2) = ex1x2 g(x1) g(x2) = ex1ex2 = ex1+x2 在一般情况下g(x1x2)g(x1) g(x2) g不是到同态映射,f(a b) = f(a) f(b),17,自同态举例,例:设代数系统V = , R为全体实数, 为普通乘法。 判断下面的哪些函数是V 的自同态映射? (1) f(x) = |x| (2) f(x) = 2x (3) f(x) = x2 (4) f(x) = 1/x (5) f(x) =
9、 x (6) f(x) = x+1解:(2) , (5), (6) 不是自同态. (1) 是自同态, f(xy) = |xy| = |x| |y| = f(x) f(y) (3) 是自同态, f(xy) = (xy)2 = x2 y2 = f(x) f(y) (4) 是自同态, f(xy) = 1/(xy) =1/x 1/y = f(x) f(y),f(a * b) = f(a) * f(b),18,同态的分类,设f为由到的一个同态映射。如果f是从A到B的满射,则f称为满同态;如果f是从A到B的单射,则f称为单一同态;如果f是从A到B的双射,则f称为同构映射,并称和同构,记作AB。,19,同态
10、的分类举例,例:令f是N3到N6的函数,且有f(0) = 0, f(1) = 2; f(2) = 4。试证明:f是到的同态映射,且f是单一同态但不是满同态。证明:为简化证明,用单一形式表示a k b:a k b = a + b k (a + b) / k 由f的定义可知:f(k) = 2k (k = 0, 1, 2) 对于N3中任意元素a和b,则有: f(a 3 b) = 2(a 3 b) = 2(a + b - 3 (a + b) / 3 ) = 2a + 2b - 6 (2a + 2b) / 6 = 2a 6 2b = f(a) 6 f(b) f是到的同态映射。 f是单射函数,f是单一同态
11、; 而f(N3) = 0, 2 , 4 N6, f不是满同态,20,代数系统的关系,1. 同构同构的定义自同构的定义2. 同态同态的定义同态的性质,21,同态的性质封闭性,1. 封闭性 设f是代数系统到的同态映射,是同态象,如果*运算关于A是封闭的,则运算关于f(A)也是封闭的。 证明:任选a, b f(A), 由f是同态映射可知:必存在x, y A, 使得 f(x) = a 和 f(y) = b 运算*关于A是封闭的 x * y A f(x * y) f(A) 又 f(x * y) = f(x) f(y) f(x) f(y) f(A) 即: a b f(A) 关于f(A)也是封闭的,22,同
12、态的性质可结合性,2. 可结合性设f是代数系统到的同态映射,如果*运算在A上是可结合运算,则同态象中运算也是可结合运算。 证明:任选a, b, c f(A), 由f是同态映射可知:必存在x, y, z A, 使得f(x) = a; f(y) = b; f(z) = c (a b) c = (f(x) f(y) f(z) = f(x * y) f(z) /* f(x * y) = f(x) f(y) */ = f(x * y) * z) /*同态定义*/ 运算*在A上是可结合运算, f(x * y) * z) = f(x * (y * z) = f(x) f(y * z) /*同态定义*/ =
13、f(x) (f(y) f(z) = a (b c) 即: (a b) c = a (b c) 中运算是可结合运算。,23,同态的性质幺元存在判定,3. 幺元存在判定设f是代数系统到的同态映射,如果中含有幺元,设为e,则f(e)为中的幺元。 证明:任选a f(A), 则必存在x A, 使得f(x) = a。 而 f(e) a = f(e) f(x) = f(e * x) /* f(x * y) = f(x) f(y) */ = f(x) = a /*同态定义*/ f(e) a = a 因此,f(e)为的左幺元。 同样有: a f(e) = f(x) f(e) = f(x * e) /*同态定义*
14、/ = f(x) = a a f(e) =a 因此, f(e)为的右幺元。 f(e)为的幺元,24,同态的性质幺元存在判定,4. 零元存在判定设f是代数系统到的同态映射,如果中含有幺元,设为,则f()为中的幺元。 证明:任选a f(A), 则必存在x A, 使得f(x) = a。 而 f() a = f() f(x) = f( * x) /* f(x * y) = f(x) f(y) */ = f() /*零元定义*/ f() a = f() 因此,f()为的左零元。 同样有: a f() = f(x) f() = f(x * ) /*同态定义*/ = f() a f() = f() 因此,
15、f()为的右零元。 f()为的零元,25,同态的性质逆元存在判定,5. 逆元存在判定设f是代数系统到的同态映射,如果中每个元素都有逆元, 则同态象中每个元素也都有逆元。证明: 中的元素存在逆元, 中必存在幺元, 不妨设为e, 则同态象中必存在幺元f(e) 任选a f(A), 则必存在x A, 使得f(x) = a, 且x-1 A, f(x-1) f(A) f(x-1) a = f(x-1) f(x) = f(x-1 * x) /* f(x * y) = f(x) f(y) */ = f(e) /*同态定义*/ 同样有: a f(x-1) = f(x) f(x-1) = f(x * x-1) /
16、*同态定义*/ = f(e)a的逆元是f(x-1). 由a的任意性,同态象中每个元素也都有逆元,a和b互为逆元的条件:b * a = e (e为幺元)a * b = e (e为幺元),26,如何求同构映射,1、观察运算表,27,利用特殊元素,若两个代数系统和同构,则到的同构映射f满足: 零元映射为零元; 幺元映射为的幺元; 中两个互逆的元素映射为中两个互逆的元素; 中非特殊元素的映射为非特殊元素,28,同构证明举例1,设集合RR0,1 ,f0,f1,f2是R上的函数,且 f0(x)=x, f1(x)=1/(1-x), f2(x)=(x-1)/x, 令A=f0,f1,f2,证明:(A,)与(N3
17、,3)同构,其中 为函数的复合运算。,29,同构证明举例1(解),先找出(A,)和(N3,3)的特殊元素:幺元、零元和互逆元素。 (A,)的幺元:f0; 零元:无 互逆元素:f1与f2互逆 (N3,3)的幺元:0; 零元:无 互逆元素:1与2互逆根据特殊元素映射为特殊元素,非特殊元素映射为非特殊元素,可得: 若g为(A,)到(N3,3)的同构映射,则g的定义只有以下两种可能: g(f0)=0, g(f1)=1, g(f2)=2; 或者, g(f0)=0, g(f1)=2, g(f2)=1;再验证g是否(A,)到(N3,3)同构映射; 只需验证:g(f1f1)=g(f1)3 g(f1); g(f
18、1f2)=g(f1)3 g(f2); g(f2f1)=g(f2)3 g(f1); g(f2f2)=g(f2)3 g(f2); 经验证,g的两种定义都是(A,)到(N3,3)同构映射。,30,课堂练习,P87:14 设集合A=e,a,b,c,*和的运算表如下所示,证明(A,*)和(A, )同构,31,课堂练习(解),先找出(A,*)和(A,)的特殊元素:幺元、零元和互逆元素。 (A,*)的幺元:e; 零元:无 互逆元素:a与c互逆,b与b互逆; (A,) 的幺元:e; 零元:无 互逆元素:a与b互逆,c与c互逆;根据特殊元素映射为特殊元素,非特殊元素映射为非特殊元素,可得: 若f为(A,*)到(
19、A,)的同构映射则f的定义只有以下两种可能: f(e)=e, f(b)=c, f(a)=a, f(c)=b ; 或者 f(e)=e, f(b)=c, f(a)=b, f(c)=a ;再验证两种f的定义是否都是(A,*)到(A, )的同构映射; 运算*和都可交换,故只需验证 f(a*a)=f(a)f(a); f(a*b)=f(a)f(b); f(a*c)=f(a)f(c); f(b*a)=f(b)f(a); f(b*b)=f(b)f(b); f(b*c)=f(b)f(c); f(c*a)=f(c)f(a); f(c*b)=f(c)f(b); f(c*c)=f(c)f(c); 经验证,f的两种定义
20、都是(A,*)到(A,)的同构映射。,32,综合举例1,例: 设在代数系统中, 令f是从N6到N6的双射函数, 且有:f(n) = 0 n为偶数f(n) = 3 n为奇数则f是的自同态映射.证明: 设a, b N6, 则 a, b都是偶数时, a 6 b也是偶数 f(a 6 b) = 0 而f(a) 6 f(b) = 0 6 0 = 0 f(a 6 b) = f(a) 6 f(b),33,综合举例1(续),例: 设在代数系统中, 令f是从N6到N6的双射函数, 且有:f(n) = 0 n为偶数f(n) = 3 n为奇数 则f是的自同态. 证明: 设a, b N6, 则 a, b都是奇数时, a
21、 6 b是偶数 f(a 6 b) = 0 而f(a) 6 f(b) = 3 6 3 = 0 f(a 6 b) = f(a) 6 f(b),34,综合举例1(续),例: 设在代数系统中, 令f是从N6到N6的双射函数, 且有:f(n) = 0 n为偶数f(n) = 3 n为奇数 则f是的自同态. 证明: 设a, b N6, 则 a为奇数且b为偶数, 或者a为偶数且b为奇数时, a 6 b为奇数 f(a 6 b) = 3 而f(a) 6 f(b) = 3 6 0 = 3 f(a 6 b) = f(a) 6 f(b),注意:本例题使用了分类讨论的证明方法。,35,综合举例2,例:设H = x | x = dn, d Z+,n Z,是一般乘法。+是一般加法。 定义映射f:f: ZH, f(n) = dn 试证明: 证明:(1)首先证明f是双射函数 对 x Z,f(x) = dx x y dx dy f(x) f(y) f是单射函数。,对a H, x Z,使得 a = dx,即a = f(x), f是满射的 由 得,f是双射函数。 (2)证明f是同态映射 x, y Z f(x + y) = d(x + y) = dx + dy = f(x) + f(y) f是同态的 由(1)(2)得, ,36,作业,P87:12、13、1812、13题证明同构最重要的步骤是给出同构映射,
限制150内