第5章 等价关系与偏序关系

一、选择题（每题3分）

1、设Z为整数集，下面哪个序偶不够成偏序集（ A ）

A、?Z,??(?：小于关系) B、?Z,??(?：小于等于关系) C、?Z,D?(D：整除关系) D、?Z,M?(M：整倍数关系)

2、序偶??(A),??必为（ B ）

A、非偏序集 B、偏序集 C、线序集 D、良序集 3、设?：小于等于关系Z为整数集，下面哪个序偶能够成良序集（ D ） A、?R,??C、?Z,????(R：正实数集) B、?Q?,??(Q?：正有理数集)

(Z?：正整数集) D、?N,??(N：自然数集)

4、设A?{?,{1},{1,3},{1,2,3}}，则A上包含关系“?”的哈斯图为（ C ）

5、集合A?{ 1, 2, 3,4 }上的偏序关系图为

则它的哈斯图为（ A ）

6、某人有三个儿子，组成集合A?{ S1, S2, S3 }，则在A上的兄弟关系一定不是（ D ） A、偏序关系 B、线序关系 C、良序关系 D、等价关系 7、有一个人群集合A?{ P1, P2, ?, Pn}，则在A上的同事关系一定是（ D ） A、偏序关系 B、线序关系 C、良序关系 D、等价关系 8、设A为非空集合，则下列A上的二元关系中为等价关系的是（ D ）

A、空关系 B、全域关系 C、恒等关系 D、上述关系都是 9、设A?{ 1, 2, 3 }，则A上不同等价关系的个数为（ C ）

A、3 B、4 C、5 D、6 10、设A?{ 1, 2, 3, 4 }，则A上不同等价关系的个数为（ C ）

A、13 B、14 C、15 D、16 注：除了等价关系可以对空集定义，而划分不能外，等价关系与划分是相同概念的不同描述． 11、设S?{ 1, 2 }，“?”为S中元素的普通乘法，定义S?S上的等价关系

R?{??a,b?,?c,d?? | ?a,b??S?S,?c,d??S?S,a?d?b?c}， 则由R产生的S?S上一个划分的分块数为（ D ）

A、1 B、2 C、3 D、4 提示：记a1??1,1?,a2??1,2?,a3??2,1?,a4??2,2?，

则由R的关系图易知S?S?{{a1},{a2},{a3},{a4}}．

12、设S?{ 1, 2, 3 }，“?”为S中元素的普通乘法，定义S?S上的等价关系

R?{??a,b?,?c,d? | ?a,b??S?S,?c,d??S?S,a?d?b?c}， 则由R产生的S?S上一个划分的分块数为（ C ）

A、3 B、5 C、7 D、9 提示：因a?d?b?c，则a?b?c?d

因a?b??2,?1,0,1,2，则等价关系R产生的S?S上一个划分的分块数为5． 二、填充题（每题4分）

1、设A?{ a, b, c,d }，其上偏序关系R的哈斯图为

则R? {?a,b?,?a,c?,?a,d?,?b,d?,?c,d?}?IA．

2、设A?{ a, b, c,d,e,f,g }，偏序集?A,R?的哈斯图为

bcfdeg，

则R? {?a,b?,?a,c?,?a,d?,?a,e?,?a,f?,?d,f?,?e,f?}?IA．

a?a,b??a??b?

3、偏序集??({a,b}),??的Hass图为

?

4、对于A?{ 1,2,3,4,6,8,12,24 }，则偏序集?A,整除关系?的哈斯图为

2484211263．

5、设A?{ ，“?”为A上整除关系，则偏序集?A,??的极小元为1，1,2,3,4,6,8,12,24 }最小元为1，极大元为24、最大元为24． 6、设A?{ 2,3,4,6,8,12 }，“?”为A上整除关系，则偏序集?A,??的极小元为2,3，最小元为无，极大元为8,12，最大元为无，既非极小元也非极大元的是4,6．

7、设A?{a,b,c}考虑下列子集S1?{{a,b},{b,c}}，S2?{{a},{a,b},{a,c}}，

S3?{{a},{b,c}}，S4?{{a,b,c}}，S5?{{a},{b},{c}}，S6?{{a},{a,c}} 则A的覆盖有S1,S2,S3,S4,S5 ，A的划分有S3，S4，S5．

8、设A?{ 1, 2, 3,4 }，S?{{1},{2,3},{4}}为A的一个分划，则由S导出的等价关系为 R? {?1,1?,?2,2?,?2,3?,?3,2?,?3,3?,?4,4?}． 提示：R?({1}?{1})?({2,3}?{2,3})?({4}?{4})．

