1.1-集合概念.ppt

1、离散数学(I),主讲教师: 冯莎莎 助课教师: 林 海 吉林大学计算机科学与技术学院 智能决策与自动推理教研室,冯莎莎 林 海 教研室电话: 5166478,学习这门课的目的: 1. 知识本身 2. 数学训练 学习这门课的方法: 1. 认真理解概念 2. 认真读书中的内容 3. 做题,基本内容,第一章 集合论基础（集合论） 第二章 命题逻辑 第三章 谓词逻辑 第四章 图与网络 （图论） 第五章 数论基础 （数论） 第六章第八章 （抽象代数）,（数理逻辑）,第一章 集合论基础,1.1 集合的基本概念 1.2 关 系 1.3 映 射,康托尔（G.Cantor,18451918 )，德国数学家。,他

2、创立了集合论作为实数理论，以至整个微积分理论体系的基础。,1845年3月3日，乔治康托生于俄国的一个丹麦犹太血统的家庭。 1856年康托和他的父母一起迁到德国的法兰克福。像许多优秀的数学家一样，他在中学阶段就表现出一种对数学的特殊敏感，并不时得出令人惊奇的结论。 他的父亲力促他学工，因而康托在1863年带着这个目地进入了柏林大学。这时柏林大学正在形成一个数学教学与研究的中心。康托很早就向往这所由魏尔斯特拉斯占据着的世界数学中心之一。所以在柏林大学，康托受了魏尔斯特拉斯的影响而转到纯粹的数学。 他在1869年取得在哈勒大学任教的资格，不久后就升为副教授，并在1879年被升为正教授。 1874年康

3、托在克列勒的数学杂志上发表了关于无穷集合理论的第一篇革命性文章。数学史上一般认为这篇文章的发表标志着集合论的诞生。,克罗内克（L.Kronecker，18231891），是康托尔的老师，他用各种用得上的尖刻语言，粗暴地、连续不断地攻击康托尔达十年之久。他甚至在柏林大学的学生面前公开攻击康托尔。横加阻挠康托尔在柏林得到一个薪金较高、声望更大的教授职位。使得康托尔想在柏林得到职位而改善其地位的任何努力都遭到挫折。 法国数学家庞加莱（H.Poincare，18541912）：我个人，而且还不只我一人，认为重要之点在于，切勿引进一些不能用有限个文字去完全定义好的东西。集合论是一个有趣的“病理学的情形”

4、，后一代将把（Cantor）集合论当作一种疾病，而人们已经从中恢复过来了。,德国数学家魏尔（C.H.HermannWeyl，18851955）认为，康托尔关于基数的等级观点是雾上之雾。 菲利克斯.克莱因（F.Klein，18491925）不赞成集合论的思想。 数学家HA施瓦兹，康托尔的好友，由于反对集合论而同康托尔断交。 . 从1884年春天起，康托尔患了严重的忧郁症，极度沮丧，神态不安，精神病时时发作，不得不经常住到精神病院的疗养所去。变得很自卑，甚至怀疑自己的工作是否可靠。他请求哈勒大学当局把他的数学教授职位改为哲学教授职位。健康状况逐渐恶化，1918年，他在哈勒大学附属精神病院去世。,康

5、托尔的主要研究成果,由于康托尔所创立的朴素集合论产生了悖论，促进了集合论公理化的工作。 具有代表性的工作有两个： 由德国数学家策梅洛(E.Zermelo)于1908年首先建立，后来由以色列数学家弗兰克尔(A.A.Fraenkel)，挪威数学家斯科伦(T.Skolem)与冯诺依曼(von Neumann)等人于20世纪20年代加以改进的ZF公理集合论系统，加入选择公理的系统成为ZFC。 von Neumann-Bernays-Gdel公理系统，简称NBG系统。 教材主要介绍康托尔的朴素集合论的工作。,1.1 集合的基本概念,定义 “所要讨论的一类对象的整体” “具有同一性质单元的集体” “把人们

6、直观的或想象的一些确定的、可区分的对象汇总在一起成一整体，便是一个集合” 通常，用大写的英文字母A, B, C,表示集合；,1、二十六个英文字母构成一个集合； 2、所有的自然数构成一个集合； 3、这间教室中的所有座椅构成一个集合； 4、平面上的所有点构成一个集合。,例如:,集合的元素,组成一个集合的那些对象或单元称为这个集合的元素。 通常，用小写的英文字母a, b, c,表示集合中的元素 。,设A是一个集合，a是集合A中的元素，记为aA，读作a属于A；若a不是集合A中的元素，则记为aA，读作a不属于A。 例如：若A是正偶数集合，则2A，8A，36A；而 3A，9A，17A,属于,有限个元素a1

