定义10.5.1
对A上的关系R, ,关系R的n次幂 定义如下:
(1) ,
(2) 。
注意,n个关系R的合成简写为 ,n个集合A的笛卡儿积经常也简写为 。二者的概念不同,却使用了相同的表示。应该注意应用的场合,以免理解错误。
例1
集合 上的关系R为
。
则
的关系图如图10.5.1所示。
图
10.5.1

在例1中有一种有意义的现象,
和 。这种现象是否普遍存在呢?下面考虑这个问题。
定理10.5.1
设A是有限集合, ,R是A上的关系,则存在自然数s和
,使得 。
证明
对 都是A上的关系,它们都是
的元素。因 ,则 。列出R的各次幂,
。由鸽巢原理,至少有两个幂是相等的,即存在自然数s和 ,使
。
(注:鸽巢原理是组合学的基本原理。它指出:如果 个物体放入n个盒子里,则有一个盒子中有两个物体。)
定理10.5.2
设A是有限集合,R是A上的关系,m和n是非零自然数,则
(1)
,
(2)
。
证明
(1)对任意的m,施归纳于n。
当n=1时,
。
假设 时结论成立,即有
。令 ,则


所以,结论得证。
(2)对任意的m,施归纳于n。
当n=1时,
。
假设 时有
。令 ,则


所以,结论得证。
定理10.5.3
设A是有限集合,R是A上的关系,若存在自然数s和t,
,使得
,则
(1) ,
其中k为自然数;
(2) ,k和i为自然数,
;
(3) 令
,则R的各次幂均为B的元素,即对任意的自然数
,有 。
证明
(1)
。
(2)施归纳于k。
当 时, ,
假设 时有 ,其中 。令
,


。
所以,结论得证。
(3)若 ,由B的定义,
。
若 ,则
。一定存在自然数k和i,使得 ,其中 。于是,
。此外, 。所以,
。
例2
对例1中的关系R,
。于是对应的 。 。R的幂中不相同的只有以上4种。
|