《离散数学—代数(11.24版)》由会员分享，可在线阅读，更多相关《离散数学—代数(11.24版)（98页珍藏版）》请在金锄头文库上搜索。
1、第六章 代 数,6.1 代数结构6.2 子代数6.3 同态6.4 同余关系 （自学） 6.5 商代数和积代数 （自学） 6.6 半群和独异点 （自学） 6.7 群6.8 环和域,6.1 代数结构,6.1.1 代数的构成和分类方法 代数通常由3部分组成: 1. 一个集合, 叫做代数的载体 载体是我们将处理的数学目标的集合(一般是非空集合)。,2. 定义在载体上的运算 定义在载体S上的运算是从Sm到S的一个映射, 自然数m的值叫做运算的元数。 从S到S的映射, 诸如给定一个实数x求x, 给定一个整数y求|y|, 叫做一元运算; 从S2到S的映射, 诸如数的加法和乘法, 都是二元运算。常见的是一元和
2、二元运算, 但理论上可定义任意的m元运算。,3. 载体的特异元素, 叫做代数常数 有些代数不含常数。这里所谓“不含”只是说我们研究该代数时并不关注这些特异元素, 不一定是真的没有。 代数通常用载体、运算和常数组成的n重组表示。,例 整数、 加法和常数0可构成一个代数。(1) 载体是整数集合I=, -3, -2, -1, 0, 1, 2, 3。(2) 定义在I上的运算是加法(记为+)。(3) 常数是0。这个代数可记为I, +, 0。,通常我们不去研究单个具体的代数, 而是一个种类一个种类地去研究。为此, 我们首先要知道什么样的两个代数是同一种类的。 第一, 要有相同的构成成分。 如果两个代数包含
3、同样个数的运算和常数, 且对应运算的元数相同, 则称两个代数有相同的构成成分。,例 3 考虑具有N, +, 0形式的构成成分和下述公理的代数类。 (1) a+b=b+a (2) (a+b)+c=a+(b+c) (3) a+0=a那么I, , 1, (S), , 和R, min, +(这里R是包含+的非负实数)等, 都是这一种类的成员。关于这一类证明了的定理, 对这些特定的代数都成立。,6.1.2 么元和零元,定义6.1-1 设*是S上的二元运算,1l是S的元素,如果对S中的每一元素x, 有1l * x = x则称1l对运算*是左么元。S中的元素0l, 如果对S中的每一元素x, 有0l*x =
4、0l则称0l对运算是左零元。 类似地可定义出右么元1r和右零元0r。,例4 代数A=a, b, c, 用右表定义, 表中位于x行和y列交叉点的元素是x 。y的值。 a和b都是右零, 无左零; b是左么, 无右么 。运算既不能结合也不能交换。,定义 6.1-2 设*是S上的二元运算, 1是S的元素, 如果对S中的每一元素x, 有1*x = x*1 = x则称1对运算*是么元。 S中的元素0, 如果对S中的每一元素x, 有0*x = x*0 = 0则称0对运算*是零元。,例 5 (a) 代数I, , 1, 0, 这里表示乘法, 有一个么元1和零元0。 (b) 代数N, +有一个么元0, 但无零元。
5、,定理 6.1-1 设*是S上的一个二元运算, 具有左么元1l和右么元1r, 那么1l=1r, 这元素就是么元。 证 因为1l和1r是左么元和右么元。1r = 1l1r = 1l 证毕。,定理 6.1-2 设*是S上的二元运算, 具有左零元0l和右零元0r, 那么0l=0r, 这元素就是零元。 证明类似于定理6.1-1。,推论6.1-2 一个二元运算的么元(零元)是唯一的。,6.1.3 逆元 如果在一代数中存在么元, 那么可定义逆元。 定义 6.1-3 设*是S上的二元运算, 1是对运算*的么元。如果x*y=1, 那么关于运算*, x是y的左逆元, y是x的右逆元。如果x*y=1和y*x=1两
6、者都成立, 那么关于运算*, x是y的逆元(y也是x的逆元)。 x的逆元通常记为x-1。 存在逆元(左逆元、右逆元)的元素称为可逆的(左可逆的、右可逆的)。,例 6 (a) 代数A=a, b, c, *由上表定义。b是么元。a的右逆元是c, b的逆元是自身, c的左逆元是a。,定理 6.1-3 对于可结合运算, 如果一个元素x有左逆元l和右逆元r, 那么l=r(即逆元是唯一的)。 证 设1对运算 。是么元, 于是l 。x = x 。 r = 1根据运算 。的可结合性, 得到l = l 。1 = l 。 (x 。r) = (l 。x) 。r = 1 。r = r 。,6.2 子代数,定义 6.2
7、-1 设 。和是集合S上的二元和一元运算, S和S的子集。如果a、bS；蕴含着a 。bS, 那么S对 是封闭的。如果aS蕴含着aS, 那么S对是封闭的。 例 1 考虑整数集合I, 设S=0, 1, 2, 3, 4, 对加法S不封闭, 因为4+4=8, 。然而对max, min, 求绝对值诸运算是封闭的。 因为对具有载体S的一个代数而言, 每一运算是定义为从Sm到S的函数, 所以一个代数的载体对定义于其上的运算总是封闭的。,定义 6.2-2 设A=S, 。, , k是一代数, 如果(1) (2) S对S上的运算 。和封闭(3) kS那么A=S, 。, , k是A的子代数。 如果A是A的子代数,
8、那么A和A有相同的构成成分和服从相同的公理。A的最大可能的子代数是它自己, 这个子代数是常存在的。如果A的常数集合在A的运算下是封闭的, 那么它组成A的最小子代数。这两种子代数称为A的平凡子代数, 其余子代数称为真子代数。,例 2 (a) 设E表示偶数集合, 那么E, +, 0是I, +, 0的一个子代数。 (b) 设M表示奇整数集合, 那么M, , 1是I, , 1的子代数。 但M, +不是I, +的子代数, 因为奇整数集合M对加法不封闭, 例如1+1=2。,6.3 同 态,两个代数在结构上是一致的, 大致地说, 有以下3点要求: (1) 两个代数必须有相同的构成成分; (2) 两个代数的载
9、体必须有相同的基数; (3) 两个代数的运算和常数必须遵循相同的规则。 这种结构上的一致性, 数学上叫同构, 可以用联系于运算和常数的一个双射函数来精确地刻画。为了便于表述, 本节暂时仅讨论形如A=S, *, , k和A=S, *, , k的代数。这里*和*是二元运算, 和是一元运算, k和k是常数。,定义 6.3-1 代数A=S, *, , k和A=S, *, k是同构的, 如果存在一双射函数h, 使 (1) h:S S (2) h(a*b) = h(a)* h(b) (3) h(a) = h(a) (4) h(k) = k这里a、b是S的任意元素。映射h叫做从A到A的同构, A叫做A在映射
10、h下的同构象。,上述定义被推广到具有任意构成成分的代数后就是: 如果双射函数h是从代数A到A的同构, 那么 (1) A和A必须有相同的构成成分; (2) 在函数h的作用下, A的每一运算保持; (3) 函数映射A的每一常数到A的对应常数(若A不含常数时, 不须考虑这一条)。 如果A和A是同构的代数, 它们基本上是不同名的相同结构; 简单地调换符号就能从A得到代数A。,例 1 设R+表示正实数集合, 那么R+, , 1同构于R, +, 0。 作映射hR+ R, h(x) = logx (i) 对数函数单调增加, 所以h是单射的; 对x0, 方程logx=y常有解x=2y, 所以h是满射的。因此h
11、是双射的。 (ii) h(ab) =log(ab) =loga+logb=h(a)+h(b) (iii) h(1) =log1=0所以, R+, , 1同构于R, +, 0。,定理 6.3-1 设C是代数集合, A、A是C的任意元素, R是关系,定义ARA当且仅当A同构于A, 那么R是C上的等价关系。 有些代数, 虽然结构上不完全一致, 但在一定范围内, 有其相似性。为了刻画这种关系, 我们放弃同构定义中, hSS必须是双射函数的要求, 但仍保持其它条件, 这就得到了数学上同态的概念。,定义 6.3-2 设A=S, *, , k和A=S, *, , k是具有相同构成成分的代数, h是一个函数。
12、如果(1) hS S(2) h(a*b) = h(a)*h(b)(3) h(a) = h(a)(4) h(k) = k这里a、b是S的任意元素, 则称h是从A到A的同态, h(S), *, , k称为A在映射h下的同态象。,图 6.3-2,设h是从A到A的同态, 如果h是单射的那么称h是单一同态; 如果h是满射的, 那么称h是满同态; 只有h是满同态时,才称A和A同态; 如果h是双射的, 即是定义6.3-1的同构。如果A=A, 那么称h是自同态; 如果A=A且h是同构, 那么称h是自同构。,例 2 (a) 映射fI I, f(x)=kx, 这里kI, 是从I, +, 0到I, +, 0的自同态
13、,因为 (1) f(x+y) = k(x+y) = kx+ky = f(x)+f(y) (2) f(0) = 0成立。如果k0, f是单射的, f是单一同态; 如果k=1或k=-1, f是双射的, f是自同构。,(b) 设fR R, f(x)=2x, 由于 (1) f(x+y) = 2(x+y) = 2x2y = f(x)f(y) (2) f(0) = 20 = 1 成立, 且f是单射函数, 所以f是从R, +, 0到R, , 1的单一同态。,6.7 群,6.7.1 群的定义和性质 定义 6.7-1 群G , * 是一代数系统, 其中二元运算*满足以下3条: (1) 对所有的a, b, cGa
14、 * (b * c) = (a * b) * c,(2) 存在一个元素e, 对任意元素aG, 有a * e = e * a = a (3) 对每一aG, 存在一个元素a-1, 使a-1 * a = a * a-1 = e,简单地说, 群是具有一个可结合运算, 存在么元, 每个元素存在逆元的代数系统。,每个元素的逆元是唯一的。 所以可看成是一种一元运算, 故一个群的构成成分可看成是G, *, -1, e, 这里-1是求逆运算。但通常为了简便仍记为G, *。 如果G是有限集合, 则称G, *是有限群; 如果G是无限集合, 则称G, *是无限群。有限群G的基数|G|称为群的阶数。 群中的运算 * 一般称为乘法。 如果 * 是一个可交换运算, 那么群G , * 就称为可交换群, 或称阿贝尔群。在可交换群中, 若运算符*改用+, 则称为加法群, 此时逆元a-1写成-a。,
