第10章 关 系 关系是在集合上定义的一个常用的概念．例如，在自然数之间可以定义相等关系和小于关系，在命题公式之间可以定义等价关系和永真蕴涵关系，在集合A的各子集之间可以定义相等关系和包含关系．此外，在学生和课程之间存在选课关系，在课程表上反映了课程、班级、教师、教室、时间等之间的关系．关系就是联系，也就是映射．在数据库的一种重要类型关系数据库中保存了各数据项之间的关系，关系数据库中的数据结构就是按照本章所定义的关系设计的．

10．1 二元关系 10．1．1 二元关系的定义 定义10．1．1 对集合A和B，A×B的任一子集称为A到B的一个二元关系，一般记作R．若<x，y>∈R，可记作xRy;若<x,y>R，可记作x y．在A=B时，A×A的任一子集称为A上的一个二元关系．二元关系可简称关系． 从形式上说，二元关系是笛卡儿积的子集，换句话说，它是有序对的集合．从语义上说，二元关系是集合A和B元素之间的联系．从下面的例子可以看出这种联系．

例1 设A＝{0，1}，B={a，b}．则 Rl={<0，a>}， R2={<0，a>，<0，b>，<l，a>} 是A到B的两个二元关系． R3＝{<O，1>，<1，0>} R4＝{<0，1>，<0，0>，<1，0>} 是A上的两个二元关系．

例2 设X＝{1，2，3}，定义X上的关系Dx和Lx为 Dx={<x,y>|x∈X∧y∈X∧x整除y} Lx＝{<x，y>|x∈X∧y∈X∧x≤y} 于是，Dx是 Dx={<1，1>，<2，2>，<3，3>，<1，2>，<1，3>}． Lx关系是 Lx={<1，1>，<2，2>，<3，3>，<1，2>，<1，3>，<2，3>}．

例3 对任意的集合A，在P(A)上的包含关系R1和真包含关系R2定义为 R1={<x,y>|x∈P(A)∧y∈P(A)∧xy} R2={<x,y>|x∈P(A)^y∈P(A)^xy}

若A＝{}，则P(A)＝{，{}}，P(A)上的R1和R2是

二元关系是二元组的集合．推广这个概念，可以用n元组的集合定义n元关系． 定义10．1．2 若n∈N且n>1，A1，A2，…，An是n个集合，则A1×A2×…×An的任一子集称为从A1到An上的一个n元关系．

10.1.2 特殊的关系 下面定义三个A上的特殊的关系． 定义10．1．3 对任意的集合A． (1)A上的恒等关系IA定义为 10.1.2 特殊的关系 下面定义三个A上的特殊的关系． 定义10．1．3 对任意的集合A． (1)A上的恒等关系IA定义为 IA={<x，x>x∈A}， (2)A上的全域关系(全关系)EA定义为 EA={<x，y>|x∈A^y∈A}， (3) 是A上的空关系．

例4 设A＝<a，b>，则 IA={<a，a>，<b，b>}， EA={<a，a>，<a,b>，<b，a>，<b，b>}．

10．1．3 定义域和值域 定义10．1. 4 对A到B的一个关系R，可以定义 (1)R的定义域dom(R)为 10．1．3 定义域和值域 定义10．1. 4 对A到B的一个关系R，可以定义 (1)R的定义域dom(R)为 dom(R)={x|(y)(<x,y>∈R)}， (2)R的值域ran(R)为 ran(R)={y|(x)(<x,y>∈R)}， (3)R的域fld(R)为 fld(R)=dom(R)U ran(R)，

例5 设A＝{a，b，c}，B＝{b，c，d}，A到B的关系R={<a,b>，<b,c>，<b,d>}，则 dom(R)={a，b}， ran(R)＝{b，c，d}， fld(R)={a，b，c，d}．

定理10．1．1 对A到B的关系R如果<x,y>∈R，则x∈UUR，y∈UUR 证明 已知<x,y>∈R，即{{x}，{x，y}}∈R．因{x，y}是R的元素的元素，故{x，y}∈U R．因x和y是UR的元素的元素，故x∈UUR,y∈UUR． 定理10．1．2 对A到B的关系R，则 fld(R)=UU R，

证明 对任意的x，若x∈fld(R)，则x∈dom(R)或x∈ran(R)．则存在y，使<x,y>∈R或<y，x>∈R．这时都有x∈UUR． 对任意的t，若t∈UUR．因为R的元素的形式是{{x},{x，y}}，所以必存在u，使{{t},{t，u}}∈R 或{{u},{u，t}}∈R．也就是t∈fld(R)．

10．2 关系矩阵和关系图 描述关系的方法有三种：集合表达式、关系矩阵和关系图。关系的定义使用了集合表达式，这一节介绍后两种方法，对有限集合上的关系，采用关系矩阵和关系图的方法，不仅使分析更加方便，而且有利于使用计算机处理，

10．2．1 关系矩阵 定义10．2．1 设集合X＝{xl，x2，…，xm}，Y＝{yl，y2，…，yn}， 10．2．1 关系矩阵 定义10．2．1 设集合X＝{xl，x2，…，xm}，Y＝{yl，y2，…，yn}， (1)若R是X到Y的一个关系，则R的关系矩阵是m×n矩阵(m行,n列的矩阵)

(2)若R是X上的一个关系，则R的关系矩阵是m×m方阵(m行、m列的矩阵)

A到B的关系R是A×B的子集，A×B有m×n个有序对．矩阵M(R)有m行(行为横向)、n列(列为竖向)，共有m×n个元素．因此，M(R)的每个元素恰好对应A×B的一个有序对．用M(R)中元素rij的值表示有序对<xi，yj>是否在R中，因为只有属于和不属于两种情况，所以rij只取值0和1是合理的．

在矩阵右方和下方标注了X和Y的元素，标注表明，x1对应第1行，x2对应第2行，y1对应第1列，依此类推．因此，第1行第3列交点的r13=1表示<x1，y3>∈R，而第3行第1列的r31＝0表示<x3，y1>  R．在使用关系矩阵时，集合X和Y中的元素分别进行了排序．这时就不必在矩阵上标注这些元素，而且也不难确定一个矩阵元素对应的有序对

例2 设A＝{1，2，3，4}，A上的大于关系>定义为>={<2，l>，<3，1>，<4，1>，<3，2>，<4，2>，<4，3>}．则关系>的关系矩阵是

10．2．2 关系 定义10．2．2 设集合X＝{x1，x2，…，xm}，Y＝{y1，y2，…yn}． 10．2．2 关系 定义10．2．2 设集合X＝{x1，x2，…，xm}，Y＝{y1，y2，…yn}． (1)若只是X到Y的一个关系，则R的关系图是一个有向图G(R)＝<V，E>，它的顶点集是V＝X∪Y，边集是E，从xi到yj的有向边eij∈E，当且仅当<xi，yj>∈R． (2)若R是X上的一个关系，则R的关系图是一个有向图G(R)＝<V．E>，它的顶点集是V＝X，边集是E，从xi到xj的有向边eij∈E当且仅当<xi，xj>∈R．

