定理定理10.5.10 A为非空有限集合,RA上的关系,则存在正整数,使得
   
证明证明 设有,则存在整数,使得,即存在序列 ,有 。设满足上述条件的最小的p,有,则个元素都是A中的n个元素, 个元素中必有两个相等,即有使,因此序列可以去掉中间一段成为和两段。第一段有t各有序对,第二段有个有序对。因此,,其中 。这与p为最小的假设矛盾。故不成立。
  由此定理可知,这时的不妨写成
   
例题例5 集合 上的关系R
   
  则 
   
  而
   
   
   
   
   
  由  
  则
   
   
  当有限集合A的元素较多时,用矩阵运算求A是的关系R的传递闭包仍很复杂。1962年Warshall提出了一种有效的算法。
Warshall算法:(令表示矩阵Bj行第i列的元素)
  (1) 令矩阵
  (2) 令
  (3) 对,如果=1,则对 ,令
   
  (4) i加1,
  (5) 若 ,则转到(3),否则停止,且
   
例题例6 A上的关系R的关系矩阵为

   
  令
  时,第1列只有,将第1行与第1行各对应元素作逻辑加,仍记于第1行。

     
  时,第2列中,将第1行与第2行各对应元素作逻辑加,记于第1行。
     
  第2列还有 ,将第4行与第2行对应加,记于第4行。
  时,第3列全是0,B不变。
  时,第4列中,将第1,2,4这3行分别与第4行对应元素逻辑加,分别记于1,2,4这3行。
     

  这就是
  有时希望所求的闭包具有两种或三种性质。应该先作哪种闭包运算呢?下面分析这个问题。
定理定理10.5.11 对非空集合A上的关系R,有
  (1) 若R是自反的,则是自反的,
  (2) 若R是对称的,则是对称的,
  (3) 若R是传递的,则是传递的。
证明证明 只证(2),其他留作思考题。
  (2)先证是对称的。对任意的,如果,则
   
  如果,则
   
   (因
   R是对称的)
  
  总之,是对称的。
  再证是对称的。为此先证,若R对称,则对非零自然数n,有是对称的。施归纳于n
  当时,是对称的。
  假设是对称的。令,对任意的,可得
  
  
  
  
  则是对称的。对非零自然数n,有是对称的。
  对任意的,可得
  
  
  所以,是对称的。
定理定理10.5.12讨论了关系性质和闭包运算之间的联系。
  如果关系R是自反的或对称的,那么经过求闭包的运算以后所得到关系仍旧是自反的或对称的。但是对于传递的关系则不然。它的自反闭包仍旧保持传递性,而对称闭包就有可能失去传递性。例如:A=|1,2,3|,R={<1,3>}是A上的传递关系,R的对称闭包
    
  显然不再是A上的传递关系。从这里可以看出,如果计算关系R的自反,对称,传递的闭包,为了不失去传递性,传递闭包运算应该放在对称闭包运算的后边,若令
定理定理10.5.13 对非空集合A上的关系R,有
  (1)
  (2)
  (3)
  其中,其它类似。
证明证明
  (1)
    
    
    
  (2)先证 。施归纳于n
   当时,
  假设时有 。令 ,则有
  
  
  
  
  
  利用这个结论
   
   
   
   
   
  (3)因为,所以。因为是对称的,所以。因此
  由定理可知,若要求出R的自反、对称且传递的闭包,则应先求,再求,最后求 。若先求,再求,则不一定是传递的。