离散数学第2章集合.ppt

2.1 集合论的基本概念2.1.1 集合的概念　　集合在某些场合又称为类、族或搜集，它是数学中最基本的概念之一，如同几何中的“点”、“线”等概念一样，不可精确定义，现描述如下:　　一个集合是能作为整体论述的事物的集体。 　　例如,　　(1) “高二(1)班的学生”是一集合。　　(2) 硬币有两面——正面和反面，“正面， 反面”构成一集合。　　(3) 计算机内存之全体单元构成一集合。　　(4) 1，2，3，…，n，…构成正整数集合。　　(5) 所有三角形构成三角形集合。　　(6) 坐标满足方程x2+y2≤R2的全部点构成图 2.1-1所示的点集。 图 2.1-1 　　组成集合的每个事物叫做这个集合的元素或成员。　　通常用大写字母A，B，C，…代表集合; 用小写字母a，b，c，…代表元素。　　如果a是集合A的一个元素，则记为　　　　　　　　　　a∈A　　读做“a属于A”，或说“a在A中”。　　如果a不是集合A的一个元素，则记为　　　　　　　　　　a　 A　　读做“a不属于A”，或说“a不在A中”。 　　任一元素，对某一集合而言，或属于该集合，或不属于该集合，二者必居其一，不可兼得。　　通常采用3种方法表示集合。　　第一种是列举法。就是把集合中的元素一一列举出来。例如“所有小于5的正整数”这个集合的元素为1，2，3，4，除这4个元素外，再没有别的元素了。如果把这个集合命名为A，就可记为　　　　　　　　　　A={1，2，3，4} 在能清楚表示集合成员的情况下可使用省略号，例如，从1 到50 的整数集合可记为{1，2，3，…，50}，偶数集合可记为{…,-4,-2,0,2,4,…}。 　　第二种是描述法。就是用谓词描述出集合元素的公共特征来表示这个集合。　　例如，上述各例可分别写成　　　　　　　　A={a|a∈I∧0＜a∧a＜5}和　　　 {a|a∈I∧1≤a≤50}，{x|　 y(y∈I∧x=2y)}这里I表示整数集合。一般地　　　　　　　　　　S={a|P(a)}表示a∈S当且仅当P(a)是真。 　　比较这两种表示方法可以看出，列举法的好处是可以具体看清集合的元素; 描述法的好处是刻画出了集合元素的共同特征。应用时可根据方便任意选用，不受限制。　　第三种是归纳定义法。该法我们将留待2.3节讨论。　　集合的元素可以是一个集合，例如A={a,b,c,D}，而 D={0,1}。　　仅含有一个元素的集合称为单元素集合。　　应把单元素集合与这个元素区别开来。例如{A}与A不同，{A}表示仅以A为元素的集合，而A对{A}而言仅是一个元素，当然这个元素也可以是一个集合，如A={1,2}。 　　称含有有限个元素的集合为有限集合。称不是有限集合的集合为无限集合或无穷集。有限集合的元素个数称为该集合的基数或势。集合A的基数记为|A|，例如　　　　　　若 A={a，b}，则 |A|=2，又|{A}|=1　　两个集合怎样才算相等呢? 以下外延公理给出了它的规定。　　外延公理 两个集合A和B相等，即A=B，当且仅当它们有相同的成员(也就是，A的每一元素是B的一个元素而B的每一元素也是A的一个元素)。 　　外延公理用逻辑符号可表达为　 A=B　 x(x∈A　 x∈B)或 A=B x(x∈A→x∈B)∧ x(x∈B→x∈A) 外延公理断言: 如果两个集合有相同的元素，那么不管集合是如何表示的，它们都相等。 　　因此,　　(1) 列举法中，元素的次序是无关紧要的。例如{x,y,z}与{z,x,y}相等。　　(2) 元素的重复出现无足轻重。例如，{x,y,x}、{x,y}、{x,x,x,y}是相同的集合。　　(3) 集合的表示不是唯一的。例如，{x|x2-3x+2=0}、{x|x∈I∧1≤x≤2}和{1，2}均表示同一集合。 2.1.2 罗素悖论　　正如本章前言中所指出的，朴素集合论由于在定义集合的方法上缺乏限制会导致悖论，现在让我们考察一下这种悖论是如何产生的。　　我们通常遇到的集合，集合本身不能成为它自己的元素。例如{a}　 {a}，但有些集合，集合本身可以成为它自己的元素，例如考察概念的集合，因为它本身是一个概念，因此这个集合可以是它自己的一个元素。因此，断言A∈A和A　 A都是谓词，可以用来定义集合。 　　1901年罗素(Bertrand Russell)提出以下悖论: 设论述域是所有集合的集合，并定义S为下述集合:　　　　　　　　　S={A|A　 A} 　这样，S是不以自身为元素的全体