例3 对例1中的X到Y的关系R，关系图G(R)如图10．2．1所示．在XY时．为了图示清楚，通常把定义域的元素x1，x2等画在一边，把值域中的元素y1,y2画在另一边．

例4 对例2中的A上的关系>，关系图G(>)如图10．2．2所示．对A上的关系．关系图中一般不区分定义域和值域，每个顶点既可以发出有向边，又可以收到有向边．

例5 对A={a,b,c}上的关系 R＝{<a，a>，<a，b>,<b,b>，<b，c>}，关系图G(R)如图10．2．3所示．图中从a到a的有向边eaa表示<a,a>∈R，这类有向边称为自圈．

10．3 关系的逆、合成、限制和象 一个关系的逆是另一个关系，两个关系的合成是第三个关系．求关系的逆与合成都是构造新关系的方法，也都是关系的运算．

10．3．1 定义 定义10．3．1 对X到Y的关系R，Y到Z的关系S，定义 (1)R的逆R-1为Y到X的关系 10．3．1 定义 定义10．3．1 对X到Y的关系R，Y到Z的关系S，定义 (1)R的逆R-1为Y到X的关系 R-1＝{<x，y>|<y，x>∈R}， (2)R与S的合成SR为X到Z的关系 SR＝{<x，y>|(z)(<x，z>∈R^ <z，y>∈S)}． 此外，对任意的集合A，还可定义

(4)A在R下的象R[A]为集合 R[A]＝{y|(x)(x∈A^<x，y>∈R)}．

对R的每个有序对<x，y>，把两个元颠倒得到有序对<y，x>，这些<y，x>的集合就是R-1．把R的关系图中每个有向边的方向颠倒就得到R-1的关系图． 如果在关系R和S中各有一个有序对，使<x，z>∈R且<z，y>∈S，则<x，y>是关系SR的元素．而且，SR包含全部这样的有序对．关系的合成如图10．3．1所示．因为<5，6>∈R且<6，7>∈S，故<5，7>∈SR．虽有<1，2>∈R，但不存在y使<2，y>∈S，故没有y使<1,y>∈SR也没有x使<x,4>∈SR．

注意，X到Y的关系R和Y到Z的关系S合成为SR，而不写成RS(注：有的书写为RS．)SR是X到Z的关系．为了求SR，应把R中每个有序对与S中每个有序对一一配合，以此确定SR的每个有序对． R A是关系R的子集，其中每个有序对<x,y>满足x∈A．可以说R A是A到Y的关系．也可以说是X到Y的关系．当dom(R) ∈A时，R A＝R．R[A]是一个集合，它实质上是只R A的值域．

例1 设集合A上的关系R为 A={a，{a}，{{a}}}， R={<a，{a}>，<{a}，{{a}}>}．

例2 设集合N上的关系R和S为 R＝{<1，2>，<1，3>，<2，3>，<3，4>}， S={<3，4>，<4，5>，<5，4>}． 则 R-1＝{<2，1>，<3，1>，<3，2>，<4，3>}， SR＝{<1，4>，<2，4>，<3，5>}， RS＝．

10．3．2 SR的关系矩阵 R-1的关系矩阵M(R-1)就是R的关系矩阵的转置矩阵．也就是说，把M(R)中每一对rij和rji(i≠j)互换就得到M(R-1)，下面介绍求SR的关系矩阵的方法． 如果A是有限集合，|A|=n．关系R和S都是A上的关系，R和S的关系矩阵M(R)=(rij)和M(S)＝(sij)都是nXn的方阵．于是SR的关系矩阵 M(SR)＝(wij)，可以用下述的矩阵逻辑乘法计算(类似于矩阵乘法)．可以写为 M(SR)=M(R)M(S)，

其中 wij＝∨k=1~n(rik∧skj)．这是由M(S)和M(R)的元素计算M(S，R)的元素wij的方法．式中的^和V分别为在集合{0，1}上的运算． ^是逻辑乘，1^1＝l，而0^1=1^0＝0^0＝0(它对应合取词)． V是逻辑和，0V 0＝0，1V0=0V1=1V1＝1(它对应析取词)．

例3 设集合A＝{1,2,3,4}，A上的关系 R＝{<1,2>,<3,4>,<2,2>}， S＝{<4,2>,<2,4>,<3,1>,<1,3>}．则

10．3．3 性质 1. 关于逆 注意，左边关系的矩阵描述为(M(R)M(S))T 10．3．3 性质 1. 关于逆 定理10.3.1 对X到Y的关系R和Y到Z的关系S，则 (1)dom(R-1)＝ran(R)， (2)ran(R-1)=dom(R)， (3)(R-1)-1＝R， (4)(SR)-1=R-1S-1 注意，左边关系的矩阵描述为(M(R)M(S))T 右边关系的矩阵描述为M(S)TM(R) T ，显然两边相等 证明 (1)对任意的x，有 x∈dom(R-1)(y)(<x，y>∈R-1) (y)(<y，x>∈R)x∈ran(R)， 所以，dom(R-1)＝ran(R)． (2)类似于(1)．

2. 合成满足结合律 定理10.3.2 对X到Y的关系Q，Y到Z的关系S，Z到W的关系R，则 关系的合成是关系的运算．定理表明，这个运算满足结合律．但是它不满足交换律，—般SRRS．

3. 关于合成的分配律 (分配律分左右两种；合成对交的分配不能保持) 定理10.3.3 对X到Y的关系R2和R3，Y到Z的关系R1，有 (1)R1(R2UR3)＝R1R2UR1R3， (2)R1(R2∩R3)R1R2∩R1R3 ， 对X到Y的关系R3，Y到Z的关系R1、R2，有 (3)(R1UR2) R3＝R1R3UR2R3， (4)(R1∩R2) R3  R1R3∩R2R3， (注意，规定关系合成符优先于集合运算符．) 证明 P167.

4. 关于象的分配律 定理10.3.3 对X到Y的关系R集合A,B,有 (1)R[AUB]＝R[A]UR[B]， (2)R[UA]=U{R[B] | B ∈A}， (3)R[A∩B]  R[A] ∩ R[B]， (4)R[∩A]  ∩{R[B] | B ∈A }，A =/= ø (5)R[A]-R[B]  R[A-B] 证明 只证(2)，(3)其他留作思考题，

4. 关于象的分配律 象对交的分配不能保持； 第四条中，A为空集时 A无意义，见p134

