中国科学技术大学：《离散数学》课程教学资源（PPT课件讲稿）第四章 有限集和无限集

有限集和无限集 ■有限集合 口元素的个数称为该集合的基数; 口满足包含排斥原理。 ■无限集合 口元素无限多,如:自然数集合N、整数集|、实数集R等。 ■问题: 口对于这样的集合有没有基数呢? 口如果有,基数是多少? 口无限集合之间有无大小的差别? 本章主要借助于函数讨论集合的所谓“大小”问题。这里 用到自然数集合这个重要的概念讨论无限集

1 有限集和无限集 ◼ 有限集合  元素的个数称为该集合的基数；  满足包含排斥原理。 ◼ 无限集合  元素无限多，如：自然数集合N、整数集I、实数集R等。 ◼ 问题：  对于这样的集合有没有基数呢？  如果有，基数是多少？  无限集合之间有无大小的差别? ◼ 本章主要借助于函数讨论集合的所谓“大小”问题。这里 用到自然数集合这个重要的概念讨论无限集

基本概念 定义41一个集合S与集合Nn={0,1,2,…n-1},如 存在一一对应函数f:Nn→S,则称S是有限集合, 并称其有基数n,如果S不是有限集合,则称为无 狠集合。 ■说明 口由集合的元素个数来定义; 口由于量变引起的质变; 口它们中的一种性质都不能随意扩展到另一个集合中

2 基本概念 ◼ 定义4.1 一个集合S与集合Nn={0,1,2，…n-1}，如 存在一一对应函数 f : Nn→S，则称S是有限集合， 并称其有基数n，如果S不是有限集合，则称为无 限集合。 ◼ 说明：  由集合的元素个数来定义；  由于量变引起的质变；  它们中的一种性质都不能随意扩展到另一个集合中

基本概念 定义42集合A和集合B的元素间,如果存在一一对 应的关系,则说A和B是等势( Cardinality)的,记 作A~B 0123….n 0149..n2 说明 口对有限集来说,两集合等势即说明两个集合的元素的 个数相同; 口集合的势: Cardinality of Sets

3 基本概念 定义4.2 集合A和集合B的元素间，如果存在一一对 应的关系，则说A和B是等势（Cardinality）的，记 作A~B ◼ 说明：  对有限集来说，两集合等势即说明两个集合的元素的 个数相同；  集合的势：Cardinality of Sets

③ Hilbert旅馆 问题 口一旅店有无穷多个房间,各房间编号依次为: #1,#2,#3 口现所有房间已住满了人,这时来了一位新客人要求住 店,怎么安排?

4 Hilbert旅馆 ◼ 问题：  一旅店有无穷多个房间，各房间编号依次为： #1， #2， #3，……  现所有房间已住满了人，这时来了一位新客人要求住 店，怎么安排？

③ Hilbert旅馆 解决方法: 口店主人把#1房的客人移到#2房,把#2房的客人移到#3 房,依此类推,新客人就住进了已腾空的#1房间 ■接着,又来了第二位新客人,旅店主也照此办理, 使第二位客人得到落实。 紧接着,来了一个有无限多个游客的旅游团要求 定住房间,怎么办? 口店主人把#房的客人移到#2房,把#2房的客人移到井4 房,#3房的客人移到#6房,等等,所有奇数号的房间 全部腾空了,新的无限多个客人就全住进了旅店

5 Hilbert旅馆 ◼ 解决方法：  店主人把#1房的客人移到#2房，把#2房的客人移到#3 房，依此类推，新客人就住进了已腾空的#1房间； ◼ 接着，又来了第二位新客人，旅店主也照此办理， 使第二位客人得到落实。 ◼ 紧接着，来了一个有无限多个游客的旅游团要求 定住房间，怎么办 ？  店主人把#1房的客人移到#2房，把#2房的客人移到#4 房，#3房的客人移到#6房，等等，所有奇数号的房间 全部腾空了，新的无限多个客人就全住进了旅店

