1.2 集合

Size: px

Start display at page:

Download "1.2 集合"

云隗
5 years ago
Views:

1 Peking University 1

2 三次数学危机 Peking University 2

3 集合是数学中最基本的概念既然是最基本的概念, 就不是很好定义, 一般只是说明要说明什么是集合, 有多种描述方法 : 所要讨论的一类对象的整体 ; 具有同一性质单元的集体等当我们讨论某一类对象的时候, 就把这一类对象的整体称为集合而集合中的对象就成为该集合中的元素 Cantor 是这样描述集合的 : 所谓集合, 是指我们无意中或思想中将一些确定的, 彼此完全不同的客体的总和考虑为一个整体这些客体叫做该集合的元素 Peking University 3

4 1.2 集合的概念和集合之间的关系 1.3 集合的运算 1.4 基本的集合恒等式 *1.5 集合列的极限 Peking University 4

5 1.2 集合的概念和集合之间的关系集合的概念集合的表示集合间的关系幂集集族 Peking University 5

6 集合的概念设 A 是一个集合,a 是集合 A 中的元素 (member), 将这一事实记为 a A, 读作 a 属于 A; 若 a 不是集合 A 中的元素, 则记为 a A, 读作 a 不属于 A 例如, 一间教室里所有桌子的整体就作为一个桌子集合每张桌子都属于这个集合, 每把椅子就不属于这个集合 Peking University 6

7 集合的表示集合用大写字母, 集合元素用小写字母如 x A,y A (1) 列举法 (listing) ---- 列出集合中的全体元素, 元素之间用逗号分开, 用花括号 { } 括起来例 : 设 A 是由 a,b,c,d 为元素的集合, B 是正偶数集合, 则 A={a,b,c,d}, B={2,4,6,8, } (2) 描述法 (Abstraction) ---- 通过说明集合中元素所具有的共同的性质来定义一个集合用谓词 P(x) 表示 x 具有性质 P,{x P(x)} 表示具有性质 P 的集合例 :P(x):x 是英文字母,Q(y):y 是十进制数字则 C={x P(x)} 和 D={y Q(y)} 分别表示 26 个英文字母和 10 个十进制数字集合 Peking University 7

8 注意 : 1) 集合中的元素各不相同 2) 集合中的元素不规定顺序 3) 集合的两种表示方法有时是可以相互转化的例 :B={x x N 且 x 为非 0 偶数 }, 或 {x x=2(k+1) 且 k N} Peking University 8

9 几个常用的集合及其记号 : N( 自然数集合 ): + * 封闭, 逆运算不封闭 Z ( 整数集合 ): + 及其逆运算,* 封闭, 但 * 的逆运算不封闭 Q ( 有理数集合 ) : +,*, 逆运算封闭, 全序域, 具有稠密性空隙 ( 不连通 ) R( 实数集合 ) C( 复数集合 ) Peking University 9

10 集合之间的关系子集相等真子集空集全集幂集 n 元集有限集集族 Peking University 10

11 定义 1.1 给定集合 A 和 B, 如果 B 中每个元素都是 A 中的元素, 则称 B 为 A 的子集 (subset), 记作 B A 或 A B, 读作 B 包含于 A 或 A 包含 B A B ( x)(x A x B) 设 A={a,b,c}, B={a,b,c,d}, C={a,b}, 则 A B, C A, C B 按子集的定义, 对于任何集合 A B C, (1) A A ( 自反性 ) (2) (A B) (B C) (A C) ( 传递性 ) Peking University 11

12 A 是 B 的子集 (subset), 记作 A B 是指 : (1)A 中的所有元素都是 B 的元素或者 (2) 在 A 中找不到一个不属于 B 的元素或者 (3) 对 x A, 均有 x B A 不是 B 的子集是指 : A 中至少有一个元素不属于 B ( x A, 但 x B) 记作 A B Peking University 12

13 证明 :A B ( x)(x A x B) 证明 : A B (A B) (( x)(x A x B)) ( x) ( (x A) (x B)) ( x) (x A x B) Peking University 13