R＝{<x，y>|x∈Z^y∈Z^y＝x2} (这里的R有具体的含意)， 上面定理中包含关系为真包含的例子 例4 设整数集合Z上的关系R为 R＝{<x，y>|x∈Z^y∈Z^y＝x2} (这里的R有具体的含意)， 集合A＝{1，2}，B＝{O，-l，-2}． 于是R[A]＝{1，4}因为<1,1>R, <2,4>R 于是R[B]＝{0，1，4}因为..． 故R[A∩B]＝ , R[A]∩R[B]={1，4} ． 此外， R[A]-R[B]= , R[A-B]={1，4} ．

10．4关系的性质 在实际问题中，我们感兴趣的往往不是一般的关系，而是具有某些特殊性质的关系．为了更好地处理这些关系，有必要深入研究关系的性质．对A上的关系来说，主要的性质有：自反性、非自反性、对称性、反对称性、传递性．这一节定义这些性质，并给出若干结论．

10．4．1 定义 一、自反、反自反 1. 定义 定义10．4．1 对A上的关系R，若对任意的x∈A都有xRx，则称R为A上自反的关系，若对任意的x∈A都有 ，则称R为A上非自反的关系． 这个定义也可以写成： R是A上自反的(x)(x∈A→xRx)， R是A上非自反的(x)(x∈A→ )，

2. 关于自反、反自反、均满足、均不满足的例子 例1 在非空集合A上的恒等关系IA和全关系EA都是自反的． 在集合B＝{x|x∈N^x≠0}上的整除关系DB和小于等于关系LB都是自反的． 在集合A的幂集P(A)上的包含关系和相等关系＝都是自反的，这些关系都不是非自反的．

例2 在非空集合A上的空关系ø是非自反的．在集合N上的小于关系<是非自反的．在集合A的幂集P(A)上的真包含关系是非自反的． 这些关系都不是自反的．

例3 在集合A＝{l，2，3}上的关系 R＝{<1，1>，<2，2>，<3，1>} 不是自反的，也不是非自反的．但是在非空集合A上，不存在一个关系，它是自反的又是非自反的． 3.等价描述 如果R是A上自反的，则关系矩阵M(R)的主对角线元素都是1(即rii都是1)，关系图G(R)的每个顶点都有自圈．如果R是A上非自反的，则M(R)的主对角线元素都是0，G(R)的每个顶点都没有自圈，

二、对称和反对称 1 定义 定义10．4．2 R为A上的关系，对任意的x，y∈A，若xRy→yRx，则称R为A上对称的关系；若(xRy∧yRx)→(x＝y)，则称R为A上反对称的关系． 这个定义也可以写成 R是A上对称的(x)(y)((x∈A^y∈A^xRy)→yRx) 只是A上反对称的(x)(y)((x∈A^y∈A^xRy^yRx)→x＝y) 反对称性还有另一种等价的定义 R是A上反对称的(x)(y)((x∈A^x∈A^xRy^x≠y)→ )，

2.对称、反对称、均满足、均不满足的例子 例4 在非空集合A上的全关系是对称的，不是反对称的， 例5 在B＝{x|x∈N^x≠0}上的整除关系、小于等于关系、小于关系都是反对称的。且不是对称的． 例6 在非空集合A上的恒等关系和空关系都是对称的，也都是反对称的， 例7 在集合A＝{1，2，3}上的关系 R={<l，2>，<2，1>，<1，3>}不是对称的，也不是反对称的． 例6和例7说明，对称性和反对称性既可以同叫满足，也可以都不满足．

3.等价描述 如果R是A上对称的，则M(R)是对称矩阵(对任意的i和j,rij＝rji)．G(R)中任意两个顶点之间或者没有有向边，或者互有有向边eij和eji(不会只有eij没有eji)，如果R是A上反对称的，则M(R)是反对称矩阵(对任意的i≠j,若rij=1则rji=0)，G(R)中任意两个顶点之间或者没有有向边，或者仅有一条有向边(不会同时有eij和eji)．

定义10．4．3 R为A上的关系，对任意的x，y，z∈A，若(xRy^yRz)→xRz，则称R为A上传递的关系． 三 传递性 定义10．4．3 R为A上的关系，对任意的x，y，z∈A，若(xRy^yRz)→xRz，则称R为A上传递的关系． 这个定义也可以写成 R是A上传递的(x)(y)(z) ((x∈A^y∈A^z∈A^xRy^yRz)→xRz)

例8 在集合A上的全关系、恒等关系、空关系都是传递的． 在B={x|x∈N^x≠0}上的整除关系、小于等于关系、小于关系都是传递的， 例9 在集合A＝{1，2，3}上的关系 R={<1，2>，<2，3>} 不是传递的关系．因为<1，2>∈R，<2，3>∈R．但是<1，3>R

10．4．2 几个结论 下列结论可以判断一些关系具有某种性质， 10．4．2 几个结论 下列结论可以判断一些关系具有某种性质， 定理10.4.1 R1,R2是A上自反的关系，则R1-1，R1∩R2，R1UR2也是且上自反的关系． 证明 对任意的x，有 x∈A=><x，x>∈Rl /\ <x，x>∈R2 <x，x>∈R1∩R2 所以，R1∩R2是A上自反的关系． 对R1-1和R1UR2的证明类似．

定理10．4．2 R1，R2是A上对称的关系,则R1-1 、R1∩R2、R1UR2也是A上对称的关系． 证明 对任意的<x，y>，有 <x，y>∈R1UR2<x，y>∈R1V<x,y>∈R2 <y,x>∈R1V<y,x>∈R2<y,x>∈R1UR2 所以，R1UR2是A上对称的关系． 对R1-1和R1∩R2的证明类似．

定理10．4，3 R1，R2是A上传递的关系，则R1-1 ，R1∩R2是A上传递的关系． 证明 对任意的<x，y>，<y，z>，有 <x，y>∈ R1-1 ^<y，z>∈ R1-1 <y，x>∈R1^<z，y>∈R1 =><z，x>∈R1<x，z>∈ R1-1 所以， R1-1是A上传递的关系． <x，y>∈R1∩R2^<y，z>∈R1∩R2 <x，y>∈Rl ^ <x，y>∈R2 ^ <y，z>∈R1^<y，z>∈R2 =><x，z>∈R1^<x，z>∈R2<x，z>∈R1∩R2 所以，R1∩R2是A上传递的关系．

注意，R1UR2不一定是传递的． 例10 在A={1，2，3}上的关系R1＝{<1，2>}，R2={<2，3>}都是A上传递的关系．但是， R1UR2＝{<1，2>，<2，3>}不是A上传递的，

定理10．4．4 R1，R2是A上反对称的关系，则R1-1及R1∩R2是A上反对称的关系， 证明 为了证明方便，把反对称性的充要条件等价改写为

