离散数学教学课件-ch6.pptVIP

第二部分 集合论 主要内容 集合概念补充（广义并、广义交） 集合运算补充（对称差） 包含容斥原理 集合的基数 一、集合概念补充 全集 E 集合A?E，则A的绝对补集~A=E-A A的全体子集构成的集合称为A的幂集，记作P(A), PA, 2A 关于广义运算的说明 (1) ??=?，??无意义 (2) 单点集{x}的广义并和广义交都等于x 注：引入广义运算的意义 可以表示无数个集合的并、交运算，例如 ?{{x} | x?R}=R 这里的 R 代表实数集合. 运算的优先权规定 1 类运算：广义运算和?运算， 运算由右向左进行 2 类运算：初级运算?, ?, ?, ?， 优先顺序由括号确定 混合运算：1 类运算优先于2 类运算 3. 对称差 A?B = (A?B)?(B?A) =(A∪B)?(A∩B) 定理 设集合S上定义了n条性质，其中具有第 i 条性质的元素构成子集Ai, 那么集合中不具有任何性质的元素数为 包含容斥原理特殊情形 设A, B为有限集合，则|A?B|=|A|+|B|?|A?B| 对于有限集合来说，集合的基数就是集合中元素的个数. 对于无限集合，如何计数呢？ “一家拥有无穷多个客房的旅店，每个房间恰能住一名旅客，并已经客满.” 当日又有一名旅客投宿，店主能否接纳？ 他让1#房间的旅客挪到2#房间， 让2#房间的旅客挪到3#房间，? 如此下去，可腾出1#房间给新来的旅客. 这说明Z+={1, 2, 3,?}与N= {0, 1, 2, 3,?}具有同样多的元素. 可N明明比Z+多一个元素！ 这一问题困扰数学家多年，直到十九世纪七十年代，康托尔研究无限集合的度量问题时，提出“集合基数”的概念，这个问题才得到彻底解决. 定义1. 度量集合大小的数称为集合的基数（势）, 记为|A|. 定理1. 设A和B为集合, 则|A|=|B|, |A||B|或|A||B|. 定义2. 若集合A到B能建立一个双射函数，则称集合A与集合B等势. 例1. 证明：N与Z+等势. 思路：构造双射函数：f(x)=x+1, ?x?N 例2. 证明：R与其真子集(0,1)等势. 定理2. 一个集合是无限集合当且仅当它存在与其等势的真子集. 例1，例2分别说明N和R是无限集合. 推论：任何有限集均不能与其真子集等势. 抽屉原理：若将大于等于n+1个物体放入n个抽屉中，则至少有一个抽屉中放了两个或两个以上的物体. 由于无限集合无法用元素的个数表示其基数，为此我们引入如下基数记号： 定义3. 与N等势的集合称为可数无限集合，简称可数集. |N|=?0(阿列夫零). 可数集的特点：集合中所有元素可以排序. 注：Z, Q, N?N是可数集. 定义4. 不是可数集的无限集统称为不可数集. 定义5. |R|=?1, 称作连续基数. 定理3. 设A是任意有限集合，则|A| ?0 ?1. 定理4. ?0是最小的无限集基数. 定理5.（Cantor定理）对任何集合A都有 |A||P(A)|. 注：此定理说明不存在最大的基数. 连续统假设：不存在任何一个基数α，使得 ?0α?1. 广义连续统假设：对于任何一个无限集A，不存在任何一个基数α，使得|A|α|P(A)|. 新春晓 信息时代到，处处有电脑. 夜来打字声，程序知多少？ 程序时时新，落花处处飘. 它们同为?0，数数便知道. 计算机，靠程序，它的本事知底细. 程序都是符号串，理应是个可数集. * 注：n元集的幂集有2n个元素. 第六章 集合代数 二、集合的运算补充 1. 广义并 A的元素的元素构成的集合，记为∪A 例：设A={{a,b,c},{a,c,d},{a,e,f}},B={a,{c,d}} 则∪A={a,b,c,d,e,f} ∪B=a∪{c,d} 若A={A1, A2,?, An}, 则∪A= A1∪A2∪?∪An 2. 广义交 非空集合A的所有元素的公共元素构成的集合，记为∩A 若A={A1, A2,?, An}, 则∩A=A1∩A2∩?∩An 例1 A={{a},{a,b}}，计算??A?(??A???A). 解： ??A?(??A???A) = ?{a,b}?(?{a,b}??{a})