六、集合的划分与覆盖

1、一. 划分与覆盖的定义定义: 若把一个集合A分成若干个叫做分块的非空子集， 使得A中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做A的一个覆盖。如果A中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做A的一个划分。等价定义：令A为给定非空集合，S=S1,S2,Sm，其中Si A ，Si，(i=1.m) 且 ，则集合S称作集合A的覆盖。如果除以上条件外，另有 Si Sj = (ij) ，则称S是A的划分。i=1mSi= A3-9 集合的划分与覆盖划分S的块：划分的元素 Si 。如果划分是有限集合，划分的秩：不同块的个数。（划分的秩就是划分的大小）如果划分是无限的，则它的

2、秩是无限的。例 A=a,b,c，考虑下列集合： S=a,b,b,c Q=a,a,b,a,c P=a,b,c G=a,b,c E=a,b,c F=a,a,c 划分的说明则 S、Q、P、G、E是A的覆盖；P、G、E是A的划分；（它们的秩分别为2，1，3）F既不是划分也不是覆盖。若是划分则必是覆盖，其逆不成立。集合的最小划分：就是由这个集合的全部元素组成的一个分块的 集合。（即秩为1的划分）集合的最大划分：就是由每个元素构成一个单元素分块的集合。 （若有n个元素，就是秩为n的划分）在上例中， G=a,b,c是A的最小划分， E=a,b,c是A的最大划分。注意：给定一个集合，其划分并不是唯一的。二.

3、交叉划分定义： 若A1,A2,Ar与B1,B2,Bs是同一集合A的两种划 分，则其中所有Ai Bj 组成的集合，称为是原来 两种划分的交叉划分。例如： 所有生物的集合X，可以分割成植物，动物，也可以分割成史前生物，史后生物，则它们的交叉划分为史前植物，史后植物，史前动物，史后动物。定理 设A1,A2,Ar与B1,B2,Bs是同一集合X的两种划分， 则 其交叉划分亦是原集合的一种划分。证明： 若题设的交叉划分是： A1 B1，A1 B2，A1 Bs， A2 B1，A2 B2，A2 Bs， Ar B1，Ar B2，Ar Bs (1)在其中任取两个元素Ai Bh，Aj Bk，考察(AiBh )(Aj

4、Bk), i. 若ij且h=k，因为AiAj= ,故(Ai Bh )(Aj Bk) (AiAj)(Bh Bk) = (Bh Bk ) = ii. 若ij且hk ，iii. 若i=j且hk，因为AiAj= , BhBk= ,故(Ai Bh )(Aj Bk) (AiAj)(Bh Bk) = = 情况与 i 相同。综上所述，在交叉划分中任取两元素，其交为(Ai Bh )(Aj Bk)=(A1 B1)(A1 B2)(A1 Bs)(A2 B1)(A2 B2)(A2 Bs)(Ar B1)(Ar B2) (Ar Bs)=(A1 (B1B2Bs)(A2 (B1B2Bs) (Ar (B1B2Bs)=(A1A2Ar) (B1B2Bs)=X X=X故，交叉划分也是原集合的一种划分。 (2)所有元素的并为定义： 给定X的任意两个划分A1, A2, Ar 和 B1, B2, Bs ，若对于每一个Aj均有Bk ，使得 Aj Bk，则A1, A2, Ar 称为 B1, B2, Bs 的加细。定理： 任何两种划分的交叉划分都是原来划分的一种加细。证明 设A1, A2, Ar 和 B1, B2, Bs