紧接着发生了更为严重的情况,来了无穷多个具有无穷多 名游客的旅游团,怎么办? 口第一个旅游团客人按如下房间编号住 3.32.3 3 口第二个旅游团客人住的房间编号为 5.52.5 口接着是

6 ◼ 紧接着发生了更为严重的情况，来了无穷多个具有无穷多 名游客的旅游团，怎么办？  第一个旅游团客人按如下房间编号住  第二个旅游团客人住的房间编号为  接着是 3, 3 2 , 3 3 ,  , 3 n ,  5, 5 2 , 5 3 ,  , 5 n ,  7, 7 2 , 7 3 ,  , 7 n , 

■这样不仅安排了无穷多个旅游团的住宿,而且还 空出了很多房间! 无限多个房间可住无穷多个具有无穷多个游客的 旅游团! 对于一个无穷集合,向其中添加有限个元素,甚至 “无穷多个”元素得到的新集合,其势不变 一个集合A,若真子集B:BCA,B与A等势,则A 一定是无限集

7 ◼ 这样不仅安排了无穷多个旅游团的住宿，而且还 空出了很多房间！ ◼ 无限多个房间可住无穷多个具有无穷多个游客的 旅游团！ 对于一个无穷集合，向其中添加有限个元素，甚至 “无穷多个”元素得到的新集合，其势不变 一个集合A，若真子集B ：B⊂A，B与A等势，则A 一定是无限集

Hilbert旅馆的内涵 口如果把自然数集合中的元素数量记为z,那么z不管加 上多大的数,乘以多少,它始终是一个无穷,不会变 大或变小。 ■问题:自然数和平方数谁要更多 口用普通人的眼光来看,前10个数字中不过4和9两个数, 前100个数中也不过10个; 口再往后,平方数在自然数中所占的比例越来越小; 口但是从另一个角度看,每一个自然数都对应着一个平 方数; 口所以,自然数和平方数是一样多的,这“一一对应”的 规则也就是判断集合是否一样大的标准

8 ◼ Hilbert旅馆的内涵  如果把自然数集合中的元素数量记为z， 那么z不管加 上多大的数，乘以多少，它始终是一个无穷，不会变 大或变小。 ◼ 问题：自然数和平方数谁要更多。  用普通人的眼光来看，前10个数字中不过4和9两个数， 前100个数中也不过10个；  再往后， 平方数在自然数中所占的比例越来越小；  但是从另一个角度看，每一个自然数都对应着一个平 方数；  所以，自然数和平方数是一样多的， 这 “一一对应” 的 规则也就是判断集合是否一样大的标准

任何一个有限集合不能与其真子集等势。 另一种有限集、无限集的定义方法; 定义:如果存在一一对应的fS→S,使得f(S)cS, 即fS)是S的真子集,则S是无限集合,否则S是有 限集合

9 任何一个有限集合不能与其真子集等势。 ◼ 另一种有限集、无限集的定义方法； ◼ 定义：如果存在一一对应的f: S→S，使得f(S)⊂S， 即f(S)是S的真子集，则S是无限集合，否则S是有 限集合

定理4.1自然数集N是无限集。 ■证明:设函数fN→N,定义为f(x)=2X,显然是 对应,而且f(N)cN,因此N是无限集。 定理4.2常数集R是无限集。 ■证明:设函数R→R,为 显然f(x)是一一对应的 x+1x≥0而且显然有f(R)cR,因 f(x)= 0 此R是无限的。 X 4 10

10 定理4.1 自然数集N是无限集。 ◼ 证明：设函数f: N→N，定义为f(x)=2x，显然f是一 一对应，而且f(N)⊂N ，因此N是无限集。 定理4.2 常数集R是无限集。 ◼ 证明：设函数f: R→R，为 显然f(x)是一一对应的， 而且显然有f(R)⊂R，因 此R是无限的