注意，这时R1UR2不一定是反对称的 例11 在A＝{1，2，3}上的关系R1={<1，2>}，R2＝{<2，1>}都是A上反对称的．但是， R1UR2＝{<1，2>，<2，1>}不是A上反对称的，

定理10．4．5 对A上的关系R，则 (1)R是对称的R＝R-1，可得 (2)R是反对称的R∩R-1IA． 证明(1)先设R是对称的，对任意的<x，y>，可得 <x，y>∈R<y，x>∈R<x,y>∈R-1， 所以，R＝R-1 再设R=R-1，对任意的<x，y>，可得 <x，y>∈R<x，y>∈R-1<y，x>∈R 所以，x是对称的．

(2)先设R是反对称的，对任意的<x，y>，可得 <x，y>∈R∩R-1<x，y>∈R^<x，y>∈R-1 <x,y>∈R^<y，x>∈ R =>x＝y=><x，y>∈IA 所以，R∩R-1IA． 再设R∩R-1IA，对任意的<x,y>，可得 <x，y>∈R^<y，x>∈R <x，y>∈R^<x,y>∈R-1 <x，y>∈R∩R-1 =><x，y>IA=>x=y 所以，R是反对称的．

10．5 关系的闭包 我们经常希望关系具有自反性、对称性和传递性．对于不具有这些性质的关系，可以扩充这个关系为更大的关系(原关系的超集合)，使新关系有这些性质．这种作法就是闭包思想．闭包是数学上常用的概念，下面先介绍多个关系的合成，再介绍闭包的定义、性质和构造方法．

10．5．1 多个关系的合成 在10．3节介绍了两个关系的合成，下面推广到多个关系的合成． 10．5．1 多个关系的合成 在10．3节介绍了两个关系的合成，下面推广到多个关系的合成． 定义10．5．1 对A上的关系R，n∈N，关系R的n次幂Rn定义如下： (1)R0＝{<x，x>|x∈A}=IA， (2)Rn+1=RnR (n≥0)． 注意，n个关系R的合成简写为Rn，n个集合A的笛卡儿积经常也简写为An。二者的概念不同，却使用了相同的表示．应该注意应用的场合，以免理解错误．

例1 集合A＝{a，b，c，d}上的关系R为 R＝{<a,b>,<b,a>,<b,c>,<c,b>}． 则R0、R1、R2、R3、R4、R5的关系图如下

在例1中有一种有意义的现象，R2=R4=R6=…和R3=R5=R7=…．这种现象是否普遍存在呢?下面考虑这个问题． 定理10．5．1 设A是有限集合，|A|=n，R是A上的关系，则存在自然数s和t，s≠t，使得Rs＝Rt， 证明 对i∈N，Ri都是A上的关系，它们都是P(A×A)的元素．因|A|=n．则|A×A|=n2，|P(A×A)|＝2(n2)．列出R的各次幂，R1,R2,R3,…,R2n2,…．由鸽巢原理，至少有两个幂是相等的，即存在自然数s和t，s≠t，使Rs＝Rt，(注：鸽巢原理是组合学的基本原理．它指出：如果n+1个物体放人n个盒子里，则有一个盒子中有两个物体．)

定理10．5．2 设A是有限集合，R是A上的关系，m和n是非零自然数，则 (1)RmRn=Rm+n， (2)(Rm)n＝Rmn． 证明 (1)对任意的m，施归纳于n． 当n=1时，RmR1=Rm+1． 假设n＝k(k≥1)时结论成立，即有RmRk=Rm+k．令n＝k十1，则 RmRk+1=Rm (RkR)=(RmRk)R=Rm+kR =Rm+k+1 结论得证

(2)对任意的m，施归纳于n． 当n=1时，(Rm)1＝Rm＝Rm*1， 假设n＝k(k≥1)时有(Rm)k＝Rmk，令n＝k+1，则 (Rm)k+1＝(Rm)k(Rm) =RmkRm＝Rmk+m ＝Rm(k+1) 所以，结论得证，

定理10．5．3 设A是有限集合，R是A上的关系，若存在自然数s和t，s<t，使得Rs=Rt，则 (1)Rs+k＝Rt+k，其中k为自然数； (2)Rs+kp+i＝Rs+i，k和i为自然数，p＝t-s， (3)令B＝{R0，R1，…，Rt-1}，则R的各次幂均为B的元素，即对任意的自然数q，有RqB， 证明 (1)Rs+k=RsRk=RtRk=Rt+k，

(2)施归纳于k， 当k=0时，Rs+0+i＝Rs+i． 假设k＝n时有Rs+np+i＝Rs+i，其中p＝t-s令k＝n+1， Rs+(n+1)p+i＝Rs+np+p+i ＝Rs+np+iRp=Rs+iRp =Rs+p+i＝Rt+i=Rs+i． 所以，结论得证．

(3)若q<t，由B的定义，Rq∈B． 若q≥t，则q-s>0．一定存在自然数k和i，使得q=s+kp+i，其中0≤i≤p-1．于是， Rq=Rs+kp+i=Rs+i．此外，s+i≤s+p-1＝t-1．所以，Rq=Rs+i∈B 例2 对例1中的关系R，R2＝R4，于是对应的s＝2，t＝4．B＝{R0，R1，R2，R3}．R的幂 中不相同的只有以上4种．

10．5．2 闭包的定义 设R是A上的关系，有时希望给R增加一些有序对构成新关系R'(显然RR')，使得R'具有自反性或对称性或传递性．但不希望R'太大，希望增加的有序对尽量少．这就是建立R的闭包的基本思想．

定义10．5．2 对非空集合A上的关系R，如果有A上另一个关系R'，满足： (2)RR'， (3)对A上任何自反的(对称的，传递的)关系R”，RR”→R’R”，则称关系R’为R的自反(对称，传递)闭包，记作r(R)(s(R)，t(R))．

这一个定义中定义了三个闭包：自反闭包r(R)，对称闭包s(R)，传递闭包t(R)，直观上说，r(R)是有自反性的R的“最小”超集合，s(R)是有对称性的R的“最小”超集合，t(R)是有传递性的R的“最小”超集合．

例3 对例1中的关系R，R的r(R)，s(R)，t(R)的关系图如图10.5.2所示．

10．5．3 闭包的性质 定理10．5．4 对非空集合A上的关系R，有 (1)R是自反的r(R)＝R， (2)R是对称的s(R)＝R， 10．5．3 闭包的性质 定理10．5．4 对非空集合A上的关系R，有 (1)R是自反的r(R)＝R， (2)R是对称的s(R)＝R， (3)R是传递的t(R)＝R． 证明 (1)先设R是自反的．因为RR，且任何包含R的自反关系R”，有RR”．所以，R满足r(R)的定义，r(R)＝R． 再设r(R)＝R．由r(R)的定义，R是自反的． (2)和(3)的证明类似．

