哈尔滨理工大学：《离散数学 Discrete Mathematics》课程教学资源（PPT课件讲稿）09 集合的基数

哈尔滨理工大喾啐斛生程 离 第9章集合的基数 算机系

第9章 集合的基数 离 散 数 学 哈尔滨理工大学本科生课程 计算机系

°本章说明 口本章的主要内容 集合的等势及其性质 重要的等势或不等势的结果 集合的优势及其性质 自然数与自然数集合 集合的基数 可数集

本章说明 q本章的主要内容 –集合的等势及其性质 –重要的等势或不等势的结果 –集合的优势及其性质 –自然数与自然数集合 –集合的基数 –可数集

°本章内啥 91集合的等势与优势 92集合的基数 本章小结 习题 作业

9.1 集合的等势与优势 9.2 集合的基数 本章小结 习题 作业 本章内容

9.1集合的等势与优势 口通俗的说,集合的势是量度集合所含元素多少的量。 口集合的势越大,所含的元素越多。 定义91设A,B是集合,如果存在着从A到B的双射函数,就 称A和B是等势( same cardinality)的,记作A≈B。 如果A不与B等势,则记作A≈B

定义9.1 设A, B是集合，如果存在着从A到B的双射函数，就 称A和B是等势（same cardinality）的，记作A≈B。 如果A不与B等势，则记作A B。 9.1 集合的等势与优势 ≈ q通俗的说，集合的势是量度集合所含元素多少的量。 q集合的势越大，所含的元素越多

等势集合的实例(1 (1)Z≈N。 x≥0 f∫:z→N,f(x) 2x-1x<0 则是Z到N的双射函数。从而证明了Z≈N

（1）Z≈N。 2 0 : , ( ) 2 1 0 x x f Z N f x x x         则f是Z到N的双射函数。 从而证明了Z≈N。 等势集合的实例(1)

等势亲合的实例(2) (2)NN≈N。 0,1 0,0> 双射函数fN×N→N,f() (m+n+1m+n) +m

等势集合的实例(2) （2） N×N≈N。 ( 1)( ) : , ( , ) 2 m n m n f N N N f m n m    双射函数      

等势集合的奥例(3 (3)N≈Q。 把所有形式为p/q(p,q为整数且q>0)的数排成一张表。 以0/1作为第一个数,按照箭头规定的顺序可以“数遍”表中 所有的数。计数过程中必须跳过第二次以及以后各次所遇到的 同一个有理数。 [18] [4] [1] [11] 3/1-2/1-1/10/11/ 2/13/1 [17 [2] [12] 3/2 2/2 -1/20/21/2 2/23/2 [6 …-3/3 2/3 -1/30/31/3 2/33/3 [16 [15] [14] [13] -3/4—-2/4-1/4-0/41/4→2/4+3/4

等势集合的实例(3) （3）N≈Q。 把所有形式为p/q (p,q为整数且q>0) 的数排成一张表。 -2/1 [5] -1/1 [4] -3/1 [18] 2/1 [10] 3/1 [11] 0/1 [0] 1/1 [1] -2/2 -1/2 [3] -3/2 [17] 2/2 3/2 [12] 0/2 1/2 [2] -2/3 [6] -1/3 [7] -3/3 2/3 [9] 0/3 1/3 3/3 [8] -2/4 -1/4 [15] -3/4 [16] 2/4 3/4 [13] 0/4 1/4 [14] … … … … … … … …以0/1作为第一个数，按照箭头规定的顺序可以“数遍”表中 所有的数。计数过程中必须跳过第二次以及以后各次所遇到的 同一个有理数

°等势集合的实例(4 (4)(0,1)≈R。其中实数区间(0,1)={xx∈R∧0<x<1} 令双射函数鍋:(0.1)→Rf(x)=tan2x-1 2 则f是(0,1到R的双射函数。从而证明了(0,1)=R

等势集合的实例(4) （4）(0,1)≈R。 其中实数区间 (0,1)={x| x∈R∧0<x<1}。 2 1 :(0,1) , ( ) tan 2 x f R f x   令双射函数   则 f 是(0,1)到R的双射函数。从而证明了(0,1)≈R

°等势亲合的实例(5 (5)[0,1(0,1)。其中(0,1)和0,1分别为实数开区间和闭区间。 01 2425 1/2x=0 1/ 双射函数f:0,110,),f(x) 1/2′ 其它

等势集合的实例(5) （5）[0,1]≈(0,1)。 其中(0,1)和[0,1]分别为实数开区间和闭区间。 2 1 1/ 2 0 1/ 2 1 ( ) 1/ 2 1/ 2 , 1,2,... n n x x f x x n x x            其它 双射函数 f : [0,1](0,1)， 0 1 2 1 2 1 2 2 1 3  2 1 n  2 2 1 2 1 2 1 3 2 1 4 2 1 5  2 n 1 2          2

等势集合的实例(6) (6)对任何a,b∈R,∝<b,[0,1={a,b。 双射函数錮:0,1→an,b,fx)=(b-a)x+a

等势集合的实例(6) （6）对任何a, b∈R，a<b， [0,1]≈[a,b]。 双射函数f：[0,1]→[a,b]，f(x)＝(ba)x+a