第12章-集合的基数.ppt

第12章集合的基数 集合的等势基数的定义基数的运算基数的比较 12 2集合的等势 定义12 2 1对集合A和B 如果存在从A到B的双射函数 就称A和B等势 记作A B如果不存在从A到B的双射函数 就称A和B不等势 记作 A B注意 证明等势即构造双射 等势是等价关系 可以用来分类 自反性 A AIA A A双射 对称性 若A B 则B Af A B双射 f 1 B A双射 传递性 若A B且B C 则A Cf A B g B C双射 gof A C双射 集合的等势 例1N N偶 N N奇f N N偶 f n 2n g N N奇 g n 2n 1例2Z N f Z N 0 n 0f n 2n n 02 n 1 n i j i j 1 2 i 例4N Q证明 因为任何有理数都可以表示成分数 即 m Z n N 0 m n 从而找出全体既约分数 它们表示出了全体有理数 并编号 f N Q f n 编号 n 的既约分数 课本中图12 2 1 集合的等势 例5R R f R R f x ex例6 0 1 Rf 0 1 R x 0 1 f x tan x 1 2 例7 0 1 0 1 f 0 1 0 1 1 2 x 0f x 1 n 2 x 1 n n N 0 x 其他注 无限集合可以和它的真子集等势 但有限集合不能 结论 无限集合可以和它的真子集等势 但有限集合不能N Z Q N N 0 1 0 1 R P A A2 证明 令f P A A2 f B B 其中 B是B P A 的特征函数 B A 0 1 B x 1 x B 1 f是单射 设B1 B2 A且B1 B2 则f B1 B1 x B2 x f B2 故 B1 B2 2 f是满射 任给 B A 0 1 令B x x A且 B x 1 A 则f B B 集合的等势 定理12 2 3 Cantor康托尔定理 1 N R 2 对任意的集合A A P A 证明 1 反证 假设N R 0 1 则存在f N 0 1 双射 对 n N 令f n xn 1 于是ran f 0 1 x1 x2 x3 xn 将xi表示成如下小数 N R x1 0 a11a21a31 x2 0 a12a22a32 x3 0 a13a23a33 xn 0 a1na2na3n 其中0 aji 9 i j 1 2 N R 选一个 0 1 中的小数x 0 b1b2b3 使得 1 0 bj 9 i 1 2 2 bn ann 3 对x也注意表示的唯一性由x的构造可知 x 0 1 x x1 x2 x3 xn x与xn在第n位上不同 这与 0 1 x1 x2 x3 xn 矛盾 N R 对角化方法x1 0 a11a21a31 x2 0 a12a22a32 x3 0 a13a23a33 xn 0 a1na2na3n ann 2 对任意的集合A A P A 证明 反证 假设存在双射f A P A 令B x x A x f x 则B P A 由f是双射 设f b B 则b B b f b b B 矛盾 12 3有限集合与无限集合 自然数定义对任意的集合A 可以定义集合A A A 把A 称为A的后继 A称为A 的前驱集合0 是一个自然数 若集合n是一个自然数 则集合n 1 n 也是一个自然数列出自然数0 1 0 0 0 0 2 1 1 1 0 1 3 2 2 2 0 1 2 有限集合与无限集合 定义12 3 1集合A是有限集合 当且仅当存在n N 使n A 集合A是无限集合 当且仅当A不是有限集合 即不存在n N 使n A 结论 不存在与自己真子集等势的自然数 鸽巢原理 不存在与自己真子集等势的有限集合 任何与自己真子集等势的集合是无限集合 例N R 任何有限集合只与唯一的自然数等势 12 4集合的基数 集合的基数就是集合中元素的个数定义9 6 1如果存在n N 使集合A与集合 x x N x n 0 1 2 n 1 的元素个数相同 就说集合A的基数是n 记作 A n或 A n或card A n空集 的基数是0定义9 6 2如果存在n N 使n是集合A的基数 就说A是有限集合 如果不存在这样的n 就说A是无限集合 集合的基数 对任意的集合A和B 它们的基数分别用card A 和card B 表示 并且card A card B A B对有限集合A和n N 若A n 则card A n 有限基数 N的基数 card N 0 无限基数 R的基数 card R 1 无限基数 基数的运算 对任意的基数k和l 若存在集合K和L card K k card L l 则 1 若K L k l card K L 2 k l card K L 3 kl card LK 其中LK是从L到K的函数的集合 对集合K L P M 如果K P且L M 则K L P M且LK MP 如果同时成立K L 且P M 则K L P M 基数的运算 例7k0 card K card 10k card K card 000 card card 1例8对任意集合A 有card P A 2card A 基数的运算 例9对任意的n N 有 1 n 0 0 2 n 0 0 3 0 0 0 4 0 0 0证明 1 令L N K a1 an 且对于i 1 2 n有ai N 则card L 0 card K n K L 于是K L a1 an 0 1 2 构造双射函数f K L N 则K L N 且n 0 card K card L card K L card N 0 基数的运算 定理12 5 1对任意的基数k l和m 有 1 k l l k k l l k 2 k l m k l m k l m k l m 3 k l m k l k m 4 k l m Kl km 5 k l m km lm 6 Kl m k l m 另外 对任意的基数k 有k 0 k k 0 0 k 1 k k 2 k k注意 对任意基数的运算的性质 与自然数的运算性质一致 基数的比较 定义12 6 1对集合K和L card K k card L l 如果存在从K到L的单射函数 则称集合L优势于K 记作K L 且称基数k不大于基数l 记作k l定义12 6 2对基数k和l 如果k l且k l 则称k小于l 记作k l例 对任意的自然数n n 0 基数的比较 例10对任意的基数k 有k 2k证明 对基数k 存在集合K 使得card K k 则有card P K 2k 构造函数f A P A f x x 则f是单射的 进而k 2k 又 K P K k 2k因此k 2k注意 不存在最大的基数 基数的比较 定理12 6 1对任意的基数k l和m 有 1 k k 2 若k l且l m 则k m 3 若k l且l k 则k l Schroder Bernstein施罗德 伯恩斯坦定理 4 k l或l k 基数的比较 例11R N2证明 先证R N2 因 0 1 R 即证 0 1 N2H 0 1 N 2 单射 z 0 1 的二进制小数 H z N 0 1 H z n z的二进制表示的第n 1位小数 再证N2 R 因 0 1 R 即证N2 0 1 2 G N 2 0 1 单射 f N 2 G f 0 f 0 f 1 f 2 第n 1位小数是f n 由此例可得 1 card R card N2 card P A 2 0注意 对任意集合A 有P A A2 举例 1 z 0 101110011 时H z 0 1 H z 1 0 H z 2 1 H z 3 1 H z 4 1 2 特征函数f 0 1 f 1 0 f 2 1 f 3 0 可以得到十进制小数f 0 1010 0 1 基数的比较 定理12 6 2对任意的基数k l和m 如果k l 则 1 k m l m 2 k m l m 3 km lm 4 若k 0或m 0 mk ml例2 0 1 2 0 0 2 0 2 0 2 0 2 0 0 2 0所以 0 2 0 2 0 基数的比较 结论对基数k和l 如果k l k 0 l是无限基数 则k l k l l max k l 对任意的无限基数k kk 2k对任意的无限集合K N K对任意的无限基数k 0 k 0是最小的无限基数 对任意的基数k k 0当且仅当k是有限基数有限集合的子集一定是有限的 12 7可数集合与连续统假设 定义12 7 1对集合K 如果card K 0 则称K是可数集合亦可描述为 如果集合K是有限的或与N等势 就称K为可数集合例对n N n是有限可数集合 N Z Q是无限可数集合 R是不可数集合 可数集合 性质 可数集的任何子集是可数集 两