定理10．5．5 对非空集合A上的关系R1，R2，若R1R2，则 (2)s(R1) s(R2)， (3)t(R1) t(R2)． 证明留作思考题．

定理10．5．6 对非空集合A上的关系R1，R2则 (1)r(R1)Ur(R2)＝r(R1UR2)， (2)s(R1)Us(R2)＝s(R1UR2)， (3)t(R1)Ut(R2) t(R1UR2)． 证明 (1)因为r(R1)和r(R2)都是A上自反的关系，所以r(R1)Ur(R2)是A上自反的关系．由R1r(R1)和R2r(R2)，有R1UR2r(R1)Ur(R2)．所以r(R1)Ur(R2)是包含R1UR2的自反关系．

由自反闭包定义，r(R1UR2)r(R1)Ur(R2)． 因为R1R1UR2，有r(R1)r(R1UR2)．类似地r(R2)r(R1UR2)，则r(R1)Ur(R2)r(R1UR2)． (2)和(3)的证明留作思考题． 注意，定理的结论(3)是包含关系，不是相等关系，下面是真包含的例子，

例4 集合A＝{a，b，c}上的关系R1和R2为，R1={<a，b>}，R2＝{<b，c>}．于是，t(R1)=R1={<a，b>}，t(R2)=R2={<b，c>}．则有t(R1)Ut(R2)＝{<a，b>，<b，c>}．但是R1UR2＝{<a，b>，<b，c>}，t(R1UR2)＝{<a，b>，<b，c>，<a，c>}．显然t(R1)U t(R2)t(R1UR2)．

10．5．4 闭包的构造方法 一、下面介绍如何求出已知关系R的三种闭包． 定理10．5．7 对非空集合A上的关系R，有r(R)=RUR0． 10．5．4 闭包的构造方法 一、下面介绍如何求出已知关系R的三种闭包． 定理10．5．7 对非空集合A上的关系R，有r(R)=RUR0． 证明: RUR0在A上自反 最小性：若R’’在A上自反且RR’’则RUR0 R’’  由定理可知，很容易构造R的自反闭包，只要把所有的x∈A构成的<x，x>加入R中． 换句话说，非空集合A上的关系R自反当且仅当 R0 R

定理10．5．8 对非空集合A上的关系R，有 s(R)＝RUR-1， 证明 RUR-1对称 最小性：若R”在A上对称且RR”则RUR-1 R” 换句话说，非空集合A上的关系R对称当且仅当 R-1 R

定理10．5．9 对非空集合A上的关系R，有t(R)＝RUR2UR3U… 推论：非空集合A上的关系R有传递性当且仅当对任意的n≥1，n∈N ，有RnR.

通常简写为 R+=Uk=1~Rk＝RU R2UR3U…， 而且 R*＝Uk=0~Rk=R0URU R2UR3 U…， 定理10．5．3指出，在R，R2，…中只有有限个不同的合成关系．所以在计算t(R)=R+时，可以只用有限个合成关系．

定理10.5.10 A为非空有限集合,|A|＝n,R是A上的关系，则存在—个正整k≤n，使得t(R)＝R+=RUR2U…URk， 证明 P176． 推论：设非空集合A的基数为n.A上的关系R有传递性当且仅当对任意的n≥k≥1，有RkR. 由此定理可知，这时的R+不妨写成R+＝t(R)=RUR2UR3U…URn．其中|A|＝n.

例5 集合A＝{a，b，c}上的关系R为 R＝{<a，b>，<b，c>，<c，a>}． 则 r(R)=RUR0 ＝{<a，b>，<b，c>，<c，a>，<a，a>，<b，b>，<c，c>}． 而 s(R)＝RUR-1 ＝{<a，b>，<b，a>，<b，c>，<c，b>，<c，a>，<a，c>}．

由 则 t(R)＝RUR2UR3 ＝{<a，b>，<a，c>，<b，c>，<b，a>， <c，a>，<c,b>，<a，a>，<b，b>，<c，c>}．

当有限集合A的元素较多时，用矩阵运算求A上的关系R的传递闭包仍很复杂．1962年Warshall提出了一种有效的算法， Warshall算法：(令B[j，i]表示矩阵B第j行第i列的元素) (1)令矩阵B＝M(R)， (2)令i＝1，n＝|A|， (3)对1≤j≤n，如果B[j，i]=1，则对1≤k≤n，令 B[j，k]＝B[j，k]VB[i，k]， (4)i加1， (5)若i≤n，则转到(3)，否则停止，且 M(R+)=B．

例6 A上的关系R的关系矩阵为

有时希望所求的闭包具有两种或三种性质．应该先作哪种闭包运算呢?下面分析这个问题． 定理10．5．11 对非空集合A上的关系R，有 (1)若R是自反的，则s(R)和t(R)是自反的， (2)若R是对称的，则r(R)和t(R)是对称的， (3)若R是传递的，则r(R)是传递的． 记忆要点：S对于传递性不能保持。

定理10．5．12 对非空集合A上的关系R，有 (1) rs(R)=sr(R)， (2) rt(R)=tr(R)， (3) st(R)ts(R)， 其中rs(R)＝r(s(R))，其他类似．此时st不能交换。 由定理可知，若要求出R的自反、对称且传递的闭包，则应求tsr(R)= trs (R)=rts(R)三者中任一个． 因为由定理10. 5. 11：st的作法是行不通的．故不应求str(R)=srt(R)=rst(R)三者中任一个 R的对称且传递的闭包ts(R) R的对称且自反的闭包? R的传递且自反的闭包?

10．6 等价关系和划分 在实数之间的相等关系、在集合之间的相等关系、在谓词公式之间的等值关系具有类似的性质．它们都具有自反性、对称性和传递性．下面把具有这三种性质的关系称为等价关系． 这是一类很重要的关系，可以用集合上的等价关系把该集合划分成等价类，

10．6．1 等价关系 定义10．6，1 对非空集合A上的关系R，如果R是自反的、对称的和传递的，则称R为A上的等价关系． 10．6．1 等价关系 定义10．6，1 对非空集合A上的关系R，如果R是自反的、对称的和传递的，则称R为A上的等价关系． 例1 在非空集合A上的恒等关系IA和全关系EA都是等价关系，在所有谓词公式的集合上的等值关系也是等价关系．

例2 集合A＝{1，2，…，8}上的关系R＝{<x，y>|x≡y(mod3)}．其中x≡y(mod3)表示x-y可被3整除， 对任意的x，y，z∈A，x-x可被3整除．若x-y可被3整除，则y-x也可被3整除．若x-y和y-z可被3整除，则x-z=(x-y)+(y-z)可被3整除．所以，R具有自反性、对称性和传递性，R是A上的等价关系．