9、非空正整数子集A上的模k等价关系R的秩为k，A/R?{[0]k,[1]k,?,[k?1]k}．

三、问答题（每题6分）

1、试比较偏序集合、线序集合与良序集合．

答：若集合A上的二元关系R是自反的，反对称的和传递的，称序偶?A,R?为偏序集； 偏序集中的各元素并非都能比较，若都能比较，偏序集成为线序集；

在线序集中，若A的任一非空子集都有一最小元素，则线序集成为良序集．

2、设|A|?5，R是A的等价关系，由R诱导的A的划分块数为3，则不同的R有多少种？ 答：一个集合上的等价关系数目与该集合的划分数目是一致的，因而，该题只需求出将5个元素的集合分成3份的划分种数即可．

如果3份中元素个数分别为3，1，1，则共有C5种， 如果3份中元素个数分别为2，2，1，则共有C5种， 因此，A上秩为3的等价关系共有C5+C5?20．

3、设A是实数集合，试判断R?{?x,y?x?A?y?A?x?y?3}是A上的偏序关系吗？等价关系吗？为什么？

答：都不是；因 ?x?A，x－x=0≠2，所以?x,x??R，R不是自反的． 四、画图填表题（每题10分）

1、设A?{ a, b, c,d,e}上的关系R? {?c,d?}?IA，画出偏序集?A,R?的哈斯图， 列表给出A的子集B1?{ a,b, c,d,e},B2?{ c,d},B3?{c,d,e}的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界． 解：哈斯图如图4.44所示：

其子集Bi,i?1,2,3上的各种特殊元素如下表所示，

B1 B2 B3 极大元 极小元 最大元 无 d 无 最小元 无 c 无 上界 无 d 无 下界 无 c 无 上确界 无 d 无 下确界 无 c 无 3232a,b,d,e a,b,c,e d d,e c c,e 2、设A?{ a, b, c}的幂集?(A)上的关系?? {?x,y?x??(A)?y??(A)?x?y}， 画出偏序集??(A),??哈斯图，列表给出?(A)子B1?{ ?,{a},{b}},B2?{{a},{c}}，B3?{{a,c},{a,b,c}}的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界． 解：哈斯图如图4.45所示：

其子集Bi,i?1,2,3上的各种特殊元素如下表所示，

B1 B2 B3 极大元 ?a?,?b? 极小元 最大元 无 无 ?a,b,c? 最小元 上界 ?a,b,c?, ?a,b? ?a,b,c?, ?a,c? ?a,b,c? 下界 上确界 ?a,b? ?a,c? ?a,b,c? 下确界 ? ?a,c? ? 无 ?a,c? ? ? ?a,c? ? ? ?a,c? ?a?,?c? ?a?,?c? ?a,b,c?

3、试填出A?{1,2,3,4,5}上的等价关系R，

其产生划分A/R?{{1,2},{3},{4,5}},并画出关系图． 解：R?{1,2}?{1,2}?{3}?{3}?{4,5}?{4,5}

其关系图为：

六、证明题（每题10分）

1、设R是A上的二元关系，如果R是传递的和反自反的，称R是A上的拟序关系， 证明：如果R是A上的拟序关系，则r(R)?R?IA是A上的偏序关系． 证明：（1）因r(R)?R?IA?IA，有r(R)是自反的；

（2）设?x,y??r(R),而x?y，则?x,y??R,若?y,x??R, 由R的传递性，知?x,x??R,与R的反自反性矛盾，则?y,x??R, 又?y,x??IA,有?y,x??R?IA?r(R)，于是有r(R)是反对称的；

（3）由R的传递性，知R?R?R，

因r(R)?r(R)?(R?IA)?(R?IA)?((R?IA)?R)?((R?IA)?IA)

?((R?R)?(IA?R))?((R?IA)?(IA?IA))?(R?R)?R?IA?r(R)，则r(R)可传递； 综上所述，可证r(R)是A上的偏序关系．

2、设R是A上的二元关系，如果R是传递的和反自反的，称R是A上的拟序关系， 证明：如果R是A上的偏序关系，则R?IA是A上的拟序关系．

证明：（1）(R?IA)?IA?(R?IA)?IA?R?(IA?IA)?R????，则R?IA反自反； （2）设?x,y??R?IA,?y,z??R?IA，则?x,y??R,?y,z??R，而x?y,y?z，因R是传递的，有?x,z??R；若x?z，则?z,y??R,?y,z??R，由R的反对称性，知y?z，与y?z矛盾，于是x?z，则?x,z??R?IA，有R?IA是传递的； 综上所述，可证R?IA是A上的拟序关系．

3、设R是A上的对称和传递关系，

