集合是数学中最基本的概念

1、第二章 集合集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的一个分支。G. Cantor(康脱)是作为数学分支的集合论的奠基人。1870年前后，他关于无穷序列的研究导致集合论的系统发展。1874年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。1878年，他引进了两个集合具有相等的“势”的概念。然而，朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901年罗素发现了有名的罗素悖论。1932年康脱也发表了关于最大基数的悖论。集合论的现代公理化开始于1908年策梅罗

2、所发表的一组公理，经过弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。另外一种系统是冯·诺伊曼-伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理一起称为ZFC系统。本部分主要介绍朴素集合论的主要内容，其中包括集合代数（第二章）、二元关系（第三章）、函数（第四章）、无限集合（集合的基数）（第五章）等。2.1 集合论的基本概念2.1.1 集合的概念集合不能精确定义。集合

3、可以描述为：一个集合把世间万物分成两类,一些对象属于该集合，是组成这个集合的成员，另一些对象不属于该集合。可以说，由于一个集合的存在，世上的对象可分成两类，任一对象或属于该集合或不属于该集合，二者必居其一也只居其一。直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。例如：方程x210的实数解集合；26个英文字母的集合；坐标平面上所有点的集合；集合通常用大写的英文字母A,B,C,来标记，元素通常用小写字母a,b,c,来表示。例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。集合的表示方法：表示一个集合的方法

4、通常有三种：列举法、描述法和归纳定义法。(1) 列举法 列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。在能清楚地表示集合成员的情况下可使用省略号。例如 A=a，b，c，z，Z=0，±1，±2，都是合法的表示。(2) 描述法 用谓词来概括集合中元素的属性来表示这个集合。例如 Bx|xRx210表示方程x210的实数解集。许多集合可以用两种方法来表示，如B也可以写成-1，1。但是有些集合不可以用列元素法表示，如实数集合。(3) 归纳定义法：2.3节再讨论。属于、不属于：元素和集合之间的关系是隶属关系，即属于或不属于，属于记作，不属于记作。例如Aa，b，c，d，

5、d，这里aA，b，cA，dA，dA，但bA，dA。b和d是A的元素的元素。外延公理：两个集合A和B相等，当且仅当它们有相同的成员。集合的元素是彼此不同的：如果同一个元素在集合中多次出现应该认为是一个元素。如 1，1，2，2，31，2，3。集合的元素是无序的：如1，2，33，1，2。2.1.2 罗素悖论1901年罗素提出以下悖论：设论述域是所有集合的集合，并定义集合。这样，S是不以自身为元素的全体集合的集合，那么“S”是不是它自己的元素呢？假设S不是自己的元素，那么S满足谓词，而该谓词定义了集合S，所以。另一方面，如果，那么S必须满足定义S的谓词，所以。这样导致了一个类似于谎言悖论的矛盾：既非，

6、也非。罗素悖论起因于集合可以是自己的元素的概念。康脱以后创立的许多公理化集合论都直接或间接地限制集合成为它自己的元素，因而避免了罗素悖论。2.1.3 集合间的包含关系 设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作BA。称B是A的扩集。包含的符号化表示为：BAx(xBxA)。如果B不被A包含，则记作BA。例如 NZQRC，但ZN。显然对任何集合A都有AA。注意：属于关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如Aa，a和a，既有aA，又有aA。前者把它们看成是不同层次上的两个集合，后者把它们看

7、成是同一层次上的两个集合，都是正确的。 设A，B为集合，如果BA且BA，则称B是A的真子集，记作BA。如果B不是A的真子集，则记作BA。真子集的符号化表示为：BABABA。例如 NZQRC，但NN。为方便起见，所讨论的全部集合和元素是限于某一论述域中，即使这个论述域有时没有明确地指出，但表示集合元素的变元只能在该域中取值。此论述域常用U表示，并称为全集。 不含任何元素的集合叫空集，记作。空集可以符号化表示为x|xx。例如x|xRx2+1=0是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。定理2.1-1 空集是一切集合的子集。证：对任何集合A，由子集定义有，右边的蕴涵式因前件为假而

8、为真命题，所以也为真。推论 空集是唯一的。证：假设存在空集和，由定理6.1有，。根据集合相等的定义，有。含有n个元素的集合简称n元集，它的含有m(mn)个元素的子集叫做它的m元子集。任给一个n元集，怎样求出它的全部子集呢？举例说明如下。例 A1,2,3，将A的子集分类：0元子集，也就是空集，只有一个：；1元子集，即单元集：1，2，3；2元子集：1,2，1,3，2,3； 3元子集：1,2,3。一般地说，对于n元集A，它的0元子集有个，1元子集有个，m元子集有个，n元子集有个。子集总数为个。全集与空集在本章中起重要作用，注意掌握它们的基本概念。注意：与的联系与区别。(1) 表示集合的元素（可以为集