7、,，an构成的集合，称为有穷集或有限集，记为a1,，an； 包含无限个元素的集合，称为无穷集或无限集。 例：所有英文字母组成的集合是有穷集，整数集合是无穷集。,有穷集 、无穷集,不含任何元素的集合，称为空集，记为，有时也用来表示。 只有一个元素a构成的集合记为a.,空集,设A是有穷集合， A中元素的个数称为A的元素数，记为A。 例如，设A是所有英文字母组成的集合，则A=26。特别， | |=0,集合的元素数（基数）,列举法；将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，例如：V=a,e,i,o,u 或B=1, 4, 9, 16, 25, 36。 描述法 ；通过描述集合中元素

8、的共同特征来表示集合，即S=x | x具有性质p 例如： V= x | x是元音字母， B= n | n=a2 , a是自然数,集合的表示法,确定性 互异性 无序性 多样性,集合的特征,任何一个对象，或者是这个集合的元素，或者不是，二者必居其一； 例如：A=x|x是自然数，且x100 B=x|x是年轻人 C=x|x是秃子,确定性,集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。 例如： 集合A=a,b,c,c,b,d，实际上，应该是A=a,b,c,d,互异性,集合与其中的元素的顺序无关 例如： a,b,c,d,e、d,c,e,a,b、 e,c,d,b,a 表示同一个集合。,无序性,

9、集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征。 例如：A=a,a,a,b,a, 1B=1,a,*,-3,a,b,x|x是汽车,地球,多样性,康托尔的朴素集合论,外延原理 任意两个集合相等，当且仅当的它们中的各个元素都是相同的。 概括原理 任给一个性质，都有一个满足该性质的对象所组成的集合。 选择原理 每个集合都有一个选择函数。,设集合S=A|A是集合，且AA 若SS，则S是集合S的元素，则根据S的定义，有S S，与假设矛盾； 若SS，则S是不以自身为元素的集合，则根据S的定义，有SS，与假设矛盾；,罗素悖论(Russells paradox),当两个集合A和B的元素完

10、全一样，即A，B实际上是同一个集合时，则称集合A，B相等，记以A=B。 例：设A=x|x是偶数，且0x10，B=2,4,6,8，则A=B。,【定义1】集合相等,设A，B是两个集合，若A的元素都是B的元素，则称A是B的子集，也称B包含A，或A包含于B，记以A B，或B A 。 若AB，且AB，则称A是B的真子集(proper subset)，也称B真包含A，或A真包含于B，记以AB，或B A 。,【定义2】子集(subset),设A=2,4,6,8 ，B= x|x是正偶数， C=x|x是整数,则有A B，B C，AC,并且A B，B C，A C 。,例：,当我们所讨论的集合都是某一集合的子 集时

11、，这个集合就称为全集，记作E。全 集是相对的。,对任意集合A, 有A A。 空集是任意集合的子集，且空集是唯一的。 对于任意两个集合A、B，A=B当且仅当AB且BA。,重要结论,是否存在集合A和B, 使得AB 且A B ？若存在，请举一例。,讨论,文氏图(Venn Diagram)用矩形中的点表示全集，用矩形中的圆周或其它形状的封闭的曲线内部的点表示E的子集，用阴影部分表示所关心的子集。 例如：集合V=a,e,i,o,u ，用文氏图表示如下:,E,V,a,u,设A 是集合，A的所有子集为元素做成的集合称为A的幂集，记以(A)或 2A。 (A)=S|S A 例： A=a,b,c ，则 (A)=

12、,a,b,c,a,b,a,c,b,c,a,b,c,【定义3】幂集(power set),|()| = () = () = () = , ,若A为有穷集，|A|=n，则|2A | = x(A)当且仅当xA。 设A、B是两个集合，AB当且仅当(A)(B)；,幂集的性质,证明：集合A和B，AB(A)(B),证明：（充分性）任意取x A，x(A),又(A)(B)，故x(B)，则xB， AB成立。 （必要性）任意取x (A)，即x A，又AB，则x B，那么x (B)，(A)(B)成立。,设C是一个集合。若C的元素都是集合，则称C为集合族。 若集合族C可表示为C=SddD，则称D为集合族C的标志（索引）

