哈工大集合论习题课-第三章 关系习题课(学生)

1习题课例1设{,,}Aabc，给出A上的一个二元关系，使其同时不满足自反性、反自反性、对称性、反对称和传递性的二元关系，并画出R的关系图。解：{(,),(,),(,),(,)}Raabccbac，关系图如图所示。例2设X是一个集合，X＝n，求：1.X上的二元关系有多少？22n2.X上的自反的二元关系有多少？3.X上的反自反的二元关系有多少？解：因为把所有的反自反的二元关系的每个都加上对角线上的序对，就变成了自反的关系，因此，自反的与反自反的个数一样多。即22nn4.X上的对称的二元关系有多少？2222nnnnn，故共有222nn个对称的关系。5.X上的反对称的二元关系有多少？22(32)nnn6.X上既是自反的也是反自反的二元关系的个数；(0)个7.X上既不是自反的也不是反自反的二元关系有多少？2(2(22))nnn解：解：可用容斥原理来计算设B表示所有自反关系构成的集合，C表示所有反自反关系构成的集合，则22nnBC。而BC，故BCBC，从而CCBCSBCSBC2222222222222(22)nnnnnnnnnnn于是，既不是自反的，也不是反自反关系共有22(22)nnn个。8.自反的且对称的关系有多少？[此结果与“反自反的且对称的关系有多少？”是一样多]即有222nn（对角线上全去掉）9.自反的或对称的关系有多少？2解：设B表示自反关系的集合，C表示对称关系的集合，则自反或对称关系的集合为：22222222nnnnnnBCBCBC。10.X上既是反自反的也是反对称的二元关系的个数为：223nn；11.X上既是对称的也是反对称的关系个数；解：X上既是对称的也是反对称的关系XRI，故有2n。12.X上既不是对称的也不是反对称的关系个数；22222(22232)nnnnnnn解：设A表示对称、B表示反对称，则既不是对称的也不是反对称的二元关系为：||||||||||||||CCABSABSABAB2222222232nnnnnnn例3设有集合A，3A，求A上具有反自反且反对称性的二元关系的数目，并写出计算过程。解：不妨设{,,}Aabc，将(,)ab，(,)ba看作一个抽屉，(,)bc，(,)cb看作一个抽屉，(,)ac，(,)ca看作一个抽屉。若要获得具有反对称性且反自反性的关系，其中的元素只能在三个抽屉中取且每个抽屉中至多取一个元素，分几种情况：（1）一个也不取，有031C种取法。（2）只取一个元素，有1326C种取法。（3）取二个元素，有232212C种取法。（4）取三个元素，有332228C种取法。故具有反自反性且反对称性的二元关系数目共有1＋6＋12＋8＝27个。若An，结果又为多少？抽屉数：22nnA，每个抽屉有3种选择，故共有223nn个。例4设{1,2,3}A，R是A的幂集2,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}A上的二元关系且{(,)|}Rabab，则R不满足下列哪些性质？为什么？3（1）自反性；（2）反自反性；（3）对称性；（4）反对称性；（5）传递性。{(,)|}Rabab等价于aRbab(,)abRab。解：(1)自反性。因为2A，但，所以(,)R，故R不是自反的。（2）反自反性。因为{1}2A，{1}{1}{1}，故({1},{1})R，故R不是反自反的。（3）对称性。,2Axy，若(,)xyR，则xy，所以yx，故(,)yxR，从而R是对称的。（4）反对称性。令{1,2}x，{1,3}y，则{1}xyyx，故(,)xyR且(,)yxR，但xy，所以(,)(,)xyyx，从而R不是反对称的。（5）传递性。令{1}x，{1,2}y，{2}z，则有{1}xy且{2}yz，故(,)xyR且(,)yzR，但xz，故(,)xzR，所以R不是传递的。例5设R是复数集合C上的一个二元关系且满足xRyxyabi，a，b为非负整数，试确定R的性质。解：1.若a＝b＝0时，则xRyxy[{(,)|0}{(,)|}]CxRyxyRxyxyxyxCI等价于，故R为C上的恒等关系，显然满足：自反，对称，反对称和传递性质。2.若,ab不全为0，则满足反对称和反自反性质，但不满足自反、对称和传递性。（1）xC，0xxabi，所以(,)xxR，故R是反自反的，但不是自反的。（2）,xyC,若xRy,则xyabi，而yxabi，因为,ab不全不4零，所以abiabi，故不可能有yRx，即R是反对称的，但R不是对称的。（3）,,xyzC，若xRy且yRz，则xyabi且yzabi，而22xzabi，因为,ab不全为零，故22abiabi，故不可能有xRz，即R不是传递的。习题课例1证明：RRRRR，其中0120iiRRRRR证：01223()()RRRRRRRRRtRR；同理可证RRR例2[书上做为定理出现]设R、S是X上的二元关系，则（1），是空关系。（2）()RR证：因为R是传递的，故()RR。（3）()RSRS证：因为RSR且RSS，故()RSR，且()RSS，从而()RSRS例3如图5所示给出下图中每个关系的自反、对称和传递闭包。··（a）（b）（c）图5（1）自反闭包5（2）对称闭包（3）传递闭包例4设R是集合A上的反对称关系，则t(R)一定是反对称的吗？证：t(R)在A上不一定是反对称的。例：{,,,}Aabcd，{(,),(,),(,),(,)}Rabbccdda则R的传递闭包为：(){(,),(,),(,),(,),(,),tRabbccddaac(,),(,),(,),(,),(,),(,),(,),(,),(,),(,),(,)}addcddcabddbbacbaabbcct(R)是全关系，故t(R)不是反对称的而是对称的。例5是否可以定义二元关系的反自反闭包与二元关系的反对称闭包？为什么？解：不可以。设A={a,b,c},R={(a,a)(a,b),(b,a),(a,c)},则反自反闭包与反对称闭包不存在。例6举例说明(())stR与(())tsR确实不相等。解：设{1,2,3,}N，在N上定义小于关系“”，则(())()sts“不等关系≠”；而(())()tst“全关系”。因此的确不相等。例7（898P）是否存在X（Xn）上的一个二元关系R，使得2,,,nRRR两两6不相等。解：存在。令{1,2,3,,}Xn，{(1,2),(2,3),,(1,)}Rnn即可。例8证明：如果R是对称的，则R＋也是对称的。证：证11(,)iixyRR，则mN，使得(,)mxyR。于是存在m－1个元素121,,,myyy，使得1112211(,),(,),,(,),(,)mmmxyRyyRyyRyyR。由R的对称性有：112211(,),(,),,(,),(,)mmmyyRyyRyyRyxR。于是(,)myxR，从而1(,)iiyxRR，即1iiRR是对称的。习题课例1设R是整数集I上的关系，mRn定义为22mn，则（1）证明：R是等价关系；（2）确定R的等价类。证：（1）因为mI，有22mm，故mRm，即R是自反的。,mnI，若mRn，即22mn，则22nm，因此nRm，即R是对称的。,,mnkI，若mRn，nRk，即22mn且22nk，故22mk，即mRk，所以R是传递的。由此可知：R是I上的等价关系。（2）因为iI，[]{,}Riii，所以R的等价类有：{[0],[1],[2],}RRR。例2设R是A上的一个自反关系，证明：R是等价关系若(,)abR且(,)acR，则(,)bcR。[书上习题]证：R是A上的等价关系。若(,)abR且(,)acR，由R的对称性有：(,)baR且(,)acR，再由R的传递性有：(,)bcRR是自反的，故aA有(,)aaR。7是等价关系不是等价关系（因为不传递）若(,)abR，由(,)aaR，有(,)baR，所以R是对称的。若(,)abR且(,)bcR，由R的对称性有：(,)baR且(,)bcR，故由题意得(,)acR，所以R是传递。因此，R是A上的等价关系。例3.令{1,2,3}A，A上的两个关系如图3所示，它们是否是等价关系？132231图3例4设1R，2R是A上的等价关系，则12RR也是A上的等价关系吗？解：12RR不一定是A的等价关系。因为12RR不一定具有传递性。举例：设{,,}Aabc，1{(,),(,),(,),(,),(,)}Raabbccabba，2{(,),(,),(,),(,),(,)}Raabbccbccb，则12{(,),(,),(,),(,),(,),(,),(,)}RRaabbccabbabccb因为12(,)abRR且12(,)bcRR，但12(,)acRR，故12RR不满足传递性，即12RR不一定是A上的等价关系。例5设{1,2,,},XnSXX。“”是S上如下的二元关系：(,),(,)ijklS，(,)(,)ijkl当且仅当ijkl。证明：(1)等价关系；(2)求等价类数。证：(1)等价关系显然；(2)等价类数为：21n。ij只能取2，3，…，2n，故等价类数有21n个。例6设R是A上的对称和传递的关系。若对A中每个a，bA，使得(,)abR，8证明：R是A上的等价关系。证：aA，bA，使得(,)abR。由R的对称性有：(,)baR。再由R的传递性有：(,)aaR。由a的任意性可知，R是A上的自反关系，故R是A上的等价关系。例7设R是集合A上的一个自反的和传递的关系；T是A上的一个关系，使得(,)(,)abTabR且(,)baR。证明：T是A上的等价关系。证：（1）因为R是A上的自反关系，所以aA，有(,)aaR，故由T的定义有：(,)aaT，即T是A上的自反关系。（2）若(,)abT，由题设：(,)abR且(,)baR。显然，(,)baT，即T是A上的对称关系。（3）若(,)abT且(,)bcT，由题设可知：(,)abR，(,)baR且(,)bcR，(,)cbR。由R传递性得：(,)acR且(,)caR，故(,)acT，所以T是A上的传递关系。由（1），（2），（3）即得T是A上的等价关系。例8设R是A上的一个二元关系，设{(,)|SabcA，使得(,)acR且(,)cb}R。证明：（1）若R是A上的等价关系，则S也是A上的等价关系；（2）证明：RS。分析：根据等价关系的定义，即关系R应满足自反性、对称性和传递性，分三步证明。证：1.证明若R是等价关系，则S也是等价关系。（1）自反性因为R是自反的，所以aA，有(,)aaR。根据S的定义，有(,)aaS，所以S是自反的；（2）对称性：若(,)abS，则cA，使得,acR且,cbR。因为R是对称的，所以,bcR且,caR，根据S的定义有,baS，所以S是对称的；(3)传递性：9若,abS，,bcS，则dA，使得,adR且,dbR。因为R是传递的，所以,abR。且eA，使得,beR且,ecR。因为R是传递的，所以,bcR。根据S的定义有,acS。所以S是传递的。由（1），（2），（3）可知：S是