R的关系图如图所示．在图中，A的元素被分成三组，每组中任两个元素之间都有关系，而不同组的元素之间都没有关系．这样的组称为等价类．

第9章给出了用平面坐标系中的矩形表示笛卡儿积A×B的图形表示法，显然可以用正方形表示A×A，如图(a)所示．A上的关系是A×A的子集，因此可以用正方形的子集表示．A上的等价关系可以用正方形的一条对角线和线上的若干正方形表示．如图(b)所示．但是图(c)所表示的关系不是等价关系．它包括了对角线，所以有自反性．它以对角线为对称轴，所以有对称性．但它没有传递性．因为R中的a和b点对应的有序对，经传递得到c点对应的有序对应在R中，但c点不在R中，

定义10．6．2 只是非空集合A上的等价关系，对任意的x∈A，令[x]R＝{y|y∈A^xRy}，则称集合[x]R为x关于R的等价类，简称x的等价类，也可记作[x] [1]R={1，4，7}＝[4]R＝[7]R， [2]R={2，5，8}＝[5]R＝[8]R， [3]R={3，6}＝[6]R． A的8个元素各有一个等价类．各等价类之间，或者相等，或者不相交，而且所有等价类的并集就是A．

定理10．6．1 R是非空集合A上的等价关系，对任意的x，y∈A，成立 (1)[x]R≠ 且[x]RA， (2)若xRy， 则[x]R=[y]R， (3)若x y，则[x]R∩[y]R＝， (4)U{[x]R|x∈A}=A． 证明 (1)对任意的x∈A，xRx，则x∈[x]R，因此[x]R≠．由等价类定义，显然[x]RA． (2)对任意的x0∈[x]R，有xRx0，由对称性，有x0Rx.由xRy和传递性，有x0Ry,yRx0, 所以x0∈[y]R.类似可证x0∈[y]R→x0∈[x]R．因此，[x]R＝[y]R．

(3)假设[x]R∩[y]R≠．则存在x0，使得x0∈[x]R且x0∈[y]R，即xRx0且yRx0，由对称性x0Ry，由传递性xRy．与已知矛盾． (4)对任意的x∈A，[x]RA．则有U{[x]R|x∈A} A．反之，对任意的x∈A，x∈[x]R，则有x∈U{[x]R|x∈A}．所以，AU{[x]R|x∈A}．因此U{[x]R|x∈A}＝A． 由定理可知，对A上的等价关系R，所有等价类的集合具有很好的性质，

定义10．6．3 对非空集合A上的关系R，以R的不相交的等价类为元素的集合称为A的商集，记作A／R， 这个定义也可以写成 A／R={y|(x)(x∈A^y=[x]R)}． 例4 对例2中的A和R，商集是 A／R＝{[1]R，[2]R，[3]R} ＝{{1，4，7}，{2，5，8)，{3，6}}．

10．6．2 划分 定义10．6．4 对非空集合A，若存在集合，满足下列条件： (1)(x)(x∈→xA)， (2)  10．6．2 划分 定义10．6．4 对非空集合A，若存在集合，满足下列条件： (1)(x)(x∈→xA)， (2)  (3)U＝A， (4)(x)(y)((x∈^y∈^x≠y)→x∩y=)，则称为A的—个划分，称中的元素为A的划分块． A的一个划分，是A的非空子集的集合(即P(A)且)，A的这些子集互不相交，且它们的并集为A．

例5 对集合A＝{a，b，c，d}．则 1＝{{a}，{b，c}，{d}}和 2＝{{a，b，c，d}}都是A的划分．{a}，{b，c}，{d}为1的划分块． 但是3={{a，b}，{c}，{a，d}} 和 4＝{{a，b，d}} 都不是A的划分．

定理10．6．2 对非空集合A上的等价关系R，A的商集A／R就是A的划分，它称为由等价关系R诱导出来的A的划分，记作R． 证明可以由定义10．6．3、定义10．6．4和定理10．6．1直接得到． 上面说明，由A上的等价关系R可以诱导出A的一个划分．下面考虑，由A的一个划分如何诱导出A上的一个等价关系．

定理10．6．3 对非空集合A的一个划分，，令A上的关系R为 R＝{<x，y>|(z)(z∈^x∈z^y∈z)} 则置R为A上的等价关系，它称为划分诱导出的A上的等价关系． 证明留作思考题．

定理10.6.4 对非空集合A的一个划分和A上的等价关系R，诱导R当且仅当R诱导， 证明 先证必要性．若诱导R，且R诱导’．对任意的x∈A，设x在的划分块B中，也在’的划分块B‘中．对任意的y∈A，有y∈BxRy(x∈B且诱导R) [x]R=[y]R(R为等价关系)y∈B'(x∈B'且R诱导') 所以，B=B'．由x的任意性，＝'． 再证充分性．若R诱导，且诱导R'．对任意的x，y∈A，可得xRy[x]R＝[y]Rx∈[x]R^y∈[x]R x和y在x的同一划分块中xR'y 所以，R＝R'． 由定理可知，集合A的划分和A上的等价关系可以建立一一对应．

例6 在集合A＝{1，2，3}上求出尽可能多的等价关系．先求A的所有划分，如图所示，

于是可得到5个等价关系． R1={<1，2>，<2，1>，<1，3>，<3，1>，<2，3>，<3，2>，<1，1>，<2，2>，<3，3>}， R2={<2，3>，<3，2>，<1，1>，<2，2>，<3，3>}， R3={<1，3>，<3，1>，<1，1>，<2，2>，<3，3>}， R4={<1，2>，<2，1>，<1，1>，<2，2>，<3，3>}， R5={<1，1>，<2，2>，<3，3>}．

10．7 相容关系和覆盖 10．7．1 相容关系 定义10．7．1 对非空集合A上的关系R，如果R是自反的，对称的，则称R为A上的相容关系． 10．7 相容关系和覆盖 10．7．1 相容关系 定义10．7．1 对非空集合A上的关系R，如果R是自反的，对称的，则称R为A上的相容关系． 例1 且是英文单词的集合 A={cat，teacher，cold，desk，knife，by}， A上的关系R为R={<x，y>|x和y至少有一相同字母}，显然，R是自反的、对称的，但不是传递的．因此，R是相容关系．

相容关系的关系图中,每个顶点都有自圈,而且若一对顶点间有边则有向边成对出现．因此可以简化关系图,可以不画自圈,并用无向边代替一对来回的有向边．对例1的R,设x1=cat,x2＝teacher,x3＝cold,x4=desk,x5=knife,x6＝by,则关系图可以简化如图