14 定义 1.2 两个 A 和 B, 若 A 包含 B 且 B 包含 A, 则称 A 与 B 相等, 记作 A=B 集合 A 与 B 不相等, 记作 A B A=B ( x)(x A x B) (A B) (B A) 例 : 设 A= {2}, B={1,4}, C={x x 2-5x+4=0}, D= {x x 为偶素数 } 则 A=D, B=C Peking University 14

15 定义 1.3 给定集合 A 和 B, 如果 A B 且 A B, 则称 A 为 B 的真子集, 记作 A B A B ( x)(x A x B) ( x)(x B x A) 设三个集合 A,B,C, 从定义可以得到下面 3 个命题为真 : (1)A A; (2) 若 A B, 则 B A ; (3) 若 A B 且 B C, 则 A C Peking University 15

16 空集定义 1.4 不含任何元素的集合叫空集, 记作 Φ 例如, Φ={x P(x) P(x)},P(x) 是任意谓词 A={x x R x 2 +1=0} 是空集, 式中 R 表示实数集合全集定义 1.5 在研究某一问题时, 如果限定所讨论的集合都是某一集合的子集, 则称该集合为全集, 记作 E 即 E={x P(x) P(x)} (P(x) 是任意谓词 ) 显然, 全集的概念相当于论域, 它是一个相对概念例如, 如果讨论 (a,b) 上的实数, 就取 (a,b) 为全集也可以取 [a,b), (a,b], 实数集 R 等为全集 Peking University 16

17 定理 1.1 空集是任意集合的子集证明 : 推论空集是唯一的证明 : 反证法 Peking University 17

18 定理 1.1 空集是任意集合的子集证明 : 任给集合 A,Φ 是空集则 ( x)(x Φ x A) 永真, 这是因为条件式的前件 (x Φ) 永假, 所以该条件式对一切 x 皆为真按子集的定义,Φ A 为真 # 推论空集是唯一的证明 : 证 : 假定 Φ 1 和 Φ 2 为二空集由定理 2,Φ 1 Φ 2,Φ 2 Φ 1 再根据定理 1,Φ 1 =Φ 2 # Peking University 18

19 定义 1.6 集合 A 的所有子集构成的集合叫 A 的幂集 (power set), 记作 P(A) 用描述法表示为 :P(A)={x x A} 性质 (1) x P(A) 当且仅当 x A (2) 设 A,B 是两个集合,A B 当且仅当 P(A) P(B) Peking University 19

20 含有 n 个元素的集合为 n 元集 (n 1) 例, 设 A={a,b,c}, 则 0 元子集 : Φ; 1 元子集 : {a},{b},{c}; 2 元子集 : {a,b},{a,c},{b,c} 3 元子集 : {a,b,c} P(A)={Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} Peking University 20

21 定理 1.2 设 A 有 n 个元素, 则 P(A) 有 2 n 个元素证明 :A 的所有由 k 个元素组成的子集个数为从 n 个元素中取 k 个元素的组合数 : n n( n 1)( n 2)...( n k 1) C k + n = ( + ) = n.. k! k = 0 N = C 0 n + C 1 n C k n C 在 (x+y) n 的展开式中令 x=y=1 得 : n n = x y C x y n k= 0 C k n n k k n k 另外, 因 Φ A, 故 P(A) 中元素的个数 N 可表示为 : 2 n n = C k=0 k n = N # Peking University 21

22 集族 : 由集合构成的集合定义 1.7 设 A 为一个集族,S 为一个集合, 若对于任意的 S, 存在唯一的 A A 与之对应, 而且 A 中的任何集合都对应 S 中的某一个元素, 则称 A 是以 S 为指标集的集族,S 称为 A 的指标集为空集族定义 : 设 A 是一个集合若 A 的元素都是集合, 则称 A 为集合族若集合族 A 可表示为 A={S d d D}, 则称 D 为集合族 A 的指标集 Peking University 22

