双射函数与集合的基数.ppt

《双射函数与集合的基数.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8.3集合的基数离散数学南京农业大学本科生课程数学系本章说明本章的主要内容集合的等势及其性质重要的等势或不等势的结果集合的优势及其性质自然数与自然数集合集合的基数可数集8.3.1集合的等势与优势8.3.2集合的基数本节小结习题作业本章内容定义8.8设A,B是集合，如果存在着从A到B的双射函数，就称A和B是等势（samecardinality）的，记作A≈B。如果A不与B等势，则记作AB。8.3.1集合的等势与优势≈通俗的说，集合的势是量度集合所含元素多少的量。集合的势越大，所含的元素越多。（1）Z≈N。则f是Z到N的双射函数。从而证明了Z≈N。等势集合的实例(1)等势集合的实例(2)（2）

2、N×N≈N。双射函数等势集合的实例(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/23/2[12]0/21/2[2]-2/3[6]-1/3[7]-3/32/3[9]3/30/31/3[8]-2/4-1/4[15]-3/4[16]2/43/4[13]0/41/4[14]……………………以0/1作为第一个数，按照箭头规定的顺序可以“数遍”表中所有的数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。等势集合的实例(4)

3、（4）(0,1)≈R。其中实数区间(0,1)={x

4、x∈R∧0

5、的。(2)对于任意的g∈{0,1}A，那么有g：A→{0,1}。令B={x

6、x∈A∧g(x)=1}则BA，且B=g，即B∈P(A)，使得f(B)=g。所以f是满射的。由等势定义得P(A)≈{0,1}A。例8.10证明复习定理8.6设A，B，C是任意集合，（1）A≈A。（2）若A≈B，则B≈A。（3）若A≈B，B≈C，则A≈C。（1）IA是从A到A的双射，因此A≈A。（2）假设A≈B，存在f:AB是双射，那么f1:BA是从B到A的双射，所以B≈A。（3）假设A≈B，B≈C，存在f:AB，g:BC是双射，则fg:AC是从A到C的双射。所以A≈C。等势的性质证明N≈Z≈Q≈N

7、×NR≈[0,1]≈(0,1)任何的实数区间（开区间、闭区间以及半开半闭的区间）都与实数集合R等势。问题：N和R是否等势？若干等势集合（1）如果能证明N[0,1]，就可以断定NR。只需证明任何函数f：N→[0,1]都不是满射的。构造一个[0,1]区间的小数b，使得b在N中不存在原像。（2）任取函数f：AP(A)，构造B∈P(A)，使得B在A中不存在原像。或者使用反证法。定理8.7康托定理（1）NR。（2）对任意集合A都有AP(A)。康托定理≈≈≈≈分析（1）首先规定[0,1]中数的表示。对任意的x∈[0,1]，令x=0.x1x2…,（0≤xi≤9）注意：为了保证表示式的唯一性，如果遇到0

8、.24999…，则将x表示为0.25000…。设f:N→[0,1]是从N到[0,1]的任何一个函数。f的所有函数值为：f(0)=0.a1(1)a2(1)…f(1)=0.a1(2)a2(2)……f(n1)=0.a1(n)a2(n)……令y的表示式为0.b1b2…，并且满足bi≠ai(i)，i=1,2,…，则y∈[0,1]，但y与上面列出的任何一个函数值都不相等。即f不是满射的。所以，NR。康托定理≈康托定理假设A≈P(A)，则必有函数f:A→P(A)是双射函数。如下构造集合B：B＝{x

9、x∈A∧xf(x)}可知B∈P(A)。于是存在唯一一个元素b∈A，使得f(b)＝B。若b∈B，则由

10、B的定义知，bf(b)，即bB，矛盾。若bB，则bf(b)，于是由B的定义知，b∈B，矛盾。（2）设g：A→P(A)是从A到P(A)的任意函数，如下构造集合B：B＝{x

11、x∈A∧xg(x)}则B∈P(A)。但是对任意x∈A，都有x∈Bxg(x)所以，对任意的x∈A都有B≠g(x)，即Brang即P(A)中存在元素B，在A中找不到原像。所以，g不是满射的。所以，AP(A)。说明康托定理≈根据这个定理可以知道