资源描述
第三篇 集 合 论 Set Theory,主要内容 第4章 集合 4.1 集合的概念与表示 4.2 集合的运算 4.3 Venn氏图及容斥原理 4.4 集合的划分 4.5 自然数集与数学归纳法 第5章 二元关系 第6章 函数,第4章 集合（Set）,4.1 集合的概念与表示,集合的概念 又称为类、族或搜集 是数学中最基本的概念之一 不可精确定义(原始概念) 集合的描述 笼统地说，一些可以互相区分的任意对象(统称为元素)聚集在一起形成的整体就叫做集合，用大写的英文字母表示，如A，B 这些对象就是这个集合的元素(或称成员) ，一般用小写字母表示，如a，b 集合中的元素不计次序 a,b,c,a=c,b,a,d 集合中的元素不计重度 x,y,x =x,y =x,x,x,y,元素与集合的关系 a是集合A的一个元素, 则记为aA，读做“a属于A”, 或说“a在A中” a不是集合A的一个元素, 则记为aA，读做“a不属于A”, 或说“a不在A中” 集合的元素可以是一个集合 例：A=a,b,c,a,b 则a,bA且a,b A,有限集与无限集,定义4.1.1 设A是一个集合。 用A或#A表示A含有的元素的个数，称做A的基数，或阶。 若#A =0，则称为空集；否则称为非空集。 若#A为一非负整数，则称A为有限集；否则称为无限集。 例： A=a,b,a, b |A|=3；|A|=1 基数为n的非空有限集称为n元(或n阶)集合,空集与全集,显然，空集是不含有任何元素的有限集，常用符号 表示 定义4.1.2 全集 恒用E表示，是指包含了讨论中涉及的全体元素的特殊集合 全集也是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以有不同的全集,集合的比较运算,定义4.1.3 集合相等(外延公理) 两个集合A和B相等, 即A=B, 当且仅当它们有相同的成员 A = B x(xAxB) x(xAxB)x(xBxA) 否则，用AB表示集合A和B不相等，即 A B x(xAxB) 定义4.1.4 设A和B是集合, 如果A的每一元素是B的一个元素, 那么A是B的子集,也称B是A的母集(或称扩集)，记为AB, 读做“B包含A”或“A包含于B”,即 ABx(xAxB),集合的比较运算,定理4.1.1设A和B是集合, A=B当且仅当A B和BA（ 的反对称性） 证明： ABBA x(xAxB)x(xBxA) x(xAxB)(xBxA) x(xAxB) A=B,集合的比较运算,定义4.1.5 设A和B是集合, 如果AB且AB, 那么称A是B的真子集,记作AB , 读作“B真包含A”或“A真包含于B”,即 ABA BAB x(xAxB)x(xAxB) x(xAxB)(x(xAxB)x(xBxA) (x(xAxB)x(xAxB)(x(xAxB) x(xBxA) x(xAxB) x(xBxA),集合的表示 列举法 将集合中的元素一一列出，写在大括号内 A=1, 2, 3, 4， B=a,b,c,d，C=,-4,-2,0,2,4, 谓词描述法(指定原理) 用谓词公式描述元素的共同属性 一般形式： S=a|P(a)表示aS当且仅当P(a)是真 A=a|aI0aa5, a|aI1a50 A=x|P(x)， B=x|Q(x) 若P(x)Q(x)，则A = B 若P(x)Q(x)，则A B 递归定义法,S被称为谓词P的广延,集合应该是充分定义(良定)的,递归定义法(归纳定义),用这种方法定义一个非空集合A时，一般应包括以下三个部分： 基本项 已知某些元素(常用S0表示由这些元素组成的非空集合)属于A，即S0 A 。这是构造A的基础，并保证非空。 递归项 给出一组规则，从A中(已获得的)元素出发，依照这些规则所获得的元素，仍然是A中的元素。这是构造A的关键部分。 极小化 如果集合S A也满足和，则S = A 。这说明， A中的每个元素都可以通过有限次使用和来获得(或称A是满足条款(1)和(2)的最小集合)，它保证所构造出的集合A是唯一的。,同样集合S能归纳地定义如下： (1) (基础)3S; (2) (归纳)如果xS和yS, 那么x+yS; (3) (极小性)S的元素都是由有限次应用条款(1)和(2)得出的。,例,如果全集是整数集合I, 那么能为3 整除的正整数集合S的谓词定义如下:,字母表与串,设表示一个有限的非空的符号(字符)集合、我们称为字母表。由字母表中有限个字符拼接起来的符号串叫做字母表上的一个字(或叫串) 例 (a) 如果=a,b, , z, 那么is, then都是上的字 (b) 如果=你, 我, 人, 工, , 是, 那么“你是工人”是上的串 (c) 如果=a, b, , z,_, 这里“_”是代表空白。那么that_was_long_ago是上的串, 习惯上印成that was long ago (d) 如果=0,1, 那么000,010,011010等都是上的串,x是上的一个字, 如果x=a1a2an, （nN, 1in, ai）, 那么x中的符号个数n称为x的长度, 记为x 长度为0的串叫做空串，记为(或) x和y都是在上的符号串，x连结(或叫并置, 毗连)y, 记为xy x=a1a2an，y=b1b2bm 则 xy=a1a2anb1b2bm x=则 xy=y z=xy x是z的词头, y是z的词尾 如果xz, 称x为真词头 如果yz,称y为真词尾 如果w=xyz, 则y是w的子串, 如果yw,称y为真子串,设是一个字母表, 上的非空串的集合+定义如下： (1) (基础)如果a, 那么a+； (2) (归纳)如果x+且a, 那么ax+； (3) (极小性)所有集合+的元素仅能由有限次应用条款(1)和(2)构成。 集合+包含长度为1, 2, 3, 的串, 所以是无限集合。然而, 在+中没有一个串包含无限数目的符号, 这是极小性条款限制的结果 例：=a,b +=a,b, aa,ab,ba,bb,aaa,aab,设是字母表, 上的所有有限符号串的集合*定义如下： (1) (基础)*； (2) (归纳)如果x*和a, 那么ax*； (3) (极小性)所有集合*的元素, 仅能有限次应用条款(1)和条款(2)构成。 *=+ 例 =a,b, *=,a,b,aa,ab,例 :算术表达式集合 设集合仅包含整数，一元运算+和-， 二元运算+、 -、 *、/ (1) (基础) 如果D=0, 1, 2, 3, 4, 5, 6, 7, 8, 9和xD+, 那么x是一算术表达式。 (2) (归纳) 如果x和y都是算术表达式, 那么 (i) (+x) 是一算术表达式 (ii) (-x) 是一算术表达式 (iii) (x+y)是一算术表达式 (iv) (x-y)是一算术表达式 (v) (x*y)是一算术表达式 (vi) (x/y) 是一算术表达式 (3) (极小性)一个符号序列是一算术表达式当且仅当它能由有限次应用条款(1)和(2)得到,小结,递归定义 (1) 基础条款(简称基础) 已知哪些元素属于集合 (2) 归纳条款(简称归纳) 一般为一些递推规则 (3) 极小性条款(简称极小性) 断言一个事物仅能有限次应用基础和归纳条款构成 其它形式 (i) 集合S是满足基础和归纳条款的最小集合 (ii) 如果T是S的子集, 使T满足基础和归纳条款, 那么T=S,集合比较运算的基本事实,定理4.1.2 设A、B和C是任意三个集合，则有 A AE AA （ 的自反性） 若AB且BC, 则AC（ 的传递性） 若AB且B C, 则A C 若A=B, 则B = A 若A=B且B = C, 则A = C,证明： (1) x, x永假, 所以 xxA永真 A (2) x, xE永真, 所以xAxE永真 AE (4) 若AB且 BC 则对x E xA xB xC 即 AC 得证,练习,设A=a,a,a,b,a,b,c, 判断下面命题的真值 aA A A aa,b,c aA a,ba,b,c a,bA a,ba,b,c ca,b,c (cA)(a ),幂集,定义4.1.6 A是集合，由A的所有子集构成的集合，称之为A的幂集。记作P(A)或2A P(A) =B| BA 例 (a) A= P(A)= (b) A=a,b P(A)= , a, b, a, b A是任意集合 AP(A) P(A),例,设A=P(a, )判断下列结论是否正确 (1) A (2) A (3) A， (4) A (5) aA (6) aA, (7) aA (8) aA 解：(1)，(2)，(3)，(4)，(7)是正确的 若| A|=n，则|P(A) |=？ 解: |P(A) |= 2n,定理4.1.3 设是有限集，则：|2A| = 2|A| 幂集元素的编码 例：a,b,c P(A)=,c,b,b,c,a,a,c,a,b,a,b,c 八个子集分别表示成：S0, S1, S2, S3, S4, S5, S6, S7 下标写成二进制形式：S000,S001,S010,S011,S100,S101,S110,S111 c b b,c a a,c a,b a,b,c S000 S001 S010 S011 S100 S101 S110 S111 若a,b,c,d，则： S9 =？ S9 =a,d a,c,d=S？ a,c,d= S1011 = S11,练习,1.设A=， B=P(P(A)，则以下哪些是真命题？ (1) B (2)B (3)B (4) B (5)B (6)B 解： P(A)= , B = , , , , 对一般集合A，有：aAaAaP(A) 2.证明：AB iff P(A)P(B),运算共性的研究(如何理解一个新的运算),运算,基本概念,基本性质,一元运算：对合律等,二元运算：交换律、结合律等,与比较运算的关系,与其他运算的关系,对性质的封闭性,证明：AB iff P(A)P(B),必要性：AB时 根据指定原理，为了证明P(A)P(B)，只需证明： S SP(A) SP(B) P(A)P(B),充分性：P(A)P(B)时 x xA xB AB, SA,SB ,(A)的成员都是(B)的成员,A的子集都是B的子集,xA ,或证：因为A P(A) 所以A P(B) ,自己补充完整,罗素悖论,1901年罗素(Bertrand Russell)提出 不存在集合S=A|A是集合，且AA 证明：假设S是一个集合，则以下两种情况有且仅有一种出现： (1) SS ，这时由S的定义知SS (2) SS ，这时由S的定义知SS 总之，恒有 SS iff SS 矛盾，所以S不可能是一个集合 一个“集合”, 如S, 它能导致矛盾，称为非良定的,4.2 集合的运算,定义4.2.1 设A和B是集合 (a) A和B的并记为AB AB=x|xAxB xAB xAxB (b) A和B的交记为AB AB=x|xAxB xAB xAxB (c) A和B的差, 或B关于A的相对补, 记为A-B A-B=x|xAxB xA-B xAxB (d) A和B对称差,记为AB AB = x|xAxB xAB xA xB,绝对补:E-A,例,例4.2.1 若取E0,1,2,3,4,5，A1,2,4及B2,5，则有： AB 1,2,4,5， AB 2， A-B 1,4， A B 1,4,5， A c0,3,5， B c0,1,3,4。 例4.2.2 设是一个字母表，用n表示上全体长度为n的串组成的集合(n)，则： *012 +*12,定义4.2.2 如果A和B是集合, AB= , 那么称A和B是不相交的。如果C是一个集合的族, 使C的任意两个不同元素都不相交, 那么C是(两两)不相交集合的族。 例：四个集合：1,2,3、4、5,6和7,8,9,10是两两互不相交的 定理4.2.1 设A 、 B和C是三个集合，则有 A A B ， B A B ； A B A ， A B B ； A - B A ； 若A B ，则B c A c ； 若A C且B C ，则A B C ； 若A B且A C ，则A B C 。,特别重要,定理4.2.2 设A 、 B 、 C和D是四个集合，且A B ， C D ，则 A C B D ； A C B D 。 定理4.2.3 设A和B是两个集合，则下面三个关系式互相等价。 A B ； A B B ； A B A 。 集合运算的基本恒等式 (集合运算基本律) P98-P99,集合等式与不等式证明的一般方法(1),试证明： A(AB) = A 方法1： A(AB) = (AE)(AB) = A(EB) = AE = A,不足：强调技巧，不规范 死记公式 难以推广应用,方法2：显然，AA(AB)； 另一方面，AA且ABA 故A(AB)A。 总之， A(AB) = A 。,适用于子集之并为子集、母集之交为母集的问题,引用集合运算基本律,集合等式与不等式证明的一般方法(2),依据指定原理,根据指定原理，为了证明A=B(A、B为集合表达式)，只需证明： x xA xB 为了证明AB，只需证明： x xA xB 这样集合等式与不等式的证明转变成谓词公式等价与蕴含的证明了。证明谓词公式等价与蕴含可采用等价变换或逻辑推证。 一般而言，等价变换比逻辑推证有明显优点。 但等价变换也有缺点。,集合等式与不等式证明的一般方法(3),证明：P(AB) = P(A)P(B) 证：(等价变换) S SP(AB) SP(A)P(B),依据指定原理, SAB,SP(A)SP(B) ,SASB ,？,证：一方面， 因为ABA，ABB 所以P(AB)P(A)， P(AB)P(B) 从而P(AB)P(A)P(B) 另一方面，SP(A)P(B)，即 SP(A)且SP(B)来说， 有SA且SB 所以SAB，即SP(AB) 这表明P(A)P(B)P(AB),(逻辑推证),思考:P(AB) = P(A)P(B)？,集合等式与不等式证明的一般方法(4),试证明：A(B-A) = 证明：x xA(B-A) xAxB-A xAxBxA x A(B-A) = ,注意到空集被定义为矛盾式的广延，所以这个证明可以简化。,反证法,假若不然， 即x：x A(B-A) 这说明xA，且xB-A 与B-A的定义相矛盾,总结(集合等式与不等式证明的一般方法),引用集合运算基本律 子集之并仍为子集 扩集之交仍为扩集 指定原理 等价变换(例4.2.5，定理5.1.3、5.4.5的证明) 逻辑推证(例4.2.4) 反证法 主要适用于证明某集合表达式为空集的情形,文氏图 ( Venn diagram ),AB,AB,A-B,=A-AB,4.3 Venn氏图及容斥原理,容斥原理,|AB|= |M1|+ |M2|+ |M3| = |B|- |AB|+ |A|- |AB|+ |AB| = |A| + |B| - |AB|,由A和B生成的最小集合,容斥原理,定理 4.3.1 设A和B都是有限集合,例,在20名青年有10名是公司职员,12名是学生,其中5名既是职员又是学生,问有几名既不是职员,又不是学生？ 解 设职员和学生的集合分别是A和B。 由已知条件A=10, B =12, AB=5 AB=A+B-AB=10+12-5=17 则,有3名既不是职员又不是学生,三个集合的容斥定理 |ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC| 例：某研究所有170名职工，其中120人会英语，80人会法语，60人会日语，50人会英语和法语，25人会英语和日语，30人会法语和日语，10人会英语、日语和法语。问有多少人不会这三种语言？ 解：令U为全集，E、F、J分别为会英语、法语和日语人的集合 |U|=170，|E|=120， |F|=80， |J|=60， |EF|=50 ，|EJ|=25，|FJ|=30， |EFJ|=10 |EFJ|=|E|+|F|+|J|-|EF|-|EJ|-|FJ|+|EFJ| = 120806050253010165 |U-(EFJ)|=170-165=5 即有5人不会这三种语言,容斥原理,定理4.3.2 设1,2,n是n个有限集，则,4.4 集合的划分,定义4.4.1 划分 给定非空集合A和非空集合族=A1,A2,Am,如果 A= A1A2Am AiAj= 或Ai=Aj(i,j=1,2,m) 称集合族为集合A的一个划分(分割 ) 划分的元素Ai称为划分的块(Block) 如果划分是有限集合,则不同块的个数即#叫划分的秩 定义4.4.2 覆盖 给定非空集合A和非空集合族=A1,A2,Am,如果 A= A1A2Am 称集合族为集合A的一个覆盖,关于集合的划分的理解,划分中的每一块是非空的 划分中的任意两块没有公共元素(两两互不相交) A的一个划分耗尽了A中的所有元素 例 设S=1,2,3 A= 1,2,2,3 B= 1,1,2,1,3 C= 1,2,3 D= 1,2,3 E= 1,2,3 F= 1,1,2,最小(粗)划分,最大(细)划分,交叉划分,定义4.4.3 若11,2,r和21,2,t是集合的两个不同划分，则称所有使ij 者(i=1,2,r；j=1,2,t)组成之集： ij(i1j2 ij) 为1和2的交叉划分。,交叉划分,例4.4.3 设集合表示某个单位全体具有高级职称的职工之集 划分11,2 1集合中的男职工之集 2 集合中的女职工之集 划分21,2,3 1集合B中的老年职工之集 2 集合B中的中年职工之集 3 集合B中的青年职工之集,A1,A2,B1,B2,B3,定理4.4.1 集合的划分1和2的交叉划分是集合的划分。,集合的划分,定义4.4.4 若11,2,r和21,2,t是集合的两个划分，若对于每一个i1都存在j2使得ij，则称1精分2，或称1是2的加细。若1精分2且存在i1和j2使得ij(即12)，则称1真精分2 。,集合的划分,定理4.4.2 集合的划分1和2的交叉划分精分1和2 证明: 设11,2,r,21,2,t ，并设1和2的交叉划分为。 则对任意，必有i 1和j 2使得i j ，显然i ，j ，即精分1和2 。,第二类Stirling数,给定集合的划分并不是唯一的 有多少种不同的方法将一n元集合划分成若干个块？ 定义4.4.5 将一n元集划分成k块的方法数称为第二类Stirling数，用S(n,k)表示 对于任意的自然数n，当kn时，有S(n,k)0，且S(n,1)1，S(n,n)1,第二类Stirling数,定理4.4.3 S(n,2)n-1-1，其中n2 定理4.4.4 S(n,k)S(n-1,k-1)+kS(n-1,k)，其中2kn 证明 设a1,a2,an-1,an是一n元集合。注意中元素an在的k划分中的情况， 情况1： an单独构成一块，则a1,a2,an-1必须划分成k-1块，其方法数为S(n-1,k-1)； 情况2： an与其它元素一起构成一块。则a1,a2,an-1必须划分成k块， an可加入其中的任一块，共有kS(n-1,k)种方法。 总之，S(n,k)S(n-1,k-1)+kS(n-1,k)。,4.5 自然数集与数学归纳法,自然数的定义 公理化方法 构造化方法 应用后继集合的概念归纳定义 定义 4.5.1 设A是任意集合, A的后继集合记为A+, 定义为 A+= AA 称A+为A的后继的同时，也常说A是A+的前趋 例 (a) a,b的后继集合：a,ba,b=a,b,a,b (b) 的后继集合： = , ,定理4.5.1 设是一个集合，则 + ； + , ； +； +； + 。,自然数,自然数集合 1908年Zermelo , , , , Von Neumann的方案 0= ， 1=0+= ，2=1+= , 定义4.5.2 自然数N是如下集合： (1) (基础) ，这里 0= 。 (2) (归纳)如果nN, 那么n+N。 (3) (极小性)如果AN且满足条款(1)和(2)，那么A=N。,自然数系统满足以下Peano公理 (1) 0N, (2) 如果nN, 则恰存在一个n的后继者n+N, (3) 0 不是任何自然数的后继者, ; (4) 如果n+=m+, 那么n=m, (5) 如果A是N的子集, 使, (i) 0A; ; (ii) 如果nA, 那么n+A 那么, A=N,归纳证明,定理4.5.3 第一数学归纳法原理 设P(n)是定义于I上的一项谓词，n0为一给定整数，为了证明n n0 ， P(n)皆为真，只需证明： P(n0)为真； k n0 ，若P(k) 为真，则P(k+)也为真 证明：令A=n| nN 且 P(n+n0)为真 往证在题设(1)和(2)成立时， A=N 显然 AN，且 由(1)知：0A 由(2)知：如果nA, 那么n+A 由归纳原理A=N,第一数学归纳法证明步骤 归纳基础：直接验证n=n0时，命题为真 归纳步骤：对任意整数k n0 ，设n=k时命题为真（归纳假设），证明当n=k+1时命题也为真 例 证明对所有nN ,证明： (1) n=0时,(2) 设n=k时，,则n=k+1时，,例：设i0是一整数，令S=i| iI 且 i i0，证明：对于S的任一非空子集J，皆存在j0 J使得对于任意的j J有j0 j（称j0为J的最小元） 注意：由于J可能是无限集合，因此不能直接对| J |进行归纳 证明：任取m J ，令A=j| jJ 且 j m，则A J ， | A | m- i0 +1，又m A知A ，且若A有最小元a，显然a必是J的最小元，故只需证A有最小元。 (1)当| A | =1时， A中仅一个元素m，它就是A的最小元 (2)设| A | =k时(k1)，命题成立，考虑| A | =k+1时的情况， 设A=j1 ,j2, jk, jk+!，由于j1 ,j2, jk是k元集合，由归纳假设 得它有最小元，设为j，则当j jk+!时， j是最小元，否则 jk+!是最小元。总之， A存在最小元。 命题得证。,考虑下面的证明过程并指出问题 证明：若n为自然数，则n+1=n. “证明”：对任意的kN，假定n=k时命题为真，即k+1=k. 从而(k+1)+1=k+1，即当n=k+1时命题也真. 由第一数学归纳法，命题得证. 证明世界上所有的人都同岁. “证明”：设世界上有n个人. (1) 当n=1时，因为只有一个人，他和自己同岁，所以命题为真 (2) 因为n=1的情况已经证明过了，所以假定对任意的自然数k1，当n=k时命题为真，现考虑k+1个人，不妨设为a1 ,a2, ak, ak+1.根据假定， a1 ,a2, ak同岁， a2, ak, ak+1同岁，所以a1 ,a2, ak, ak+1都与a2同岁.即n=k+1时命题也真.由第一数学归纳法，命题得证,定理4.5.4 第二数学归纳法原理 设P(n)是定义于I上的一项谓词，n0为一给定整数，为了证明n n0 ， P(n)皆为真，只需证明： P(n0)为真； n n0 ，若k= n0 ,n0+1, n时P(k)皆为真，则P(n+)也为真 证明：令J=n| nI ， n n0 且 P(n)为假 往证在题设(1)和(2)成立时， J= 假若不然，已证J必有最小元j0. 由(1)知： n0 J.故j0 n0 ,从而当k= n0 ,n0+1, j0 -1时P(k)皆为真，由(2)知， P(j0)为真，与j0 J矛盾.,例：有数目相等的两堆棋子, 两人轮流从任一堆里取几颗棋子, 但不能不取也不能同时在两堆里取。规定凡取得最后一颗者胜。求证后取者可以必胜。 证明 对每堆棋子数目n作归纳证明。为了便于叙述, 设甲为先取者, 乙为后取者。 n=1时, 甲必须在某堆中取一颗。于是另一堆中的一颗必为乙所得, 乙胜。 设nk时, 后取者胜。 现证n=k时也是后取者胜。 设第一轮甲在某堆先取r颗, 0rk。 乙在另一堆中也取r颗。则： (1) 若rk, 经过两人各取一次之后, 两堆都只有k-r颗, k-rk, 现在又是甲先取, 根据归纳假设乙胜。 (2) 若r=k, 显然是乙胜。证毕,练习,证明：对于任意n8，必存在非负整数s和t，使得n=3s+5t Fibonacci数列定义为 F0=0, F1=1, Fn+2=Fn+1+Fn(nN) 证明：若n1，则,
展开阅读全文