《集合概念与符号》由会员分享，可在线阅读，更多相关《集合概念与符号（35页珍藏版）》请在金锄头文库上搜索。
1、集合论1. 集合概念与符号 集合(直观描述) 集合相等和子集合 子集的表示方式和全集 常用数学符号和常用集合记号起源 集合论(Set Theory)是现代数学的基础它的起源可追 溯到16世纪末，主要是对数集进行卓有成效的研究 但集合论实际发展是由 19世纪 70年代德国数学家康托 尔(G . Cantor) 在无穷序列和分析的有关课题的理论研 究中创立的康托尔对具有任意特性的无穷集合进入 了深入的探讨，提出了关于基数、序数、超穷数和良 序集等理论，奠定了集合论的深厚基础因此，康托 尔被誉为集合论的创始人但随着集合论的发展，以 及它与数学哲学密切联系所作的讨论，在本世纪初， 出现了许多似是而非、
2、自相矛盾的悖论，如著名的罗 素(B . A . W . Russell)悖论，有力冲击了或者说动摇了 集合论的发展 由此原发许多数学家哲学家为克服这些矛盾而建立了 各种公理化集合论体系，其中尤以本世纪初、中期的 ZFS(E . Zermelo, A . Fraenkel, T . Skolem)和NBG(Von Neurnann, P . Bernavs, K . Gdel)公理化体系最为流行. 到 20世纪 60年代，P . L . Cohen发明了强制方法而得 到了关于连续统与选择公理的独立性成果，尔后的研 究结果推陈出新，大量涌现在同一时代，美国数学 家 L . A.Zadeh提出了Fu
3、zzy集理论, 以及 20世纪80年 代波兰数学家Z . Pawlak发表了Rough集理论，这两种 理论区别于以往的集合论， 是一种新的模糊集理论， 受到了学术界的重视和青睐，取得了喜人成果还有 多位著名学者也为集合论的发展作出了重要贡献 集合论在计算机科学、人工智能领域、逻辑学及语言 学等方面都有着重要的应用对子从事计算机科学的 工作者来说，集合论是不可缺少的理论知识，熟悉和 掌握它是十分必要的集合(直观描述) 具有某种属性的对象总体(通常用大写字 母表示，如A,B等)，这些对象称为其元 素 (通常用小写字母表示，如x,y等). x是A的元素记为: xA (读作x属于A) x不是A的元素记
4、为: xA (读作x不属于A) 集合的基本特性是，对于给定的集合A， 任何对象x, xA与xA中有且只有一个 成立. 小于10的正奇数集合A=1, 3, 5, 7, 9 表面看起来不相干的元素所构成的集合 a, 2, Fred, New Jerseg 集合B=x | x是小于10的正奇数 上例中集合A=B集合相等和子集合 集合相等：如果两个集合A和B有同样的 元素组成，就说集合A和B相等，记作A= B或B=A. 子集合: 如果集合B的元素都是集合A的 元素，B叫做A的子集合(简称子集). 记作 BA (读作B包含于A)，或AB (读作A包 含B). 命题： A= B当且仅当AB且AB.子集的表
5、示方式和全集 设A是一个集合,其子集B通常用下面的形 式表示：B=xA | P(x), 其中P(x)表示x 在B中所要满足的条件 空集：不含任何元素的集合叫做空集,用 符号表示,空集是任何集合的子集： =xA | x x 在数学的讨论中，常常涉及到的是某个 固定集合的子集，例如，实数的子集. 这 个固定集合叫做全集. 一般用E表示.集合的基数 定义4 令S为集合。若S中恰有n个不同元 素，n是非负整数，就说S是有限集合， 而n是集合S的基数，用| S |表示。 例 令A为小于10的正奇数集合，则| A | = 5 空集没有元素，所以| | = 0 定义5 如果一个集合不是有限的，就说 它是无限
6、的。幂集合 很多问题都要检查一个集合的元素的所 有可能的组合，看它们是否具有某种性 质。为了考虑集合元素所有可能的组合 ，我们构造一个新集合，它以S的所有子 集作为它的元素。幂集合 定义6 已知集合S, S的幂集合是集合S所 有子集的集合，用P(S)表示。 例 集合0, 1, 2的幂集合是 P(0,1,2=,0,1,2,0,1,0,2 ,1,2,0,1,2。 空集的幂集合是什么？集合的幂集 合是什么？幂集合 空集的幂集合是什么？集合的幂集 合是什么？ P()= P()=, 如果一个集合有n个元素，那么它的幂集 合有2n个元素。2. 笛卡尔积 定义7 有序n元组（a1,a2,an)是以a1为第
7、一个元素，a2为第2个元素，an为第n 个元素的有序组。 2元组特称为有序偶。 集合A和B的笛卡尔积C=AB表示所有有 序偶(a,b)的集合, 其中aA, bB. 也就是 AB=(a,b) | aA且 bB笛卡尔积 例 令A为某大学所有学生的集合，B表示 该大学开设的所有课程的集合。A和B的 笛卡儿积AB是什么？ 解：笛卡儿积AB由形为(a, b)的所有有 序偶组成，其中a是学生，而b是该校开 的一门课。集合AB可以用来表示该校 学生选课的所有可能情况。笛卡尔积 例 A=1,2, B=a, b, c, AB=? 上例中AB是否等于BA笛卡尔积 定义9 集合A1, A2,An的笛卡儿积用 A1A
8、2An表示，这是有序n元组 (a1,a2,an)的集合，其中对于i=1,2,n， aiAi。 什么是笛卡儿积ABC，其中 A=0,1,B=1,2,C=0,1,2?笛卡尔积 什么是笛卡儿积ABC，其中 A=0,1,B=1,2,C=0,1,2? 解： ABC=(0,1,0),(01,1),(0,1,2),(0,2,0),(0,2, 1),(0,2,2),(1,1,0),(1,1,1),(1,1,2),(1,2,0),(1,2, 1),(1,2,2)3. 集合运算 集合的并 集合的交 集合的差运算和余(补)运算 集合运算的性质集合的并 集合A和B的并是由A或B的所有元素组成 的集合, 记为AB, 也
9、就是 AB=x | xA或xB 集合并运算的性质： 交换律 A B= B A 结合律A (B C)= (A B) C集合的交 集合A和B的交是由所有A和B的公共元素 组成的集合, 记为A B, 也就是 A B=x | xA且xB 集合交运算的性质： 交换律 A B= B A 结合律A (B C)= (A B) C集合的差运算和余(补)运算 集合的差运算：由集合A中不在集合B中的元 素所组成的集合叫做集合A与集合B的差，记 作A-B, 也就是 A-B=xA | xB 设全集为U，集合AU, U-A叫做A关于U的补 集，当U是公认的时候，简称为A的补集，记 为集合相等集合相等的证明 可以考虑用成员
10、表来证明集合相等。我 们考虑一个元素可能属于的集合的每一 种组合，并证明在同样的集合组合中的 元素属于等式两边的集合。用1表示元素 数属于一个集合，用0表示元素不属于一 个集合。集合相等的证明 例 用成员表证明 A(BC)=(A B) (AC)集合的计算机表示 无序存储。 缺点：做集合的并集、交集和差集等运算会 浪费时间，因为这些运算需要大量元素检索集合的计算机表示 利用全集元素的一个任意排序存放元素 以表示集合。 假定全集U是有限的，首先为U的元素任意 规定一个顺序，例如a1,a2,an。于是可以用 长度为n的位串表示U的子集A：如果ai属于 A，则位串中第i位是1；如果ai不属于A，则 位
11、串中第i位是0。集合的计算机表示 例 令U=1,2,3,4,5,6,7,8,9,10，而且U的 元素从小到大排序，即ai=i。表示U中所 有奇数的子集、所有偶数的子集和不超 过5的整数的子集的位串分别是什么？ 解：U中所有奇数的子集即1,3,5,7,9的 位串，第1，3，5，7，9位为1，其他位 位0，即 10101 01010集合的计算机表示 例 集合1,2,3,4,5和1,3,5,7,9的位串分别是 11111 00000和10101 01010，用位串求出它们 的并集和交集。 解：这两个集合的并集合的位串是 11111 00000 10101 01010 = 11111 01010，表示
12、集合1,2,3,4,5,7,9 这两个集合的交集的位串是 11111 00000 10101 01010 10101 00000，表示集合1,3,56. 集合的势 等势的概念 自然数和有限集 可数集 幂集 不可数集等势的概念 如何说清有限集: 自然数的构造 数数的澄清和推广-等势: 如果两个集合 A和B之间存在双射,就说A与B是对等的 或等势的.记做AB. 等势的性质: 1. 自返性: AA; 2. 对称性: ABBA; 3. 传递性: AB, BCAC.自然数和有限集 自然数: 0:=, 1:= 递归定义: n+1:=0,1,n 自然数集: N=0,1, N+ =1,2, 有限集: 如果集合
13、A与某个自然数对等， 就说A是有限集. 约定: 空集是有限集 两个不同自然数是不对等的. 自然数可以 看成是有限集势的代表可数集(I) 无限集: 不是有限集的集合叫做无限集 可数集: 与自然数集N等势的集合叫做可 数集 命题1. 有理数集Q=m/n | mZ, nN+是 可数的 证明：利用高度h=|m|+n 命题2. 可数集的子集是有限的或可数的可数集(II) 命题3. 有限多个或可数多个可数集的并 集仍然是可数的 证明: 次对角排列法. 事实1. 任何无限集都有可数子集 事实2.设A是无限集, B可数集,则ABB 说明: 有些数学书或文章中把有限或可数 集一起叫做至多可数的(at most countable) 或可列的(enumeratable),甚至就叫可数的不可数集 不可数集: 不对等于N的无限集叫做不可 数的 连续统势: 与P(N)对等的集合叫做具有连 续统的势 事实3. F=f: N0,1与P(N)等势 事实4. X=AP(N) | kN, nk, nA 是可数的 事实5. 在二进制中1=0.11.(1循环)
