西安电子科技大学：《离散数学》课程教学课件（题解）第四章 函数与无限集合 4-3 可数与不可数集合

西安电子科技大学离散数学软件学院第二篇集合论第4章函数与无限集合4.1函数的概念第21课时第22课时4.2复合函数和逆函数第23课时4.3可数与不可数集合第24课时4.4集合基数的比较

西安电子科技大学 离散数学 软件学院 第二篇 集合论 第21课时 4.1 函数的概念 第4章 函数与无限集合 4.3 可数与不可数集合 4.2复合函数和逆函数 4.4 集合基数的比较 第22课时 第23课时 第24课时

西安电子科技大学集合的基数$4.3.1软件学院度量集合大小的数称为集合的基数，记为A/基数有限集合的大小可以用集合中元素的个数来表示，但对于无限集合来讲元素的个数变得毫无意义，因为无限集合中元素的个数是无限的，给尔伯特（e的》宝馆

西安电子科技大学 集合的基数 软件学院 基数 §4.3.1 1 2 3 有限集合的大小可以用集合中元素的个数来表 示，但对于无限集合来讲元素的个数变得毫无 意义，因为无限集合中元素的个数是无限的。 度量集合大小的数称为集合的基数，记为|A|

西安电子科技大学S4.3.1集合的基数软件学院家两个集合A和B，如果A和B的基数相同，称A与B等势，记为A~B。『定理』等势是任何集合族上的等价关系。『定理』（Zemelo三歧性定律）设A和B是任意集合，则以下三条中恰有一条成立(c) |A/=|Bl(a) |A/<[Bl(b) |B/<[Al『定理』（Cantor-Schroder-Bernstein定理）设A和B是集合，如果|A|≤|B|且|B|≤|A|，那么A|=|B

西安电子科技大学 §4.3.1 集合的基数 软件学院 两个集合A和B，如果A和B的基数相同，称A与B等势， 记为A~B。 『定理』（Cantor-Schroder-Bernstein定理）设A和B 是集合，如果|A|≤|B|且|B|≤|A|，那么|A|=|B|。 『定理』等势是任何集合族上的等价关系。 『定理』（Zemelo三歧性定律）设A和B是任意集合，则以 下三条中恰有一条成立。 （a）|A|<|B| （b）|B|<|A| （c）|A|=|B|

西安电子科技大学集合的基数的度量标准$4.3.2 集软件学院家设A、B是任意集合。（a）如果存在一个从A到B的双射函数，那么A、B等势（基数相同），记为|A=|B|；（b）如果存在一个从A到B的单射函数，那么|A|≤|Bl;（c）如果存在一个从A到B的单射函数，但不存在双射函数，那么IA|<|B|。两个集合等势当且仅当这两个集合间存在双射函数

西安电子科技大学 §4.3.2 集合的基数的度量标准 软件学院 设A、B是任意集合。 （a）如果存在一个从A到B的双射函数，那么A、B等势（基 数相同），记为|A|=|B|； （b）如果存在一个从A到B的单射函数，那么|A|≤|B|； （c）如果存在一个从A到B的单射函数，但不存在双射函数， 那么|A|<|B|。 两个集合等势当且仅当这两个集合 间存在双射函数

西安电子科技大学S4.3.2集合的基数的度量标准软件学院【例题】证明正整数集合与自然数集合等势。证明：定义函数f:N一→I+，f ()=x+1。f显然是双射的，所以N~I+

西安电子科技大学 软件学院 【例题】证明正整数集合与自然数集合等势。 证明：定义函数f: N→I+，f (x)=x+1。f显 然是双射的，所以N~I+。 §4.3.2 集合的基数的度量标准

西安电子科技大学S4.3.2集合的基数的度量标准软件学院茶家务【例题】证明实数集合R与R的子集(O,1）等势证明：定义函数f:R→(O,1),f (x)=argtan(x) / 元+1 /2f显然是双射的，所以R~(O,1)

西安电子科技大学 软件学院 【例题】证明实数集合R与R的子集(0,1) 等势。 证明：定义函数f: R→(0,1)， f (x)=argtan(x)/π+1/2 f显然是双射的，所以R~(0,1)。 §4.3.2 集合的基数的度量标准

西安电子科技大学S4.3.3有限集合与无限集合软件学院标准的有限集：Nk={(0,1,2,.",k-1)(a）如果有从Nk={0,1,2,...,k-1)到A的双射，那么集合A是有限集合，A具有基数k。（b）如果集合A不是有限集合，即对任意的k，A到N.都不可能建立双射函数，那么它是无限集合

西安电子科技大学 软件学院 标准的有限集： Nk={0,1,2,.,k-1} （a）如果有从Nk={0, 1, 2,., k-1}到A的双 射，那么集合A是有限集合，A具有基数k。 （b）如果集合A不是有限集合，即对任意的 k，A到Nk都不可能建立双射函数，那么它是 无限集合。 §4.3.3 有限集合与无限集合

西安电子科技大学$4.3.3有限集合与无限集合软件学院家茶茶茶『定理』自然数N是无限集合。证明：设n是任意自然数，f是任意从o,1，,n1到N的函数。设k=1+maxf(O),f(1),,f(n-1))，那么kEN。但k在函数f下找不到原象，因此f不可能是满射的。故N不可能与任一有限集合等势，N是无限集合

西安电子科技大学 §4.3.3 有限集合与无限集合 软件学院 『定理』自然数N是无限集合。 证明：设n是任意自然数，f是任意从{0,1,.,n- 1}到N的函数。 设k=1+max{f(0),f(1),.,f(n-1)}，那么k∈N。 但k在函数f下找不到原象，因此f不可能是满 射的。故N不可能与任一有限集合等势，N是 无限集合

西安电子科技大学可数集合$4.3.4软件学院与自然数集N等势的集合称为可数无限可数无限集合集合，可数无限集合的基数用“o（阿列夫零）表示。有限集合和可数无限集合统称为可数集合。可数集合

西安电子科技大学 软件学院 可数无限集合 可数集合 §4.3.4 可数集合 与自然数集N等势的集合称为可数无限 集合，可数无限集合的基数用“א0” （阿列夫零）表示。 有限集合和可数无限集合统称为可数集合

西安电子科技大学可数集合$4.3.4软件学院【例题】设I表示整数集合，证明：「I=o。证明：作函数f:N→I,x当x是偶数2f (x)=x+1当x是奇数2f是双射的，所以N～I，即III=o

西安电子科技大学 §4.3.4 可数集合 软件学院 【例题】设I表示整数集合，证明：|I|=א0。 证明：作函数f: N→I， ⎪⎩ ⎪⎨⎧ + − 2 1 2 x x f是双射的，所以N~ I，即|I|=א0。 f (x)= 当x是偶数 当x是奇数