9、合）与集合本身的从属关系，(2) 表示两个集合之间的包含关系。例如：对于集合A=a,b,c,a是A的子集：aA，a是A的元素：aA。注意：不要写成aA和aA。，但；是一元集，而不是空集。，。本节要求：熟练掌握集合、集合的子集、包含、相等、空集、全集、幂集等概念及其符号化表示。2.2 集合上的运算2.2.1 集合的交、并和差运算1. 集合交、并、差运算的定义（注意集合运算与逻辑运算的对应关系） 设和是集合，(1) 和的交记为，定义为：；(2) 和的并记为，定义为：；(3) 和的差记为，定义为：。例：设，则，定义：如果是两个集合，那么称和是不相交的。如果是一个集合的族，且中的任意两个不同元素都不相

10、交，那么称是（两两）不相交集合的族。2. 集合的并和交运算的推广（广义交、广义并）个集合 ，无穷可数个集合： ，一般情形： （），3. 集合交、并、差运算的性质：(1) 交换律 ， ，(2) 结合律 ， .(3) 分配律 ， (4) 幂等律 , ,(5) 同一律 , ，(6) 零 律 ,(7) 吸收律 ， ，(8) 德摩根律 (9) (a) , (b) , (c), (d),(e) 若，,则，,(f) 若，则, (g) 若，则，(h) 。证：利用运算的定义（与逻辑运算的关系）或已证明的性质。2.2.2 集合的补运算1. 集合的补运算的定义定义：设是论述域而是的子集，则的（绝对）补为：当且仅当和

11、。2. 集合补运算的性质：(1) 矛盾律 ； (2) 排中律 ；(3) 德摩根律 ， ， ， ；(4) 双重否定律（的补的补是）：；(5) 若，则。例：证明A(BC)(AB)( AC)。证对任意的x，xA(BC) xAxBC xA(xBxC) xA(xBxC) xAxBxC (xAxB)(xAxC) xAB)xAC x(AB)(AC)所以 A(BC)(AB)( AC)。例：证明AEA。证对任意的x，xAExAxExA(因为xE是恒真命题)，所以AEA。注意：以上证明的基本思想是：设P，Q为集合公式，欲证PQ，即证PQQP为真。也就是要证对于任意的x有 xPxQ和xQxP成立。对于某些恒等式可以

12、将这两个方向的推理合到一起，就是 xPxQ。不难看出，集合运算的规律和命题演算的某些规律是一致的，所以命题演算的方法是证明集合恒等式的基本方法。证明集合恒等式的另一种方法是利用已知的恒等式来代入。例：证明A(AB)A。证 A(AB)(AE)(AB)A(EB)A(BE)AEA。例：证明等式ABAB。证对于任意的x，xABxAxBxAxBxAB，所以ABAB。注意：上式把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。例：证明(AB)BAB证 (AB)B(AB)B(AB)(BB)(AB)EAB。例：证明命题ABBABAAB。证(1) 证ABBAB，对于任意的x，xAxAxBxABx

13、B(因为ABB)，所以AB。(2) 证ABABA。显然有ABA，下面证AAB，对于任意的x，xAxAxAxAxB(因为AB) xAB，由集合相等的定义有ABA。(3) 证ABAAB。ABAB(AB)B(因为ABA)A(BB)A。(4) 证ABABB。ABB(AB)BB。注意：上式给出了AB的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。例：化简(ABC)(AB)(A(BC)A)。解因为ABABC，AA(BC)，故有(ABC)(AB)(A(BC)A)(AB)ABA。2.2.3 环和与环积定义：两集合的环和（对称差）和环积定义为：环和： 环积：2

14、. 环和与环积的性质：(1) ，(2) ， ， (3) ， ；(4) ， ，(5) ，(6) , , ，(7) ， .例：已知ABAC，证明BC。证 已知ABAC，所以有A(AB)A(AC) (AA)B(AA)CBCBCBC。3. 集合运算的文氏图表示（教材P62图2.2-1）注意：如果没有特殊说明，任何两个集合都画成相交的。2.2.4 幂集合定义：设是一个集合，的幂集是的所有子集的集合，即。若是元集，则有个元素。例：若，则；若，则。对任意集合：，。集合运算的顺序：为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：称广义交，广义并，幂集，绝对补运算为一类运算，交，并，补，环和，环

15、积运算为二类运算。一类运算优先于二类运算；一类运算之间由右向左顺序进行；二类运算之间由括号决定先后顺序。2.2.5 有限集的计数定理2.2-1 设都是有限集合，则以下公式成立：(a) , (b) ,(c) ，(d) , (e) , (f) 。使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来。一般地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相交的，然后将已知集合的元素数填入表示该集合的区域内。通常从个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为。根据题目中的条件，列

16、出一次方程或方程组，就可以求得所需要的结果。例：对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。解：设，同时会英、法和德语的人为个，只会英、法和德语的人分别为个，根据题意画出文氏图如图2.1所示。由已知条件列出方程组如下：解得，。 图2.1 图2.2例：求1到1000之间(包含1和1000在内)既不能被5和6，也不能被8整除的数有多少个。 解 设，用表示小于等于的最

