习 题 二

1.确定下列二元关系：

（1）

（2）  

解：(1) 

(2)    

2. 请分别给出满足下列要求的二元关系的例子：

（1）既是自反的，又是反自反的；

（2）既不是自反的，又不是反自反的；

（3）既是对称的，又是反对称的；

（4）既不是对称的，又不是反对称的.

解：设 是定义在集合 上的二元关系。

(1)   令 ，则 ，于是 既是自反又是反自反的；

(2)   令 ，于是 既不是自反又不是反自反的；

(3)   令 ，于是 既是对称又是反对称的；

(4)   令 ，于是 既不是对称又不是反对称的。

3. 设集合 有 个元素，试问：

（1）共有多少种定义在 上的不同的二元关系？

（2）共有多少种定义在 上的不同的自反关系？

（3）共有多少种定义在 上的不同的反自反关系？

（4）共有多少种定义在 上的不同的对称关系？

（5）共有多少种定义在 上的不同的反对称关系？

解：设 ，于是

(1)   共有 种定义在 上的不同的二元关系；

(2)   共有 种定义在 上的不同的自反关系；

(3)   共有 种定义在 上的不同的反自反关系；

(4)   共有  种定义在 上的不同的对称关系；

(5)   共有 种定义在 上的不同的反对称关系，其中， 。

4. 请分别描述自反关系，反自反关系，对称关系和反对称关系的关系矩阵以及关系图的特征.解：(1) 自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈。

(2)   反自反关系矩阵的主对角线上元素全为0; 而关系图中每个结点上均无圈。

(3)   对称关系矩阵为对称矩阵; 而关系图中任何两个结点之间的有向弧是成对出现的, 方向相反。

(4)   反对称关系矩阵 的元素满足：当 时， 。

5．设 ，试求 及 .

解：

  。

6. 试举出使

 

 

成立的二元关系 的实例.

解：设 ,

于是, 有 , 因此,

, 从而,  。

又， ，因此，

，从而,  。

7. 设 和 是集合 上的二元关系. 下面的说法正确吗?请说出理由.

（1）若 和 是自反的，则 也是自反的；

（2）若 和 是反自反的，则 也是反自反的；

（3）若 和 是对称的，则 也是对称的；

（4）若 和 是反对称的，则 也是反对称的；

（5）若 和 是传递的，则 也是传递的

解：(1) 正确。因为对任意 ，有 ，所以 。故 是自反的。

(2)   错误。例如，设 ，且 ，于是 。故 不是自反的。

(3)   错误。例如，设对称关系 。于是， ，但 。故 不是对称的。

(4)   错误。例如，设反对称关系 。于是， 。故 不是反对称的。

(5)   错误。例如，设传递关系 。于是， ，但因为 ，所以， 。

8．设 和 是集合 上的二元关系，试证明：

（1） ；

（2） ；

（3）

并举出使 时使 的实例.

 解：(1)   

                 

                 

                 

(2)  

              

              

              

(3)     由定义，  于是，

。

    下证对任意 ，有 。

任取 ，不妨设 。于是，存在  使得 从而， 。举例说明“ ”成立。设 ，于是， 。

9．设 和 是集合 上的二元关系，试证明：

（1） ；

（2） ；

（3）

并请给出 时使 和 的实例.

解：设 是集合 上的二元关系。注意到 ，于是，

(1)    

               =

               =

               =

               =

(2)     , ,

。任取 ，

(i)      若  则  且  从而，

               ；

(ii)    若  则  即  从而，

 且  于是，

              

故 。举例说明“ ”成立。

设 ，于是， ，而

，

因此， 。

（3）证明：因为

 

 

 

 

 

 

 

 

 

 

 

又设 A= {1, 2, 3} , ，于是，  而，

 

故  .

10．有人说，“如果集合 上的二元关系 是对称和传递的，则 必是自反的. 因此，等价关系定义中的自反性可以去掉”. 并给出如下证明，如果 ，由 的对称性有 ，再由 的传递性知， 且 ，即 是自反的. 你的看法如何?

解：说法不正确。 对任意 , 对称性并不要求一定有 ，

   因此也就不一定有<y, x>。于是 <x , x> R。

11．设 是集合 上的自反关系. 试证明 是等价关系当且仅当若 ，则 .

解：设R是等价关系。若 <x, y>, <x, z> R , 则由R的对称性知, <y, x> R。

再由R的传递性有<y, z> R。

反之, 假设只要<x, y>, <x, z> R, 就有<y, z> R。

(1) 对称性。 设< x, y > R，由自反性有<x, x> R。于是<y, x> R。