定义10．7．2 对非空集合A上的相容关系R，若CA，且C中任意两个元素x和y有xRy，则称C是由相容关系R产生的相容类，简称相容类． 这个定义也可以写成C={x|x∈A^(y)(y∈C→xRy))． 例2 对例1中的相容关系R，相容类有{x1，x2}，{x3，x4}，{x6}，{x2，x4，x5}等，前两个相容类都可以加入其他元素，构成更大的相容类．如{x1，x2}加入x3得到另一相容类{x1，x2，x3}．后两个相容类再加入任何新元素都不是相容类了，这两个相容类称为最大相容类，

定义10．7．3 对非空集合A上的相容关系R，一个相容类若不是任何相容类的真子集，就称为最大相容类，记作CR． 对最大相容类CR有下列性质：(x)(y)((x∈CR^y∈CR)→xRy) 和 (x)(x∈A-CR→(y)(y∈CR^x y))． 在相容关系的简化图中，最大完全多边形是每个顶点与其他所有顶点相连的多边形，这种最大完全多边形的顶点集合，才是最大相容类，此外，一个孤立点的集合也是最大相容类；如果两点连线不是最大完全多边形的边，这两个顶点的集合也是最大相容类，

例3 对例1中的相容关系R，最大相容类有 {x1，x2，x3}，{x2，x3,x4}，{x2，x4，x5}和{x6}； 定理10．7．1 对非空有限集合A上的相容关系R，若C是一个相容类，则存在一个最大相容类CR，使CCR． 证明 设A＝{a1，a2，...,an}．构造相容类的序列C0C1C2…

使C0＝C，Ci+1＝Ci∪{aj}，而j是满足ajCi且aj与Cj中各元素有关系R的最小下标， 因为|A|＝n，所以至多经过n-|C|步，过程就结束，而且序列中最后一个相容类是CR.结论得证． 对任意的a∈A，有相容类{a}．它必定包含在某个CR中．所以，CR的集合覆盖住A．

10．7．2 覆盖 定义10．7．4 对非空集合A，若存在集合满足下列条件： (1)(x)(x∈→xA)， (2)， 10．7．2 覆盖 定义10．7．4 对非空集合A，若存在集合满足下列条件： (1)(x)(x∈→xA)， (2)， (3)U＝A， 则称为A的一个覆盖，称中的元素为的覆盖块， 一个划分是一个覆盖，但一个覆盖不一定是一个划分．因为划分中各元素不相交，覆盖中各元素可能相交． 定理10．7．2 对非空集合A上的相容关系R，最大相容类的集合是A的一个覆盖，称为A的完全覆盖，记作CR(A)．而且CR(A)是唯一的． 证明从略．

定理10．7．3 对非空集合A的一个覆盖={A1，A2，…，An}，由确定的关系R＝A1XA1 U A2 XA2 U…U AnXAn 是A上的相容关系． 证明从略． 由A上的一个相容关系R，可以确定一个A的完全覆盖CR(A)．由A的一个覆盖，也可确定一个A上的相容关系．但是不同的覆盖，可能确定同一个相容关系．

例4 集合A={1，2，3，4}的两个覆盖 1={{1，2，3}，{3，4}}和2＝{{1，2}，{2，3}，{3，1}，{3，4}} 可以确定相同的相容关系 R＝{<1，2>，<2，1>，<1，3>，<3，1>，<2，3>，<3，2>，<3，4>， <4，3>，<1，1)，<2，2>，<3，3>，<4，4>}，

10．8 偏序关系 在实数之间的小于等于关系，在集合之间的包含关系具有类似的性质．它们都具有自反性、反对称性和传递性．下面把具有这三种性质的关系称为偏序关系．它和等价关系同为很重要的关系．

10．8．1 偏序关系和拟序关系 定义10.8．1 对非空集合A上的关系R，如果R是自反的、反对称的和传递的，则称R为A上的偏序关系． 10．8．1 偏序关系和拟序关系 定义10.8．1 对非空集合A上的关系R，如果R是自反的、反对称的和传递的，则称R为A上的偏序关系． 在不会产生误解时，偏序关系R通常记作≤．当xRy时，可记作x≤y，读作x“小于等于”y． 例1 在集合N-{0}上的小于等于关系和整除关系，都是偏序关系．对集合A，在P(A)上的包含关系也是偏序关系，

定义10．8．2 对非空集合A上的关系R，如果R是非自反的和传递的，则称R为A上的拟序关系， 在不会产生误解时，拟序关系R通常记作<，当xRy时，可记作x<y，读作x“小于”y． 例2 在集合N上的小于关系是拟序关系．对集合A，在P(A)上的真包含关系也是拟序关系． 偏序关系又称弱偏序关系，或半序关系，拟序关系又称强偏序关系．

定理10．8．1 R为A上的拟序关系，则R是反对称的． 证明 假设R不是反对称的．则存在x∈A，y∈A，x≠y，使<x，y>∈R且<y，x>∈R．由传递性，<x，x>∈R．与非自反性矛盾． 有的书上把反对称性也作为拟序关系定义的—个条件．定理表明，这是不必要的． 定理10．8．2 对A上的拟序关系R，RUR0是A上的偏序关系． 证明从略． 定理10．8．3 对A上的偏序关系R，R-R0是A上的拟序关系， 拟序关系和偏序关系的区别只是自反性．由于它们类似，只要把偏序关系搞清，拟序关系也容易搞清．以下只讨论偏序关系．

定义10．8．3 集合A与A上的关系R一起称为一个结构．集合A与A上的偏序关系R一起称为一个偏序结构，或称偏序集，并记作<A，R>． 例3 (N，≤)和<P(A)，>都是偏序集．

10.8.2 哈斯图 利用偏序关系的良好性质，可以把它的关系图简化为较简单的哈斯图，首先，由于自反性，每个顶点都有自圈，则可不画自圈．其次，由于反对称性，两个顶点之间至多一条有向边，则可约定箭头指向上方或斜上方并适当安排顶点位置，以便用无向边代替有向边．最后，由于传递性，依传递可得到的有向边可以不画．下面定义盖住关系，并给出作图规则，

定义10．8．4 对偏序集<A，≤>，如果x，y∈A，x≤y，x≠y，且不存在元素z∈A使得x≤z且z≤y，则称y盖住x．A上的盖住关系covA定义为 covA＝{<x，y>|x∈A^y∈A^y盖住x}． 例4 集合A＝{1，2，3，4，6，12}上的整除关系DA是A上的偏序关系．则A上的盖住关系covA为 covA={<l，2>，<1，3>，<2，4>，<2，6>，<3，6>，<4，12>，<6，12>}．

对偏序集<A，≤>，A上的盖住关系covA是唯一的．可以用盖住关系画偏序集的哈斯图．作图规则为： (2)若x≤y且x≠y，则顶点y在顶点x上方， (3)若<x，y>∈covA，则x，y间连无向边，

例5 例4中偏序集的哈斯图如图10.8.1． 例6 对A＝{a，b，c}，<P(A)，>是偏序集，它的哈斯图如图10．8．2．

