《数学集合论》PPT课件.ppt

1 集合论(Set Theory)是现代数学的基础它的起源可 追溯到16世纪末，但集合论实际发展是由 19世纪 70 年代德国数学家康托尔(G . Cantor) 在无穷序列和分 析的有关课题的理论研究中创立的. 集合论在计算机科学、人工智能领域、逻辑学及语言 学等方面都有着重要的应用对于从事计算机科学的 工作者来说，集合论是不可缺少的理论知识，熟悉和 掌握它是十分必要的 第3章 集合、关系与映射 2 3.1 集合的基本概念 一、集合的概念 把具有相同性质的所有对象汇集在一起就称为一个集合. 把组成集合的对象称为元素。 例如： 方程x210的实数解集合； 26个英文字母的集合； 坐标平面上所有点的集合； 3 二、集合的表示 一般用带下角标或不带下角标的大写字母表示集合，如 A, B, P1, P2, Q1, Q2等; 一般用带标号或不带标号的小写字母表示集合，如 a, b, c, a1, a2,等; 3.1 集合的基本概念 4 三、说明集合的方法 （1）列举法：如A=1,2,3,4，B0,2,4,6,8,10, （2）描述法：如A=x|P(x),P(x)是元素x所具有的性质。 例：A=x|x2-5x+6=0 （3）特定的字符集：在集合中常约定： N表示自然数集合；I(或Z)表示整数集合； Q表示有理数集合；R表示实数集合； E表示偶数集合； O表示奇数集合； P表示素数集合； F表示分数集合； C表示复数集合； R表示正实数集合； R*表示非零实数，即R*=x|xRx0; （4）图示法：用封闭曲线表示集合，封闭曲线内的点 表示集合中的元素 3.1 集合的基本概念 5 注意： (1)集合的元素是确定的，即对集合A，任一元素a 或属于此集合(aA)或不属于此集合(aA) ， 两者必居其一。 集合中的每个元素均不相同。 即集合 1,2,2,3,4,4 = 1,2,3,4 (3) 集合中的元素是无序的。 例：4,3=3,4 3.1 集合的基本概念 6 包含关系： 若集合B中的每个元素都是A中的元素，称B包含于A 或A包含B，称集合B是集合A的一个子集记为 BA : (x)(xBxA) 如果B不被A包含，则记作B A。 例如：NZQRC，但Z N。 3.1 集合的基本概念 四、集合间的关系：相等关系和包含关系 结论：对任何集合A都有A A A。 例如： Aa，a和a的关系为 a A ，又有 aA 7 若B是A的子集且在A中存在不属于B的元素，则称 集合B是集合A的一个真子集，记为 BA : BA(x)(xAxB ，称A真包含于B。 3.1 集合的基本概念 例如：N Z Q R C 8 相等关系： 若集合A的任一元素都是集合B中的元素并且集合B 中的元素也是集合A中元素，则称这两个集合相等， 记为AB :(x)(aA aB) 或 AB : (AB)(BA) 否则称这两个集合不相等，记为A B 3.1 集合的基本概念 9 五、子集具有的性质： AA 自反性 ABBAAB 反对称性 ABBCA C 传递性 证明: 这里仅给出的证明, 余下类似可证 ABBA (x)(xAxB)(x)(xBxA) (x)(xAxB)(xBxA) (x)(xAxB) AB 3.1 集合的基本概念 10 不包含任何元素的集合称为空集。记为 例如：A=x|x2-1, xR 对任何集合A， A 全集U：所有集合都是U的子集。 3.1 集合的基本概念 11 六、集合的运算 交运算： AB := x|xAxB 3.1 集合的基本概念 12 并运算： AB: x|xAxB 3.1 集合的基本概念 13 两个集合的并和交运算可以推广成n个集合的并和交： A1A2Anx|xA1xA2xAn A1A2Anx|xA1xA2xAn 六、集合的运算 3.1 集合的基本概念 并和交运算还可以推广到无穷多个集合的情况： A1A2 A1A2 14 差运算： BA : x|xBxA 3.1 集合的基本概念 15 全集U：所有集合都是U的子集。 补集：全集U与集合A的差集称为A的补集， 记为 UA=x|x A A U 3.1 集合的基本概念 16 对称差运算： AB:= x|x(AB)x(BA) AB 3.1 集合的基本概念 显然： AA AB BA ABA AU 17 图形表示集合间的关系文氏图(Venn Digram表示) U A, B 3.1 集合的基本概念 AB 18 1. 交换律 ABBA ； ABBA 2. 结合律 A(BC)=(AB)C A(BC)=(AB)C 3. 分配律 A(BC)=(AB) (AC) A(BC)=(AB)(AC) 4. 吸收律 A(AB)=A ； A(AB)=A 5. De Mergam律 6. 幂等律 AAA ; AAA 7. 补余律 零律 A AUU 5. 壹律 AUA AA 6. 互补律 重非律 集合运算的算律：设A,B,C是任意三个集合。 19 定理：设A, B, C, D是任意三个集合。 （1） 若A B，则ABA ；ABB； (BA)AB （2） AB A, B; A, B AB （3） 若A B且C D；则AC BD ； AC BD （4） 若AB ；则称A，B不相交；若还有ABU， 则称A，B为互补。 （5）若A B，则 （6） A(BC)(AB)(AC) ； A(B C) (AB) (AC) (7) A (BC)(A B) (A C) 但 A (BC) (AB) (AC) 幂集：由集合A的所有子集组成的集合称为A的幂集。 记为P(A)或2A 即P(A):B|BA 例如：Aa P(A)=,a A=a,b P(A)=,a,b,a,b A=,a P(A)=,a,a 设Aa1,a2,an,则A的子集B的二进制编码为： 若aiB，则ai记为1，否则记为0，i1,2,n. 按此规定得到的一个二进制数称为集合B的编码。 设|A|=n,则P(A)= 2n 21 集合的应用求若干有限集合并的元素个数。 定理：设A1，A2是两个有限集合， 记|A1|, |A2|为它们所含的元素个数， 则|A1A2|= |A1|+|A2| A1A2| 例1：假设某班有50名学生，其中英语成绩为优的25名， 数学成绩为优的20名，又有15名学生数学和英语成绩均 为优。问这两门课都不是优的学生有几名？ 解：英语成绩为优的学生组成的集合是A；|A|=25 数学成绩为优的学生组成的集合是B；|B|=20 因此这两门可成绩均为优的学生组成的集合是AB； | AB |=15 所以 | AB |=|A| +|B| AB |=25201530， 这说明两门课中至少有一门课为优的学生是30名， 所以这两门课都不是优的学生有503020名 例2：求出在1和90之间(包括90)能被2，3，5 任一 数整除的整数个数。 解：设A1，A2，A3分别为表示1和90之间能被2，3，5 任一数整除的整数集合。 所以 在1和90之间(包括90)能被2，3，5 任一数整除 的整数个数为66。 24 3.2 关 系 定义1（笛卡尔积或直乘积） 设A，B是任意两个集合， AB|xA, yB 称为集合A和B的笛卡尔积或直乘积。 称为有序对或序偶对，x称为序偶对的第一 个元素，y称为序偶对的第二个元素。 = iff a=x且b=y 25 例：A=a,b，B=1,2,3，C=x 则 AB, BA, , , , 结论：设 |A|=n, |B|=m, 则 | AB |=nm 3.2 关 系 (AB)C,x,x,x, ,x,x,x 结论： (AB)C A(BC) A(BC), , 26 笛卡儿积运算的性质: 1. 若A，B中有一个空集,则它们的笛卡儿积是空集, 即 AA A 2. 当AB且A,B都不是空集时,有 ABBA。 所以,笛卡儿积运算不满足交换律。 3. 当A,B,C都不是空集时,有 (AB)CA(BC). 所以,笛卡儿积运算不满足结合律。 27 定理1(笛卡儿积运算对或运算满足分配律,即) 设A, B, C是任意三个集合；则 A(BC) = (AB)(AC) /对具有左分配律 A(BC) = (AB)(AC) /对具有左分配律 (AB)C= (AB)(AC) /对具有右分配律 (AB)C= (AB)(AC) /对具有右分配律 3.2 关 系 28 证明： A(BC)=(AB)(AC) /对具有左分配律 令x, y为分别属于集合A和集合BC的任意元素, 则 A(BC) xAy(BC) xA(yByC) (xAyB)(xAyC) AB AC (AB)(AC) 所以： A(BC)=(AB)(AC) 3.2 关 系 29 定理2：设A, B, C，D是任意四个集合；则 若AB且CD，则ACBD 规定： AAA A,记为AnAn-1A 例：A1,2 A3=A2A= 1,22 1,2 = ,1, ,2, ,1,2, ,1, ,2, ,1, ,2 3.2 关 系 30 定义2（二元关系） 设A, B是任意两个集合，则AB的任一子集称为从A到B的 二元关系(简称关系)，记为R，显然R AB， 若R，则称x和y有关系R，记为xRy; 否则R，则称x, y没有关系，记为xRy 若AB，则称关系R是集合A上的一个二元关系，即RA2； R| xA, 称R为A上的恒等关系，记为IA； 若R，则称R为空关系，记为A； 若RAAA2，则称R为全域关系，记为UA； 设|A|=n, 则A2的序偶对一共有n2个，A上的二元关系一共有 3.2 关 系 31 例1：A=a,b, B=1,2,3 则R1,是一个从A到B的(二元)关系。 同理 R2, 也是一个从A到B的(二元)关系。 例2：A=a, b, c, 则 IA,是一个A上的恒等关系。 UA ,是一 个A上的全域关系。 3.2 关 系 32 定理：若R1和R2是A上的关系，则 R1R2， R1R2， R1R2也是A上的关系。 3.2 关 系 证明：因为R1和R2是A上的关系，则R1 A2， R2 A2 所以R1R2 A2； R1R2 A2； R1R2 A2； 故 ，R1R2， R1R2， R1R2， 也是A上的关系。 33 定义3 设R是从集合A到B的一个关系，称 domRx|(y)(R) 为R的定义域。 romRy|(x)(R) 为R的值域。 3.2 关 系 例：R,的 domR=a,b romR=1,2,3 34 关系的表示 矩阵法 图形法 3.2 关 系 35 矩阵法： 设两个有限集合 A=x1, x2, , xm, B=y1, y2, , yn, R AB. 则对应于二元关系R有一个关系矩阵: MR=(rij)mn, 其中 R 否则 这里i1, 2, , m， j=1, 2, , n. 3.2 关 系 36 例如, Ax1,x2,x3, B=y1, y2, R=, 则: 矩阵法: 37 例如：Ax1,x2,x3,x4, A上的一个关系R为 R=, 矩阵法: 38 图形表示： 设R AB。用小圆圈分别表示集合A、B中的元素， 若R，则由x向y引一条有向边(或称为弧)。 关系的表示：矩阵法和图形法 例1: Ax1,x2,x3, B=y1, y2, R=, x3 x2 x1 y1 y2 39 例2: A1,2,3,4, A上的一个关系R为 R=, , 关系的表示：矩阵法和图形法 设R A2。用小圆圈表示集合A中的元素， 若R，则由x向y引一条有向边(或称为弧)。 40 关系的性质、合成和逆 定义(关系的性质)：设R是A上的一个二元关系。 R在A中自反:=(x)(xAxRx) R在A中非自反: =(x)(xA(xRx) R在A中对称:= (x)(y) (x,yAxRyyRx) R在A中反对称: =(x)(y)(x,yAxRyxy(yRx) R在A中传递: =(x)(y)(z)(x,y,zAxRyyRzxRy) 41 而实数集合上的小于关系和集合上的真包含关系 都是反自反关系。 例如:A上的全域关系UA，恒等关系IA 实数集合上的小于等于关系 正整数集合上的整除关系 包含关系R是给定集合族A上的 自反、反自反关系举例 都是自反关系。 例: 设A=1,2,3，R1，R2，R3是A上的关系，其中 R1, R2 R3, 说明R1，R2和R3是否为A上的自反关系和反自反关系 解: R1是自反的,R2是反自反的,R3既不是自反的也不是 反自反的。 结论：不自反的关系未必反自反； 不反自反的关系未必自反； 43 例如: A上的全域关系UA，恒等关系IA和空关系 都是A上的对称关系。 恒等关系IA和空关系也是A上的反对称关系。 但全域关系UA一般不是A上的反对称关系，除非A 为单元集或空集。 对称、反对称关系举例 A 44 设A1,2,3，R1，R2，R3和R4都是A上的关系，其中 R1, R2, R3, R4, 说明R1，R2，R3和R4是否为A上对称和反对称的关系。 解: R1既是对称也是反对称的。 R2是对称的但不是反对称的。 R3是反对称的但不是对称的。 R4既不是对称的也不是反对称的。 结论： 不对称的关系未必反对称； 不反对称的关系未必对称； 二元关系既可对称也可反对称； 对称、反对称关系举例 45 反对称的另一种定义： R在A中反对称: = (x)(y)(xRyxy (yRx) /x,yA = (x)(y)(xRy)x=y (yRx) = (x)(y)(xRyyRx )x=y) = (x)(y)(xRyyRxx=y) 关系的性质 R4, 不是反对称的 46 例如: A上的全域关系UA,恒等关系IA和空关系 都是A上的传递传递 关系。 小于等于关系，整除关系和包含关系 也是相应应集合上的传递传递 关系。 小于关系和真包含关系是相应应集合上的传递传递 关系。 传递关系举例 A 47 设A1,2,3，R1，R2，R3是A上的关系，其中 R1, R2, R3 说明R1，R2和R3是否为A上的传递关系。 解: R1和R3是A上的传递关系，R2不是A上的传递关系。 传递关系举例 48 利用关系的表示来判断关系的性质 49 关系的运算：逆和合成 定义(逆运算) 设R是从集合A到集合B的二元关系 R-1:= | xA, yB且xRy 称为关系R的逆关系。 显然R-1是从集合B到集合A的二元关系. 例：A1,2,3, B=a,b R=,从集合A到集合B的二元关系 则： R-1,从集合B到集合A 的二元关系 50 定理：设R和S是从集合A到集合B的关系。 R-1是一个关系 xR-1y iff yRx (R-1)-1=R (RS)-1=R-1S-1 (RS)-1=R-1S-1 (R S)-1 =R-1 S-1 证明 ：令x, y分别为集合A和集合B中的任何元素，则 若 x(RS)-1y y(RS)x yRx ySx xR-1y xS-1y x(R-1S-1)y 根据定义知, (RS)-1=R-1S-1 关系的运算：逆和合成 51 令x, y分别为集合A和集合B中的任何元素， 则若x(R S)-1yy(R S)x yRx(ySx) xR-1y(xS-1y) x(R-1- S-1)y 由定义知, (R S)-1=R-1- S-1. 关系的运算：逆和合成 52 定义 (合成运算) 设R是从集合A到集合B的二元关系， S是从集合B到集 合C的二元关系，则称 R o S:=| (xAzC(y)(yB) xRyySz 为关系R和关系S的从A到C二元关系。 例：令R=, , S=, 则 R o S =,. S o R=. R o S S o R 关系的运算：逆和合成 53 结论： 关系合成运算满足结合律，不满足交换律. 特别, 当 R=S时, 记 Rn=Rn-1 o R. 关系的运算：逆和合成 定理3.2.1 设R ，R1和R2 是从A到B的二元关系， (p84) S是从B到C的二元关系，则有下列结论： (1) (R o S)-1 = S-1 o R-1 (2) (R1 R2 ) -1= R1-1 R2 -1 ; /书上错 (R1 R2 ) -1= R1-1 R2 -1 (3) (AB) -1= BA (4) (R1R2 ) -1= R1-1 R2 -1 ; (5) R1R2 iff R1-1R2-1 (6) (7) (R1R2) o S = (R1 o S) (R2 o S) 练习 (R1R2) o S (R1 o S)(R2 o S) 55 利用两个关系的关系矩阵求它们的合成关系. 例：R,是从A=1,2,3到B=a,b,c的关系 S=,是从B=a,b,c到C=x,y,z的关系 求 R o S R o S, 56 关系的闭包运算 现在来讨论另一种重要关系闭包. 所谓闭包是指， 对于给定的关系R和一种性质P, 把包含R并且满足性质 P的最小关系称为R对于P的闭包, 记为P(R). 若P是自反 的, 则称R是自反闭包, 记为r(R), 若P是对称的，则称R 是对称闭包, 记为s(R); 若P是传递的, 则称R是传递闭包 ,记为t(R). 57 关系的闭包运算 定义3.2.1 设R和R是集合A上的一个二元关系，若满足下列条件： (1) R是自反(对称,传递)关系； (2) R R ； 若R也是A上的自反(对称,传递) 关系且R R ， 则R R , 称R是R的自反(对称,传递) 闭包关系， 记为为r(R)(s(R)和t(R). 结论： R是包含R的最小的自反(对称,传递) 关系。 58 定理1 设R是集合A上的一个二元关系，则 R是自反的 iff r(R) = R R是对称的 iff s(R) = R R是传递的 iff t(R) = R 关系的闭包运算 59 证明： 只证明 设R为自反. 由于RR, 取R 为R,以及任何包含R 的自反关系 R , 有RR R, 可见R满足自反 闭包定义, 即r(R) = R. 下面再给出关于闭包的三个构造性定理. 关系的闭包运算 定理3.2.2 设R是集合A上的任一二元关系，则 r(R) = R IA s(R) = RR-1 t(R) = Ri 关系的闭包运算 61 证明 只证明和 令R R IA, 显然RR . 则R 在A中自反. 又因 为对于任意包含R的自反关系R, 显然有IA R, 因此有R IA R, 即R R. 由自反闭包定义知, r(R) =R , 即r(R) =R IA. 首先证明 Ri t(R). 用归纳法证明如下: 当i1时，根据传递闭包定义, R t(R); 假设当i1时Ri t(R), 欲证Ri+1 t(R)。 x,y,zA, 若 Ri+1,因为Ri+1 Ri o R 所以 yA,使得Ri且R 由假设知 , t(R), 则 t(R) 因此, Ri+1 t(R). 于是, Ri t(R). 次证 t(R) Ri, 由于包含 R的传递关系都包含 t(R)，且R Ri, 因此只需证明Ri是传递即可. x, y, z A, 则 设Ri, Ri, 则必s,t N+ 使得 Rs， Rt 因此, Rs+t ,故 Ri 所以 Ri是传递的. 综上可知, t(R) = Ri. 64 推论 t(R) Ri，其中kn 例. 设R=, 试求r(R), s(R)和t(R). 解: r(R)=R IA =, s(R)=RR-1 =, 关系的闭包运算 65 下面求t(R), 因A只含有3个元素 ，所以k3. R= , R2=R o R=, R3=R2 o R= , 于是 t(R)=RR2R3 =, , , 关系的闭包运算 例：设Aa,b,c,d, R, 则 r(R),s(R),t(R) 为 解: (1) r(R)=R IA =, =,., (2) s(R)=RR-1 =, =, (3) t(R)=RR2R3 =, , =, 67 关系矩阵为: 证明 只给出的证明 因为r(R)=R IA, 已知R为对称, 而IA显然也是对称的, 因此r(R)是对称的. t(R)=RR2R3, 用归纳法证明t(R)对称. 当 i1时， R是对称的。 定理 R为自反s(R)和t(R)为自反 R为对称r(R)和t(R)为对称 R为传递r(R)为传递 假设对于i1时, Ri是对称, 欲证Ri+1是对称. 令x, yA, 则: xRi+1y x(Ri o R)y (z)(xRizzRy) (z)(zRixyRz) (z)(yRzzRix) y(R o Ri)x yRi+1x 故Ri+1是对称的, 于是t(R)是对称的. 70 证明 sr(R)=s(R IA )= (R IA ) (R IA )-1 = (R IA ) (R-1(IA )-1) = RR-1 IA = s(R) IA =rs(R) (其中 IA = (IA )-1) 闭包运算律： rs(R)=sr(R) (自反对称闭包等于对称自反闭包) rt(R)=tr(R) (自反传递闭包等于传递自反闭包) st(R)ts(R) (对称传递闭包包含于传递对称闭包) 71 若RS, 则显然有s(R)s(S), t(R)t(S). 根据对称闭 包的定义, Rs(R), 于是 t(R)ts(R) st(R)sts(R) 由于s(R)对称，则ts(R)亦对称, sts(R)=ts(R). 所以, 可得, st(R)ts(R) 72 注意： ts(R) 不一定包含于st(R) 例如：若R, 则 s(R)=, ; t(R)= ts(R)=, st(R)=, 73 Warshall算法：求传递闭包的新方法 设R是具有n个元素的集合A上的任一二元关系， 由MR 求Mt(R)如下： (1) MR M；1i (2) 对于j1,n, 若有wji=1,则wjkwjkwik (k=1,n) (3) i+ (4) 若in，则转(2), 否则结束，此时M即为R的传递闭包 矩阵Mt(R) 。 例: 设Aa, b, c, d, R, 问t(R)？ 练习：p92(11) 75 等价关系与划分 定义（ 等价关系特殊的关系） 设R是非空集合A上的一个二元关系， 若关系R自反、对称和传递，则称R为A上的等价关系 例如： 实数中的等于关系；直线间的平行关系； 在一群人的集合上年龄相等的关系是等价关系； 而朋友关系不一定是等价关系,因为它可能不是传递的. 例：设A=1,2,8，如下定义A上的关系R： R=|x，yAxy(mod 3) /模3同余关系 其中xy(mod 3)称作x与y模3相等(即x除以3的余数与y除 以3的余数相等), 则R为A上的等价关系，因为 xA，有xx(mod 3) x, yA，若xy(mod 3)，则有yx(mod 3) x, y, zA，若xy(mod 3)，yz(mod 3)， 则有xz(mod 3) 一般，若R|x,yZxy(mod k)，kN+ 则R是等价关系。 定义: 设R是非空集合A上的等价关系,对 xA,令xR=y| yAxRy 则称xR为x关于R的等价类,简称为x等价类. 在上例中有 0R =3R =-3R =,-6,-3,0,3,6,; 1R =4R =-2R =,-5,-2,1,4,7,; 2R =5R =-1R =,-4,-1,2,5,8,; 集合A=1,2,8上等价关系的关系图 79 商集： 设R为非空集合A上的等价关系, 称 xRxA 为A 关于R的商集,记作A/R 即 A/R xRxA 如上例 A/R= 0R,1R,2R = ,6,-3,0,3,6,; ,5,-2,1,4,7,; ,-4,-1,2,5,8,; 80 定理(等价类类的性质质) 设设R是非空集合A上的等价关系，则则 （1） xA，xR是A的非空子集。 （2） x,yA，如果xRy，则则xR=yR。 （3） x,yA，如果(xRy)，则xRyR=. （4）x|xA=A 证证明： (1)xA，xR是A的非空子集。 由等价类的定义可知, xR=y| yAxRy A。 又由于等价关系的自反性有xxR，即xR非空。 (2) x,yA，如果xRy，则xR=yR。 任取zA ，若有zxR = R = R 因此有RR =R = R 从而证明了zyR. 则 xR yR。 同理可证 yR xR，从而得到了xR=yR。 （3） x,yA，如果(xRy) ，则则xRyR=. 假设设xRyR ，则则存在zxRyR，从而有 zxRzyR，即RR成立。根据 R的对对称性和传递传递 性必有R，与(xRy) 矛盾， 即假设错误设错误 ，原命题题成立。 （4）xR|xA=A 先证xR|xAA 任取y，yxR|xA = x(xAyxR) = yA (因为x A) 从而有xR|xA A 再证A xR|xA 任取x，xA, xxRxA =xxR|xA 从而有A xR|xA成立。 综上所述得xR|xA=A。 84 定义3.2.2 设A是非空集合,如果存在一个A的子集族 S=A1,A2,Am满足以下条件: (1) Ai(i=1,2,m)非空； (2) S中任意两个不同元素交集为空； (3) S中所有元素的并集等于A； 则称S为A的一个划分，且称S中的元素Ai为划分块. 划分 85 例. 考虑集合Aa, b, c, d的下列子集族 (1) a,b,c,d 又称最大划分(块最多) (7) ,a,b,c,d (6) a,b,c,a,d (5) a,b,c (4) a,b,c,d (3) a,b,c,d (2) a,b,c,d 又称最小划分(块最少) 86 交叉划分 设S1和S2是集合A的两个划分，由S1和S2元素间 所有非空交集作为元素的集合称为S1和S2的交叉划分。 例 S1 a,b,c,d ,S2a,c,b,d的交叉划分为 a,b,c,d 87 加细划分 设S1和S2分别是集合A的两个划分,若对于S1中的任一元 素S1i，在S2中都存在元素S2j,使得S1i S2j,则称S1是S2 的加细划分。若还有S1S2,则称S1是S2的真加细划分。 例 S1a,b,c,d是S2 a,b,c,d的 加细划分且为真加细划分。 88 定理：交叉划分是原来集合的加细划分。 因为S1iS2j S1i且S1iS2j S2j 89 定理：等价关系与划分的关系相互确定 把等价类的性质和划分的定义相比较，易见商集就是A 的一个划分，并且不同的商集将对应于不同的划分。反 之任给A的一个划分S，如下定义A上的关系R： R=|x,yAx与y在S的同一划分块中 则不难证明R为A上的等价关系，且该等价关系所确定 的商集就是S。 由此可见，A上的等价关系与A的划分是一一对应的。 90 例：设Aa,b,c,d,e, R= , , , 则集合A上等价关系R的商集为 A/R=a,b,c,d,e,即为集合A的一个划分。 反之，由划分a,b,c,d,e确定的集合A上的等 价关系为a,ba,b,c,dc,d,ee = , , , 等价关系与划分的关系相互确定 91 例 设Aa1,a2,a3, 求出A上所有的等价关系 解: R=UR R=, R=IR R=, R=, 92 对于n元集合A上的全部划分个数可转化为将n个不同球 放入r(rn)个相同的盒中，无空盒的不同放法数，由第 二类Stirling数求得，记为S(n,r)，此递归公式为： S(n,r)=rS(n-1,r)+S(n-1,r-1). 其中： S(n,0)=0, S(n,1)=1, S(n,2)=2n-1-1, S(n,n-1)= , S(n,n)=1是递归计算的基础。 例如,求4元集A上全部等价关系数,通过求A的全部划分数而给出 解:第二类Stirling个数为=S(4,1)+S(4,2)+S(4,3)+S(4,4) =1+(23-1)+6+1=15. 等价关系与划分 练习：计算5个元素A上的全部等价关系数 93 定义(偏序关系与偏序集) 设R是集合A上的一个二元关 系, 如果R具有自反性, 反对称性和传递性, 那么称R为 一个偏序关系(或部分序, 或半序关系); 记为，并称 为偏序集。 偏序关系 94 例如: 1.实数集合R上的小于等于关系是一个偏序关系， 偏序集为。 2.正整数集I+关于整除关系D是一个偏序关系， 偏序集为。 偏序关系 95 4.集合A=a,b,c,d,e上的关系R是一个偏序关系，偏序 集, 这里 R=, , , 。 偏序关系 3. 集合的包含关系是一个偏序关系，集合全体S作成一 个偏序集. 96 相容关系与覆盖 定义（ 相容关系特殊的关系） 设R是非空集合A上的一个二元关系， 若关系R自反、对称，则称R为A上的相容关系 例如： 实数中的等于关系；直线间的平行关系； 在一群人的集合上年龄相等的关系是相容关系； 而朋友关系也是相容关系。 结论：等价关系是相容关系，反之不真。 97 定义(覆盖) 设A是非空集合,如果存在一个A的子集族 S=A1,A2,Am满足以下条件: (1) Ai(i=1,2,m)非空； (2) S中所有元素的并集等于A； 则称S为A的一个覆盖。 结论：划分是覆盖，反之不真。 相容关系与覆盖 98 例. 考虑集合Aa, b, c, d的下列子集族 (1) a,b,c,d (7) ,a,b,c,d (6) a,b,c,a,d (5) a,b,c (4) a,b,c,d (3) a,b,c,d (2) a,b,c,d 99 例：设集合=a1,a2,a3,a4,a5,a6,a7 R=, , , , a1 a2 a3 a4 a5 a6 a7 相容关系与覆盖 100 相容关系与覆盖 定义（相容类） 设R为A上的相容关系若C A，如果对于C中任 意两个元素a，b，都有aRb，则称C是有相容关系R 产生的相容类。 相容类为 a1,a2,a3,a3,a4 a3,a5,a6,a5,a6,a7 101 相容关系与覆盖 定义（最大相容类） 设R为A上的相容关系不能真包含在任何其它相 容类中的相容类，称为最大相容类。 最大相容类为 a1,a2,a3,a3,a4,a5 a3,a5,a6,a7 102 相容关系与覆盖 定义（完全覆盖） 设R为A上的相容关系其所有最大相容类的集合 称为集合A的完全覆盖。 完全覆盖为 a1,a2,a3,a3,a4,a5 a3,a5,a6,a7 103 相容关系与覆盖 定理（最大相容类） 集合A上的相容关系R与完全覆盖存在一一对应 由完全覆盖a1,a2,a3,a3,a4,a5,a3,a5,a6,a7可得 集合A上的相容关系Ra1a1a2,a3a2,a3 a3,a4,a5a3,a4,a5a3,a5,a6,a7a3,a5,a6,a7 =, , , , , 104 映 射(特殊的二元关系) 定义(映射) 设R是从集合A到集合B的一个二元关系， 若对于集合A中的任一元素x，在B中有唯一的元素y， 使之R, 则称R为从集合A到集合B的一个映射。 记为f, x称为y的原象，y称为x的映象，记y=f(x)。 X的取值范围A称为f(x)的定义域；记domf f(x)|xA称为f(x)的值域；记ranf 结论：映射可以理解为集合A中的每一个元素在B 中有唯一的一个元素与之对应。 映射f与关系R的区别： (1) domf=A; domRA (2) xA,在B中都有唯一的yB，使得f(x)=y 即f(x)=y和f(x)=z, 则一定有y=z (3) 若|A|=m, |B|=n, 则从AB的关系有2mn 而从AB的映射有nm 106 例1： A=x1,x2,x3; B=y1,y2,y3, 则 R1, 是映射 R2 , , , 不是映射 映 射(特殊的二元关系) 例2： A=x1,x2,x3,x4; B=y1,y2,y3, 则 R2, 是映射 107 例3： A=x1,x2,x3; B=y1,y2,y3,y4, 则 R3, 是映射 例4： A=x1,x2,x3,x4; B=y1,y2,y3, 则 R4, 是映射 映 射(特殊的二元关系) 结论： 设f是从集合A到集合B的一个映射, 则映射f满足以下条件： (1) domfA, (2) ranfB, 记作 f: AB. 定义 设A,B为集合,所有从A到B的映射构成集合记为BA, 读作“B上A”.即 BA =f | f:AB , 例如：Ax,y,z B=a,b, 则从A到B的映射为： f1=,；f2=, f3=,；f4=, f5=,；f6=, f7=,；f8=, (3) 若|A|=m, |B|=n, 则从AB的关系有2mn 而从AB的所有映射|BA| =|B|A|=nm 定义（特殊映射） 设f：AB， (1) 若ranf=B，则称f：AB是满射。 (2) x1，x2A，若x1x2，一定有f(x1)f(x2)。 则称f：AB是单射。 (3) 若f：AB既是满射又是单射，则称f：AB是 双射(或一一映射)。 思考：当集合A、B元素有限时，则从A B的 满射，单射，双射间元素个数之间满足 什么关系？ 例如：Ax,y,z B=a,b,下面映射是什么特殊映射？ f1=,； f2=,； f3=,； f4=,； f5=,； f6=,； f7=,； f8=,； 满射 一般映射 满射 满射 一般映射 满射 满射 满射 结论：若f是从A到B的满射，则|A|B|. 例如：Ax,y B=a,b,c,下面映射是什么特殊映射？ f1=,； f2=,； f3=,； f4=,； f5=,； f6=,； f7=,； f8=,； f9=,； 单射 单射 单射 一般映射 一般映射 单射 单射 单射 结论：若f是从A到B的单射，则|A|B|. 一般映射 例如：Ax,y B=a,b,下面映射是什么特殊映射？ f1=,； f2=,； f3 =,； f4 =,； 双射 双射 一般映射 一般映射 结论：若f是从A到B的双射，则|A|B|. 例 判断下面映射是否为单为单 射，满满射，双射的，为为什么? (1) f：RR，f(x)= -x2+2x-1 (2) f：Z+R，f(x)=lnx，Z+为为正整数集 (3) f：RZ，f(x)= (4) f：RR，f(x)=2x+1 115 (1)f：RR，f(x)= -x2+2x-1 例 判断下面映射是否为单射，满射，双射的，为什么? 解： f：RR，f(x)=-x2+2x-1是开口向下的抛物线， 不是单调映射，并且在x=1点取得极大值0。因此 它既不是单射也不是满射。 116 (2) f：Z+R，f(x)=lnx，Z+为正整数集 解：f：Z+R，f(x)=lnx是单调单调 上升的，因此是单单射的, 但不是满满射的，因为为ranf=ln1，ln2， R。 例 判断下面映射是否为单射，满射，双射的，为什么? 117 解：f：RZ，f(x)= 是满满射的，但不是单单射的，例如f(1.5)=f(1.2)=1 (3) f：RZ，f(x)= 例 判断下面映射是否为单射，满射，双射的，为什么? 118 (4) f：RR，f(x)=2x+1 解： f：RR，f(x)=2x+1是满射，单射，双射的， 因为它是单射并且ranf=R。 例 判断下面映射是否为单射，满射，双射的，为什么? 119 常用映射 (1)设f：AB，如果存在bB使得对所有的xA都有 f(x)=b，则称f：AB是常映射； (2)对所有的xA都有IA(x)=x。则称A上的恒等关系IA为 A上的恒等映射且为双射； (3) 设R是A上的等价关系，令 g：AA/R g(a)=aR，aA 称g是从A到商集A/R的自然映射且为满射。 例 A=1,2,3，R=,IA是A上的等价关系, 那么有 g(1)=g(2)=1,2，g(3)=3 120 映射的运算：复合映射与逆映射 定义(复合映射) 设f：A B; g: B C; aA, 规定： (gf)(a)=g(f(a) 则称gf为集合A到集合C的映射，也称g与f的复合 映射。 设f是A上的映射，则定义： f0(x)=x fn(x)=ffn-1(x)= f(fn-1(x), nZ+ 例：设f, g, h: R R ,且有 f(x)x3, g(x)2x1, h(x)x/2. 求 fg, gf, fff2 ， f3 ff2 解： 所求的复合映射都是R到R的映射,且满足 fg(x)f(g(x)(2x1)3=2x4； gf(x)g(f(x)2(x3)12x7； ff(x)f(f(x)(x十3)十3x6； f3(x) ff2(x)f(x6) x63=x9 f h g(x)f(h(g(x)=(2x+1)/23x7/2. 定理: 设f: AB, g: BC (1)如果f, g是单射，则gf :AC也是单射； 反之 若gf :AC是单射，则f是单射； (2) 如果f, g是满射，则gf :AC也是满射； 反之 若gf :AC是满射，则g是满射； (3) 如果f, g是双射，则gf :AC也是双射； 反之 若gf :AC是双射，则g是满射，f是单射； 证明自看p97 123 逆映射 设f : AB的双射,则 f -1是映射, 并且是从B到A的双射； 对双射f : AB, 称f -1 : BA是f 的逆映射； 对任何双射f :AB及其逆映射 f -1 :BA, 它们的复合 都是恒等映射, 且满足 f -1 f IA, f f -1 = IB 结论：若 f：A B的双射; g: B C双射；