集合论初步和关系

第二篇集合论,研究内容,本篇由集合论初步、关系、有限集与无限集、函数四部分构成。,集合论的发展历程,集合论是现代各科数学的基础，它是德国数学家康托（GeogCantor,18451918）于1874年创立的。18761883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。,随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。19041908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。,罗素悖论,1901年罗素提出以下悖论：设论述域是所有集合的集合，并定义集合这样，S是不以自身为元素的全体集合的集合，那么“S”是不是它自己的元素呢？罗素悖论起因于集合可以是自己的元素的概念。康脱以后创立的许多公理化集合论都直接或间接地限制集合成为它自己的元素，因而避免了罗素悖论。,罗素的理发师悖论,住在一个村子里的理发师挂了一个牌子，上面写到：我只给不给自己理发的人理发。考虑这个理发师给不给自己理发？,集合论发展的详细历程,G.Cantor(康脱)是作为数学分支的集合论的奠基人。1870年前后，他关于无穷序列的研究导致集合论的系统发展。1874年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。1878年，他引进了两个集合具有相等的“势”的概念。然而，朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901年罗素发现了有名的罗素悖论。1932年康脱也发表了关于最大基数的悖论。集合论的现代公理化开始于1908年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。另外一种系统是冯诺伊曼-伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理一起称为ZFC系统。,集合论的应用,现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。,第一章集合论初步,集合是现代数学各分支的共同基础，当然也是本书的基础，要求熟练地掌握本章的全部内容。本章的一些内容，如集合的定义、并、交、文氏图等已在中学及大学的其他课程中学习过，但为了内容的完整及这些内容基础地位，仍然会简单介绍一下。本章主要讲述集合的基础理论、基本方法和应用。,1.1集合的基本概念,集合的定义具有某种共同性质的事物汇集为一个整体称为集合。集合不能精确定义。一般用A、X等表示。元素构成这个集合的每一个事物称为元素。可以是具体东西，也可以是抽象的。任一元素或属于该集合或不属于该集合，记为,集合的表示方法,列举法列出集合的所有元素。描述法用谓词来概括集合中元素的属性来表示这个集合。例：Bx|xR且x210表示方程x210的实数解集。归纳定义法,集合间的关系,设A、B为集合，两集合的元素相等，则集合相等记为A=B；否则AB设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作。真包含关系:记作,注意集合、元素之间的关系,属于关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如Aa，a和B=a，既有aA，又有aA。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的。,定义全集、空集及相关定理,定义：全集-所有考虑对象的全体；空集-不含任何元素的集合；有限集-集合的元素个数为有限个；无限集-集合的元素个数为无限个。定理：设A、B是一集合，E为全集，有（1）（2）A=B的充要条件是A、B相互包含。,集合代数（A、B为集合）,A和B的交记为，定义为：A和B的并记为，定义为：A和B的差记为，定义为：A和B的对称差记为，定义为：A的补记为，定义为：若，则称A、B是分离的。,集合运算的定律,(1)交换律(2)结合律(3)分配律(4)幂等律,(5)同一律(6)零一律(7)吸收律(8)德摩根律(9)双补律,例1,证明A(BC)(AB)(AC)证：对任意x,有故A(BC)(AB)(AC),例2,证明A(AB)A证：A(AB)(AE)(AB)A(EB)A(BE)AEA,例3,化简(ABC)(AB)(A(BC)A)。解：由ABABC，AA(BC)，有原式(AB)ABA,例4,证明,注意：上式给出了AB的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。,1.2幂集、n元有序组、笛卡尔乘积,定义幂集设A是一个集合，A的幂集是A的所有子集的集合，即定理若集合A为n个元素的有限集，则A的幂集的元素个数为2n，因此A的幂集也记为2A。,求下列集合的幂集,例1例2例3,n元有序组,定义：两个按照一定次序排列的客体a、组成一个有序序列称为有序偶，记以（，）。其中为第一客体，为第二客体。序偶相等：有序偶（，）（，），如果有，则说序偶相等。例：平面坐标系中点的坐标。,定义个按一定次序排列的客体组成一个有序序列，称为元有序组，并记以例：身份证号码时间的表示学生的学号,笛卡尔乘积,定义：集合、的笛卡尔乘积表示为例1：一小时内的时间表示，某时某分（a,b）可用笛卡尔乘积表示。教材第12页。例2：A=1，2，B=a,b,则,几个定义,集合A的笛卡尔乘积定义定义：集合、C的笛卡尔乘积表示为以此类推，可以定义n个集合的笛卡尔乘积考虑是否相等？,第二章关系,在现实世界中，事物之间都有联系，单值依赖联系是事物之间联系中比较简单的，比如说日常生活中事物的成对出现，而这种成对出现的事物具有一定的顺序，例如，上、下；大、小；左、右；父、子；高、矮等等。通过这种联系，研究事物的运动规律或状态变化。世界是复杂的，运动也是复杂的，事物之间的联系形式是各种各样的，不仅有单值依赖关系，更有多值依赖关系。,“关系”这个概念就提供了一种描述事物多值依赖的数学工具。这样，集合，映射关系等概念是描述自然现象及其相互联系的有力工具，为建立系统的、技术过程的数学模型提供了描述工具和研究方法。映射是关系的一种特例。,本章主要讨论关系及其表示，关系的运算及一些常见的关系。关系是一个基本概念，在数学和计算机中用关系来描述各集合及各元素间的联系。,2.1关系的基本概念,例设有两间学生宿舍a、b,有6位同学分配宿舍。讨论“某位同学住哪间宿舍”这种关系，用R来表示。设分配方案如下:1-a,2-b,3-b,4-a,5-a,6-a(1)可记为1Ra,2Rb,3Rb,4Ra,5Ra,6Ra；(2)也可用序偶的形式定义为R=(1,a),(2,b),(3,b),(4,a),(5,a),(6,a)(3)从子集的角度上定义，设A=1，2，3，4，5，6，B=a,b,R是笛卡尔乘积AB的一个子集。,定义,设A、B为集合，称的一个子集R为从A到B的一个二元关系。关系R中的有序偶即是集合R的元素。对于二元关系，若，则称、有关系，可记作xRy；若，则记作。D(R):R的定义域。R中序偶的第一客体允许选择对象的范围。C(R):R的值域。R中序偶的第二客体允许选择对象的范围。,空关系：全关系：A上的关系：当集合A=B时，或者（）（）=A。定义：n元关系R是的一个子集。A上的恒等关系通常记IA。,例子,例1.设A=1,2，B=2,3,4,(1,3),(2,3)，(1,4),(1,2),(2,2)都是从A到B的二元关系，同时(1,2),(2,2)也是A上的二元关系。例2.实数集上的大于关系。例3.设A=2，3，4，5，6，A上的整除关系。“/”=R=(2,2),(3,3),(4,4),(5,5),(6,6),(2,4),(3,6),(2,6),关系的表示方法,关系的表示方法有三种：集合表示法，关系矩阵和关系图。1.集合表示法因为关系是一个集合，因此可以用集合的列举法或描述法来表示它。在前面的叙述中，已经多次采用了这两种方法。例：R1=(a,b)|(a+b)/5是整数用的是描述法，R2=(1,2),(2,4),(3,3)用的是列举法。,关系的图的表示,通常可以用图来刻画关系。关系图使关系表示更直观。设,RAB,在平面上用或分别标出A、B中元素的点（称为结点）。如果，则自结点ai至结点bj作一条有向弧，箭头指向bj，采用这种方法连接起来的图称为R的关系图。,例1,设A=1,2,3,4,R=,，R的关系图为：,例2,设A=1,2,3,4，R是A上关系。R=(1,1),(1,2),(2,3),(2,4),(4,2)，写出R的关系图。,关系的矩阵表示,关系矩阵：设，R是A上的关系，令，则称为R的关系矩阵，记作MR。关系矩阵为关系的运算提供了数学运算对象。,基于关系与关系矩阵互相唯一决定的特性，可用关系矩阵有效地刻画关系的许多性质。如对于有限集A上的任意关系R与S：空关系的关系矩阵为全零矩阵：；全关系的关系矩阵为全1矩阵，记为J；相等关系的关系矩阵为单位矩阵：。,例1,设A=1,2,3,4,写出集合A上大于关系“”的关系矩阵。解：=,，故关系矩阵,例2,设A=2,3,4,5，B=6,7,8,9，由A到B的关系R定义为R=(a,b)|a与b互质。试写出R的关系矩阵MR。解R=(2,7),(2,9),(3,7),(3,8),(4,7),(4,9)(5,6),(5,7),(5,8),(5,9)，所以关系矩阵为,2.2关系的运算,关系的交、并、补、差由于关系是有序偶的集合，有关集合的运算在关系中也是适用的。例：教材第17页。,复合关系,设R是从X到Y上的关系，S是Y到Z上的关系，则R与S的复合关系RS定义为例：R=(1,2),(3,4),(2,2),S=(4,2),(2,5),(3,1),则,例1,设A=a,b,B=1,2,3,4,C=5,6,7,R=,S=,。则，。,例2,设A=1,2,3,4,A上的关系R=,S=,，求解,上例2矩阵表示则,复合关系运算不满足交换律，但关系的复合运算满足结合律。复合关系可以用图形表示，也可以用矩阵来求。关系的矩阵运算是布尔运算，只涉及0和1。布尔加：0+0=0，1+1=1，0+1=1+0=1布尔乘：1*1=1，1*0=0*1=0*0=0,定理：设、S、T分别表示从X到Y、Y到Z、Z到U的关系，则有定理的证明可见教材。定义：设X上关系R，则Rn定义如下：易知,逆关系,定义：设R是从X到Y的关系，R=(x,y)|xX,yY，则从Y到X的关系(y,x)|xX,yY，称为R的逆关系。也记为R-1。R的逆关系R-1就是R中所有序偶第一第二客体顺序颠倒后所得集合。定理：设R、S分别是从X到Y，从Y到Z的关系，则,逆关系的图形表示和矩阵表示。关系R的逆关系图是R的关系图的有向边方向改变。关系R的逆关系矩阵是MRT，即原矩阵的转置矩阵。例：教材20页例2.7,2.3关系的重要性质,通过上述讨论，我们已经看到在集合X上可以定义很多不同的关系，但真正有实际意义的只是其中的一小部分，它们一般都是有着某些性质的关系，下面我们讨论集合X上的二元关系R的一些特殊性质。设R是X上的二元关系，R的主要性质有以下5种：自反性，对称性，传递性，反自反性和反对称性。,关系的5个性质,定义设R为集合A上的二元关系，则(1)若对所有的aA，有(a,a)R，则称R是自反的；(2)若对所有的aA，有(a,a)R，则称R为反自反的;(3)对任意a,bA，若有(a,b)R，就必有(b,a)R，则称R是对称的；,(4)若有(a,b)R，ab,必有(b,a)R，则称R为反对称的；或者定义：对任意a,bA，若有(a,b)R，(b,a)R，就必有a=b，则称R为反对称的；(5)对任意a,b,cA，若有(a,b)R，(b,c)R，就必有(a,c)R，则称R为传递关系。,例1设A=a,b,c,d,判断下列关系是否为自反关系或反自反关系；R1=(a,b),(b,c)R2=(a,a),(b,b),(c,c),(d,a)R3=(a,a),(a,b),(d,d),(c,c),(b,b)R4=(a,a),(b,b),(c,c),(d,d),例2,判断下列关系是否为对称关系或反对称关系；R5=(a,a),(a,b),(b,a),(b,c),(c,b)R6=(a,a),(a,b),(b,c),(d,c)R7=(a,a),(c,b),(c,d),(d,c)R8=(b,b),(d,d),例3,判断下列关系是否为传递关系。R9=(b,c),(c,c),(c,d),(b,d)R10=(b,c),(c,b),(b,b),(a,d)R11=(b,c),(d,a),(d,c)解：R9是传递关系。R10不是传递关系。R11是传递关系。,关系的这些性质，在关系矩阵和关系图上大多可以得到明确的反映。,若关系r是自反的，则关系矩阵的主对角线上的元素全为1；若r是对称的，则关系矩阵是对称阵；若r是反对称的，则对ij，若aij=1，则aji=0。,若关系r是自反的，则r的关系图中的每一个结点引出一个单边环；若r是对称的，则在关系图中，对每一由结点ai指向结点aj的边，必有一相反方向的边；若r是反对称的，则在其图中，任何两个不同的节点间最多只有一条边，而不会同时有两条相反方向的边；若r是传递的，则若有由结点ai指向ak的边，且又有由结点ak指向aj的边，就必有一条由结点ai指向aj的边。,从集合上判断关系性质,R自反的当且仅当R反自反的当且仅当R是对称的当且仅当R是反对称的当且仅当R是传递的当且仅当,从关系图上判断,每一个结点都有环，则R具有自反性。每一个结点都没有环，则R具有反自反性。若两个不同点之间有边，则一定成对出现，那么R有对称性。若任两个不同点之间的有向边都不成对出现，那么R有对称性。任三个结点a、b、c，不存在这样的情形，有a到b，b到c的有向边，但没有a到c的有向边，则R有传递性。,从关系矩阵上判断，记MR=（rij）,R有自反性等价于rii=1,i=1n，R有反自反性等价于rii=0,i=1nR有对称性等价于rij=rji，R有反对称性等价于rij+rji1，任意ij设M(R2)中某元素sij=1,那么M(R)中rij=1,则R有传递性等价于sijrij,思考,数集上的小于关系、等于关系、小于等于关系具有的性质。幂集上的包含关系具有什么性质。整数集上的整除关系具有什么性质。非空集上的空关系、全关系具有的性质。空集上的关系具有的性质。恒等关系具有的性质。,2.4关系上的闭包运算,给定一个关系，通过增补一些元素，使得它具有我们希望的性质，这就是闭包运算。例：设A=a,b,c，R=(a,b),(b,c),(c,a)，求自反、对称、传递闭包r(R),s(R),t(R)。,定义关系的闭包运算,设R为集合A上的二元关系，如果A上的二元关系R1满足：(1)R1是自反(对称、传递)的；(2)；(3)若A上的二元关系R2也满足(1)、(2)有；则称R1为R的自反、对称、传递闭包，记为r(R)、s(R)、t(R)。,闭包的说明,一个关系对应的闭包就是包含原关系的具有所求性质的一种最小的关系。从定义可以看出，R的自反(对称、传递)闭包就是包含R并且具有自反(对称、传递)性质的最少元素的一种关系。显然，若R已经是自反(对称、传递)的，那么R的自反(对称、传递)闭包就是它自身。,构造闭包的方法,定理1设R是A上关系，则r(R)=RIA定理2定理3若A是n个元素的有限集，则,例,1、求整数集上小于关系的自反闭包，对称闭包，传递闭包。2、设A=a,b,c，R=(a,b),(b,c),(c,a)，求闭包r(R),s(R),t(R),解,r(R)=R(a,a),(b,b),(c,c)s(R)=R(b,a),(c,b),(a,c)t(R)=RR2R3其中R2=(a,c),(b,a),(c,b)R3=(a,a),(b,b),(c,c),利用关系矩阵求闭包,设关系R，关系矩阵为M，r(R),s(R),t(R)的关系矩阵分别为Mr,Ms,Mt，则,利用关系图求闭包,设关系R，r(R),s(R),t(R)的关系图分别记为Gr,Gs,Gt，以下述方法添加新的边得到闭包：自反闭包：将没有环的结点加上一个环。对称闭包：考察每一条边，如果有一条单向边，则加一条反方向边。传递闭包：如果从a到b有边，b到c有边，ac间没有边，则在ac间加一条边，使得关系图具有传递性。,例,设关系R，r(R),s(R),t(R)，关系图如下图所示。,练习题,设A=a,b,c,d上的关系R=(a,b),(b,a),(b,c),(c,d)(1)写出R，r(R),s(R),t(R)的关系图。(2)计算r(R),s(R),t(R)。(3)写出R，r(R),s(R),t(R)的关系矩阵。,解：,矩阵,2.5次序关系,定义设R是集合X上的二元关系，若R具有自反性、反对称性和传递性，则称R为X上的偏序关系，记为“”。（区别于常规的小于等于符号）称集合X为R的偏序集，用（X，R）表示。例：数集上小于等于关系；集合A的幂集P（A）上的包含关系；集合A=2，3，4，6，7，8上的整除关系都是偏序关系。,拟序关系,定义拟序关系：设R是集合X上的二元关系，若R具有反自反性、传递性，则称R为X上的拟序关系，记为“”。例：数集上小于关系；集合A的幂集P（A）上的真包含关系。,拟序和偏序,定理：集合X上的关系是拟序的，则其必是反对称的。证明：反证法。定理：设R是X上的关系，则：（1）如果R是一个拟序关系，则r(R)=RIX（2）如果R是一个偏序关系，则R-IX是拟序关系。,线性次序,定义：线性次序关系设R是X上的偏序，如果对每个x,y,必有xy或yx，则称R是线性次序的（也叫全序的）或称R是X上的线性次序关系。例：教材书26页例2.31、例2.32例：字典次序,偏序集上的元素,定义：设偏序集(A,),(1)若成立，则称y为B的最大元素；(2)若成立，则称y为B的最小元素；(3)若成立，则称y为B的极大元素；即没有比y更大的元素。(4)若成立，则称y为B的极小元素；即没有比y更小的元素。,最小元与极小元的不同,(1)最小元是B中最小的元素，它与B中其它元素都可比；而极小元不一定与B中所有元素可比，只要没有比它小的元素，它就是极小元。(2)对于有限集，极小元一定存在，但最小元不一定存在。(3)最小元如果存在，一定是唯一的，但极小元可能有多个。(4)如果B中只有一个极小元，则它一定是最小元。(5)如果B中有最小元，则一定是B的唯一的极小元。,定义：设yA，B是A的子集,（1）若成立，则称y为B的上界；（2）若成立，则称y为B的下界；（3）令，则称C的最小元素为B的最小上界或上确界；（4）令，则称C的最大元素为B的最大下界或下确界。,分析,由以上定义可知，B的最小元一定是B的下界，同时也是B的最大下界。同样，B的最大元一定是B的上界，同时也是B的最小上界。但反过来不一定正确，B的下界不一定是B的最小元，因为它可能不是B中的元素。同样，B的上界也不一定是B的最大元。B的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界与最大下界是唯一的。,定理,设(A,)为偏序集，B是A的子集，(1)如果y是B的最大元素，那么y是B的极大元素；(2)如果y是B的最大元素，那么y是B的上确界；(3)如果y是B的一个上界且yB，那么y是B的最大元素。同样，若y是最小元素，也有同样的结果。,例：写出最元，极元，上下界,1、A=1，2，3，4，5，6，B=2，3，4。2、A=a,b,c,P(A)上的包含关系是偏序关系。3、A=2x18,xN，R是A上整除关系。（1）R=3，4，7，9（2）S=3，6，9，18（3）T=3，6，9，12，15，18,哈斯图,X上偏序关系可用Hasse图来表示，规则如下：（1）用平面上结点表示偏序集中的元素，对X中任一元素。（2）若xy,且xy，则将x画在y的下面。（3）若xy,xy，且没有不同于xy之间的元素z，使得xyz，则在xy之间用直线连接它们。用以上方法表示的图称为哈斯图。,例1：设A=1,2,3,4,6,12，则是偏序集。,=,关系图比较复杂略，关系矩阵为,例2：设B=2,3,6,12,24,36，是B上的整除关系,B上整除关系略。A、B的哈斯图如下：,例3,设集合A=1,2,3,4,5,6,7,8,9,10,11，偏序集的（A，）哈斯图如下图。求上、下界。B1=1,2,3,4,5,6,7B2=8,9,10,11B3=6,7,8,9B4=6,7,8,9,10,11B5=2,3,4,5,写出上、下界,8,9分别是集合B1=1,2,3,4,5,6,7A的上界；1,2,3,4,5,6,7分别是集合B2=8,9,10,11A的下界；2,3,4,5都不是集合B3=6,7,8,9A的下界；B4=6,7,8,9,10,11A的最大下界(下确界)是1；B5=2,3,4,5A的最下上界（上确界）是9。,例偏序集，由如下哈斯图给出。写出最元、极元。,（1）B1=b,d,e,g（2）B2=b,c,d,e,f,g（3）B3=a,c,d（4）B4=d,e,最元、极元,B1的最大元为g；B1的极大元为g；B1的最小元为b；B1的极小元也为b。B2无最大元和最小元；B2的极大元是f,g；极小元是b,c。B3无最大元，其最小元为a；B3的极大元为c,d；极小元为a。B4无最大元，也无最小元；B4的极大元、极小元都是d,e。,例:如下哈斯图表示一偏序集。,考虑集合B1=h,i，它有上界j，k，但无最小上界；它有下界f，g,b,c,d,e,a，但没有最大下界。当B2=b,c,d,e时，它有上界h，i,j,k，无最小上界；它没有下界和最大下界。,2.6相容关系,定义：一个在X上的关系R，如果是自反的、对称的，则称R为相容关系。用表示。一般而言，相容关系并不满足传递性。例：教材例2.39、例2.40。例：班里同姓的同学。修同一门课程的同学。同一年出生的同学。,相容关系的关系矩阵是对称的，且对角线元素均为1。相容关系图的简化：结点上环去掉，两点间双向的两条边把方向去掉，改成无向的一条边。,最大相容性分块,定义：设有集合X上的相容关系，A是X的子集，如A中任何元素都互为相容关系，且X-A中的任何元素没有一个与A中所有元素相容，则称A是X中的极大相容性分块。例：班里同姓的同学。修同一门课程的同学。同一年出生的同学。均是相容关系，且是极大相容性分块。,最大完全多边形：它的任一顶点与其他顶点相连，且这种多边形不能再扩充。如：三个结点的最大完全多边形是三角形；四个结点的是对角线相连的四边形。从图的观念上看，如果在图中各结点构成一个最大完全多边形，则这些结点构成了一个极大相容性分块。,例,设给定的相容关系图为下图，求它的极大相容性分块。,解：,极大相容性分块为：a1,a2,a4,a6,a3,a4,a6,a4,a5,a7,例：相容关系的极大相容性分块,（1）1，3，4，2，3，4，5（2）a,b,c，a,b,d,完全覆盖,定义：设有X上的相容关系，它的极大相容性分块的集合称为X的完全覆盖。定义：X上的每个相容关系，唯一的定义一个完全覆盖。覆盖的定义：设X是非空集合，S=S1,S2,Sm，其中Si都是X的非空子集，如果，则称S是集合X的一个覆盖。,2.7等价关系,定义：X上的关系R如果是自反的、对称的、传递的，则称R为等价关系。例：任何集合上的恒等关系和全关系都是等价关系；空集上的二元关系是等价关系，但非空集合上的空关系不是等价关系。例：三角形集合的相似关系。班级同学集合上的同学关系，同龄关系。,例：整数集上的同余关系,整数集上关系R=（x,y）|x-y能被m整除。关系R是等价关系。证明：R有自反性；对称性；传递性。满足这个关系R的x、y用m除后有相同的余数，故也称R为同余关系，或以m为模的同余关系。一般将xRy写成xy(modm)叫做x与y对模m是同余的，这个式子叫做同余式。对于x、y,有x-y=mk,k为整数。,模为3的同余关系,设A=0,1,2,3,5,6,8，R为A上的模3等价关系，则R=,。R的关系图见图,划分,定义：设A1、A2Am是S的子集，如果满足：（1）所有的Ai间是分离的。（2）则称A=A1、A2Am为S的一个划分，A1、A2Am为划分的块。,等价类,定义：设R是X上等价关系，对任意x可以构造X的子集xR=y|yX且xRy,称之为x对于R的等价类。xR是X内所有与x有等价关系R的元素构成的集合。有如下性质：（1）（2）若yxR,则xR=yR（3）若yyR,但，则xRyR,等价类,由等价类的定义性质知:X内的任两元素对于R的等价类或相等或分离，故X内所有元素对R的等价类的并集就是X。也可以说，X的元素对于R的等价类定义了X的一个划分，且这样的划分就是唯一的。原因：由等价类的性质知等价关系R构成的类两两不相交，且覆盖X，且X的所有元素对于R的等价类是唯一的。,商集,定理：X上的等价关系R所构成的类产生一个集合X的划分，此划分叫X关于R的商集。记X/R。X/R是一个集合，元素是X上的元素所构成的等价类。商集的所有元素即