证明：若?a?A,?b?A,??a,b??R，则R是A上的等价关系． 证明：?a?A,?b?A,??a,b??R，因R是对称的，有?b,a??R，

又因R是传递的，所以?a,a??R，则R在A上自反，故R是A上的等价关系． 4、设R是S上的偏序关系，证明：R是S上的偏序关系． 证明：（1）?x?S，因R在S上的自反性，则?x,x??R， 有?x,x??R，于是，R?1在S上是自反的；

（2）设?x,y??R,而x?y，则?y,x??R,因R在S上的反对称性，有?x,y??R, 则?y,x??R,于是，R?1在S上是反对称的；

（3）设?x,y??R,?y,z??R，则?z,y??R,?y,x??R，

因R在S上的传递性，有?z,x??R,则?x,z??R,于是，R'在S'上是传递的； 综上所述，可证R是S上的偏序关系．（题4在证明中用了定义法） 5、设R是S上的等价关系，证明：R是S上的等价关系．

?1证明：（1）因R在S上的自反性，有IS?R，则IS?IS?R，有R在S上自反；

?1?1?1?1?1?1?1?1?1?1?1?1?1?R，则(R?1)?1?R?R?1，有R?1在S上对称；

2?1221??1（3）因R在S上的传递性，有R?R，则(R)?R?R?R，有R在S上可传递；

