定理10.5.10 A为非空有限集合，R是A上的关系，则存在正整数，使得 　　　。 证明 设有，则存在整数，使得，即存在序列 ，有 。设满足上述条件的最小的p，有，则个元素都是A中的n个元素， 个元素中必有两个相等，即有使，因此序列可以去掉中间一段成为和两段。第一段有t各有序对，第二段有个有序对。因此，，其中 。这与p为最小的假设矛盾。故不成立。 　　由此定理可知，这时的不妨写成 　　　。 例5 集合 上的关系R为 　　　。 　　则　 　　　 　　而 　　　 　　　 　　　 　 　 　　　 　　由　　 　　则 　　　 　　　 　　当有限集合A的元素较多时，用矩阵运算求A是的关系R的传递闭包仍很复杂。1962年Warshall提出了一种有效的算法。 Warshall算法：（令表示矩阵B第j行第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的自反、对称且传递的闭包，则应先求，再求，最后求 。若先求，再求，则不一定是传递的。