(2) 传递性。 设<x, y>, <y, z> R。 由对称性有<y, x> R, 再由假设有<x, z> R。

12．设 和 都是集合 上的等价关系，试证明 当且仅当 .

证明：设 , 则显然 。

反之, 设 。若 , 则不妨设<x , y>   但<x , y>  .

于是  ,     .

由划分之定义得知 , 矛盾.。故 。

13．设 是定义在整数集Z上的模5同余关系，求Z/R.

解：设 R= { <y , x>| x≡y(mod 5)}.于是

[0] ={…-15,-10,-5,0,5,10,15…}

[1] ={…-14,-9,-4,1,6,11,16,…}

[2] ={…-13,-8,-3,2,7,12,17,…}

[3] ={…-12,-7,-2,3,8,13,18,…}

[4] ={…-11,-6,-1,4,9,14,19,…}

A/R = {[0] ,[1] ,[2] ,[3] ,[4] } .

14．设 和 是集合 的两个划分，令

 

试证明 也是 的一个划分.

 证明:  .

(1)   由S 定义知, ;

(2)   任取 和 , 1<=i ,j<=r, 1<=j,m<=s .

 

     (3)

         

     故 S 是 的一个划分.

15．定义在4个元素的集合 之上的等价关系共有多少个？若 呢？

解：设A={1,2,3,4},则A上的等价关系数目即A上的划分的数目共有15个.

(1)    最大划分 { {1}, {2}, {3} ,{4} }

(2)    最小划分 {{1 ,2, 3 ,4}}

(3)    将A分成两个集合S={ , } , 共有两种可能：

(i)   | | = | | ，共有 种, 即

{{1, 2} , {3, 4}},  {{1, 3}, {2, 4}},  {{1, 4}, {2, 3}}。

(ii)   | | = 1, | | =3, 共 种, 即

{{1}, {2,3,4}}, {{2}, {1,3,4}}, {{3}, {1,2,4}, {{4},{1,2,3}}

(4)    将A分成三个集合, 则恰有一个集合为2个元素,故共有 种分法，即

{{1, 2}, {3}, {4}}, {{1, 3}, {2} ,{4}}, {{1, 4}, {2} ,{3}},

       {{2, 3}, {1}, {4}}, {{2,4, {1}, {3}}, {{3,4}, {1}, {2}}}

设  表示可k元集合A上的全部等价关系数目, 则

 

16．设 ，偏序关系 为整除. 试分别画出 ，以及 的Hasse图.

                12

解：       15                                               54 

                            6                       

      3           5    2            3                      27

                                                           9

                            1                             3

 <A1, >          <A2, >                     <A3, >

 

 

x1

x2

x3

x4

x5

图2.3

17．设 的Hasse图如图2. 3所示：

 

（1）求 的最大（小）元，极大（小）元；

（2）分别求 和 的上（下）界，上（下）确界.

 解：(1) 最大元x1, 无最小元;

(2)             上界        下界       上确界         下确界

{x2, x3, x4}       x1         x4          x1             x4

{x3, x4, x5}     x1,x3        无           x3             无

{x1, x2, x3}       x1        x4           x1             x4

18．请分别举出满足下列条件的偏序集 的实例：

（1） 为全序集，但 的某些非空子集无最小元；

（2） 不是全序集， 的某些非空子集无最大元；

（3） 的某些非空子集有下确界，但该子集无最小元；

（4） 的某些非空子集有上界，但该子集无上确界

解：(1) <Z , > 为全序集, Z 整数集,但< , >无最小元 ,

        其中 ={ ;

(2)题16中的<A1, >,子集{3 ,5}无最大元;

(3)   题16中的<A2, >,子集{2,3,6}有下确界但无最小界;

(4)   子集{a,b,e}有上界d, e,但无上确界。

19．试证明：每一个有限的全序集必是良序集.

证明：设<A, >为全序集, 且|A| = n。

任取 ,因B中的任意两个元素x, y均有x<=y或者y<=x。

因此, B中必有最小元a.故<A, >为良序集。

20．设 为偏序集. 试证明 的每个非空有限子集至少有一个极小元和极大元.

证明：设B是A的非空有限集.若B中部存在极大(小)元,则对任何 ,

若存在 y ,使得x y(y x),如此下去,得出B为无限集.矛盾.故结论成立。

21．设 为全序集. 试证明 的每个非空有限子集必存在最大元、最小元.

证明：设B是A上的一个非空有限集,由题知,B中至少有一个极大(小)元。

又故<A, >为全序,故极大(小)元均唯一, 且就是最大(小)元。