17、大整数，表示的最小公倍数，则， ， ， ， 。将这些数字依次填入文氏图，得到图2.2，由图可知，不能被5，6和8整除的数有1000(200+1003367)600 个。本节要求：(1) 熟练掌握集合的交、并、差、补、广义交、广义并、环和、环积等运算的定义及性质；(2) 掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法；(3) 牢记基本的集合恒等式，并能准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式。2.3 归纳法2.3.1 集合的归纳定义一个集合的归纳定义由部分组成：（1） 基础条款（简称基础）：它指出某些事物属于集合，它的功能是给集合以基本元素，使所定义的集合

18、非空。（2） 归纳条款（简称归纳）：它指出由集合的已有元素构造新元素的方法。归纳条款的形式总是断言：如果事物是集合的元素，那么用某种方法组合它们而成的一种新事物也在集合中。它的功能是指出为了构造集合的新元素，能够在事物上进行的运算。（3） 极小性条款（简称极小性）：它断言一个事物除非能有限次应用基础和归纳条款构成外，那么这个事物不是集合的成员。例：教材P70-72例1例6。2.3.2 自然数自然数可以应用后继集合的概念归纳地定义。定义：设是任意集合，的后继集合记为，定义为。例：的后继集合是。的后继集合是；的后继集合是。定义：自然数是如下集合：(1) （基础）；(2) （归纳）如果，那么；(3)

19、 （极小性）如果，且满足条款(1)和(2)，那么。皮亚诺(Peano)公设： 自然数可以按如下定义：(1) ；(2) 如果，那么恰存在一个的后继者；(3) 不是任何自然数的后继者；(4) 如果，那么；(5) 如果，使(i)，(ii)若，则；那么。2.3.3 归纳证明对于形式的命题，如果其论述域是归纳定义的集合，则归纳法往往是有效的证明方法。归纳法证明通常由基础步骤和归纳步骤两部分组成，它们分别对应于的定义的基础和归纳条款。（1） 基础步骤：这一步证明的定义中的基础条款指定的每一元素，是真；（2） 归纳步骤：证明如果事物有性质，那么用归纳条款指定的方法，组合它们所得的新元素也具有性质。归纳定义的

20、极小性条款保证的所有元素仅仅应用基础条款和归纳条款才能构成，因此证明了以上两步，就足以推出。自然数具有以下归纳特征：（1）（基础）；（2）（归纳）如果，那么；（3）（极小性）如果，且满足：(i)，(ii) 对，若，则；那么。数学归纳法第一原理：利用数学归纳法第一原理的归纳证明过程：（1） （基础）先证明是真，可用任意证明技术；（2） （归纳）证明是真。数学归纳法第一原理作为推理规则的形式如下：例：教材P75-76例8-例10。数学归纳法第二原理：作为推理规则的形式如下：证明过程：（1）（基础）证明是真，（时，对一切永假，所以永真，所以证明是真等价于证明是真）（2）（归纳）证明当对一切，为真时，

21、为真。例：教材P77例11。本节要求：(1) 掌握集合和自然数的归纳定义方法；(2) 掌握并熟练运用数学归纳法第一原理和第二原理。2.5 集合的笛卡尔乘积 由两个元素x和y（允许x=y）组成的序列记作<x,y>，称为二重组或有序对或序偶，其中x是它的第一元素（分量），y是它的第二元素（分量）。有序对<x,y>具有以下性质：1当xy时，<x,y><y,x>； 2<x,y>=<u,v>的充分必要条件是x=u且y=v。注意：这些性质是二元集x,y所不具备的。例如当xy时有x,y=y,x。原因在于有序对中的元素是有序的，而集合中的

22、元素是无序的。 已知<x+2,4>=<5,2x+y>，求x和y。解 由有序对相等的充要条件有x+2=5，2x+y=4，解得x=3，y=-2。 设是个元素，定义为重组。注意：重组是一个二重组，其中第一个分量是重组。如代表而不代表，按定义后者不是三重组，并且。重组与相等当且仅当，。 设A，B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积（叉积），记作A×B。笛卡儿积的符号化表示为A×B=<x,y>|xAyB。集合（）的叉积记为或，定义为设A=a,b, B=0,1,2，则A×

23、B=<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>；B×A=<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>。由排列组合的知识不难证明，如果|A|=m，|B|=n，则|A×B|=mn。笛卡儿积的运算性质(1).对任意集合A，根据定义有 A×=, ×A=；(2).一般地说，笛卡儿积运算不满足交换律，即A×BB×A(当ABAB时)；(3)笛卡儿积运算不

24、满足结合律，即(A×B)×CA×(B×C)(当ABC时)；(4).笛卡儿积运算对并和交运算满足分配律，即A×(BC)=(A×B)(A×C)； (BC)×A=(B×A)(C×A)；A×(BC)=(A×B)(A×C)； (BC)×A=(B×A)(C×A)。我们证明其中第一个等式。证 任取<x,y>，<x,y>A×(BC) xAyBCxA(yByC)(xAyB)(xAyC)<x,y>A×B<x,y>A×C<x,y>(A×BA×C)所以有 A×(BC