第一章集合的概念及运算 §11集合的概念 自从19世纪末德国数学家康托为集合论做奠基工作以来,集合论在一百年的时间里 经称为数学中不可缺少的基本的描述工具。 集合作为数学中最基本的概念,是不能被严格定义的,只能加以描述。简单说来,一个 集合就是一些不同对象构成的整体。 一般地,人们用大写英文字母A,B,C,…表示集合,用小写英文字母a,b,c, 表示集合中的元素。用a∈A表示a为A的元素,读作a属于A:用a∈A表示a 不是A的元素,读作a不属于A 可以用两种方法来表示集合 a.列举法:列出集合中的全体元素,元素之间用逗号分开,然后用花括号括起来。设A 是以a,b,c,d为元素的集合。则A={a,b,c,d}。 b.描述法:即集合的成员可以用其具备的独特性质来描述。例如 A={x∈R:x≥2}。 注1:对于集合的表示法应该注意以下几点 (1)集合中的元素是各不相同的 (2)集合中的元素不规定顺序 (3)集合的两种表示法有时是可以互相转化的。 注2:随意地用描述法来确定(定义)集合,可能导出不可预料的困难。设B是含10个 以上元素的集合构成的集合,则有B∈B。设C是由集合构成的集合,使得 C={x:x是集合且xgx} 那么C∈C还是CgC呢,无论哪一个情况都会导出矛盾?这是一个悖论。是英国数理学 家罗素( Russel!提出的,称为罗素悖论 除罗素悖论外,还有一些其他的悖论,说明不加限制地使用集合一词会出毛病。对集合概 念的运用必须制定一些规则,这就导致了公里化集合论。而把由康托开始建立的未进行公 理化的集合论称为朴素集合论 我们将学习朴素集合论的基本内容,但借鉴公理化集合论的思想,以避免出现悖论。 定义11设A,B为二集合,若B中的元素都属于A,则称B是A的子集,也称A包 含B或B含于A,记作BcA
1 第一章 集合的概念及运算 §1.1 集合的概念 自从 19 世纪末德国数学家康托为集合论做奠基工作以来,集合论在一百年的时间里,已 经称为数学中不可缺少的基本的描述工具。 集合作为数学中最基本的概念,是不能被严格定义的,只能加以描述。简单说来,一个 集合就是一些不同对象构成的整体。 一般地,人们用大写英文字母 A , B ,C ,"表示集合,用小写英文字母 a ,b , c , "表示集合中的元素。用 a A ∈ 表示 a 为 A 的元素,读作 a 属于 A ;用 a A ∉ 表示 a 不是 A 的元素,读作 a 不属于 A 。 可以用两种方法来表示集合。 a. 列举法:列出集合中的全体元素,元素之间用逗号分开,然后用花括号括起来。设 A 是以 a ,b , c , d 为元素的集合。则 A = { , , , } abcd 。 b. 描述法:即集合的成员可以用其具备的独特性质来描述。例如, Ax x =∈ ≥ { : 2} R 。 注 1:对于集合的表示法应该注意以下几点: (1) 集合中的元素是各不相同的; (2) 集合中的元素不规定顺序; (3) 集合的两种表示法有时是可以互相转化的。 注 2:随意地用描述法来确定(定义)集合,可能导出不可预料的困难。设 B 是含10 个 以上元素的集合构成的集合,则有 B∈ B 。设C 是由集合构成的集合,使得 C xx x x = ∉ {: } 是集合且 那么C C ∈ 还是C C ∉ 呢,无论哪一个情况都会导出矛盾?这是一个悖论。是英国数理学 家罗素(Russell)提出的,称为罗素悖论。 除罗素悖论外,还有一些其他的悖论,说明不加限制地使用集合一词会出毛病。对集合概 念的运用必须制定一些规则,这就导致了公里化集合论。而把由康托开始建立的未进行公 理化的集合论称为朴素集合论。 我们将学习朴素集合论的基本内容,但借鉴公理化集合论的思想,以避免出现悖论。 定义 1.1 设 A , B 为二集合,若 B 中的元素都属于 A ,则称 B 是 A 的子集,也称 A 包 含 B 或 B 含于 A ,记作 B ⊆ A
定义12设A,B为二集合,若A包含B且B包含A,则称A与B相等,记作A=B 定义13设A,B为二集合,若A为B的子集,且A≠B,则称A为B的真子集,记 作ACB。 定义1.4不具有任何元素的集合称为空集,记作Q 注1:空集是任何集合的子集;空集是唯一的 定义1.如果限定所讨论的集合都是某一集合的子集,则称该集合为全集,常记为E 定义16设A为一个集合,称由A的所有子集组成的集合为A的幂集,记作P(A) 注1:以A表示A中的元素个数,当A|为有限数时,称A为有限集。元素个数为n (n为自然数)的集合称为n元集 除了P(A)这样由集合构成的集合外,我们还会遇到许多形式的由集合构成的集合,统称这样 的集合为集族。幂集是特殊的集族 定义17设为一集族,S为一个集合,若S中的元素a可一一对应到划中的元素A, 则称4是以S为指标的集族,记为划={A:a∈S}或={4n}as 注:如果将空集看作集族,则称Q为空集族 我们要特别提到多重集合的概念。前面谈到的集合都是由不同对象组成的,而在实际中,某 元素的重复出现往往表达了某种特别的意义。例如,在一个班里学生的名字,可能有两 或多个学生有相同的名字,并且我们又有可能会谈及到学生名字的总体。又例如,某项工程 中所需要的工程技术人员的种类可用集合 A={机工程师,机械工程师,数学家,制图员,程序员 表示,但从集合A中看不出所需要人员的数量。再如方程 的解集应以{0,1,1,1表示。于是引出多重集合的概念。 定义18设全集为E,E中元素可以不止一次在其中出现的集合A,称为多重集合。若E中 元素e在A中出现k(k≥0)次,则称e在A中的重复度为k。 例11设全集E={a,b,c,d,e},A={a,a,b,b,}为多重集合,其中a,b的重复度为2
2 定义 1.2 设 A , B 为二集合,若 A 包含 B 且 B 包含 A ,则称 A 与 B 相等,记作 A = B 。 定义 1.3 设 A , B 为二集合,若 A 为 B 的子集,且 A ≠ B ,则称 A 为 B 的真子集,记 作 A ⊂ B 。 定义 1.4 不具有任何元素的集合称为空集,记作∅ 。 注 1:空集是任何集合的子集;空集是唯一的。 定义 1.5 如果限定所讨论的集合都是某一集合的子集,则称该集合为全集,常记为 E 。 定义 1.6 设 A 为一个集合,称由 A 的所有子集组成的集合为 A 的幂集,记作 ρ( ) A 。 注 1:以| | A 表示 A 中的元素个数,当| | A 为有限数时,称 A 为有限集。元素个数为 n ( n 为自然数)的集合称为 n 元集。 除了 ρ( ) A 这样由集合构成的集合外,我们还会遇到许多形式的由集合构成的集合,统称这样 的集合为集族。幂集是特殊的集族。 定义 1.7 设 A 为一集族, S 为一个集合,若 S 中的元素α 可一一对应到 A 中的元素 Aα , 则称 A 是以 S 为指标的集族,记为 {: } A S A = ∈ α α 或 { } A = Aα α∈S 。 注:如果将空集∅ 看作集族,则称∅ 为空集族。 我们要特别提到多重集合的概念。前面谈到的集合都是由不同对象组成的,而在实际中,某 一元素的重复出现往往表达了某种特别的意义。例如,在一个班里学生的名字,可能有两个 或多个学生有相同的名字,并且我们又有可能会谈及到学生名字的总体。又例如,某项工程 中所需要的工程技术人员的种类可用集合 A ={ } 电机工程师,机械工程师,数学家,制图员,程序员 表示,但从集合 A 中看不出所需要人员的数量。再如方程 3 x x( 1) 0 − = 的解集应以{0,1,1,1}表示。于是引出多重集合的概念。 定义 1.8 设全集为 E , E 中元素可以不止一次在其中出现的集合 A ,称为多重集合。若 E 中 元素 e 在 A 中出现 k ( k ≥ 0 )次,则称 e 在 A 中的重复度为 k 。 例 1.1 设全集 E ={,,, ,} abcde , A ={, ,,,} aabbc 为多重集合,其中 a ,b 的重复度为 2
c的重复度为1,而d,e的重复度为0。 其实,集合可看成是各元素重复度均小于等于1的多重集合。在图论部分,我们将会用到多重 集合的概念 §12集合的运算 给定两个集合A,B,除了他们的交,并运算外,我们还要介绍差和对称差两种运算 定义21设A,B为两个集合,由属于A而不属于B的元素组成的集合称为B对A的相对 补集,记作A一B,称“一”为相对补运算符,A-B可表示为 A-B={x:xX∈A且xgB} 也可称为A减B的差。 注:设E为全集,AcE,称E一A为A的补集,记作A 定义22设A,B为两个集合,由属于A而不属于B或属于A而不属于B的元素组成的集 合称为A与B的对称差,记作A⊕B,称“”为对称差运算符,AB可描述为 AB={x:x∈A但xgB,或X∈B但xgA 注1:容易看出A由B=(A-B)∪(B-A)=(AUB)-(A∩B) 2:A=A.A⊕A=。 我们下面来定义两个多重集P和O的交,并,差运算。 P和Q的并,记为P∪Q,它也是一个多重集,使得P∪Q里任一个元素的重数,等于该 元素在P和Q中重数的最大者:P和Q的交用P∩Q来表示,使得P∩Q的任一元素的重 数,等于该元素在P和Q中重数的最小者;P和Q的差用P-Q来表示,使得如果一个元素 在P中的重数大于它在Q中的重数,那么该元素在P-Q中的重数等于它在P中的重数减去 它在Q中的重数,否则它在P-Q中的重数为0。类似地,对称差PQ中元素的重数等于 元素在P中和Q中两个重数的绝对差值
3 c 的重复度为1,而 d , e 的重复度为 0 。 其实,集合可看成是各元素重复度均小于等于 1 的多重集合。在图论部分,我们将会用到多重 集合的概念。 §1.2 集合的运算 给定两个集合 A , B ,除了他们的交,并运算外,我们还要介绍差和对称差两种运算。 定义 2.1 设 A , B 为两个集合,由属于 A 而不属于 B 的元素组成的集合称为 B 对 A 的相对 补集,记作 A− B ,称“ − ”为相对补运算符, A− B 可表示为 A−= ∈ ∉ B xx Ax B {: } 且 , 也可称为 A 减 B 的差。 注:设 E 为全集, A E ⊆ ,称 E − A 为 A 的补集,记作 A 。 定义 2.2 设 A , B 为两个集合,由属于 A 而不属于 B 或属于 A 而不属于 B 的元素组成的集 合称为 A 与 B 的对称差,记作 A⊕ B ,称“ ⊕ ”为对称差运算符, A⊕ B 可描述为 A⊕= ∈ ∉ ∈ ∉ B xx Ax B x Bx A {: , } 但 或但 注 1:容易看出 A⊕= − − = − B AB BA AB AB ( )( ) ( )( ) ∪ ∪∩ 2: A⊕∅= A , A A ⊕ =∅ 。 我们下面来定义两个多重集 P 和Q 的交,并,差运算。 P 和Q 的并,记为 P Q∪ ,它也是一个多重集,使得 P Q∪ 里任一个元素的重数,等于该 元素在 P 和Q 中重数的最大者; P 和Q 的交用 P Q∩ 来表示,使得 P Q∩ 的任一元素的重 数,等于该元素在 P 和Q 中重数的最小者; P 和Q 的差用 P Q− 来表示,使得如果一个元素 在 P 中的重数大于它在Q 中的重数,那么该元素在 P Q− 中的重数等于它在 P 中的重数减去 它在Q 中的重数,否则它在 P Q− 中的重数为 0 。类似地,对称差 P Q ⊕ 中元素的重数等于 元素在 P 中和Q 中两个重数的绝对差值
还可以将交,并运算推广到集族上 定义23设为一个集族,称由别中全体集合的元素组成的集合为的广义并集,记作∪ 称∪为广义并运算符, 可描述为 Ux={x:存在A∈,使得x∈丹} 例21设={a,b},,d,td,e,},则={a,bcd,e,八} 当是以S为指标集的集族时,∪=U{:a∈S}=UA 定义24设为非空集族,称由烈中全体集合的公共元素组成的集合为烈的广义交集,记作 ∩,称∩为广义交运算符,∩2可描述为 ∩={x:对任意A∈都有x∈A 例22设={12,3,1,16,7},则∩= 当2是以S为指标集的集族时,∩2=∩{4a∈S}=∩A 有限集元素的计数 (1)| AUBA|+|B|-|A∩B|:(2)|A④BHA|+|B|-2|A∩B 定理21设A1,A2 A.为n个有限集合,则 U4∑4-∑An4+∑|4n4n4+ +(-)-∑|4n4∩…∩4|+…+(-114∩40…∩A1 此定理称为包含排斥原理,简称容斥原理。 证明:采用数学归纳法易证。 例23求出在1和250之间,能被2,3,5,7中任意一个数整除的整数的个数。 解:设A1,A2,A4,A4分别是1和250之间能被2,3,5,7整除的整数集合。因为
4 还可以将交,并运算推广到集族上。 定义 2.3 设 A 为一个集族,称由 A 中全体集合的元素组成的集合为 A 的广义并集,记作∪A , 称 ∪ 为广义并运算符,∪A 可描述为 ∪A A = ∈∈ {: , } x 存在 使得 A xA 。 例 2.1 设 A = {{ , },{ , },{ , , }} ab cd de f ,则∪A = {,,, ,, } abcde f 。 当 A 是以 S 为指标集的集族时, {: } S AS A α α α α ∈ ∪∪ ∪ A = ∈= 。 定义 2.4 设 A 为非空集族,称由 A 中全体集合的公共元素组成的集合为 A 的广义交集,记作 ∩A ,称 ∩ 为广义交运算符。∩A 可描述为 ∩A A = ∈∈ {: , } x 对任意 都有 A xA 。 例 2.2 设 A = {{1,2,3},{1, , },{1,6,7}} a b ,则∩A = {1}。 当 A 是以 S 为指标集的集族时, {: } S AS A α α α α ∈ ∩∩ ∩ A = ∈= 。 有限集元素的计数: (1)| || | | | | | A∪ ∩ B A B AB =+ − ;(2)| | | | | | 2| | A⊕ B A B AB =+ − ∩ 定理 2.1 设 A1, A2 ,", An 为 n 个有限集合,则 12 123 12 123 1 1 | | || | | | | n n i i ii iii i i ii iii A A AA AAA = = < << ∪ =− + + ∑∑ ∑ ∩ ∩∩ " 1 2 1 2 1 1 2 ( 1) | | ( 1) | | k k k n ii i n ii i A A A AA A − << < +− + + − ∑ " ∩ ∩"∩ " ∩ ∩"∩ 。 此定理称为包含排斥原理,简称容斥原理。 证明:采用数学归纳法易证。 例 2.3 求出在1和 250 之间,能被 2, 3, 5, 7 中任意一个数整除的整数的个数。 解:设 A1, A2 , A3 , A4 分别是1和 250 之间能被 2, 3, 5, 7 整除的整数集合。因为
250 AH-=125,|A2 3|=83.4÷/250 5/=50,|4/250 14∩23/≈41.140A¥\2×5/=25,14014/250 250 =17 2×7 144/3250 3×5|=16,|A2∩4 =11l,|A3∩A A∩A2∩A3F= =8,|4∩A04F 4n4∩4A230 250 2×5×7 =3,14n4n4[3x5x7=2 1A∩A2∩A3nAF 3×5×7 所以,我们有 AUA2UA2UA4=(125+83+50+35)-(41+25+17+16+11+7)+(8+5+3+2)-1 =193 §13基本的集合恒等式 交,并,补的综合运算规律。 设E为全集,A,B,C为E的子集,则下面列出的运算规律成立 (1)等幂律A∪A=A,A∩A=A (2)交换律AUB=BUA,A∩B=B∩A (3)结合律(∪B)UC=AU(BUC),(A∩B)∩C=A∩(B∩C) (4)分配律AU(B∩C)=(AUB)∩(4UC),A∩(BUC)=(A∩B)U(A∩C) (5)德·摩根律AUB=A∩B,A∩B=A∪B A-(B∪C)=(A-B)∩(A-C),A-(B∩C)=(A-B)U(A-C (6)吸收律AU(A∩B)=A,An∩(UB)=A (7)零律AUE=E,A∩= (8)同一律AU=A,A∩E=A (9)排中律AUA=E
5 1 250 | | 125 2 A ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ , 2 250 | | 83 3 A ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ , 3 250 | | 50 5 A ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ , 4 250 | | 35 7 A ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ , 1 2 250 | | 41 2 3 A A ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ × ∩ , 1 3 250 | | 25 2 5 A A ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ × ∩ , 1 4 250 | | 17 2 7 A A ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ × ∩ , 2 3 250 | | 16 3 5 A A ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ × ∩ , 2 4 250 | | 11 3 7 A A ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ × ∩ , 3 4 250 || 7 5 7 A A ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ × ∩ , 123 250 || 8 235 AAA ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ × × ∩ ∩ , 124 250 || 5 237 AAA ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ × × ∩ ∩ , 134 250 || 3 257 AAA ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ × × ∩ ∩ , 234 250 || 2 357 AAA ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ × × ∩ ∩ , 1234 250 | |1 2357 AAAA ⎢ ⎥ = = ⎢ ⎥ ⎣ ⎦ ××× ∩∩∩ , 所以,我们有 1234 | | (125 83 50 35) (41 25 17 16 11 7) (8 5 3 2) 1 AAAA ∪∪∪ = + + + − + + + + + + +++ − =193 §1.3 基本的集合恒等式 交,并,补的综合运算规律。 设 E 为全集, A , B ,C 为 E 的子集,则下面列出的运算规律成立。 (1) 等幂律 AAA ∪ = , AAA ∩ = (2) 交换律 ABBA ∪ ∪ = , ABBA ∩ ∩ = (3) 结合律 () () A∪∪ ∪∪ B C A BC = , () () A∩∩ ∩∩ B C A BC = (4) 分配律 A∪∩ ∪∩∪ ( )( )( ) BC AB AC = , A∩∪ ∩∪∩ ( )( )( ) BC AB AC = (5) 德·摩根律 ABAB ∪ ∩ = , ABAB ∩ ∪ = A− =− − ( )( )( ) B C AB AC ∪ ∩ , A− ( )( )( ) B C AB AC ∩ ∪ =− − (6) 吸收律 A∪ ∩ ( ) AB A = , A∩ ∪ ( ) AB A = (7) 零律 AEE ∪ = , A∩ ∅=∅ (8) 同一律 A A ∪∅ = , AE A ∩ = (9) 排中律 A∪ A E =