23 例如 [1] 设 A 1 ={x x N x 为奇数 },A 2 = {x x N x 为偶数 }, 则 {A 1,A 2 } 是以 {1,2} 为指标集的集族 [2] P(A) 是一个集合族, 设 A 1,A 2,A 3,... 是集合的序列, 且两两之间互不相同, 则集合 {A 1,A 2, A 3,...} 是一个集合族, 可表示为 {A i i Z}, 其中 Z 为自然数集合, 是指标集 [3] 设 p 是一个素数,A k ={x x=k(mod p)}, k = 0, 1,, p-1, 则 {A 1,A 2,,A p-1 } 是以 {0, 1, 2,,p-1 } 为指标集的集族 Peking University 23

24 多重集合设全集为 E,E 中元素可以不止一次在 A 中出现的集合 A, 称为多重集合. 若 E 中元素在 A 中出现 k(k 0) 次, 则称在 A 中的重复度为 k. 例 : 设全集 E={a,b,c,d,e},A={a,a,b,b,c} 为多重集合, 其中 a,b 的重复度为 2,c 的重复度为 1, 而 d,e 的重复度均为 0 集合可看作是各元素重复度均小于等于 1 的多重集合 Peking University 24

25 1.3 集合的运算定义 1.8 设 A B 为两个集合, 称由 A 与 B 的所有元素组成的集合为 A 与 B 的并集 (union), 记作 A B, 称为并运算符, A B 的描述法表示为 A B={x x A x B} 设 :A={x x N 5 x 10},B={x x N x 10 x 为素数 }, 则 A B = {2,3,5,6,7,8,9,10} Peking University 25

26 集合的并运算可以推广到有限个或可数个集合对于可数个集合 A,A i= 1 i,..., 记 A A = A为并集 10 i= 设 A ={x x R n-1 x n},n=1,2,...,10, 则 n A = { x x R 0 x 10} = [0,10] n Peking University 26

27 定义 1.9 设 A B 为两个集合, 称由 A 与 B 的公共元素组成的集合为 A 与 B 的交集 (intersection), 记作 A B, 称为交运算符, A B 的描述法表示为 A B={x x A x B} 设 :A={x x N 5 x 10},B={x x N x 10 x 为素数 }, 则 A B = {5,7} 集合的交运算可以推广到有限个或可数个集合设 A ={x x R 0 x n},n=1,2,..., 则 i= 1 n A = { x x R 0 x 1} = [0,1] n Peking University 27

28 定义 1.10 设 A B 为两个集合, 若 A B=Ø, 则称 A,B 是不交的 (disjoint), 设 A 1, A 2, 是可数个集合, 若对于任意的 i j, 均有 A i A j =Ø, 则称 A 1, A 2, 是不相交的设 A ={x x R n-1< x < n},n=1,2,..., 则 n A, A,... 是互不相交的 1 2 Peking University 28

29 定义 1.11 设 A B 为两个集合, 称属于 A 而不属于 B 的全体元素组成的集合为 B 对 A 的相对补集 (difference), 记作 A-B, 称 - 为相对补运算符, A-B 的描述法表示为 A-B={x x A x B} 定义 1.13 设 E 为全集,A E, 称 A 对 E 的相对补集为 A 的绝对补集 (complement), 并将 E-A 简记为 A, 称为绝对补运算符, A 的描述表示为 A ={x x E x A} Peking University 29

30 定义 1.12 设 A B 为两个集合, 称属于 A 而不属于 B, 或属于 B 而不属于 A 的全体元素组成的集合为 A 与 B 的对称差, 记作 A B, 称为对称差运算符,A B 的描述法表示为 A B= {x (x A x B) ( x A x B)} A B =(A-B) (B-A)=(A B) -(A B ) 设 :A={x x R 0 x < 2},B={x x R 1 x < 3}, 则 A B = {x x R 0 x < 1} = [0,1) B - A = {x x R 2 x < 3} = [2, 3) A B = [0,1) [2,3) 将 R 作为全集, 则 ~A = (-, 0) [2, + ) Peking University 30

31 文氏图 : 用矩形代表全集, 用圆或其他闭合曲线的内部代表 E 的子集, 并将运算结果得到的集合用阴影部分表示用文氏图可将集合表示如下 : A B={x x A x B} A B={x x A x B} A-B={x x A x B} A B=(A-B) (B-A) A ={x x E x A} 注意 : 文氏图只是对某些集合之间的关系及运算结果给出一种直观而形象的示意性的表示, 而不能用来证明集合等式及包含关系 Peking University 31