13、集。,【定义4】集合族、标志集,显然，2A是一个集合族。 设A1, A2, A3, 是集合的序列，且两两之间互不相同，则集合A1, A2, A3, 是一个集合族，可表示为Ai| iN，其中,N是自然数集合，是该集合的标志集合。,设A，B是两个集合。所有属于A或者属于B的元素做成的集合，称为A和B的并集，记以AB。即AB=x|xA或xB 例如，令A=a，b，c，d，B=c，d，e，f，于是AB=a，b，c，d，e，f。,【定义5】集合的并集(Union),并集的文氏图,A,B,AB,设A，B是两个集合。由属于A又属于B的元素组成的集合，称为A和B的交集，记以AB。即AB=x|xA且xB 例如，令

14、A=a，b，c，d，B=c，d，e，f，于是AB=c，d。,【定义6】集合的交集(Intersection),交集的文氏图,A,B,AB,证明：（充分性）任意取x A，由于AB=A，故x AB，即x A并且x B，故AB成立。 （必要性）易见AB A成立，往证A AB 成立。任意取x A，由于AB，故x B，即x AB，即A AB，故 AB=A。,证明：AB 当且仅当AB=A,证明：AB 当且仅当AB=B,设A1，A2，An是n个集合，A1A2An ，简记为 A1A2An ，简记为,并集和交集的推广,对于有限集A1和A2，有 A1 A2 A1 A2 A1 A2 ,容斥原理(principle

15、of inclusion-exclusion),对于有限集A1，A2和A3，有 A1 A2 A3 = A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3 提示： A1 A2 A3 = (A1 A2) A3,设A1，A2，An是n个有穷集合，则,容斥原理(principle of inclusion-exclusion),称为包含排斥原理，简称容斥原理。,设A，B是两个集合。由属于集合A而不属于集合B的所有元素组成的集合，称为A与B的差集，记以A-B，或AB。即A-B=x|xA且xB 例如，令A=a，b，c，d，B=c，d，e，f，于是A - B=a，b。,【定义7】集合的差

16、集(Difference),差集的文氏图,A,B,A-B,E,设A是一个集合，全集E与A的差集称为A的余集或补集，记以A。即A=E-A 例如，令E=a，b，c，d，e，f，A=b，c，于是A=a，d，e，f。 特别，,【定义8】集合的补集(Complement),补集的文氏图,A,E,设A，B是两个集合。则A与B的环和(对称差),记以AB, 定义为AB=(A-B)(B-A)。 A与B的对称差还有一个等价的定义，即AB=(AB)-(AB)。 例：令A=a，b，c，d，B=c，d，e，f，于是AB=a，b， e，f。,【定义9】集合的对称差,对称差的文氏图,A,B,AB=(A-B) (B-A),E

17、,设A，B是两个集合，则A与B的环积定义为 A B = AB,【定义10】集合的环积,A,B,E,我们将(a1,a2 , ,an)称为有序n元组，其中，a1是其第一个元素， a2是其第二个元素， ，an是其第n个元素。 两个有序n元组(a1,a2 , ,an)和(b1,b2 , ,bn)相等当且仅当ai=bi , i=1,2,n,【定义11】有序n元组,对于有序n元组，当n=2时，我们将其称作有序二元组，也称作有序对,或序偶。 有序对的特点： 若ab,则(a,b)(b,a) 两个有序对(a,b)和(c,d)相等当且仅当a=c，b=d,【定义12】有序对,设A，B是两个集合，所有有序对(x, y

18、)做成的集合(其中xA，yB)，称为A，B的直乘积(笛卡儿积)，记以AB。 AB=(x，y)xA且yB。,【定义13】笛卡儿积(Cartesian product),设A1,A2 , ,An是n个集合，由所有有序n元组(a1,a2,an)做成的集合(其中aiAi，i=1,2, ,n)，称为A1,A2,An的直乘积(笛卡儿积)，记以A1A2 An。 A1A2 An=(a1,a2 , ,an) aiAi，i=1,2, ,n 。,【定义14】笛卡儿积的推广,设A=1,2，B=a,b,c,则AB=(1,a), (1,b),(1,c),(2,a),(2,b),(2,c)； BA =(a,1), (a,2),(b,1),(b,2),(c,1),(c,2)；,例如：,1. |AB|=A B； 2. 对任意集合A，有A = ， A= ； 3. 直乘积运算不满足交换律，即ABBA； 4. 直乘积运算不满足结