第一章 集 合 1. 集合的概念及其表示 2. 集合之间的关系 3. 集合的运算 4. 容斥原理
本章学习目标 通过本章的学习，应达到如下目标： 深入理解掌握集合的概念和不同的表示方法； 理解集合间的关系和特殊集合，包括幂集等； 熟练掌握集合的基本运算（交、并、补、差、对称差等）；理解集合运算的规律和主要证明方法； 了解集合的图形表示法，能够借助文氏图直观表示复杂的集合；
1.1 集合论(set theory) 十九世纪数学最伟大成就之一 集合论体系 创始人康托(Cantor) 朴素(naive)集合论 公理(axiomatic)集合论（蔡梅罗(Zermelo ) ) 创始人康托(Cantor) 公理化集合论: 1908年另一个德国数学家蔡梅罗(Zermelo)建立了集合论的抽象公理系统。 Georg Ferdinand Philip Cantor 1845 ~ 1918 德国数学家, 集合论创始人。他在这一领域的贡献包括实数集合不可数性的发现。
什么是集合(set) 集合：是一种原始概念，不能精确定义。一些具有某种特点的对象的整体就构成集合，这些对象称为元素(element)或成员(member)。 用大写英文字母A,B,C,…表示集合 用小写英文字母a,b,c,…表示元素 aA：表示a是A的元素，读作“a属于A” aA：表示a不是A的元素，读作“a不属于A” 的左边是元素，右边是集合。 康托: “凡是在我们的感觉或思维中可以明确区分的对象物，把它们看成是一个整体，这个整体，我们就称它是集合”
什么是集合(set)（续） 例 ： (1) 偶素数集合{2}, 称为单元集。 (2) 二进制的基数集合{0, 1}。 (3) 英文字母(大写和小写)的集合。 (4) C#语言的基本字符构成一个字符集。 (5) 计算机主存的全部存储单元集合。 (6) 全体实数的集合。 (7) 广工全体师生的集合。
集合的性质1（外延 (extension) 公理） 1. 外延 (extension) 公理--两个集合A和B相等的充分必要条件是它们有相同的元素。 I：互异性: 一个集合的各元素是可以互相区分开的, 即每一元素在一个集合中只出现一次。 II：无序性: 集合中元素排列次序无关紧要, 即集合表示形式的不唯一性。例：{a, b} = {b, a} III. 确定性：任一元素是否属于一个集合, 回答是确定的。 两个集合A和B相等的充分必要条件是它们由相同的元素组成。
集合的性质2（正则 (regularity)公理） 3. 对任何集合S, 有{S} S；只能说 S {S}，不能说S={S}。（正则 (regularity) 公理的推论） 从而规定了集合{S}与 S的不同层次性。 说明： 1.集合与其成员是两个截然不同的概念, 集合的元素可以是任何具体或抽象事物, 包括别的集合, 但不能是本集合自身。 2.先有成员后才形成集合, 所以一个正在形成中的集合并不能作为一个实体充当本集合的成员。 {S}：以S为元素的集合：复合的集合。
1.2 数的集合表示 N：自然数(natural numbers)集合， N={0,1,2,3,…} Z：整数(integers)集合， Z={0,1,2,…}={…,-2,-1,0,1,2,…} Q：有理数(整数商Quotient : i/j, j 0) R：实数(Real numbers)集合 C：复数(complex numbers)集合 P：素数或质数 (Prime)集合 下面给出本书中几个常见集合的表示符号以方便后面的引用。
1.3 集合的表示 列举法（枚举法） 描述法（特征法）
1.列举法(roster) 列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来，例如 A={a,b,c,d,…,x,y,z} 集合中的元素不规定顺序。 C={2,1}={1,2} 集合中的元素各不相同。 C={2,1,1,2}={2,1}
用列举法表示集合并不总是可能的。 例如, 区间[0, 1]中的所有实数的集合就不能用这种方法给出。 从计算机的观点看, 列举法是一种“静态”表示法, 若把全部列举的数据都存储在计算机中, 那将占用大量的存储空间。
2.描述法(defining predicate) 也称作特征法。以某个小写英文字母表示该集合中的任意一个元素，并指出该类元素的共同特征。 例 : 正奇数集合 Odd = {m | m=2n + 1且nN}。 例 : [0, 1]上的所有连续函数所形成的集合可记成 : C[0, 1] = {f (x) | f (x)在[0, 1]上连续}。
描述法(defining predicate) 描述法也称作谓词法，性质描述法。 用谓词P(x)表示x具有性质P ，用{x|P(x)}表示具有性质 P 的集合，例如 P1 (x): x是小写英文字母 A={x|P1 (x)}={x| x是英文字母} ={a,b,c,d,…,x,y,z} P2 (x): x是十进制数字 B={x|P2(x)}= {x|x是十进制数字} ={0,1,2,3,4,5,6,7,8,9}
={x|x>0且x是偶数} //描述法 描述法（续） 两种表示法可以互相转化，例如 E={2,4,6,8,…} //列举法 ={x|x>0且x是偶数} //描述法 ={x|x=2(k+1)，k为非负整数} ={2(k+1) | k为非负整数} 有些书在列举法中用:代替|, 例如 {2(k+1): k为非负整数}
1.4 集合之间的关系 子集、真子集（包含关系与相等关系） 空集、全集 幂集
集合的包含关系：子集与真子集 子集：设A和B是两个集合, 若A中的每一个元素都是B的元素, 则称A是B的子集(subset), 也称B包含(include)A, 记作A B(或B A)。 真子集：若A为B的子集, 且A B, 则称A为B的真子集(proper subset), 或称B真包含A, 记作A B, B称为A的超集(superset)。 集合A和集合B无任何关系。
子集、真子集(举例) 设A={England国家足球队全体成员} B={England国家足球队前锋成员} C={欧文, 鲁尼} 则有 B A, C B, C A 也有 B A, C B, C A
子集(举例) 设A={a,b,c},B={a,b,c,d},C={a,b},则 AB, CA, CB， C AB a b c d e f g h i j … A … B … … C
真子集(举例) 例 ：N Q R C。 例 ：台湾人都是中国人, 台湾人真包含于中国人, 即 {台湾人} {中国人}。 “”与“”“”的区别: 符号“”表示元素与集合间的隶属关系; 例： 1N /* 1{N}，正确与否？*/ “” “”是集合之间的包含关系, “” “”的两边均是集合, 地位平等。 集合之间可以没有任何关系。
包含关系的性质 设A、B、C为3个集合, 由定义可知集合的包含关系有如下性质： (1) A A。 (自反性) (2) 若A B且B A, 则A = B。(反对称性) (3) 若A B且B C, 则A C。(传递性)
“”传递性证明 若AB,且BC, 则AC 证明: 因为 AB ，所以对于任意属于A的元素x，都有xB； 又因为BC，则xC； 任何属于A的元素都属于C。即： AC
“”传递性证明 若AB,且BC, 则AC 证明: 要证AC，即证AC并且AC 首先证明AC AB AB 并且 AB AB 同理 BC BC, 所以AC. 反证法证明AC 假设A=C, 则BCBA, 又AB, 故A=B, 此与AB矛盾, 所以A=C不成立，因而AC成立. 所以, AC.
集合的相等关系 相等关系定义1：由外延公理, 集合A与集合B的元素完全相同时, A = B。 相等关系判定定理： 设A和B是任意两个集合, 若A B 且 B A, 则称A与B相等, 记作 A = B。 由外延定理证明两个集合相等是困难的。
集合的相等关系有如下性质： (1) A = A。 (自反性) (2) 若A = B, 则B = A。 (对称性) (3) 若A = B且B = C, 则A = C。 (传递性) 两个相等的集合并不意味着它们是用同样的方式定义的。 例 ：设集合A是方程 x2 – x = 0 的解的集合, A = {x | x2 – x = 0}; x2 – x = 0 的解为0和1 B = {0, 1}; 则 A = B。
空集(empty set) 空集:不包含任何元素的集合称为空集(empty set), 记作, 或{ }。 例 ：方程 x2 + 1 = 0 的实根集合是空集。 这说明空集是客观存在的。 空集的引入, 可以使许多问题的叙述得到简化。 下列命题成立： ； {}
例1 ：判断下列命题的真假: (1) (2) (3) {} (4) {} Solution ：(2)为假; 其余均为真。 例2： 列出 B = {}和 C = 的全部(真)子集。 Solution ： {} 且 {} {}； B有两个子集: 和 {} ； B只有一个真子集 : 。 C, 所以C只有一个子集, 没有真子集。 例3:是否存在集合A和B, 使得 AB 且 A B。 Solution ：存在。例 A = {a}, B = {a, {a}}。
空集的性质 （1） 空集是一切集合的子集。 （2） 空集是唯一的。 proof 若存在空集合 1和2, 由（1）知 1 2 和 2 1, 根据集合相等的定义 1 = 2。 对于每个非空集合S, 至少有两个不同的子集, 即 S 和 S S。 我们称和S自身是S的平凡子集。
全集 全集: 如果限定所讨论的集合A都是某个集合U的子集,则称集合U是全集。某些书上也记作E。 全集是相对的, 视情况而定, 因此不唯一.全集只包含与讨论有关的所有对象, 并不一定包含一切事物。 例：讨论(a,b)区间里的实数性质时, 可以选U=(a,b), U=[a,b), U=(a,b], U=[a,b], U=(a,+),U=(-,+)等
幂集(power set) 幂集: 设A是集合，A的全体子集组成的集合,称为A的幂集,记作P(A)，或者2A 。A称作P(A)的指标集。 P(A)={x|xA} 注意: xP(A) xA。也就是说，P(A)中的每一个元素都是集合，这些集合中的元素全部都只能来自集合A。 例：A={a,b}, P(A)={,{a},{b},{a,b}}. A的全体子集是指：A中的全部元素的组合而成的所有集合加上空集。
集合的基 例：A={a,b}, P(A)={,{a},{b},{a,b}}. 基：也称作“势”。集合A中元素的个数。 基数是有限数的集合称为有限集, 否则称为无限(infinite)集。一般仅对有限集讨论其基的值。 定理：设A是有限集，且|A|=n，则A的幂集的基|P(A)|= 2n 。 例：A={a,b}, P(A)={,{a},{b},{a,b}}. |A|=2，则|P(A)|=4
给定一个有限集, 要保证不重复和不遗漏地写出它的全部子集, 办法之一就是将子集按基数由小到大地分类, 相同基数类的子集再按字母数字顺序逐个地写出。 例:求出集合S = {a, b, c}的所有子集。n=3 Solution: 0元子集, 只有一个C30个: ; 1元子集, 有C31个: {a}, {b}, {c}； 2元子集, 有C32个: {a, b}, {a, c}, {b, c}； 3元子集, 有C33个: {a, b, c} 。 共有子集数: C30+C31+C32+C33= (1+1)3 = 23 = 8
子集与二进制数 通过建立子集与二进制数的关系，求出集合的所有子集。 A={a1, a2, …, an}, |A|=n a1 a2 a3 … 0/1 1 B1010…01 = {a1, a3 , an} B0110…00 = {a2, a3} A的子集与n位二进制数一一对应
子集与二进制数（举例） a b c 子集 B 1 {c} {b} {b,c} {a} {a,c} {a,b} {a,b,c} 例：设A = {a, b, c}, |A| = 3, P(A) = { B0= B000 = , B1= B001 ={c}, B2= B010 ={b}, B3= B011 ={b,c}, B4= B100 ={a} , B5= B101 ={a,c} B6= B110 ={a,b} , B7= B111 = a,b,c} } a b c 子集 B 1 {c} {b} {b,c} {a} {a,c} {a,b} {a,b,c}
若|A|=n，A的任一子集都可用n位二进制数中的某个数来表示;反之, 若给出2n －1中的任何一个值, 就能够确定A相应的子集。 我们只用下标来确定子集的各元素, 而字母B则是无关紧要的。 若使用十进制数作为子集的下标, 则转换为A的基数位数的二进制数后同样处理。
例 : 设S = {a1, a2,. , a8}, 由B17 和B31所表示的S的子集各是什么 例 : 设S = {a1, a2, ..., a8}, 由B17 和B31所表示的S的子集各是什么? 应如何表示子集{a1, a8}和{a3, a8, a7}? 解 S有28 = 256个不同的子集, 可表示为B0, B1, B2, B3, … , B255, 二进制下标有8位. B17 = B00010001 = {a4, a8} B31 = B00011111 = {a4, a5, a6, a7 , a8} {a1, a8} = B10000001 = B129 {a3, a8, a7} = B00100011 = B35。
空集的幂集举例 1. ||=0，|P()|=20=1; P() = 。 2. |{}|=1，|P({})|=21=2; 解释： {}, 但 {}, {}。 表示空集, 其中没有任何元素； {} 表示集合族, 它有唯一的一个集合元素
幂集的性质 A B成立当且仅当P(A) P(B) (2) P(A∩B) = P(A)∩P(B) (4) P(A’) (P(A))’
重点掌握 集合的概念及表示方法 子集、真子集、空集、全集、幂集等概念
子集与二进制数（练习） 设A = {a, b, c，d}，利用子集与二进制数的关系，求P(A).
练习题
作业 P 5：3、6 举一个具体的例子说明什么是罗素悖论？罗素悖论对集合论的影响？