32 例 1 设 A={1,2,3},B={1,4},C={3} 求 A B, B A A B, B A,A-B, A B, C A, B C 解 : 例 2 设 E={a,b,c,d},A={a,c},B={a,b,c,d},c=Φ, 求 A, B, C 解 : Peking University 32

33 例 1 设 A={1,2,3},B={1,4},C={3} 求 A B, B A A B, B A,A-B, A B, C A, B C 解 :A B={1,2,3,4}=B A A B={1}=B A A-B={2,3} A B={2,3,4} C A={3}, B C=Φ 例 2 设 E={a,b,c,d},A={a,c},B={a,b,c,d},c=Φ, 求 A, B, C 解 : A ={b,d}, B =Φ, C ={a,b,c,d}=e Peking University 33

34 定义 1.14 设 A 为一个集族, 称由 A 中全体元素的元素组成的集合为 A 的广义并集, 记作 A, 称为广义并运算符, 读作大并 (Big U), A 的描述法表示为 A ={x z(z A x z)} 例 : 设 A={{a,b},{c,d},{d,e,f}}, 则 A={a,b,c,d,e,f} 定义 1.15 设 A 为非空的集族, 称由 A 中全体元素的公共元素组成的集合为 A 的广义交集, 记作 A, 称为广义交运算符, 读作大交 (Big Arch), A 的描述法表示为 A ={x z(z A x z)} 例 : 设 A={{1,2,3}, {1,a,b},{1,6,7}}, 则 A={1} Peking University 34

35 广义并广义交举例 Peking University 35

36 运算的优先级第一类运算 : 绝对补, 求幂集, 广义并, 广义交按由右到左的顺序进行第二类运算 : 并, 交, 相对补, 对称差往往由括号决定, 按左向右的顺序进行 Peking University 36

37 有穷集合的计算包含排斥原理 (Inclusion-Exclusion Principle) 设 A 1,A 2,, A n 为 n 个集合, 则 n A = A A A + A A A... i= 1 n i i i j i j k i= 1 i j i j k + n+ 1 ( 1) A1 A2... Ak 此定理称为包含排斥原理, 简称容斥定理 Peking University 37

38 Peking University 38

39 容斥定理的应用 [ 例 1.1] 在 1 到之间既不是某个整数的平方, 也不是某个整数的立方的数有多少个? Peking University 39

40 [ 例 1.2] 对 24 名科技人员进行掌握外语情况的调查, 统计资料如下 : 会说英日德法语的人数分别为 13,5,10,9 其中同时会说英语日语的人数为 2, 同时会说英语德语或同时会说英语法语, 或同时会说德语法语两种语言的人数均为 4, 会说日语的人既不会说法语也不会德语, 试求只会说一种语言的人数各为多少? 又同时会说英德法语的人数为多少? Peking University 40

41 已知 : A B C D = 24, A =13, B =5, C =10, D =9, A B =2, A C = A D = C D = 4, B C = B D = A B C = A B D = B C D = A B C D =0, A B C D = 24 A B C D = A + B + C + D - A B - A C - A D - B C - B D - C D + A B C + A B D + B C D + A C D - A B C D 把已知代入上面公式可得 : A C D = 1 设只会说英日德法语的人数分别为 x1,x2,x3,x4, 则 x1= A - (B C D) A = A - (B A) (C A) (D A) =4, x2=3,x3=3, x4=2 # Peking University 41

42 Peking University 42

43 小结 E = - ~ P( ) Peking University 43

44 作业 P20: 3,6,8,10 P21: 13, 16 Peking University 44

Microsoft PowerPoint - chapter ppt

Microsoft PowerPoint - chapter ppt 第 3 讲集合的概念与运算 1. 集合的概念 2. 集合之间的关系 3. 集合的运算 4. 文氏图容斥原理 2005-7-5 集合论与图论第 3 讲 1 集合论 (set theory) 十九世纪数学最伟大成就之一集合论体系朴素 (naive) 集合论公理 (axiomatic) 集合论创始人康托 (Cantor) Georg Ferdinand Philip Cantor 1845 ~