10．8．3 上确界和下确界 定义10．8．5 对偏序集<A，≤>，且B  A，进一步 10．8．3 上确界和下确界 定义10．8．5 对偏序集<A，≤>，且B  A，进一步 (1)若(y)(y∈B^(x)(x∈B→y≤x))，则称y为B的最小元， (2)若(y)(y∈B^(x)(x∈B→x≤y))，则称y为B的最大元， (3)若(y)(y∈B^(x)((x∈B^x≤y)→x＝y))，则称y为B的极小元， (4)若(y)(y∈B^(x)((x∈B^y≤x)→x＝y))，则称y为B的极大元，

例7 在例4的偏序集<A，DA)的哈斯图中．令B1＝{2，4，6，12}，则B1的最大元和极大元是12，最小元和极小元是2，令B2＝{2，3，4，6}，则B2的极大元是4和6，极小元是2和3，没有最大元和最小元． 注意区别最小元与极小元．B的最小元应小于等于B中其他各元．B的极小元应不大于B中其他各元(它小于等于B中一些元，并与B中另一些元无关系)，最小元(最大元)不一定存在，若存在必唯一．在非空有限集合B中，极小元(极大元)必存在，不一定唯一．

定义10．8．6 对偏序集<A，≤>，且B  A，进一步 (1)若(y)(y∈A^(x)(x∈B→x≤y))，则称y为B的上界， (2)若(y)(y∈A^(x)(x∈B→y≤x))，则称y为B的下界， (3)若集合C＝{y|y是B的上界}，则C的最小元称为B的上确界或最小上界， (4)若集合C＝{y|y是B的下界}，则C的最大元称为B的下确界或最大下界，

例8 集合A={2，3，4，6，9，12，18}，A上的整除关系DA是偏序关系．偏序集<A，DA>的哈斯图如图所示．

B1＝{2，4}的上界是4和12，上确界是4，下界和下确界是2．B2={4，6，9}没有上下界，没有上下确界．B3={2，3}的上界是6，12，18，上确界是6，没有下界和下确界． B的上下界和上下确界可能在B中，可能不在B中，但一定在A中．上界(下界)不一定存在，不一定唯一．上确界(下确界)不一定存在，若存在必唯一．

10．8．4 全序关系和链 定义10．8．7 对偏序集<A，≤>，对任意的x，y∈A，若有x≤y或y≤x，则称x和y是可比的． 10．8．4 全序关系和链 定义10．8．7 对偏序集<A，≤>，对任意的x，y∈A，若有x≤y或y≤x，则称x和y是可比的． 定义10．8．8 对偏序集<A，≤>，如果对任意的x，y∈A，x和y都可比，则称≤为A上的全序关系，或称线序关系，并称<A，≤>为全序集． 例9 N上的小于等于关系是全序关系，所以<N，≤>是全序集．N-{0}上的整除关系不是全序关系，对非空集合A，P(A)上的包含关系不是全序关系．

定义10．8．9 对偏序集<A，≤>，且BA，进一步 (1)如果对任意的x，y∈B，x和y都是可比的，则称B为A上的链，B中元素个数称为链的长度． (2)如果对任意的x，y∈B，x和y都不是可比的，则称B为A上的反链，B中元素个数称为反链的长度． 例10 对例8中的偏序集．{2，4，12}，{3，6，18}，{3，9}，{18}都是链．{4，6，9}，{12，18}，{4，9}都是反链． 对全序集<A，≤>，显然A是链．A的任何子集都是链．

定理10．8．4 对偏序集<A，≤>，设A中最长链的长度是n，则将A中元素分成不相交的反链，反链个数至少是n． 当n=1时，A本身就是一条反链，定理结论成立，(这时≤是恒等关系)假设对于n=k，结论成立．考虑n＝k+1的情况．当A中最长链的长度为k+1时，令M为A中极大元的集合，显然M是一条反链．而且A-M中最长链的长度为k，由归纳假设，可以把A-M分成至少A个不相交的反链，加上反链M，则A可分成至少k十1条反链．

这个定理称为偏序集的分解定理，这是组合学三大存在性定理之—，有广泛的应用． 定理10．8．5 对偏序集<A，≤>，若A中元素为mn+1个，则A中或者存在一条长度为m+1的反链，或者存在一条长度为n+1的链． 证明：反证，若反链最长m,链最长n,则元素最多只有mn个。

10．8．5 良序关系 定义10．8．10 对偏序集<A，≤>，如果A的任何非空子集都有最小元，则称≤为良序关系，称<A，≤>为良序集． 例11 <N，≤>是全序集，也是良序集．<Z，≤>是全序集，不是良序集．其中Z是整数集．因为ZZ，但是Z没有最小元．

定理10．8．6 一个良序集一定是全序集． 证明 设<A，≤>是良序集．对任意的x，y∈A，可构成{x，y}A，它有最小元.该最小元或为x或为y，则x≤y或y≤x.所以，<A，≤>是全序集．

定理10．8．7 一个有限的全序集一定是良序集． 证明 设A={a1，a2，…，an}，且<A，≤>是全序集．假设<A，≤>不是良序集，则存在非空子集BA，B中没有最小元．因为B是有限集合，所以存在x，y∈B，使x和y无关系．与全序集矛盾．

对一个非良序的集合，可以定义集合上的一个全序关系，使该集合成为良序集．例如，<Z，≤>不是良序集．在Z上定义全序关系R为：对a，b∈Z，若|a|≤|b|，则aRb;若a>0，则-aRa，于是 0R-1，-1R1，1R-2，-2R2，…这样，Z的最小元是0，Z的子集都有最小元，<Z，R>是良序集．这个定义R的过程称为良序化．

定理10．8．8(良序定理) 任意的集合都是可以良序化的． 良序定理可以由Zorn引理证明，它们都是选择公理的等价形式．这里不给出证明， 设R是实数集合，≤是R上的小于等于关系．显然，<R，≤>是全序集，不是良序集．可以在<R，≤>上定义常用的区间．

定义10．8．11 在全序集<R，≤>上，对于a，b∈R，a≠b，a≤b，则 (1)[a，b]＝{x|x∈R^a≤x≤b)，称为从a到b的闭区间， (2)(a，b)＝{x|x∈R^a≤x≤b^x≠a^x≠b)，称为从a到b的开区间 (3)[a，b)＝{x|x∈R^a≤x≤b^x≠b}，(a，b]={x|x∈R^a≤x≤b^x≠a}都称为从a到b的半开区间， (4)还可以定义下列区间 (-，a]={x|x∈R^x≤a}， (-，a)={x|x∈R^x≤a^x≠a}， [a，)＝{x|x∈R^a≤x}， (a，)＝{x|x∈R^a≤x^x≠a}， (-，)=R．