(b) 对???,标准序?，重复上一题。
3.5 等价关系
41. 设R是A上的等价关系，将A的元素按R的等价类顺序排列，则等价关系的关系矩阵
MR有何特征？
42. 证明集合A上的全域关系A?A是等价关系。 43. 假设A是含n各元素的有限集合（n?N），问 (a) 有多少个元素在A上的最大等价关系中？ (b) A上的最大等价关系的秩是什么？ (c) 有多少个元素在A上的最小等价关系中？ (d) A上的最小等价关系的秩是什么？ 44. 设R和R?是集合A上的等价关系， (a) 证明RR?是集合A上的等价关系；
R?不一定是集合A上的等价关系，要尽可能小地选取集合A。
(b) 用例子证明R45. 设R1和R2是非空集合A上的等价关系，确定下述各式，哪些是A上的等价关系，对不
是的举例说明。 (a) A?A?R1； (b)R1?R2； (c)R12；
(d)r(R1?R2)（R1?R2的自反闭包）； (e) R1R2。
46. R是整数集合I上的等价关系，将R中的每一序偶?x,y?标在I?I笛卡儿平面上，
所得图形有何特点？
47. 应用上题结论说明下述I集合上的二元关系是否是等价关系，对不是的说明为什么，并
找出R诱导的等价关系。 (a) R??；
(b) R?{?a,b?|(a?0?b?0)?(a?0?b?0)}；
第29页 共53页
(c) R?{?a,b?|(a?0?b?0)?(a?0?b?0)}；
(d) R?{?a,b?|?x(x?I?10x?a?10(x?1)?10x?b?10(x?1))}； (e) R?{?a,b?|a整除b}。
Ra，48. R是集合A上的二元关系，对于所有的a,b,c?A，如果aRb,bRc，则c那么称R是循环的，试证明R是自反的和循环的当且仅当R是一等价关系。
49. 下述论证一位着每一对称的何传递的关系是一等价关系。设R是一对称的何传递关系， (i) 因为R是对称的，如果?x,y??R，那么?y,x??R；
(ii) 因为R是传递的，如果?y,x??R??x,y??R，那么?x,x??R，所以R是自
反的。这得出R是一等价关系。 这个论证有什么错误？
50. 设A?{a,b,c}，求出A的所有划分；设A的所有划分构成的集合是P，画出
?P,细分?的哈斯图。
51. 设A?{a,b,c,d}，?1是A的划分，?1?{{a,b,c},{d}}。 (a) 列出?1诱导出的等价关系的序偶；
(b) 对划分?2?{{a},{b},{c},{d}}，?2?{{a,b,c,d}}，做同样工作； (c) 画出偏序集合?{?1,?2,?3},细分?的哈斯图。
52. 设?1和?2是非空集合A的划分，说明下列各式哪些是A的划分，哪些可能是A的划分，
哪些不是A的划分？ (a) ?1(b) ?1?2； ?2；
(c) ?1??2； (d) (?1(?2??1))?2。
,Am}是集合A的划分，若AiB??，i?1,2,,m，试证明
53. 设{A1,A2,第30页 共53页
{A1B,A2B,,AmB}是AB的划分。
,?k是A上划分序列，使?i?1真细分?i，找
54. 设A是n个元素的有限集，假设?1,?2,出最大可能的序列长度。
55. 设A?I，定义A上的R1,R2,R3如下：
aR1b?a?b(mod3)，aR2b?a?b(mod5)，aR3b?a?b(mod6)，
(a) 对偏序集合?{A/R1,A/R2,A/R3},细分?画出哈斯图； (b) 描述一下各式所诱导的等价关系，它们的秩是什么？
A/R1A/R2，A/R1A/R3，A/R1?A/R2，A/R1?A/R3。
56. 设Rj表示I上模j等价，设Rk表示I上模k等价， (a) 证明I/Rk细分I/Rj当且仅当k是j的整数倍； (b) 描述划分I/Rk?I/Rj； (c) 描述划分I/RkI/Rj。 57. 证明如果?1细分?2，那么?1?2??1和?1??2??2。
58. 设P表示非空集合A的所有划分的集合，考虑偏序集合?P,细分?，设?1和?2是P的
成员， (a) 证明?1?2是集合{?1,?2}的最大下界；
(b) 证明?1??2是集合{?1,?2}的最小上界。
59. 设R是集合A上的二元关系，如果R是自反的和对称的，则称R是相容关系。设
A?{316,347,204,678}，R?{?x,y?|x?A?y?A?x和y有相同的数字}，
(a) R是相容关系吗？ (b) 画出R的关系图。
(c) 所有等价关系都是相容关系吗？
(d) 相容关系的关系图和等价关系的关系图有何不同？
第31页 共53页
补充习题：
1设A={a,b}，B={1,2}，求A上的恒等关系IA和A到B的全域关系A×B。 2设A={a1,a2,a3,a4}，B={b1,b2,b3}，R是A到B的二元关系，定义为：
R={
3设A={1,2,3,4}，R是A的二元关系，定义为：
R={<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>,<4,1>} 写出A上二元关系R的关系矩阵。
4设X={1,2,3,4}，X上的二元关系H和S定义如下：
x?y是整数} 2x?yS={
3H={
试求H∪S，H∩S，~H，S-H。
5X={1,2,3,4,5}，X上的二元关系R和S定义如下：
R={<1,2>,<3,4>,<2,2} S={<4,2>,<2,5>,<3,1>,<1,3>}
试求R°S，S°R，R°(S°R)，(R°S)°R，R°R，S°S，R°R°R 。 6A={ 1,2,3,4}，A上的二元关系R定义如下：
R={<1,2>,<2,1>,<2,3>,<3,4>} 求二元关系R的各次幂。
7A={1,2,3,4,5}，A上的二元关系R和S定义如下：
R={<1,2>,<2,2>,<3,4>} S={<1,3>,<2,5>,<3,1>,<4,2>} 试求MR °
S和
MR ° MS，它们是否相等 ?
8设X={1,2,3,4}，Y={a,b,c}，X到Y二元关系
R={<1,a>,<2,b>,<4,c>}，
⑴试求RC，写出MR和MRC，验证MRC=MRT
⑵画出R和RC的关系图，验证将R关系图中的弧线的箭头反置可得到RC关系图。 9设R是实数集合，
第32页 共53页