离散数学-同态和同构.ppt

离散数学(二)第二讲,计算机学院: 焦晓鹏,同态和同构,主要内容:,重点和难点:,一、同态与同构,两个代数在结构上是一致的, 大致地说, 有以下3点要求: (1) 两个代数必须有相同的构成成分; (2) 两个代数的运算和常数必须遵循相同的规则; (3) 两个代数的载体必须有相同的基数。 这种结构上的一致性, 数学上叫同构, 可以用与代数的“运算” 和“常数”密切相关的一个双射函数来精确地刻画。,一、同态与同构,同态定义: 设A=和A=是具有相同构成成分 的代数, h是一个函数。如果满足 (1) hS S； (2) 对所有a，bS,均有h(a*b) = h(a)*h(b)； (3) 对所有aS均,有h(a) = h(a)； (4) h(k) = k； 则称h是从A到A的同态, 称为A在映射h下的 同态象。,一、同态与同构,同态的分类: 根据函数h的特点，可将同态分成如下几类： (1) 如果h是单射，那么称h是单一同态; (2) 如果h是满射的, 那么称h是满同态; (3) 如果h是双射的,那么称h是从A到A的同构; (4) 如果A=A, 那么称h是自同态; (5) 如果A=A且h是同构, 那么称h是自同构。,一、同态与同构,同态的图示:,h是从A到A的同态, 称为A在映射h下的同态象,一、同态与同构,例1(a)：R：正实数集， R：实数集，试证明： 与同构。 证明：设f R R, f(x)=logx, 由于 (1) 证明f R R 双射。 易见f R R单射,因为对数函数单调增加； fRR满射：任意yR,存在x=eyR,使得f(x)=logey=y; (2) 运算保持。对所有 x，y R,均有f (xy)=log(xy) =logx+logy=f (x)+f (y)； (3) 常元运算保持。f(1)=log1=0。 所以与同构。,一、同态与同构,例1(b)：集合A=1, 2, 3, 4, 函数fA A, f =, , , , f 0表示A上的恒等函数；f 1表示f；f 2表示合成函数ff；f 3表示f 2f； f 4表示f 3f；则f 4=f 0。设F=f 0, f 1, f 2, f 3, 则代数可以用左下方的运算表给定, 这里f 0是么元。集合N4=0, 1, 2, 3,+4是模4加法,代数用右下方的运算表给定, 这里0是么元。试证明这两个代数同构。,一、同态与同构,例1(b)证明：，F=f 0, f 1, f 2, f 3;，N4=0, 1, 2, 3 作映射hFN4, h(f i) = i (i=0, 1, 2, 3) (1) hF N4双射； (2) h(f 0) =0； (3)任取f i， f jF， i， j N4, 因为h(f i) = i ， h(f j) = j ,所以 h(f if j) = h(f i+j) = h(f (i+j) mod 4) = (i+j) mod 4 = i +4 j = h(f i) +4h(f j)。 所以, 代数和同构。,一、同态与同构,例1(c)：证明代数和是不同构的。 证明：使用反证法。假设h是从到的一个同构。因为h是从N到I+的一个满函数, 必有xN( x2) 和某质数p(p3), 使h(x)=p( I+中有无限多的质数), 因此有以下式子成立： p=h(x)=h(x+0)=h(x)h(0) (1) p=h(x)=h(x-1)+1)=h(x-1)h(1) (2) 但因为p是一质数, 唯一的因子是p和1, 根据(1), h(x)=1或h(0)=1; 根据(2), h(1)=1或h(x-1)=1。 因为01x-1x, 所以，在映射h下, 1至少是两个元素的象, 得出h不是双射函数,因此和不同构。,一、同态与同构,定理 1：设h是从A=到A=的同态, 那么A的同态象是A的子代数。 证明：为证同态象是A的一个子代数, 只要证明: (1) h(S)S。这从h: S S函数的事实得出。h(S) S (2) 据同态定义,h(k)=k,因为kS,得出k=h(k)h(S),即kh(S)。 (3) h(S)关于运算*是封闭的。因为如果a,bh(S), 那么存在x、yS, 使h(x)=a和h(y)=b。所以a*b=h(x)*h(y)=h(x*y)=h(z)h(S) (由于x*y=zS)。 (4) h(S)关于运算是封闭的。对任意ah(S), 存在元素xS, 使h(x)=a, 所以a = h(x) = h(x)h(S) (由于xS)。 证毕。,二、同态代数的性质,定理2 设h是从代数A= 到A= 的同态, 这里*, *, , 都是二元运算, A= 是A的同态象。 (a) 若*可交换(可结合), 则在A中, *也是可交换(可结合) 。 (b) 对*, 若A有么元e (零元0), 则对*, 代数A中有么元h(e) (零元h(0)。(此时h(e) 不一定是代数A中的实际么元, 除非h是满同态。) (c) 对于*,若一个元素xS具有逆元x-1, 则对于*, 在代数A中, 元素h(x)具有逆元h(x-1)。 (d) 若运算*对运算是可分配的, 则在A中运算* 对运算也是可分配的。,二、同态代数的性质,定理2(a)的证明： 因为h：Sh(S)是代数A到A满同态，所以h(S)中任一元素可写成h(x)的形式，其中xS。 对于任意h(x1) , h(x2) , h(x3) h(S), x1 , x2 , x3 S有 h(x1) *h(x2) = h(x1 * x2) = h(x2*x1) = h(x2)*h(x1) 所以， (h(x1)*h(x2)*h(x3)=h(x1*x2)*h(x3)=h(x1*x2)*x3) =h(x1*(x2*x3)=h(x1)*h(x2*x3) =h(x1)*(h(x2)*h(x3) 所以, *是可交换(或可结合的)。证毕。,二、同态代数的性质,例2：设S = a, b, c, d, S=0, 1, 2, 3, 代数A=和B=由下表定义:,可以验证在函数h: SS中，其中h(a)=0, h(b)=1, h(c)=0, h(d)=1，保持运算。因此, h: SS是A到B的同态。 (1)同态象保持代数A的可结合性,但代数B=却是