离散数学屈婉玲第八章.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 基数的相等和大小 定义8.11 设A, B为集合, 则 (1) cardA=cardB ? A≈B (2) cardA≤cardB ? A??B (3) cardAcardB ? cardA≤cardB∧cardA≠cardB 根据上一节关于势的讨论不难得到： card Z = card Q = card N×N =?0 card P(N) = card 2N = card [a,b] = card (c,d) =? ?0? card Acard P(A) 其中2N = {0,1}N * 基数的大小 不存在最大的基数. 将已知的基数按从小到大的顺序排列就 得到： 0, 1, 2, …, n, …, ?0, ?, … 其中： 0, 1, 2…, n, … 是全体自然数, 是有穷基数. ?0, ?, … 是无穷基数, ?0是最小的无穷基数, ?后面还 有更大的基数, 如cardP(R)等. * 可数集 定义8.12 设A为集合, 若cardA≤?0, 则称A为可数集或可列集. 实例： {a,b,c}, 5, 整数集Z, 有理数集Q, N×N等都是可数集, 实数集 R不是可数集, 与R等势的集合也不是可数集. 对于任何的可数集, 它的元素都可以排列成一个有序图形. 换 句话说, 都可以找到一个“数遍”集合中全体元素的顺序. 可数集的性质： 可数集的任何子集都是可数集. 两个可数集的并是可数集. 两个可数集的笛卡儿积是可数集. 可数个可数集的笛卡儿积仍是可数集. 无穷集A的幂集P(A)不是可数集 * 实例 解 (1) 由T={B, A, S, E, L}知 cardT=5 (2) 由B=?, 可知 cardB=0. (3) 由|A|=4 可知 cardC=cardP(A)=|P(A)|=24=16. 例7 求下列集合的基数 (1) T={x | x是单词“BASEBALL”中的字母} (2) B={x | x∈R∧x2=9∧2x=8} (3) C=P(A), A={1, 3, 7, 11} * 例8 设A, B为集合, 且 cardA=?0, cardB=n, n是自然数, n≠0. 求card A×B. 实例 解 方法一 构造双射函数 由cardA=?0, cardB=n, 可知 A, B都是可数集. 令 A={a0,a1,a2,…}, B={b0,b1,b2,…,bn?1} 对任意的ai,bj, ak,bl∈A×B有  ai,bj=ak,bl ? i=k∧j=l 定义函数 f :A×B→N f(ai,bj)=in+j, i=0,1,…, j=0,1,…,n?1 易见f是A×B到N的双射函数, 所以 card A×B=card N = ?0 * 方法二 直接使用可数集的性质求解. 因为 card A=?0, card B=n, 所以A, B都是可数集. 根据性质(3) 可知 A×B也是可数集, 所以 card A×B≤?0 显然当 B≠?时, card A? card A×B, 这就推出 ?0? card A×B 综合上述得到 card A×B=?0. 实例 * 第八章 习题课 主要内容 函数，从A到B的函数 f:A?B，BA，函数的像与完全原像 函数的性质：单射、满射、双射函数 重要函数：恒等函数、常函数、单调函数、集合的特征函 数、自然映射 集合等势的定义与性质 集合优势的定义与性质 重要的集合等势以及优势的结果 集合基数的定义 * 基本要求 给定 f, A, B, 判别 f 是否为从A到B的函数 判别函数 f:A?B的性质（单射、满射、双射） 熟练计算函数的值、像、复合以及反函数 证明函数 f:A?B的性质（单射、满射、双射） 给定集合A, B，构造双射函数 f:A?B 能够证明两个集合等势 能够证明一个集合优势于另一个集合 知道什么是可数集与不可数集 会求一个简单集合的基数 * 练习1 1．给定A, B 和 f, 判断是否构成函数 f:A→B. 如果是, 说明该 函数