离散数学 第3讲 同余关系和商代数.ppt

1 离散数学 二 同余关系和商代数 主要内容 重点和难点 一 同余关系 关于运算的同余关系 设 是代数A 的载体S上的等价关系 任取a b c S 1 当a b时 若有ac bc和ca cb 那么我们说等价关系 在运算 下具有置换性质 或者说等价关系 在运算 下仍能保持 称 是关于运算 的同余关系 2 当a b时 若有 a b 那么我们说等价关系 在运算 下具有置换性质 或者说等价关系 在运算 下仍能保持 称 是关于运算 的同余关系 一 同余关系 同余关系定义 设R为代数A 的载体S上的等价关系 如果在代数运算 下仍能保持 则称R是关于运算 的同余关系 一 同余关系 例1 给定代数A I 整数集合 运算 为普通乘法运算 R为I上的模k相等 k I 关系 即xRy当且仅当x y modk 现在证明R是关于运算 的同余关系 证明 a 容易看出R是I上的等价关系 b 下面只需证明对任意a b c I 若aRb 则 a c R b c 和 c a R c b 设aRb 即存在n I使得a b kn 于是 a c b c tn 因此 a c R b c 又乘法是可交换 有 c a R c b 所以 R是关于 的同余关系 一 同余关系 例2 给定代数A I 整数集合 I上的一元运算 定义为 z I z z2 modm m 0 I上的模m相等关系R为 z1Rz2当且仅当z1 z2 modm 问 R是关于运算 的同余关系吗 证明 a 容易看出R是I上的等价关系 b 因此只需证明对任意z1 z2 I 若z1Rz2 则 z1 R z2 若z1Rz2 即z1 z2 modm 设z1 m a1 r z2 m a2 r 0 r m 1 a1 a2 I z1 z1 2 modm m a1 r 2 modm a1 2m2 2ma1 r2 modm r2 modm z2 z2 2 modm m a2 r 2 modm a2 2m2 2ma2 r2 modm r2 modm 所以 z1 z2 modm 即 z1 R z2 一 同余关系 代数A上的同余关系定义 设 是代数A 的载体S上的等价关系 对一切元素a b c S 若 1 若a b 则ac bc和ca cb 2 若a b 则 a b 都满足 则 称为代数A上的同余关系 的等价类叫做关系 的同余类 注意 S上的等价关系 是代数A的同余关系当且仅当 关于A的每一运算是同余的 一 同余关系 例3 A a b c d 运算表 a 为在A上定义的 运算 表 b 为A上的等价关系R 判断R是不是关于运算 的同余关系 从上述表中可以看出cRd b c d b d a 但是d与a不等价 即b c与b d不等价 所以R不是关于运算 的同余关系 一 同余关系 定理1 等价关系 关于二元运算 是一个同余关系当且仅当对任意a b c d S a b和c d时有ac bd 证明 必要性 设 是关于运算 的同余关系 并对任意a b c d S 假设a b和c d a b蕴含着ac bc 而c d蕴含着bc bd 根据 的传递性 得出ac bd 充分性 是一等价关系 假设对任意a b c d S 当a b和c d时 ac bd 因为c c 故如果a b 那么ac bc 类似地 ca cb 所以 关于运算 是一同余关系 一 同余关系 自然等价关系 h是A到A 的任一个同态 h S S 可诱导出一个S上的自然等价关系 这一关系定义如下 a b S a b当且仅当h a h b 定理2 设h是从A 到A 的一个同态 如果在A上定义二元关系R aRb h a h b a b S 则R是代数A上的同余关系 证明 先证R是等价关系 对任意a b S h a h a aRa R自反 若aRb 则h a h b 有h b h a bRa R对称 若aRb bRc 则有h a h b h b h c h a h c aRc R传递 综上所述 R是等价关系 再证该等价关系R是A上的同余关系 证明见下页 由 和 知R是A上的同余关系 一 同余关系 定理2 设h是从A 到A 的一个同态 如果在A上定义二元关系R aRb h a h b a b S 则R是代数A上的同余关系 证明 再证该等价关系R是A上的同余关系 对任意a b c d S i 如果aRb 则h a h b h a h b h为同态 h a h a h b h b h a h b aR b 即R是关于运算 的同余关系 ii 如果aRb cRd 则h a h b h c h d h a h c h b h d h为同态 h a c h a h c h b d h b h d h a c h b d a c R b d 即R是关于运算 的同余关系 由定理2可以看出 一个同态可以诱导出一个同余关系 反过来 可以证明一个同余关系也可以导出一个同态 二 商代数 回忆 设R是非空集合S上的等价关系 称划分 a R a S 为S关于R的商集 记为S R 即S R a R a S 商代数的定义设 是代数A 上的同余关系 A的关于 的商代数定义为A 其中运算 和 的定义如下 对所有 a b S a b a b a a S 表示等价关系 下S的商集 即等价关系 的等价类的集合 为证明A 是一个代数必须证明 和 都是良定的 即运算 和 的结果不依赖于参加运算的等价类中的表示元素 1 证明S 关于运算 和 是封闭的 2 证明 是良定的 即证明如果 a b 那么 a b 3 证明 是良定的 即证明如果 a b 和 c d 那么 a c b d 二 商代数 证明 1 证明S 关于运算 和 是封闭的 显然 2 证明 是良定的 即证明如果 a b 那么 a b 如果 a b 那么a b 因为 是同余关系 a b 所以 a b 由 的定义知 a a 和 b b 这得出 a b 这样 运算 是良定的 3 证明 是良定的 即证明如果 a b 和 c d 那么 a c b d 如果 a b 和 c d 那么a b和c d 因为 是一同余关系 a c b d 所以 a c b d 由 的定义知因为 a c a c 和 b d b d 得 a c b d 所以 是良定的 综上所述 和 都是S 上良定的运算 因此A 是具有与A相同构成成分的代数 证毕 二 商代数 商代数的运算和常数保留了许多原代数的性质 1 代数A中如果运算 是可交换的 那么A 中 也是可交换的 2 如果 是可结合的 也是可结合的 3 A中如果k是关于 的么元 那么A 中 k 是关于 的么元 4 如果k是关于 的零元 那么 k 是关于 的零元 定理1 如果 是代数A 上的同余关系 那么规范映射h S S h a a a S 是从代数A到商代数A 的同态 称为与 相关的自然同态 证明 1 代数A与A 是具有与A相同构成成分 2 设h是从S到S 的规范映射 根据商代数的定义有 a b a b 和 a a 因而h a b a b a b h a h b h a a a h a 即h保持了A的运算 3 根据规范映射的定义有h k k 因此 h是从A到A 的同态 该定理说明一个同余关系可以导出一个同态 三 商代数和同态象的关系 定理2 设f是从A 到A 的同态 是A上由f诱导的同余关系 那么 从A 到存在同构h 证明 定义h S f S h x f x 1 证明h是良定的 如果 x y 那么x y 所以 f x f y 因为h x f x 和h y f y 所以h x h y h是良定的 2 证明h是双射函数 h S f S 是单射 对任意x1 x2 S 若f x1 f x2 则x1 x2 x1 x2 h S f S 是满射 f S 上的任一元素均可写成f x 于是存在 x S 使h x f x 3 证明h保持运算 h x y h x y f x y f x f y h x h