集合是现代数学中最为基本的

第1章集合论集合是现代数学中最为基本的，也是应用最广泛的一个概念。粗略的说，在一定场合下所考察研究的事物全体都可称为一个集合。例如，全体男人、全体女人、全体青少年、某工厂全体中层干部、某公园星期天的全体游客等等，可分别构成各种人的集合；而全体实数、全体有理数、全体自然数以及10以内的全体自然数等等，可构成各种数的集合；有时，甚至连两头牛、三只羊和一匹骆驼也可构成一个集合。集合在数学领域有着重要的作用，特别在计算机科学所涉及到的数学理论中，集合论是十分有用的基本工具。§1.1集合的概念与表示1.1.1集合的概念集合是一个不能精确定义的基本概念。在集合论中研究的集合通常是由具有某种特定性质的、可以互相区别的、具体的或抽象的若干事物组成的。组成集合的每一个具体的或抽象的事物，被称为该集合的一个元素。如某学院的全体学生是一个集合，而每一个学生就是其中一个元素。通常用大写的带下标或不带下标的英文字母表示集合的名称；用小写的带下标或不带下标的英文字母表示组成集合的事物，即元素。并且约定N﹑I﹑Q和R分别表示自然数集、整数集、有理数集和实数集等等。按照传统的概念，若给定一个集合A，则某一事物a，或者是它的一个元素，或者不是它的元素，二者必居其中之一，决不允许模棱两可。若元素a属于集合A，记作a∈A，若元素a不属于A，记作aA。1.1.2集合的表示一般可用三种方法表示集合。列举法：列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来。设A是以a,b,c,d为元素的集合，B是正偶数集合，则A＝{a,b,c,d},B={2,4,6,…}。描述法：通过指出集合中元素所具有的性质来表示集合。如果集合A中的元素具有性质p，不是集合中的元素都不具有性质p，也就是说A是所有具有性质p的元素组成的集合，这时，将A表示为{x|p(x)}.例如，A={x|x是整数}，B={x|x为年龄大于十八岁的中国公民}。集合的第三种表示法特征函数表示法在下面小节介绍。对于集合的表示法应该注意以下几点：(1)集合中的元素是各不相同的。(2)集合中的元素不规定顺序。(3)集合的两种表示法有时是可以互相转化的。例如列举法中的B可用描述法表示为B={x|x0且x为偶数}或B={x|x=2(k+1),k为非负整数}。而描述法中的A可用列举法表示为A={…,-2,-1,0,1,2,…}。1.1.3集合的相等与包含定义1.1设A,B为二集合，若B中的每个元素都是A中的元素，则称B是A的子集，也称A包含B或B包含于A，记作AB或BA。若B是A的子集且A中至少有一个元素不属于B，则称B是A的真子集，记作BA.设A={a,b,c},B={a,b,c,d},C={a,b},则CAB且有CAB.又如，每个自然数都是整数，而有些整数不是自然数，所以，N是I的子集，而且N是I的真子集，亦即NI.定理1.1集合之间的包含关系具有下列性质：(ⅰ)AA（自反性）(ⅱ)若AB﹑BA，则A=B（反对称性）；(ⅲ)若AB﹑BC则AC（传递性）.这里，A，B，C是任意的集合。定义1.2设A，B为二集合，若A包含B且B包含A，则称A与B相等，记作A=B.例如，设A是小于10的素数集合，即A={2,3,5,7}，又如{1,2,4}={1,4,2}，{1,3,5,7,…}={x|x是正奇数}。定义1.3不拥有任何元素的集合称为空集合，简称为空集，记作.空集是客观存在的。例如设A={x|x2+1=0且x∈R}，则A=，即A是空集。定义1.4如果在一个具体问题中，限定所讨论的集合都是某一集合的子集，则称该集合为全集或论域，常记为E或Ｘ。全集是一个相对性概念，由于所研究的问题不同，所取的全集也不同。例如在研究平面解析几何时，总是把整个坐标平面作为全集；而在研究整数的问题时，可以把整数集I作为全集。我们规定，空集是任何集合的子集，而集合A是全集E的子集，即AE.和A称为A的两个平凡子集。定义了论域Ｘ，可以介绍集合的第三种表示法。先介绍特征函数的概念。设给定论域X的一个子集AX，对X中的任一元素x，它与A的关系只有两种情况，即x∈A或xA。从而确定了一个从x到{0,1}的映射，即称映射为集合A的特征函数。AxAxAAxx,1,0)(|:集合A的特征函数在x处的函数值刻画了元素x对A隶属程度。当隶属程度为1时，表示x属于A；当隶属程度为0时，表示x不属于A。因此，与集合{0,1}相对应。如果把一个命题的真伪只取两个值{0,1}，０代表伪，１代表真，这就是所谓的“二值逻辑”了。§1.2集合的运算1.2.1集合的并﹑交﹑补﹑差运算定义2.1由两个集合A和B的所有元素组成的集合称为A,B的并集，记为A∪B.即A∪B＝{x|x∈A或x∈B}.如：{1,2}∪{5,6}={1,2,5,6}{1,2}∪{2,3}={1,2,3}集合之间的相互关系和有关运算在几何上可用文氏图进行形象的描述。即可用正方形或长方形表示全集E，而集合可用正方形或长方形中的圆来表示，通常在图中用有阴影的区域表示新组成的集合（如下图）。定义2.2由两个集合A和B的公共元素组成的集合称为A,B的交集，记为A∩B.即A∩B＝{x|x∈A且x∈B}.如：{1,2}∩{2,3}={2}{1,2}∩{5,6}=通常，当A∩B＝时，称A和B不相交。定义2.3属于A但不属于B的元素组成的集合称为A关于B的差集，记为A-B。特别，称E-A为A的补集，记为Ā.即A-B＝{x|x∈A且xB}，Ā={x|xA}.如：{1,2}-{2,3}={1}{1,2}-{5,6}={1,2}{1,2}-{1,2,3}=.若E为N，A＝{1,2},则Ā=N-{1,2}={3,4,5,…}.定理2.1设Ａ、Ｂ、Ｃ为三个集合，若AB，则(A∪C)(B∪C)，(A∩C)(B∩C).定理2.2集合的并交运算有如下性质：(1)A∪A=A（并的幂等律）A∩A=A（交的幂等律）(2)A∪B=B∪A（并的交换律）A∩B=B∩A（交的交换律）(3)A∪(B∪C)=(A∪B)∪C（并的结合律）A∩(B∩C)=(A∩B)∩C（交的结合律）(4)A∪(A∩B)=A（并的吸收律）A∩(A∪B)=A（交的吸收律）(5)A∪(B∩C)=(A∪B)∩(A∪C)（并关于交的分配律）A∩(B∪C)=(A∩B)∪(A∩C)（交关于并的分配律）证明：(1)幂等律与(2)交换律可以从定义直接推出。下面仅证明求并运算的另外三种性质。首先证明(3)中并的结合律。如果x∈A∪(B∪C),那么x∈A或x∈B∪C,而x∈B∪C表示x∈B或x∈C。所以，若x∈A∪(B∪C),则x∈A或x∈B或x∈C。亦即x∈A∪B或x∈C，从而x∈(A∪B)∪C,于是证得A∪(B∪C)(A∪B)∪C同理可证A∪(B∪C)(A∪B)∪C所以，由集合间包含关系的反对称性证得A∪(B∪C)=(A∪B)∪C现在证明(4)中并的吸收律。若x∈A∪(A∩B),则x∈A或x∈A∩B,从而x∈A，所以A∪(A∩B)A，由并集的定义AA∪(A∩B)所以A∪(A∩B)=A.最后证明(5)中并关于交的分配律：若x∈A∪(B∩C)，则x∈A或x∈B∩C.当x∈A时，x∈A∪B且x∈A∪C，从而x∈(A∪B)∩(A∪C).当x∈B∩C时，x∈B且x∈C，于是x∈A∪B且x∈A∪C，从而x∈(A∪B)∩(A∪C).综上所述，当x∈A∪(B∩C)时，有x∈(A∪B)∩(A∪C)，亦即A∪(B∩C)(A∪B)∩(A∪C)反之，若x∈(A∪B)∩(A∪C)，则x∈A∪B且x∈A∪C，这样，当xA时，x∈B且x∈C，所以x∈A∪(B∩C)，于是，(A∪B)∩(A∪C)A∪(B∩C)从而证得A∪(B∩C)=(A∪B)∩(A∪C)定理2.3集合运算还有如下性质：(1)零律A∪E=E;A∩=(2)同一律A∪=A;A∩E=A(3)排中律A∪Ā=E(4)矛盾律A∩Ā=(5)交补转换律B-A=B∩Ā(6)德摩根律绝对形式相对形式A-(B∪C)=(A-B)∩(A-C)A-(B∩C)=(A-B)∪(A-C)BABABABA下面仅对(6)中的德摩根律的相对形式进行证明。证明：类似可证A-(B∩C)=(A-B)∪(A-C).)()()()()()()()()(CABACABACBAACBACBACBA集合的特征函数具有以下运算性质：(1)，即A∪B的特征函数等于两集合A，B的特征函数的最大值。(2)，即A∩B的特征函数等于两集合A，B的特征函数的最小值。(3)设是的补集，则即集合A与它的补集的特征函数值之和等于1。此外，还可以根据特征函数的概念来描述集合间的下列关系：(1)A=的充要条件是≡0；(2)集合A等于论域X的充要条件是≡1；(3)的充要条件是；(4)A＝B的充要条件是.1.2.2集合的幂集运算我们先来看一个例子，设全集E={a,b,c},它的所有可能的子集计有：S0=,S1={a},S2={b},S3={c},S4={a,b},S5={b,c},S6={c,a},S7={a,b,c}这些子集都包含在E中，即SiE(i=0,1,2,3…,7)，但是SiE.如果把Si作为元素，将可以另外组成一种集合。定义2.4给定集合A，由集合A的所有子集为元素组成的集合，称为集合Ａ的幂集，记为P(A).例如A={a,b,c}P(A)={,{a},{b},{c},{a,b},{b,c},{c,a},{a,b,c}}定理2.4如果有限集合A有n个元素，则其幂集P(A)有2n个元素。现在我们引进一种编码，用来唯一的表示有限集幂集的元素，现以上面S={a,b,c}这个集合为例。P(S)={Si|i∈J}J={i|i是二进制数且000≤i≤111}例如,S011=S3={c},S110=S6={c,a}等。一般的P(S)={S0,S1,…,},即P(S)={Si|i∈J},J={i|i是二进制数且000…0≤i≤111…1}.（0和1均为n个）。定理2.5集合的幂集运算具有如下性质：(1)AB当且仅当P(A)P(B);(2)P(A)∪P(B)P(A∪B);(3)P(A∩B)=P(A)∩P(B);(4)P(A-B)(P(A)-P(B))∪{}.1.2.3集合的笛卡尔乘积在日常生活中，有许多事物是成对出现的，而且这种成对出现的事物，具有一定的顺序。例如，上和下；左和右；34；张华高于李明；中国地处亚洲；平面上的点的坐标等。(4,2)和(2,4)表示平面上不同的两个点。也就是说，平面上点的笛卡儿坐标可视为两个实数组成的序列。同样，英语单词可视为由若干个字母组成的序列。在很多情况下，都需要把n个个体组成的序列作为一个实体来考察。定义2.5若n是自然数，则由n个个体组成的序列a1,a2,…,an称为n元组，记为(a1,a2,…,an).其中ai(1≤i≤n)称为该n元组的第i个坐标。定义2.6如果两个n元组对应的坐标均相同，那么称这两个n元组相等。也就是说，(a1,a2,…,an)=(b1,b2,…,bn)是指ai=bi(1≤i≤n).应该指出，n元组中的元素不一定是来自同一个集合，它们可以代表不同类型的事物。例如，a代表操作码，b代表地址码，则(a,b)就代表一条单地址指令；当然亦可将a代表地址码，b代表操作码，(a,b)仍代表一条单地址指令；但上述这种约定，一经确定，次序就不能予以变化了。定义2.7所有由依次从集合D1,D2…,Dn中各取出一个元素构成的n元组组成的集合称为D1,D2…,Dn的笛卡儿乘积，记为D1D2…Dn.亦即，D1D2…Dn＝{(d1,d2,…dn)|di∈Di，当1≤i≤n时}.特别，DD…D（n个D）记为Dn。