《集合的基数》PPT课件.ppt

第6章 集合的基数,本章学习目标 集合的基数是指集合的元素个数的多少，对有限集合来说， 基数就是集合所包含元素的个数，两个有限集的“大小”相等是指 它们包含的元素个数相同。对于无限集合，用等势来表示两个无 限集的“大小”相等。通过本章学习，读者应该掌握以下内容： （1）函数的基本概念 （2）单射、满射和双射函数 （3）函数的复合运算 （4）函数的逆运算,第6章 集合的基数,6.1 基数的概念 6.2 可数集和不可数集 6.3 基数的比较,第6章 集合的基数,6.1 基数的概念 定义6.1 设A、B为两个集合，如果存在从A到B的双射函数， 则称A与B是等势的，记作AB。 例6.1 验证自然数集N与非负奇数集合M是等势的。 证明 因为N与M的元素之间可以作一双射函数，即 f（n）=2n+1 所以，NM。,第6章 集合的基数,6.1 基数的概念 定理6.1 设A、B和C为任意的集合，则 （1）AA； （2）若AB，则BA； （3）若AB，BC，则AC。,定义6.2 如果有一个从集合0，1，n到A的双射函数，则称 集合A是有限的；如果集合A不是有限的，则称它是无限的。,定理6.2 自然数集合N是无限的。,第6章 集合的基数,6.1 基数的概念 定义6.3 （1）对于有限集合A，称与A等势的那个唯一的自然数为A的基 数，记作card A，即 card A=n An （2）自然数集合的基数记作0（读作阿列夫零），即 card N = 0 （3）实数集合的基数记作（读作阿列夫），即 card R = 0,第6章 集合的基数,6.1 基数的概念 定义6.3 例6.3 证明区间0，1与（0，1）基数相同。 证明 设集合 A=0，1，A0，1 定义f：0，1 （0，1）使得：,第6章 集合的基数,6.1 基数的概念 则，f是双射函数。,第6章 集合的基数,6.2 可数集和不可数集 定义6.4 与自然数集合等势的任何集合称为可数的。可数集合的 基数也用0（读作阿列夫零）表示。 例如，2，4，6，8，2n， -1，-3，-7，-9，-2n +1， x为素数，其中xN 都为可数集。,定理6.3 A为可数集的充分必要条件是可以把A排列成 A=a1，a2，an， 的形式。,第6章 集合的基数,6.2 可数集和不可数集 定理6.4 任意无限集，一定包含可数子集。 证明 设A为无限集，从A中取出一个元素，记为a1，因A为无限 集，A-a1也为无限集，所以从A-a1中取出一个元素，记为a2 ，而A-a1，a2仍为无限集，所以又可以取出a3，重复这个过程 ，可得到A的可数子集。,定理6.5 任意无限集，一定与它的某一真子集等势。 证明 设无限集为A，根据定理6.3，A中包含可数子集B=a1， a2，an，设M=A-B，定义A到A-a1的函数f，使得f在 M上是恒等函数，即f（x）=x，xM，在B上，使得f（an）=an+1 （n=1，2，3，）。显然f是双射函数。因此定理得 证。,第6章 集合的基数,6.2 可数集和不可数集 定理6.6 可数集的任意无限子集是可数集。 证明 设A=a1，a2，an，为可数集，B为A的无限子集， 将在A中而不在B中的元素删去，同时注意到B是无限集合，则 有B=ai1，ai2，ain，因此，B是可数的。,定理6.7 可数集与有限集的并是可数集。 证明 设A=a1，a2，an，为可数集，B=b1，b2，bm 为有限集，则AB=b1，b2，bm，a1，a2，an，不 妨设am+i=ai，（i=1，2，），a1=b1，a2=b2，am=bm，则 AB=a1，a2，an，所以AB为可数集。,第6章 集合的基数,6.2 可数集和不可数集 定理6.8 可数个可数集的并集是可数集。 证明 设可数个可数集为： A1=a11，a12，a13，a1n， A2=a21，a22，a23，a2n， A3=a31，a32，a33，a3n， 令A=A1A2A3，对A中的元素排列如下：,第6章 集合的基数,6.2 可数集和不可数集 定理6.8 可数个可数集的并集是可数集。,第6章 集合的基数,6.2 可数集和不可数集 定理6.8 可数个可数集的并集是可数集。 在上面元素的排列中，由左上端开始，其每一斜线上的每一元素 的两足码之和都相同，依次为2，3，4，各斜线上元素的个 数依次为1，2，3，4，故A的排列为： a11，a21，a12，a31，a22，a13， 所以，A的可数的。,第6章 集合的基数,6.2 可数集和不可数集 定理6.9 设自然数集合为N，则笛卡儿积NN是可数集。,定理6.10 有理数的全体组成的集合是可数集。,定理6.11 全体实数集合R是不可数集。,第6章 集合的基数,6.3 基数的比较 定理6.9 设自然数集合为N，则笛卡儿积NN是可数集。 定义6.5 设A，B为任意两个集合， （1）若存在f：AB且f是单射函数，则称B优势于A，或称A劣势 于B，记作AB。 （2）若AB且A与B之间不存在双射，则称B绝对优势于A，或称 A绝对劣势于B，记作AB。 定理6.12 设A，B为两个集合，则AB当且仅当存在CB，使 得AC。 推论 设A，B为两个集合， （1）若AB，则AB； （2）若AB，则AB且BA。,第6章 集合的基数,6.3 基数的比较 定理6.13 设A，B和C为三个集合， （1）AA； （2）若AB，BC，则AC。,定理6.14 设A，B为两个集合，则以下三条中恰有一条成立。 （1）card Acard B； （2）card Bcard A； （3）card A = card B。,定理6.15 设A，B为两个集合，如果card Acard B，card Bcard A，则有card A = card B。,第6章 集合的基数,6.3 基数的比较 例6.4 证明0，1与（0，1）有相同的基数。 证明 作单射函数： f：（0，1）0，1，f（x）=x g：0，1 （0，1），g（x）=图片,第6章 集合的基数,6.3 基数的比较 例6.5 设A=N，B=（0，1），card A=0，card A=，求证：card（AB）= 证明 定义一个从AB到正实数的函数f， f：ABxxR x0 f（n，x）=n+x 因为f是单射函数，并且card xxR x0=。此外，作映射g， g：（0，1） AB g（x）= 因为g是单射的，故 card（0，1）。所以 card（AB）=,第6章 集合的基数,6.3 基数的比较 定理6.16 设A是有限集合，则card A0。 定理6.17 设A是无限集合，则0card A。 定理6.18