第一章预备知识 M={x|x≤4,正整数 一个集合M的基数(当M为有限时即它的元素的数目)用 M|表示.对于上面定义的M,自然,|M|=4. 令A,B是二个集合.如果(a)(a∈A→a∈B),则称A 为B的子集.记为A≌B.进而,定义三个主要的运算:并、 交和差分别如下所示 AUB={ax|(x∈A)(x∈B)} 1.1.1) A∩B={x(x∈A)∧(x∈B)}; (112) \B={c|{x∈A)∧(xgB)} (113) 奶果BSA,则A\B=A-B用B(A)表示,并称之为B对 A的补.如果所有的集合都是g的子集,则集合A对9的补 简单地写为A.空集就是一个没有任何元素的集合,总是用 表示,对于9的子集间的上述运算服从如下的规律 S1排中律:Acg A∩A=AUA A (114 S2交换律:VA,B≤9, AUB=BUA (1.15) A∩B=B∩A
511集合 s3结合律:vA,B,Cg, A∪(B∪C)=(AUB)∪C A∩(BnC)=(4^B)∩C s4吸收律:ⅤA,B An(AUB)=AU(A∩B s5分配律:VA,B,C∈!, A∪(B∩C)=(AUB)n(AUC); (118) A∩(BUC)=(A∩B)∪(A∩C) S6通界律:VA∈9, 0∩A=6,UA=A; (1.19) g∩A=A,gUA=9 s7单补律:Acg, A∩A=四; AU A (1.110) 由这些定律出发,可以得到很多重要结果.这里仅列出一 些将会用的 定理1.11VAg且
第一章预备知识 (Xsg)((A∩X=A)V(A∪X=X) A=; (L.111) X≤g2)[(A∩X=X)v(AUX=A) A=5 定理1.12VA,Bc9, A∩B=A分A∪B=B (1.112) 定理113VA,B,Ccg, (A∩B=A∩C)A(AUB=AUC) E C 1.13) 定理1.14VA∈Ω, A= A (1L14) 定理115VA,B∈9 AuB=A∩B: (1.115) A∩B=A∪B 由上所述,可以看出D=9和5=國.进而,还可以看出 对称性(或者说对偶性}任何一个关于,∩,,的结论均可通 过交换∪和∩,和g而得出另一个结论 对于A,BC9,从A到B的-…个单射是指这样的一个映 象α:A→B使得:a,b∈A, a≠b→a(a)≠a(b
§12序 单射也称为1-1对应.一个满射则是这样的一个映象A A→B使得:∈B, 3a∈A,B(a)=b 如果一个映象既是单射又是满射,则称为双射.如果两个集合 之间有一个双射,则称它们是同构的.用A~B表示A与B 同构.同构的集合具有相同的基数.对于有限集A和B,判定 它们同构与否是微不足道的.因为这时有:VA,B9, A~B分|A|=|B 812序 对于一个集合M,MxM=(<x,3x|Vz,∈M}称为M 的笛氏积.其中,当x≠y时,〈,yx≠<y,xx 所谓一个集合M上的一个二元关余,即指M×M的一个 子集,形容词“二元”常被忽略.如果对于x,y∈M,满足关系 R,则记<x,y>∈R,或xRy.一个序,记为<,就是这样的一 个关系R使得满足如下的三个定律 O1反射律:Vm∈M,cRa, O2反对称律:vx,y∈M,xRy^yRx→x=y O3传递律:V,y,z∈M,cRy∧yRz→cRz 如果一个集合M上带有一个序圣,则称之为偏序集,记为 (M,≤). 定理121对于一个偏序集(M,)Vmx1,x2,…,xn∈M x1x2≤…<xn-x1→x1=x2 (1.21)
6 第一章预备知识 有时,称这个定理为反循环律.如果一个关系只满足O1 和O3但不满足O2,则称它为拟序,记为·<,一个集合M,若 带有一个拟序·<,则称它为拟序集,记为(M,·<) 定理122个拟序集(M,·<)的任何一个子集S本 身也是一个拟序集,其上之拟序为限制在S上的部分 如果在M上的一个拟序E还满足如下的对称律O2,则称 它为一个等价关亲,或简称为等价,记为~ O2对称律:Vx,y∈M,xy→yRx 对于M上的一个等价~.可以定义(M)={y|wy∈ M,y~r称为x在M中的等价类.由M上的所有等价类 构成的集合称为(M,~)的商集,记为M/~.在一个拟序集 M,·<)上,令~<依如下方式的确定:vx,y∈M, <3分(z·<3)∧ 则,容易看出~<是M上的一个等价.而且,(M/~<,·<) 也是一个找序集 定理123个拟序集(M,·<是一个偏序集,当且 仅当M~a=M,或者说它满足反循环律 在一个偏序集(M,≤)中,可以由反反射律 ∈M, 传递律 x<3)A(3<x)→xxz 和 x3分(xy){四=y)