链接版第二章集合论

CHAPTER2SETTHEORYGlossaryset:集合subset:子集object,element,member：成员，元素paradox:悖论well-defined:良定，完全确定brace：花括号representation：表示sensible:有意义的rationalnumber：有理数emptyset:空集orderedpair：有序对，序偶Cartesianproduct:叉积，笛卡尔积Venndiagram:文氏图contain(in):包含(于)universalset:全集finite(infinite)set:有限(无限)集cardinality:基数，势powerset:幂集setoperation：集合运算disjointsets：不相交集intersection：交union：并complement:补集，补元symmetricdifferenee:对称差Booleanalgebra:布尔代数binaryoperation：二元运算unaryoperation：一元运算identity:么元，单位元inverse:逆元commutative:可交换的associative:可结合的distributive:可分配的idempotent:等幂的absorption:吸收DeMorgan'slaws:德摩根律binaryoperation：二元运算unaryoperation：—元运算unity：么(单位)元zero:零元dual:对偶relation：关系domain:定义域range：值域inverserelation:逆关系composition：复合reflexive:自反的antireflexive:反自反的symmetric:对称的antisymmetric:反对称的transitive:传递的reflexiveclosure:自反闭包symmetricclosure:对称闭包transitiveclosure:传递闭包graph：无向图vertex(vertices):顶点edge:边directedgraph(digraph):有向图initialvertex:起点terminalvertex:终点partialordering：偏序partiallyorderedset(poset):偏序集comparable:可比的totalordering,chain,linearordering：全序，链，线序Hassediagram:哈斯图equivaleneerelation：等价关系equivaleneeclass:等价类mutuallyexclusive：互斥disjoint:不相交partition:划分，分割function:函数，映射codomain：陪域preimage:原像image:像mapping：映射compositefunction：复合函数onto,surjective:到上函数，满射onetoone,injective:单射，一对一函数bijection,one-to-onecorrespondence：双射， 对应permutation：置换，排列identityfunction：单位函数invertiblefunction：可逆函数本章内容及教学要点：2・1IntroductiontoSets教学内容：elements，sets，representationsofsets，subsets，propersubset，emptyset，universalset，finitesets，infinitesets，cardinality2・2OperationsonSets教学内容：operationsonsets:intersection、union、setdifference、symmetricdifference、complement，powerset，orderedpair，Cartesianproduct，algebraicpropertiesofsetoperations2・3VennDiagrams教学内容：Venndiagrams2・4BooleanAlegebras教学内容：Booleanalgebras，binaryoperations，unaryoperations，unity，zero，complement2・5Relations教学内容：relation，inverserelation，composition，propertiesofrelation，closure，graph，directedgraph(digraph)2・6PartiallyOrderedSets教学内容：partialordering，poset，totalordering，Hassediagram2・7EquivalenceRelations教学内容：equivalencerelation，equivalenceclass，partition2・8Functions教学内容：function，domain，range，onto，one-to-one，bijection，inverse，identityfunction定理证明及例题解答IntroductiontoSets20世纪数学中最为深刻的活动就是关于数学基础的探讨，集合论因是为了研究数学基础而发展起来的.集合论是现代数学的基础，是数学中不可或缺的基本描述工具.可以这样讲，现代数学与离散数学的“大厦”建立在集合论的基础之上.集合论的研究起源于对数学的基础研究：对数学的对象、性质及其发生、发展的一般规律进行的科学研究.德国数学家康托尔从1874年始，发表了一系列集合论方面的著作，从而创立了集合论.在自然科学中，除了研究处于孤立的个体之外，更重要的是将一些相关的个体放在一起进行研究，这就直观地产生了引入集合这一概念的要求.集合是最简单的数学对象.随着计算机时代的到来，集合的元素已由传统的“数集”和“点集”拓展成包含文字、符号、图形、图表和声音等多媒体信息，构成了各种数据类型的集合.从而集合论在编译原理、开关理论、信息检索、形式语言、数据库和知识库、CAD、CAM、CAI及AI等各个领域得到了广泛的应用.但数学家们不久就在康托尔的理论（我们称之为朴素（古典）集合论）中发现了逻辑矛盾，即所谓的“悖论"（paradox，导致了数学发展史上的第三次危机.其中最为著名的就是1901年罗素发现的''罗素悖论〃S={x|xS}.“罗素悖论〃的通俗表示是所谓的“理发师悖论”：一个村庄的理发师，自夸本村无人可比，宣称他当然不给自己刮胡子的人刮胡子，但却给本村所有自己刮胡子的人刮胡子.哪么他是否应当给自己刮胡子？正是寻求解决第三次数学危机的各种努力，给数学基础问题的研究带来了全新的转机.一部分数学家开始把精力集中于解决具有“能行性”的问题上.20世纪30年代中后期，图灵对计算的本质进行了研究，从而实现了对计算本质的真正认识.图灵提出了'图灵机”这一计算模型用来解决“能行计算”问题，而电子计算机正是这种模型的具体实现.Asetisanywell-definedcollectionofobjectsorelements.Wedon'tspecifywhatanobjectisandthedescriptionofasetasacollectionofobjectsisbasedontheintuitivenotionofanobject.Well-definedjustmeansthatitispossibletodecideifagivenobjectbelongstothecollectionornot.Almostallmathematicalobjectsarefirstofallsets.Thussettheoryis,inasense,thefoundationonwhichvirtuallyallofmathematicsisconstructed.一个集合是作为整体识别的、确定的、互相区别的一些事物的全体.严格地讲，这只是一种描述，不能算是集合的定义.类似于几何中的点、线、面等概念，在朴素集合论中，集合也是一种不加定义而直接引入的最基本的原始概念(一给出定义就要引入悖论(paradoxes)).而集合论中的其他概念，则都是从它出发给予了严格的定义.构成集合的每个事物称为这个集合的元素或成员(member,element).集合一般用大写字母表示，元素用小写字母表示.但这也不是绝对的，因为一个集合可以是另外一个集合的元素.例2・1・1英文字母的集合，C语言的基本字符集，全体实数，计算机内存单元集合.例2・1・2 {1,2,3}={2,1,3}={3,1,2}.例2・1・3常用集合：N,Z(Z+,Z-),P,Q,R,C,①(emptyset,空集).集合的表示：枚举法(listingtheelementsofthesetbetweenbraces):Theorderoftheelementsofasetisnotimportant.Repeatedelementsinthelistingoftheelementsofasetcanbeignored；性质描述法(specifyingapropertythattheelementsofthesethaveincommon)：S={x:P(x)}；定义2.1.1IfaisoneoftheobjectsofthesetA,wesaythataisanelementofAorabelongstoA.WeindicatethefactthatxisanelementofthesetAbywritingxeA,andweindicatethefactthatxisnotanelementofthesetAbywriting A.(如果x是集合A的一个元素，则称x属于A,记作xeA;否则称x不属于A,记作x电A)例2・1・41eN,0.5eQ,3.0eR,—1纟N,、2电Q.集合有三个重要的特性：互异性、无序性和确定性.定义2・1・2(Inclusionrelation，包含关系)IfeveryelementofAisalsoanelementofB,wesaythatAisasubsetofBorthatAiscontainedinBandwewriteA匸B.(设A和B是两个集合.若A中的每个元素都是B的元素，则称A是B的子集或称B包含A、A包含于B,记作AB.)定义2.1.3(外延性原理)WesaythatA=BifthesetsAandBhavethesameelements.若A匸B但A工B,则称A为B的真子集(propersubset)记作AuB，B称为A的扩集或超集(superset).例2.1.5下列各集合中，哪几个分别相等?A1={a,b}(2)A2={b,a}A3={a,b,a}(4)A4={a,b,c}A5={x|(x-a)(x-b)(x-c)=0}A6={x|x2-(a+b)x+ab=0}例2.1.6NuQuRuC.定义2.1.4Theemptyset,denotedby①orby{},isthesetthatcontainsnoelements.TheuniversalsetUisaspecialandvolatilesetwhichcontainsalltheobjectsunderconsideration(在一定讨论范围内，若所有集合均为某一集合的子集，则称该集合为全集(universalset)，记为U)全集有多种选择.通常全集不需要具体指明，但是有些时候则需要明确指明全集.空集是任何集合的子集(对任一集合A，有①匸A).对任一非空集合A，它至少有两个不同的子集①和A，称它们为A的平凡子集(①匸A，A匸A).集合的包含关系(inclusionrelation)有如下性质：(1)自反性：AA；反对称性：AoB,B匸A二A=B;(3)传递性：AB,B匸C二A匸C.而集合的真包含关系(properinclusionrelation)贝9只有传递性AuB，BuCnAuC.显然A匸B且B匸A。A=B.例2・1・7A=｛x|x2-x=0且xGR｝,B=｛0,1｝,则A=B.例2.1.8判断下列命题的真假：①匸①，①w①，①匸｛①｝， ①w｛①｝，｛①｝w｛｛①｝｝，｛①｝w｛①，｛①｝｝，①匸｛｛①｝｝，｛①｝匸｛｛①｝｝定义2.1.5AsetAiscalledfiniteifithasndistinctelements,wherenwN.niscalledthecardinalityofAandisdenotedby|A|(基数或势).基数为有限的集合称为有限集(finiteset),否则称为无限集(infiniteset)；I①1=0.例2・1・9N,I,Q+，R,C都是无限集；大于3且小于1的整数集是空集，H=｛x|xwR且X2+x+1=0｝是空集；偶素数集是有限非空集.丨①1=0，|｛0,1｝1=2，|｛①｝|=1，|N|=n0，|R|=ni-ASSIGNMENTS：PP38：2，4，6，8，10，16，20，26SetOperations定义2.2.1IfAandBaresets,wedefinetheirunion(intersection)asthesetconsistingofallelementsthatbelongtoAorB(bothAandB)anddenoteitbyAuB(AnB).WedefinethesetdifferenceA-BasthesetofallelementsthatareinAbutarenotinBanddenoteitbyA-B.ThecomplementofasetA,denotedbyA，,isthesetU-A.WedefinethesymmetricdifferenceofAandBasthesetofallelementsthatbelongtoAorB,butnottobothAandB,anddenoteitbyA人B(A㊉B).设有集合A与B,则称由A与B的公共元素组成的集合为A与B的交集，记作AcB,即AnB={x:xGA且xGB};Twosetsthathavenocommonelementsarecalleddisjointsets(若AcB=①(即A与B无公共元素)，则称A与B不相交);称由A与B的所有元素组成的集合为A与B的并集，记作AuB,即AuB={x:xGA或xeB}；类似地，我们可以定义AuBuC, A2u…uAn,AcBnC,(3)称由属于A但不属于B的元素组成的集合为A与B的差，记作A-B,即A-B={x:xeA且XgB}.特别地，称U-B为B的补集，记作B'(或B、〜B).称由属于A但不属于B的元素或属于B但不属于A的元素组成的集合为A与B的环和或对称差，记为AAB,即AAB={x:(xeA且x电B)或(xeB且x电A)}=(A-B)u(B-A).例2.2.1设A={2，3}，B={1，5，8}，C={3，6}，U={1，…，10}，求AuB,CcB,A-B,B-A,B'.例2・2・2设A={2,3},B={1,5,8},U={1,・・・,10},求AAB,BAA,AaA,Aa①,UaA.集合运算的性质(Algebraicpropertiesofsetoperations)定理2・2・1ForarbitrarysetsAandB,A-B=AnB，.证明定理2・2・1定理2.2.2(DeMorgan'slaw)ForarbitrarysetsAandB,(а) (AcB)'=AruB'.(b)(AuB))=A，cB'-证明定理2・2・2定义2.2.2IfAisaset,thenthesetofallsubsetsofAiscalledthepowersetofAandisdenotedbyP(A).(设A为一个集合，称由A的所有子集作为元素构成的集合为A的幂集，记为P(A)(2A)，即P(A)={S: A})例2・2・3P(①)={①},P({①})={o,{o}},P({a})={o,{a}};设A={0,1},则P(A)={o,{0},{1},{0,1}}；设B={0,1,2},则P(B)={o,{0},{1},{2},{0,1},{0,2},{1,2},B}.定理2.2.3ForarbitrarysetsA,BandC,A匸AuB,B匸AuB；AcB匸A,AcB匸B;A-B匸A;A-B=AcB'；AaB=(A-B)u(B-A)A匸C,B匸C—AuB匸C;A匸B,A匸C—A匸BcC;A匸B—B'匸a，；oeP(A),AGP(A);A匸B—P(A)匸P(B);(б) P(A)uP(B)匸P(AuB);P(AcB)=P(A)cP(B);(8)若A是有限集，贝则|P(A)|=2|A|.例2.2.4设A，B是任意集合，证明下列条件相互等价：A匸B; (2)AuB=B; (3)A=AnB.证明例2・2・4基本集合恒等式关于集合的运算，有下列基本规律：交换律(Commutativelaws)：AuB=BuA,AnB=BnA；结合律(Associativelaws):(AuB)uC=Au(BuC),(AnB)nC=Ac(BcC);分配律(Distributivelaws):(AuB)nC=(AnC)u(BnC),(AnB)uC=(AuC)c(BuC);同一律(Identitylaws)：A①=A-①=AcU=A;零一律(Dominationlaws)Ac①=①,AU=U;有补律(Complementlaws)：排中律Aua，=U；矛盾律：Aca，=①；等幂律(Idempotentlaws)：AuA=AcA=A；双否律(Complementationlaw)：(A，)，=A；吸收律(Absorptionlaws)：A屮acb)=ac(aub)=A；德摩根律(DeMorgan'slaws):(AcB):=a、b'/(AuB):=a，cb'例2.2.5(1)设A,B,C都是集合，且AcB=AcC,AuB=AuC,则B=C；对任意集合A,B,证明：A-B=①。A匸B.证明例2・2・5定义2・2・3TheCartesianproduct(叉积，笛卡尔积)ofthesetsAandB,denotedbyAxB,istheset{(a,b):aGAandbGB}.Theobject(a,b)iscalledanorderedpair(有序对)withfirstcomponent(第一成员)aandsecondcomponent(第二成员)b.例2.2.6LetA={1,2,3}andB={r,s}.ThenAxB={(1,r),(1,s),(2,r),(2,s),(3,r),(3,s)}.BxA={(r；1),(r,2),(r,3),(s,1),(s,2),(s,3)}.Foranytwofinite,nonemptysetsAandB,|AxB|=|A||B|.ASSIGNMENTS：PP44-45：12，14，16，18，26，28，34，50，52，54VennDiagramsAusefultoolforrepresentingandobservinghowtheoperationsworkistheVenndiagrams.InaVenndiagram,setsarerepresentedasinteriorsofcircles,andtheuniversalsetisrepresentedasarectangular.文氏图法(Venndiagrams)：用于描述集合间的关系及其运算，其特点是直观、形象、信息量大且富有启发性■一般用矩形表示全集U,用圆表示U的子集A，B，C等等.ASSIGNMENTS：PP47-48：2，4，6，8，24，28，30BooleanAlgebrasThecircuitsincomputersandotherelectronicdeviceshaveinputs,eachofwhichiseithera0ora1,andproduceoutputsthatarealso0sand1s.Circuitscanbeconstructedusinganybasicelementthathastwodifferentstates.Suchelementsincludeswitchesthatcanbeineithertheonortheoffpositionandopticaldevicesthatcanbelitorunlit.1n1938ClaudeShannonshowedhowthebasicrulesoflogic,firstgivenbyGeorgeBoolein1854inhisThelawsofthought,couldbeusedtodesigncircuits.TheserulesformthebasisforBooleanalgebra.定义2.4.1(二元运算)Anoperatoronasetisbinaryifitcombinesoroperatesontwoelementsofasettoproduceanotherelementoftheset.定义2.4.2(一元运算)Anoperatoronasetisunaryifitoperatesononeelementofasettoproduceanotherelementoftheset.定义2.4.3(布尔代数)ABooleanalgebraisasetBcontainingspecialelements1and0togetherwithbinaryoperators,+and・andaunaryoperator'onB,whichsatisfythefollowingaxiomsforallx,y,andzinB:CommutativeLaws:x•y=y•xx+y=y+xAssociativeLaws:x•(y•z)=(x•y)•zx+(y+z)=(x+y)+zDistributiveLaws:x•(y+z)=(x•y)+(x•z)x+(y•z)=(x+y)•(x+z)IdentityLaws:x+0=xx•1=xComplementLaws:x•x'=0x+x'=1Theelement1iscalledunity(么(单位)元),theelement0iscalledzero(零元),andx‘iscalledthecomplement(补元)ofx.Thebinaryoperation■isoftenomittedsox・yiswrittensimplyasxy.(设B是一个非空集合，•和+是B上的二元运算，'是B上的一元运算，0和1是B中两个特殊元素.若它们满足：(a)交换律:x•y=y•xx+y=y+x结合律:x•(y•z)=(x•y)•zx+(y+z)=(x+y)+z分配律:x•(y+z)=(x•y)+(x•z)x+(y•z)=(x+y)•(x+z)(d)同一律:x+0=xx•1=x(e)互补律:x•x'=0x+x'=1则(B,•+,，,0,1)是一个布尔代数.)定理2.4.1ForallelementsxandyofaBooleanalgebra:IdempotentLaws(等幂律):x•x=xx+x=xNullLaws(零律):x•0=0x+1=1AbsorptionLaws(吸收律):x•(x+y)=xx+(x•y)=x证明定理2・4・1定理2.4.2(补元的唯一性)ThecomplementofanelementxofaBooleanalgebraisuniquelydefinedbyitsproperties;thatis,iX+x'=1,x•x'=0,x+x*=1andx•x*=0,thenx'=x*■证明定理2・4・2定理2.4.3ForallelementsxandyofaBooleanalgebra:InvolutionLaws(对合律):(x,),=xComplementofIdentitiesLaws:O'=11'=0DeMorgan'sLaws(德摩根律):(x+y)'=x•yr(x•y)'=x，+y‘定理2・4・4InaBooleanalgebra,x+y=yifandonlyifx•y=x.证明定理2・4・4定理2.4.5（对偶原理） InaBooleanalgebra,eachaxiomconsistsofapairofequationsthataredual（对彳禺式）inthesensethatifreplace+by•,•by+,0by1,and1by0inoneequation,wegettheotherequation.ASSIGNMENTS：PP53：2，6，8，10，12，14Relations关系是一种被广泛使用的概念，如日常生活中的父子关系、朋友关系、债主与债户关系，自然科学中的函数关系、相似关系、对称关系.在计算机科学理论中关系理论的应用更为普遍：如关系数据库中数据特性关系、程序的输入与输出关系、计算机语言的字符关系、OOP编程中的类继承关系、结构化程序设计中的函数或子程序调用关系、程序的串行与并行运算关系.从前我们介绍集合时，并不关心集合的成员之间有什么关系.而事实上客观世界是由各种各样的事物组成的，事物之间存在着一定的相互作用、相互联系和相互制约的关系.集合的元素并不是乌合之众.因此我们既有必要研究集合元素的个性、共性，更有必要研究元素之间的关系.关系描述了某一集合中两个元素之间的一种特征.关系理论与集合论、数理逻辑以及组合学、图论有很密切的联系.Relationshipsbetweenelementsofsetsoccurinmanycontexts.Everydaywedealwithvariousrelationships.Relationshipsbetweenelementsofsetsarerepresentedusingthestructurecalledabinaryrelation.Relationscanbeusedtosolveproblemssuchasdeterminingwhichpairsofcitiesarelinkedbyairlineflightsinanetwork,findingaviableorderforthedifferentphasesofacomplicatedproject,orproducingausefulwaytostoreinformationincomputerdatabases.定义2.5.1LetAandBbenonemptysets.ArelationRbetweenAandB(A到B的关系)isasubsetofAxB.If(a,b)GR,wesaythataisrelatedtobbymeansofRandwewriteaRb.(A<B的子集R称为A到B的一个二元关系■若(a,b)eR,则称元素a,b有关系R或a与b相关，记为aRb.若(a,b)纟R,则称元素a与b不相关)特别地，当A=B时，称R匸AxA是A上的关系(arelationonA).例2.5.1LetA={1,2,3}andB={r,s}.ThenR={(1,r),(2,s),(3,r)}isarelationbetweenAandB.例2.5.2LetA={1,2,3,4,5}.DefinethefollowingrelationR(<,lessthan)onA:aRbifandonlyifa<b.ThenR={(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)}.例2.5.3LetA=Z+.DefinethefollowingrelationR(|,division)onA:aRbifandonlyifadividesb.Then4R12,but5R7.例2.5.4LetAbethesetofallpossibleinputstoagivencomputerprogram,andBthesetofallpossibleoutputsfromthesameprogram.DefinethefollowingrelationRfromAtoB:aRbifandonlyifbistheoutputproducedbytheprogramwheninputaisused.若R=O，则称之为空关系；若R=AxB，则称R为全域关系■任一关系是笛卡尔积AxB的子集.A上的二元关系{(x,x)|xGA}称为A上的恒等关系，记为I.定义2・5・2LetR匸AxB.ThedomainofR(定义域),denotedbyDom(R),isthesetofelementsinAthatarerelatedtosomeelementsinB.TherangeofR(值域)，denotedbyRan(R),isthesetofelementsinBthatarerelatedtosomeelementsinA.Dom(R)={a|aGAA(3b)(bGBA(a,b)GR)}Ran(R)={b|bGBa(3a)(aGAa(a,b)GR)}例2・5・5设A={1,2,3,4}，R匸AxA定义为：(a,b)GR。2|(a-b)，求R，R的定义域和值域.例2・5・6LetRbetherelationgivenin[例2.5.1].ThenDom(R)=A,Ran(R)=B.例2・5・7LetRbetherelationgivenin[例2.5.2].ThenDom(R)=(1,2,3,4),Ran(R)={2,3,4,5}.定义2・5・3LetR匸AxB.TherelationR-1匸BxA(theinverseofR,R的逆关系)isdefinedbybR-1aifandonlyifaRb.(设A,B均是集合，R匸AxB,则称下列集合R-i={(y,x)|(x,y)eR}匸BxA为R的逆关系)Itisclearfromthedefinitionthat(R-1)-1=R,Dom(R-1)=Ran(R),andRan(R-1)=Dom(R).例2・5・8(1)R上的“S〃与“n〃互为逆关系Z上的“=〃与它本身互为逆关系；任一集合A上的恒等关系I的逆关系是它本身；Z+上的''整除〃与''倍数〃关系互为逆关系A={1,2,3},B={a,b,c},R={(1,a),(2,b),(3,a)},R-1={(a,1),(b,2),(a,3)}.定义2・5・4LetR匸AxB,S匸BxC.Thecomposite(复合)ofSandRistherelationT匸AxCdefinedby(a,c)GTifandonlyifthereisanelementbofBsuchthat(a,b)GRand(b,c)GS.WedenoteTbyS。R.特别地，若A=B=C,R=S，则记R2=R。R，R3=R。R。R， 例2・5・9设A=B=C={1,2,3}，R={(1,3),(2,3)},S={(3,1)},求R。S，SoR.定理2・5・1Compositionofrelationsisassociative;thatis,ifR匸AxB,S匸BxC,andT匸CxD,thenTo(S。R)=(T。S)。R.证明定理2・5・1定义2.5.4LetRbearelationonasetA.IfaRaforallainA,thenwesaythatRisreflexive.(若对va,,有aRa，则称R是自反的)IfaRaforallainA,thenwesaythatRisantireflexive・(若对vaGA,有(a,a)纟R,则称R是反自反的)IfwheneveraRb,thenbRa,thenwesaythatRissymmetric.(对va,bGA,只要aRb,则必有bRa，则称R在A中是对称的)IfwheneveraRbandbRa,thena=b(orifa丰b,thenaRborbRa).WesaythatRisantisymmetric.(对va,bGA,只要aRb,bRa，则必有a=b.则称R在A中是反对称的)IfwheneveraRbandbRc,thenaRc.WesaythatRistransitive.(对va,b,cGA,只要aRb,bRc,则必有aRc.则称R在A中是传递的)例2・5・10(1)I,therelationofequalityonthesetA(A上的恒等关系或相等关系)isreflexive.LetR={(a,b)|a^b,a,bGA}(therelationofinequalityonthesetA,A上的不相等关系).ThenRisantireflexive.LetA={1,2,3}andR={(1,1),(2,1)}.ThenRisnotreflexiveandantireflexive.LetAbeanonemptyset.LetR=①(TheemptyrelationonA,A上的空关系).ThenRisantireflexivebutnotreflexive.RisreflexiveifandonlyI匸R.RisantireflexiveifandonlyifIcR=①・IfRisreflexiveonasetA,thenDom(R)=Ran(R)=A.例2.5.11 (1)LetA=ZandR={(a,b)|a<b},therelationlessthan(<).ThenRisantisymmetricbutnotsymmetric;LetA={1,2,3,4}andR={(1,2),(2,2),(3,4),(4,1)}.ThenRisnotsymmetric.Butitisantisymmetric.LetA=Z+,andR={(a,b)|adividesb}.ThenRisreflexiveandantisymmetric,butnotantireflexiveandsymmetric.定义2・5・5LetRbearelationonasetA.Thereflexiveclosure（自反闭包）ofRisthesmallestreflexiverelationonAcontainingRassaubset.Thesymmetricclosure（对称闭包）ofRisthesmallestsymmetricrelationonAcontainingRasasubset.Thetransitiveclosure（传递闭包）ofRisthesmallesttransitiverelationonAcontainingRasasubset.定理2.5.2LetRbearelationonasetA.（a） ThereflexiveclosureofRisRuI.（b） ThesymmetricclosureofRisRuR-1.（c） If|A|=n,thenthetransitiveclosureofRistherelationRuR2u・・・uRnwh 2=ROR,…,Rk+1=RORk.证明定理2・5・2Representationofafiniteantireflexivesymmetricrelation定义2・5・6Agraph（无向图）isafinitesetVcalledthevertexset（顶点集）,anantireflexivesymmetricrelationRonVandacollectionEoftwo-elementsubsetsofVdefinedby{a,b}GEifandonlyif（a,b）GR.ThesetEiscalledtheedgeset（边集）.AnelementofEiscalledanedge（边）.AgraphisdenotedbyG（托）■If{a,b}GE,thenwesayaandbarejoinedorconnected（连接）bytheedge{a,b}.定义2・5・7Adirectedgraph（有向图）ordigraph，denotedbyG（V,E），consistsofasetofvertices,togetherwitharelationEonVcalledthesetofdirectededge.AnelementofEiscalledadirectededge（有向边）.If（a,b）GE,thenaiscalledtheinitialvertex（起点）of（a,b）andbiscalledtheterminalvertex（终点）.ASSIGNMENTS：PP58-61：4，18，20，28，30，38，40，42，64，82，96PartiallyOrderedSets定义2・6・1ArelationRonAisapartialordering(偏序)ifitisreflexive,antisymmetric,andtransitive.IftherelationRonAisapartialordering,then(A,R)isapartiallyorderedsetorposet(偏序集)withorderingR.例2・6・1(1)Z,R上的、y〃、“n〃，Z+上的整除和倍数关系是偏序关系；设A为任一集合，则(P(A),匸)为一偏序集；但Z，R上的“〈”、“〉〃不是偏序关系.注：由于集合中的偏序关系是Z，R上的、y〃、“n〃的推广，故常用“S〃表示一般的偏序关系，偏序集用(A,S)表示，用>表示偏序关系<的对偶偏序关系.Notethatthesymbol<isbeingusedtodenotethedistinetpartialorders具体理解时，我们应该从具体定义或上下文中了解这些偏序关系的意义.定义2.6.2Twoelementsaandboftheposet(S,<)arecomparable(可比的)ifeithera<borb<a.Ifeverytwoelementsofaposet(S,<)arecomparable,thenposet(S,<)isatotalorderingorachain(全序，链，线序).例2.6.2(1)LetTbethesetofallpositivedivisorsof30andtherelationonTbethedivisibility|.Thentheintegers5and15arecomparablebut5and6arenotcomparable.(2)LetSbethepowersetof{a,b,c}andtherelationonSbetheinclusion匸.Then(S,匸)isaposetbutnotachain,because{a,b}and{a,c}arenotcomparable.NowwewillsimplifythedigraphofapartialorderonafinitesetA.Indeed,sinceapartialorderisreflexive,everyvertexinthedigraphofthepartialorderhasaloop.Soweshalldeleteallsuchloopsfromthedigraphtosimplifythematte.rWeshallalsoeliminatealledgesthatareimpliedbythetransitiveproperty.定义2・6・3设(A,<)是一个偏序集.若bGA满足a<b且b丰a;若xGA使得a<x,x<b,则必有x=a或x=b.则称b是a关于<的覆盖(overlay).例2・6・3 (1)在偏序集(R,<)中，任意实数均无覆盖在(Z,<)中，任意自然数均有唯一的覆盖，即它的后继在({1,2,3,4,5},丨)中，1的覆盖为2和3,2的覆盖为4,而3、4和5无覆盖.对一个偏序集：(1)由于它的自反性,故对应的关系图的每个顶点都有自回路，因此可以省略.每个顶点用点(dot)表示.通过适当安排顶点的位置使各有向边的箭头方向向上，从而有向边可以简化为无向边；(2)若a<b但b不是a的覆盖，则省略a到b的有向边.经过这样处理得到的图称为偏序关系V的哈斯(Hasse)图・任一个偏序关系都有一个哈斯图(Hassediagram).例2・6・4(1)设A={a,b},求(P(A),匸)的哈斯图；设A={a,b,c},求(P(A),匸)的哈斯图；设A={1,2,3,...,12},求(A,|)的哈斯图.解例2・6・4例2・6・5给定偏序关系R的哈斯图，也可求R的表达式.解例2・6・5ASSIGNMENTS：PP63-64：4,8,10,12,18,22,44,46EquivalenceRelations定义2.7.1ArelationRonasetAiscalledanequivalencerelation(等价关系)ifitisreflexive,symmetricandtransitive■(设A为集合，R匸AxA,若R是自反的、对称的和传递的，则称R是A上的等价关系■且若xRy，则称x与y等价)平面上直线之间的平行关系；三角形之间的全等(congruenttriangles)和相似关系，R上的“=〃关系，矩阵之间的''等价〃、''相似〃关系；而R上的二＜，＜，＞及正整数集上的整除和倍数关系都不是等价关系.例2.7.1LetA=Z,m＞1andR={(a,b)|aandbyieldthesameremainderwhentheyaredividedbym}.Wecallmthemodulus(模)andwritea三b(modm),read“aiscongruenttobmodm(a和b模m同余).Congruencemodmisanequivalentrelation(Z上的模m同余关系(m＞2)(congruentrelationmodm)是等价关系).AnequivalencerelationRonAseparatestheelementsofAintosubsetswheretheelementsinagivensubsetareallrelatedtoeachotherthroughtherelationR.(等价关系的作用是将A中的元素划分成互不相交的若干类，每一类的元素有若干共同的性质：如模m同余的整数关于m有相同的余数，全等三角形有相等的边与角.)定义2.7.2LetaGAandRbeanequivaleneerelationonA.Let[a]denotetheset{x:xRa},calledtheequivalenceclass(等价类)containinga.[A]RdenotesthesetofallequivalenceclassesofAfortheequivalencerelationR.(若R为A上的等价关系，aeA，称下列集合={y:yeAAaRy}为a关于R的等价类(记为a/R或[a])(equivaleneeclassofR),称a为等价类[a]的一个代表.称集合{[a]:aGA}为A关于等价关系R的商集(A/R).)例2・7・2由Z上的模m同余关系(m>2)得到的等价类就是模m同余类[0],[1],…，[m-1].例2.7.3LetA={1,2,3,4}andconsidertheequivalencerelationR={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,4)}.Then[A]R={{1,2,3},{4}}.定义2・7・3LetAandIbesetsandletvA>={AiGI},withInonemptybeasetofnonemptysubsetsofA.Theset<A>iscalledapartition(划分,分割)ofAifbothofthefollowingaresatisfied:AicAj=ofori丰j.A=A.iiGI定理2.7.1AnonemptysetofsubsetsvA>ofasetAisapartitionofAifandonlyifvA>=[A]forsomeequivalencerelationR.R证明定理2・7・1ASSIGNMENTS：PP68-69：2,4,8,10,22,24,30,32,34,36,38FunctionsAfunction,aspecialtypeofrelation,playsanimportantroleinmathematics,computerscience,andmanyapplications.定义2・8・1ArelationfonAxBisafunction(函数，映射)fromAtoB,denotedbyf:A—BforeveryaGA,thereisoneandonlyonebGBsothat(a,b)Gf.Iff:A—Bisafunctionand(a,b)Gf,wesaythatb=f(a).Aiscalledthedomain(定义域)offandBiscalledthecodomain(陪域).If A,thenf(E)={b:f(a)forsomeanE}iscalledtheimage(像)ofE.TheimageofAitselfiscalledtherange(值域)off.IfF匸B,thenf1(F)={a:f(a)eF}iscalledthepreimage(原像)ofF设A,B是非空集合.一个从A到B的函数f:A—B是一个满足下列条件的从A到B的关系：对每一个aGA,存在唯 个B满足(a,b)Gf.如果(a,b)Gf,则我们一般表示成f(a)=b，a称为函数f的自变量(argument),b称为a在函数f下的像(image)或值(value).函数也叫做映射(mapping)或变换(transformation).例2.8.1LetA={-2,-1,0,1,2}andB={0,1,2,3,4,5}.DefinetherelationfAxBasf={(-2,5),(-1,2),(0,1),(1,2),(2,5)}.TherelationfisafunctionfromAtoB.例2.8.2LetA={-2,-1,0,1,2}andB={0,1,2,3,4,5}.Letf:A—Bbedefinedbyf(x)=x2+1.IFE={1,2},thenf(E)={2,5}.IFF={0,2,3,4,5},thenf-1(F)={-1,1,-2,2}.f(A)={1,2,5}.定理2.8.1Letg:A—Bandf:B—CbefunctionsfromAtoBandfromBtoCrespectively.Then(a)Thecompositionf。gisafunctionfromAtoC,denotedbyf。g:A—CIfaGA,then(f。g)(a)=f(g(a)).定理2.8.2Thecompositionoffunctionsisassociative.例2.8.3设A=B=Z,C=所有偶数组成的集合.函数f和g定义为：g(a)=a+1f(b)=2b则(fog)(a)=f(g(a))=2g(a)=2(a+1).定义2・8・2Afunctionf:A—Bisone-to-oneorinjective(单射)iff(a)=f(b)impliesthata=b.Afunctionf:—Bisontoorsurjective(满射，到上)ifforeveryyEBthereexistsanaGAsothatf(a)=b.Afunctionthatisbothone-to-oneandontoisone-to-onecorrespondence(一一对应)orbijection(双射).IfA=Bandf:A—Bisabijection,thenfiscalledtobeapermutation(置换，排列)ofA.例2.8.4LetA={a,b,c},B={d,e,f},C={j,k},andD={o,m,n,p}.Considerthefollowingfunctions,fromAtoB,AtoD,andDtoCrespectively:f1={(a,e),(b,f),(c,d)}.f2={(a,m),(b,o),(c,p)}.f3={(d,k),(e,k),(f,j)}.Determinewhethereachfunctionisonetoone,ontoorbijection.定理2.8.3Ifafunctionf:A—Bisabijection,thentheinverserelationf-1isafunctionfromBtoAthatisalsoabijection.Conversely,forf:A—B,iff-1isafunctionfromBintoA,thenfisabijection.证明定理2・8・3定义2.8.3LetI:A—AbedefinedbyI(a)=aforallaGA.ThefunctionIiscalledtheidentityfunctiononA(A上的单位函数).定理2.8.4Iff:A—Bisabijection,then(a)f(f-1(b))=bforeachainB.(b)f-1(f(a))=aforeachainA.定理2・8・5Iff:A—AandIistheidentityfunctiononA,thenI。f=f。I=f.Iffhasaninversefunction(bijection),thenf。f-i=f-i。f=i.定理2.8.6Letg:A—Bandf:B—C;thenIfgandfareontoBandC,respectively,thenf。gisontoC.Ifgandfarebothone-to-one,thenf。gisone-to-one.Ifgandfarebothbijection,thenf。gisbijectiontooand(f。g)-1=g-1。f-1・ASSIGNMENTS：PP68-69：12，16，22，24，28，30，34，36，44定理证明及例题解答定理2・2・1aeA-B。(aGA)A(a电B)o(aeA)a(aeB')oae(AcB')定理2・2・2ae(AuB))oa电ABo(a电A)a(a电B)o(aeA')a(aeB')oae(AB')例2・2・4-(2)由定义显然有B匸AuB.下证AuB匸B.vaeAuB,则aeA或aeB.因为AB,所以aeB■即AuBB.-(3)由定义显然有AcB匸A.下证A匚AnB.vaeA,则aeAuB.因为AuB=B，所以aeB.即aeAcB，故AAcB.-(1)vaeA,因为AcB=A，所以aeAnB,即aeB■故AB.例2・2・5B=Bu(AcB)=Bu(AcC)=(BuA)c(BuC)=(CuA)c(BuC)=(CuA)c(CuB)=Cu(AcB)=Cu(AcC)=C.u显然；-用反证法证明.若A不是B的子集.则3aeA,但a纟B,即aeA-B.aha+xn•tha•(I+XT1:•>+>•XH>+>•xha+xnXH>•XXH>•XnXH>+X)-XH>•Xn>H>+X5N刪殽•*XJX女・><H*XX+OJX•*x+x•*xHcx+X)•*xHI•*xH*x*x・><H*X・><+0H*xx+xXH(*X+X)•><"TXJXXHI•XHS+I)•XH(A•X)+(I•XT>•x)+x(0)fx+xhcx•d+xhcx+x)•(T+xrT•(T+xrT+x(q)XHO+XHOX•X)+XH(X+X)•(x+xTl:•(X+XTX+X(e)Tqzwl眠•哽氏eHCQ—<<nJ叩H心Molls-=MOMMON•#joo」nsopo>4一sueho£oq心4O-Is(3SO1Mp、e)nle(po)<#ose(ve)nCLUJ(PO)<su(Yq)<#UJ(q、e))oUJoEn(#£q、e)<scp、q))g^qEnw(sol-,(p、e)#o(sol-,(p、e)nscp、q)<#,q、e)ncl£po)<s出Qq)<#,q、e))CQ出qmn(le(po)<#os出Qe)oJEn(#os)。一出(p、e)TSNwl蝦First,weshowthatRR2u…uRn匸Rbymathematicalinduction.Forn=1,wehaveR匸R.AssumethatRuR2u Rk匸R.WewillshowthatRuR2u•••uRkuRk+1匸R,thatisRk+1匸R.Let(a,c)ERk+1.Thenther