当前位置： >>
离散数学无穷集合及基数
集合与图论第5节 无穷集合及其基数引言什么是无穷集合? 无穷集合之间能否比较大小? 无穷集合有什么特殊性质?本部分内容主要是利用映射，尤其是利用双 射为工具，建立可数集、不可数集，并研究它们 的一些性质，从而得到无穷(限)集合的特征性质。 然后将有穷集合元素的个数的概念推广到无穷集 合，建立无穷集合的基数的概念。1/29集合与图论第4节 无穷集合及其基数主要内容：? ? ? ? ? 可数集 不可数集 基数及其比较 康托-伯恩斯坦定理 悖论与公理化集合论2/29集合与图论什么是集合的基数？集合的基数亦称作集合的势。 粗略的说，就是一个集合的“规模”，它的“大 小”，或者更确切地说，它有多少个元素。 通俗的说，集合的势是量度集合所含元素多少的 量。集合的势越大，所含的元素越多。 很明显，如果集合中只有有限个元素，我们只要 数一数它有多少个可以了，这时集合的基数就是其中 所含元素的个数。 值得注意的是无限集，它所含的元素有无穷多 个， 这时怎样去数？ 为了解决这个问题，我们首先从伽利略“悖论” 3/29 说起。集合与图论伽利略“悖论”1638年意大利的天文学家伽利略发现了下面 的问题： N+={1,2,3,…,n,…}与N(2)={1,4,9,…,n2,…} 这两个集合，哪一个的元素更多一些？ 一方面，凡是N(2)的元素都是N+的元素，也就 是说N(2)?N+，而且由于2，3，5等元素都不在N(2) 中，所以N(2)?N+。这样看来，N+中的元素要比 N(2)中的元素要多。4/29集合与图论伽利略“悖论”但另一方面，对于N+中的每个元素都可以在N(2) 中找到一个元素与之对应，这样看来，N(2)中的元素 不比N+中的元素要少。那么到底N+与N(2)中所含元素的个数是否一样呢 ？如果是，那么就有部分=整体？然而按照传统，部分怎么能等于全体呢？这就 是伽利略“悖论”，它不仅困惑了伽利略，还使许 多数学家亦束手无策。5/29集合与图论一一对应与可数集1874年，Cantor注意到伽利略”悖论”。 在1874年到1897年间完全解决了这个问题。 Cantor详细地分析了断定有限集合的元素多少 的方法，即采用数数的方法。他认为“数数的过程” 就是作“一一对应的过程”。 Cantor认为这种“一一对应”的方法不仅适用 于有限集，也适用于无限集。 他牢牢地抓住这个原则，抛弃了部分必定小于 全体的教条，经历了大约23年之后，他才冲破了传 统观念的束缚，革命性的解决了伽利略“悖论”。 Cantor认为在N+与N(2)之间存在着一一对应(即 双射)，因此N+与N(2)的元素个数是相等的。6/29集合与图论一一对应与可数集定义4.1 设A，B是集合，若存在着从A到B的 双射，就称A和B等势(或对等)，记作A≈B。Cantor把自然数集N+称为可数集(或可列集)， 这是因为它的元素可以一个一个的数出来。 凡是与自然数集N+等势的集合，它们的元素 通过一一对应关系，也都可以一个一个的数出来， 因此： 定义4.2 凡是与自然数集N+等势的集合，称为 可数集(或可列集)。7/29集合与图论一一对应与可数集显然，N也是可数的。 Cantor以此为出发点，对无限集合进行考察，他 发现下面的集合都是可数集： (1) ODD = {x| x?N，x是奇数}≈N F：N?ODD F(n)=2n+1 （F： N+?ODD F(n)=2n-1） (2) EVEN = {x| x?N，x是偶数}≈N F：N?EVEN F(n)=2n （F： N+?EVEN F(n)=2(n-1)） (3) N(n)={x|x=mn，m，n?N }≈N F：N?N(n) F(m)= mn8/29集合与图论 (4) N×N≈N一一对应与可数集9/29集合与图论 (5) Z≈N一一对应与可数集F: Z?N F(n)=2n (n≥0)F(n)=2|n|-1 (n&0)(6) Z×Z≈N10/29集合与图论一一对应与可数集Cantor在解决了Z×Z≈N后，用类似的思想解 决了Zn≈N。在这种想法之下，Cantor得到了一个令人惊异 的发现：Q≈N。 并且利用他独创的“折线法”，巧妙的建立了Q与 N的一一对应。为建立N到Q的双射函数，先把所有形式为p/q (p，q为整数且q&0)的数排成一张表。显然所有的有 理数都在这张表内。 11/29集合与图论一一对应与可数集12/29集合与图论一一对应与可数集注意：以0/1作为第一个数，按照箭头规定 的顺序可以“数遍”表中所有的数。但是这个计 数 过程并没有建立N到Q的双射，因为同一个有理数 可能被多次数到。例如1/1，2/2，3/3，…都是有理 数1。 为此我们规定，在计数过程中必须跳过第二 次以及以后各次所遇到的同一个有理数。如1/1被 计数，那么2/2，3/3，…都要被跳过。表中数p/q上 方的方括号内标明了这个有理数所对应的计数。 这样就可以定义双射函数f：N→Q，其中f(n) 是[n]下方的有理数。从而证明了N≈Q。 13/29集合与图论Cantor对角线法与不可数集正是由于这一发现，使得他甚至猜想R也是可数 集，并且着手去证明它。他没有得到预期的结果， 却又作出了更伟大的发现。 Cantor利用它著名的对角线法，证明了[0,1]是不 可数集，在这个基础上证明了R也是不可数的，甚至 于Rn也是不可数的。 注：(1)如果集合X不是可数集且X不是有限集，则 称X为不可数集。 (2)可数集与不可数集是对无穷集合而言的，有 限集既不称作不可数集合也不称作可数集。14/29集合与图论Cantor对角线法与不可数集定理4.1 区间[0,1]中的所有实数构成的集合是不 可数集。证 区间[0,1]中每个实数，都可以写成十进制无限 位小数形式0.a1a2a3a4...，其中每位ai?{0,1,2,...,9}。约定每个有限位小数后均补以无限多0。 假定定理不成立，于是[0,1]中全体实数可排成一 个无穷序列:a1,a2,a3,...,an,...。15/29集合与图论Cantor对角线法与不可数集每个ai写成十进制无限小数形式排成下表 a1=0.a11a12a13a14...a1n... a2=0.a21a22a23a24...a2n... a3=0.a31a32a33a34...a3n... 其中aij?{0,1,2,...,9} ....................... an=0.an1an2an3an4...ann... .......................构造一个新的小数 b=0.b1b2b3...bn...，其中：若ann=5，则bn≠5； 若ann≠5，则bn=5，n=1,2,3,… 显然，b?[0,1]，但?n?N，b?an，矛盾。16/29集合与图论Cantor对角线法与不可数集这说明[0,1]是不可数集，从而证明了并非一切 无限集合都是可数集，无限集合也是有区别的。 Cantor首次对无限集合从“定量”方面进行了 深入研究，使人们深刻认识到集合N与R有本质不同。 Cantor用对角线元素来构造小数x*的方法称为 Cantor对角线法。 Cantor所创造的这一方法是一个强有力的证明 方法，在函数论和计算机科学中有许多应用。在计 算的复杂性理论和不可判定问题中，对角线法也是 为数不多的几个重要方法之一。17/29集合与图论无限集合的性质性质1 集合A为可数集的充分必要条件是A的全 部元素可以排成无重复项的序列 a1,a2,...,an,... 性质2 无限集A必包含可数子集。 性质3 可数集的任一无限子集也是可数集。 性质4 从可数集A中除去一个有限集M，则A\M 仍是可数集，即A≈A\M。 性质5 设M是一个无穷不可数集，A为M的至多 可数子集(即A有穷或可数)，则M≈M\A。 定义4.3 凡能与自身的一个真子集对等的集合 称为无穷集合，或无限集合。 18/29集合与图论集合的基数如果要对任意的集合谈论它们中元素的“ 个数”，这就需要把有限集合里元素“个数”的 概念推广到无限集合中，要求下一个定义对任何 集合都适用。 集合的基数或集合的势是集合论中基本概 念之一，在朴素集合论体系中讨论基数的概念， 只能从几条规定或公理出发。 设A为任意一个集合，现在规定用cardA表示 A中的元素“个数”，并称cardA为集合A的基数， 并再作以下五条规定：19/29集合与图论集合的基数(1) 对于任意的集合A和B，规定 cardA=cardB当且仅当A≈B。 (2) 对于任意的有限集合A，规定与A等势的自 然数n为A的基数，记作cardA=n。 (3) 对于自然数集合N，规定cardN=?0?? (读作阿列夫零)。 (4) 对于实数集合R，规定cardR=?( ??读作阿列 夫)。 (5) 将0，1，2，…，?… ，?，0??都称作基数， 其中0，1，2，…称作有穷基数，而?…?，0??称作无 穷基数。20/29集合与图论集合的基数定义4.4 集合A的基数是一个符号，凡与A等势 的集合都赋以同一个记号，集合A的基数记为|A|， 也记作cardA。 定义4.4’ 所谓集合的基数是指所有与该集合等 势的集合所构成的集族的共同性质。(冯 诺伊曼) 定义4.4’’ 集合的基数是集合的这样一种特性， 当把集合里元素固有特点抽出，以及把各元素在集 合中的次序不顾之后，仍然保留下来的特性，就叫 做基数。21/29集合与图论Cantor连续统猜想定义4.5 凡与集[0,1]对等的集称为具有“连续 统的势”的集，或简称连续统。 实数集R、无理数之集都是连续统。 Cantor猜想(连续统猜想，CH)： 在 ?0??与???之间是否还有别的基数？ 1938年，K.哥德尔证明了CH对ZFC公理系统 （见公理集合论)是协调的。 1963年，P.J.科恩证明CH对ZFC公理系统是独 立的。 这样，在ZFC公理系统中，CH是不可能判定 真假的。这是20世纪60年代集合论的最大进展之 22/29 一。集合与图论基数及其比较定义4.6 集合A的基数与集合B的基数称为是相 等的，当且仅当A≈B。 定义4.7 ?，?是任意两个基数，A，B是分别以 ?，?为其基数的集。如果A与B的一个真子集对等， 但A却不能与B对等，则称基数?小于基数?，记为 ?&?。 规定?≤?当且仅当?&?或?=?。 规定?&?当且仅当?&?。 规定?≥?当且仅当?&?或?=?。23/29集合与图论基数及其比较规定?≤?当且仅当存在单射f: A?B。 规定?&?当且仅当存在单射f: A?B，且不存在A 到B的双射。 无穷集合的基数也称超穷数，超穷数也可以比较 大小。于是，像下面这些句子是有意义的：“平面上 的点多还是平面上的圆多？”，“集合[0,1]中的数比 自 然数集N中的数多”，“有理数和自然数一样多。” 问题：无穷基数有多少？ 有没有最大的无穷基数？定理4.2 (康托)对任一集合M，?M?&?2M?。24/29集合与图论康托-伯恩斯坦定理在有限数大小的比较中，对任取两个有限数（非 负整数）m，n，下面三式有且仅有一式成立: m&n，m=n，m&n。那么，对任两个无限数?，?，下面三个式子是否 也有且仅有一个成立呢? ?&?，?=?，?&?。 答案是肯定的。25/29集合与图论康托-伯恩斯坦定理设Ａ是一个基数为?的集合，Ｂ是基数为?的集合。如果?=?，那么?&?，?&?都不能成立。若?&?，?&?同时成立，则从A到B的每个单射都不 是满射，而从B到A的每个单射都不是满射。 我们能证明这是不可能的，从而?&?与?&?不能同 时成立。 定理4.3 (康托-伯恩斯坦)设A，B是两个集合。 如果存在单射f: A?B与单射g: B?A，则A与B对等。 只要能利用f与g直接建立一个从Ａ到Ｂ的一个一 一对应即可。 26/29集合与图论 推论 设?,?,?为任意三个基数。如果?≤?， ?≤?，则?≤?。 定理4.4 (E. Zermelo，策梅罗) 设?与?为任意两 个基数，则以下三个式子?=?，?&?，?&?中恰有一 个式子成立。27/29集合与图论悖论与公理化集合论首先从朴素集合论蕴含的悖论谈起。所谓悖论是指这样一个命题A，从A出发可以导出 一个语句B，然而若假定B真，则可以推知B不真；若假 定B不真，又可以推知B真。 Cantor悖论(最大基数悖论)(1899) 按Cantor的集合概念，可以有所有集合的集合U。 一方面，由Cantor定理得到|U|&|P(U)|； 但另一方面，U是所有集合组成的集合，所以对 任一X?P(U)， X?U 且X是一个集合，从而X?U， 因此，P(U)?U ，所以|U|≥|P(U)|矛盾。28/29集合与图论 (1902年)罗素悖论令S = { x | x?x } 则S?S ? S?S ? S?S S?S ? S?S1919年罗素将其悖论通俗化： 某一村落中的一个理发师，他只替村中所有不 给自己理发的人理发，到底他是否替自己理发？ Cantor悖论和罗素悖论只涉及集合的概念，看 来Cantor的集合概念蕴含着矛盾。为了消除悖论， 人们建立集合论的公理系统，在保留概括原则种的 合理因素，对造集的任意性加以限制。在公理集合 论中已出现的悖论都消掉了。29/29
离散数学集合复习题_数学_高中教育_教育专区。第 3 章 集合一、选择题(每题 ...离散数学无穷集合及基数 29页 1下载券喜欢此文档的还喜欢 2011年全国自考复变函...《离散数学》题库及答案_理学_高等教育_教育专区。可以用来复习离散数学 ...答:(4)(空集没有任何元素,且是任何集合的子集) 18、若集合 S 的基数|S|...离散数学王元元习题解答 (5)_研究生入学考试_高等教育_教育专区。王元元主编,...有限集合中元素的个数称为基数(cardinality) (无穷集合的基数概念将在 以后重新...《应用离散数学》方景龙版课后习题答案《应用离散数学》方景龙版课后习题答案隐藏&& §3.6 集合的等势与基数 习题 3.6 1. 判断下列集合是否为无限可数集,若是,给...? A?B=A 3 《离散数学》讲稿 分别对条件(1)到...本节主要内容 集合的基数与有穷集合 包含排斥原理 ...R}, cardB=|B|=0 无穷集的实例: N, Z, Q,...2005级-离散数学(1)教案-李占山,于海鸿,卢欣华_...相关概念 2.集合的分类:有穷集(有限集) 、无穷集...2.集合的基数 集合基数的定义,表示形式; 两个集合...离散数学第一讲discrete1_理学_高等教育_教育专区。...4. 集合论的发展?看待无穷集合的两种观点:实无穷...?超穷基数和超穷序数 ?朴素集合论的悖论:罗素...离散数学基础_理学_高等教育_教育专区。离散数学基础...4. 集合论的发展看待无穷集合的两种观点:实无穷与...超穷基数和超穷序数 朴素集合论的悖论:罗素悖论 ...《离散数学》教案第一章 集合与关系集合是数学中最...1870 年前后,他关于无穷序 列的研究导致集合论的...1932 年康脱也发表了关于最大基数的悖论。集合论的...离散数学期末复习_教育学_高等教育_教育专区。离散...1870 年前后, 他关于无穷序列的研究导致集合论的...集合的表示方法、集合的基数 2. 集合的包含、相等...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。登录后才能写笔记
登录后才能写评论
登录后才能提问
教学录像主讲人
本单元其他资源
本模块知识点
本单元主讲教师
主办单位：高等教育出版社&&&&&&&&京ICP备号-2&&&&&&京公网安备-2
中国大学精品开放课程适用于《中华人民共和国著作权法》
高等教育出版社享有中国大学精品开放课程信息网络传播的专有使用权 未经书面允许，请勿转播三亿文库包含各类专业文献、高等教育、各类资格考试、中学教育、行业资料、幼儿教育、小学教育、专业论文、????????1?? ?????_??????05等内容。
　一个具有市场杀伤力的购买理由通常由这四个关键点构成,想 让你的产品成为爆款,就要解决这四个关键。 一个新产品上市前,经营者必须能够清楚的回答两个问题: 一是... 　【辅导步骤】 辅导步骤】 一、故事引入 现在,老师要给同学们出一算术题:1+1 等于几?(板书:1+1=?)对,在数学上 1+1 是等于 2,但在生 活中,有时 1+1... 　如皋市长江镇郭元小学 邹志梅 【摘要】在本篇论文中,笔者结合自身以往的工作经验,列举了几种不算 成功的“开学第一课”,阐述了开学第一课的重要性,并由此引出... 　2、想一想:小明有什么烦心事呢? (热心组织活动,同学们却不乐意参加。 ) 3、出示课题:组织活动,不受欢迎,怎么办? 二、思考辨析 1、说一说: 1)你曾经有过... 　我们只有做好团队的建设工作, 才能更好地吸引优秀人才、留住优秀人才、激发员工的潜能力、早就 良性的竞争环境,使 1+1&2 不只是一句口号,而是一个实实在在的 ... 　史宁中教 授说,如果在整数范围内,最小的一位数应当是-9,而不是1,更不 是0。 (涉及比较的还有“最小的偶数是不是0?”,也需要说清楚范 围。第二,要解决... 　例如,当系统有一点小问题时,中新旅不能自己解决,而只能完 全依赖于开发方,但开发方有时不能及时赶到,导致系统不能及时得到修复。甚至更简单的 事,例如,网上的... 　发表:澎湃新闻 特约撰稿:王缉宪
1993 年到香港教书,一呆就是二十几年。香港已经成了我的第二故乡。这二十几 年 ...(蟹老板Workshop)
(副刊游侠)
第三方登录：判断：若集合A是集合B的真子集,则这两个集合不可能等势._百度知道
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。
判断：若集合A是集合B的真子集,则这两个集合不可能等势.
我有更好的答案
是错的判断是否等势,-1}B -&gt，主要看能否找到一个 一 一对应的映射关系如果能找到：A = {1}B = {1，则两个集合等势例如
元素个数不相等，如何一一映射？
有些等式是有2个解得，比如平方
采纳率：51%
来自团队：
为您推荐：
其他类似问题
真子集的相关知识
等待您来回答}