（2）因R在S上的对称性，有R2?1则R'?(R'?R)?(R'?(S'?S'))?R?(S'?S')?R'，有R'在S'上是对称的； 综上所述，可证R是S上的等价关系．（题5在证明中用了集合法）

?16、设R,S是A上的偏序关系，证明：R?S是A上的偏序关系．

证明：（1）?x?A，因R,S在A上的自反性，则?x,x??R?S，有R?S在A上自反； （2）设?x,y??R?S,而x?y，则?x,y??R,?x,y??S,因R,S在A上的反对称性，有?y,x??R,?y,x??S,则?y,x??R?S,于是，R?S在A上是反对称的； （3）设?x,y??R?S,?y,z??R?S，

则?x,y??R,?y,z??R;?x,y??S,?y,z??S，因R,S在A上的传递性， 有?x,z??R,?x,z??S,则?x,z??R?S，于是，R?S在A上是传递的； 综上所述，可证R?S是A上的偏序关系．（题6在证明中用了定义法） 7、设R,S是A上的等价关系，证明：R?S是A上的等价关系．

证明：（1）因R,S在A上自反，有IA?R,IA?S，则IA?R?S，有R?S在A上自反； （2）因R,S在A上对称，有R则(R?S)?1?1?R,S?1?S，

2?R?1?S?1?R?S，有R?S在A上对称；

222（3）因R,S在A上传递，有R?R,S?S，

则(R?S)?((R?S)?R)?((R?S)?S)?R?S?R?S，有R?S在A上可传递； 综上所述，可证R?S是A上的等价关系．（题7在证明中用了集合法） 8、设R是S上的二元关系，S'?S定义S'上的二元关系R'?R?(S'?S'),

证明：如果R是S上的偏序关系，那么R'是S'上的偏序关系． 证明：（1）?x?S'?S，因R在S上的自反性，则?x,x??R，而?x,x??S'?S'， 有?x,x??R?(S'?S')?R'，于是，R'在S'上是自反的；

（2）设?x,y??R',而x?y，则?x,y??R,因R在S上的反对称性，有?y,x??R, 则?y,x??R?(S'?S')?R',于是，R'在S'上是反对称的；

（3）设?x,y??R',?y,z??R'，因R在S上的传递性，有?x,z??R, 而?x,z??S'?S'，则?x,z??R?(S'?S')?R'，于是，R'在S'上是传递的； 综上所述，可证R'是S'上的偏序关系．（题8在证明中用了定义法）

9、设R是S上的二元关系，S'?S定义S'上的二元关系R'?R?(S'?S'),

证明：如果R是S上的等价关系，那么R'是S'上的等价关系． 证明：（1）因R在S上的自反性，则IS?R，而S'?S,有IS'?IS?R，而IS'?S'?S'， 有IS'?R?(S'?S')?R'，于是，R'在S'上是自反的；

2?R，而(S'?S')?1?S'?S'，

?1?1?1?1则(R')?(R?(S'?S'))?R?(S'?S')?R'，有R'在S'上是对称的；

（2）因R在S上的对称性，有R2?1（3）因R在S上的传递性，有R?R，

有R'?R?R?R，而R'?(S'?S')?(S'?S')?S'?S'，

则R'?(R'?R)?(R'?(S'?S'))?R?(S'?S')?R'，有R'在S'上是传递的； 综上所述，可证R'是S'上的等价关系．（题9在证明中用了集合法） 10、若R是A上的等价关系，则S?{?a,b?|a,b?A??c?A(?a,c??R??c,b??R)}也是A上的一个等价关系． 证明：（1）?a?A，由R自反，则?a,a??R??a,a??R，??a,a??S，有S自反；（2）??a,b??S，则?c?A，使?a,c??R,?c,b??R,

由R在A上对称，有?b,c??R,?c,a??R,有?b,a??S，知S对称； （3）若?a,b??S,?b,c??S，则?d?A，使?a,d??R,?d,b??R, 同时?e?A，使?b,e??R,?e,c??R,

由R在A上传递，知?a,b??R,?b,c??R,有?a,c??S，有S传递； 综上所述，可证S是A上的等价关系．（题10在证明中用了定义法）

222六、证明计算题（每题10分）

1、设A?{1,2,3}，在A?A上定义R:??a,b?,?c,d???R? a?b?c?d， “?”为普通加法，证明：R是A?A上的等价关系，并求出[?1,3?]R,A?A/R． 证明：（1）??a,b??A?A,?a?b?a?b,???a,b?,?a,b???R,即R自反； （2）???a,b?,?c,d???R,则a?b?c?d,?c?d?a?b, 则??c,d?,?a,b???R，即R对称；

（3）???a,b?,?c,d???R,??c,d?,?e,f???R,则a?b?c?d?e?f， ???a,b?,?e,f???R,即R传递； 综上得出，R是A?A上的等价关系，

且[?1,3?]R?{?a,b??a,b??A?A,a?b?4}?{?1,3?,?2,2?,?3,1?},

A?A/R?{[?1,1?]R,[?1,2?]R,[?1,3?]R,[?2,3?]R,[?3,3?]R}．

2、设A?{1,2,3,4}，在A?A上定义R:??a,b?,?c,d???R? a?d?b?c， “?”为普通加法，证明：R是A?A上的等价关系，并求出[?2,4?]R,A?A/R． 证明：（1）??a,b??A?A,?a?b?b?a,???a,b?,?a,b???R,即R自反； （2）???a,b?,?c,d???R,则a?d?b?c,?c?b?d?a, 则??c,d?,?a,b???R，即R对称；

（3）???a,b?,?c,d???R,??c,d?,?e,f???R, 则a?d?b?c,c?f?d?e?a?d?c?f?b?c?d?e 有 a?f?b?e，???a,b?,?e,f???R,即R传递； 综上得出，R是A?A上的等价关系，

且[?2,4?]R?{?a,b??a,b??A?A,a?b?2}?{?1,3?,?2,4?},

A?A/R?{[?1,1?]R,[?1,2?]R,[?2,1?]R,[?1,3?]R,[?3,1?]R,[?1,4?]R,[?4,1?]R}． 3、设A?{1,2,3,4}，在A?A上定义R:??a,b?,?c,d???R? a?d?b?c， “?” 为普通乘法，证明： R是A?A上的等价关系，并求出[?2,4?]R,A?A/R． 证明：（1）??a,b??A?A,?a?b?b?a,???a,b?,?a,b???R,即R自反； （2）???a,b?,?c,d???R,则a?d?b?c,?c?b?d?a, 则??c,d?,?a,b???R，即R对称；

（3）???a,b?,?c,d???R,??c,d?,?e,f???R, 则a?d?b?c,c?f?d?e?a?d?c?f?b?c?d?e， 有 a?f?b?e，???a,b?,?e,f???R,即R传递； 综上得出，R是A?A上的等价关系，

且[?2,4?]R?{?a,b??a,b??A?A,2a?b}?{?1,2?,?2,4?},

A?A/R?{[?1,1?]R,[?1,2?]R,[?2,1?]R[?1,3?]R,[?3,1?]R,[?1,4?]R,[?4,1?]R}． 4、设A?{ 1, 2, 3, 4 }，在A的幂集?(A)上规定R?{?s,t?|s,t??(A)?(|s|?|t|}， 证明：R是?(A)上的等价关系，并写出商集?(A)R．

证明：⑴?s??(A) ，由于|s|?|s|，所以?s,s??R，即R自反的；

⑵?s,t??(A) ，若?s,t??R，则|s|?|t|?|t|?|s|，??t,s??R，R是对称的； ⑶?s,t,u??(A)，若?s,t??R且?t,u??R，即|s|?|t|?|u|， 则?s,u??R 所以R是传递的； 综上得出，R是?(A)上的等价关系，

?(A)R?{[?]R,[{1}]R,[{1,2}]R,[{1,2,3}]R,[{1,2,3,4}]R}．