chap-可数集与不可数集PPT课件

2020 4 24 1 4 1等势 如何比较两个集合中元素的多少呢 引入等势的概念 定义4 1 1设A和B是集合 若存在A到B的双射 则称A与B等势 记为A B 可形象理解为A与B的元素一样多 是一个等价关系 例1自然数集N与偶自然数集E是等势的 其中定义N到E的双射 为 n 2nn N 2020 4 24 2 证明 是一个等价关系 证明 设S X 任意两个元素之间存在双射 X是集合 是S上的二元关系 A B S 存在双射 A B 对每个A S 存在恒等映射I A A I是双射 于是A A 故 是自反的 对任意A B S 若A B 则存在双射 A B 显然双射 1 B A存在 于是B A 故 是对称的 对任意A B C S 若A B B C 则存在双射 A B和 B C 而 A A B C 即双射 A C存在 于是A C 故 是传递的 综上所述 是等价关系 2020 4 24 3 有限与无限 定义4 1 2 设Nn 0 1 n 1 n 1 若集合A与Nn等势 则称A为有限集 否则称A为无限集 2020 4 24 4 无限多的自然数 定理4 1 1自然数集合N是无限集 证明 设n N n 1 令 是从Nn到N的映射 Nn 0 1 n 1 下证 不是双射 令k 1 max 0 1 n 1 于是k N 但对任意x Nn 均有 x k 因此 不是满射 更不是双射 由定义4 1 2知 N为无限集 啊哈 这下我们知道有无限多个自然数了 2020 4 24 5 抽屉原理 鸽巢原理 我们知道 若A B均为有限集 且A与B之间存在双射 则A和B的元素个数相等 即A B 但是 定理4 1 2任何有限集均不能和其真子集等势 此定理也称为抽屉原则 若将n 1个物体放入n个抽屉中 则至少有一个抽屉中放了两个或两个以上的物体 抽屉原则对无限集并不总是成立 即无限集能够与其真子集等势 这是无限集合的一个非常重要的性质 我们已经看到自然数集等势于它的真子集 偶数集合 下面我们再看几个例子 2020 4 24 6 正实数和全体实数一样多 例2 令R和R 分别为实数集合和正实数集合 即R x R x 0 显然 R R 即R 是R的真子集 但是R R 证明 定义映射f如下 f x ex x R于是 对任意的x R 存在唯一的y R 使y ex f x 另一方面 对任意的y R 存在唯一的x lny R 使f x ex elny y 这说明f是R到R 的一个双射 因此 R R 2020 4 24 7 例3 A 0 1 B 0 1 A B R 显然A B 构造一A到B的双射 说明A B 解 令A1 0 1 2 1 3 1 n 作f A B为 任取x1 x2 A x1 x2 显然 f x1 f x2 且对任意y B 若y 0 则取x 0 有f 0 0 若y 1 则取x 1 2 A1 于是f 1 2 1 2 1 y 若y 1 n 取x 1 n 1 A1 故f 1 n 1 1 n y 若y B A1 则取x y 于是f x x y 综上所述f是A到B的双射 于是A B f 0 0f 1 n 1 n 1 n 1 1 n A1 n N f x x x 0 1 A1 2020 4 24 8 4 2集合的基数 几个记号 同有限集合中元素的个数的记法一样 集合A的基数用 A 表示 每个有限集合都恰与某个集合Nn 0 1 n 1 等势 其中n 0 N0 如果A Nn 则A中有n个元素 即 A n 若A为无限集 则用一个特殊的符号 i 读作阿列夫i i是一个正整数 来表示它的基数 例如 对于自然数集合N 令 N 0 读作 阿列夫零 2020 4 24 9 如何比较集合的大小 1 若A B 则称A的基数与B的基数相等 记为 A B 否则记为 A B 2 若存在A到B的单射 则称A的基数小于或等于B的基数 记为 A B 或称B的基数大于或等于A的基数 记为 B A 3 若 A B 且 A B 则称A的基数小于B的基数 记为 A A 根据集合的基数来比较它们的大小 定义4 2 1令A B为两个集合 由定义 A B 可形象地理解为A中的元素与B中的元素一样多 2020 4 24 10 集合大小是可比的 定理4 2 1设A和B为两个集合 总有 A B 或者 B A 即任意两个集合总可比较大小 像实数一样 任何两个基数都可以比较大小 所以有 2020 4 24 11 基数之间的相等关系是等价关系 定理4 2 2基数之间的相等关系 是一个等价关系 即对任何集合A B和C 有 1 A A 2 若 A B 则 B A 3 若 A B 且 B C 则 A C 2020 4 24 12 基数间的 是偏序关系 定理4 2 3基数之间的小于或等于关系 是一个偏序关系 即对任何集合A B和C 有 1 A A 2 若 A B 且 B A 则 A B 3 若 A B 且 B C 则 A C 2020 4 24 13 几个关于基数的问题 我们知道自然数有无限多个 那么自然数集合是不是就是最大集合的呢 如果自然数集合不是最大的 那么比它更大的集合是什么样的呢 是不是存在最大的基数呢 不 不存在最大的集合 山外有山 天外有天 我们的口号是 只有更大 没有最大 2020 4 24 14 山外青山楼外楼 定理4 2 4对任意集合A 均有 A A 其中 A 为A的幂集 证明 令f A A f a a a A 显然 f是单射 于是 A A 显然 象集 a a A 是 A 的真子集 所以 f不是满射 从而不是双射 于是我们有 A A 错 错 错 错误是 虽然f不是双射 但不能说明A与 A 之间不存在其它的映射是双射 正确的作法是证明A与 A 存在任何的双射都是不可能的 2020 4 24 15 山外青山楼外楼 假设 A A 则存在A到 A 的双射g 令B a A a g a g a 是a所对应的A的子集 显然B A b A 使g b B 但是 1 若b B 则由B之定义有b g b 即b B 2 若b B 即b g b 则由B之定义有b B 总之有b B当且仅当b B 矛盾 故 A A 综合以上 定理得证 定理4 2 4对任意集合A 均有 A A 其中 A 为A的幂集 证明 令f A A f a a a A 显然 f是单射 于是 A A 讨论B的存在性 双射g A A a A g a A 即 g a 是A的子集 又 作集合D A A A A 显然 D A 即D A 令 a A g a D 于是 a D 即a g a 但a A A 2020 4 24 16 无限集也分大小 且无最大者 定理4 2 4说明 对任意无限集 它的幂集就比它大 因此对任意无限集都存在更大的集合 我们记自然数集合N的幂集的基数为 1 也就是 N 1 由定理4 2 4知 0 1 可以证明 R N 其中R为实数集 于是 N R 实际上N是最小的无限集 依次可以推得实数集合的幂集的基数为 2 2020 4 24 17 4 3可数集与不可数集 定义4 3 1 设A是一个集合 若A与N等势 则称A为可数无限集 若A是有限集 则称A为可数集 有时也将可数无限集简称为可数集 遇到讨论可数集的问题时要注意区分无限和有限两种情况 不是可数集的集合就称为不可数集 2020 4 24 18 整数集是可数集 例1 整数集Z是可数集 证明 可定义N到Z的映射 如下 n n 2 n为偶数 n 1 n 2 n为奇数 不难验证 为双射 故N Z 则Z是可数集 说明 映射 将1 0 偶数 正整数 奇数 除1外 负整数 2020 4 24 19 定理4 3 1A是可数无限集当且仅当A的所有元素可以如下编号排出 a1 a2 a3 an 此定理告诉我们 任何集合只要它的元素可以排序 就是可数的 如何判别一集合是可数的 2020 4 24 20 可数集的子集仍是可数的 定理4 3 2可数集的子集仍是可数集 证明 设A是可数集 若A是有限集 则它的子集仍是有限集 当然也是可数集 若A是无限集 则由定理4 3 1知 A的元素可排列成 a1 a2 a3 an 3 3 显然 A的无限子集可如下得到 从左向右看式 3 3 可以依据子集中元素出现的次序将该子集的元素排列为 ai1 ai2 ai3 ain 由定理4 3 1知 该子集是可数集 2020 4 24 21 有理数集Q是可数集 例2 有理数集是可数集 证明 已知任何非零有理数均可表示成确定的既约分数 故把全体有理数按如下方式排列 1 0排在最前面 2 对正分数 按它的分子与分母的和数由小到大排列 若和数相等 则分子小的排前面 3 对负分数 把它紧排在相应的正分数后面 显然 任意有理数总会排入此序列中 由定理4 3 1知 Q是可数集 这种排序的方法称为字典排序法 2020 4 24 22 三角形方法 有理数还可以按下表排序 显然用此方法可将所有的有理数排序 分子 分母 123456 1234 此方法称为三角形方法 是很有用的方法 2020 4 24 23 符号串的集合是可数的 令 为一字母表 上的符号串为 1 2 3 4 ii 1这里 i为长度为i的符号串的集合 为可数集 事实上 若 k 则每一个符号串就是一个k进制的数 显然它们是可以按序排列起来 所以 为可数集 2020 4 24 24 不是所有的集合都能排序 如果一个集合的元素可以排序 那么我们就可以一个一个地去数 是不是所有的集合的元素都能排序呢 不 不是所有的集合都能排序 比如 0 1 中实数的集合 让我们来设想一下将它的元素排一个序 0理所当然排在第一位 但是0之后应该排哪个呢 0 1 不 0 01 不 0 001 不 你会发现第二个就不知道排哪个好了 这样看来实数集合是没法去数了 2020 4 24 25 实数集是不可数的 定理4 3 3实数集是不可数的 证明 取R的子集 0 1 x R 0 x 1 由定理4 3 2知 只需证明 0 1 是不可数集即可 若 0 1 可数 则可将 0 1 中的数排成序列 1 0 a11a12a13 2 0 a21a22a23 3 0 a31a32a33 考虑数r 0 r1r2 rk 其中当akk 1则rk 1 当akk 1则rk 2 k 1 2 这样就保证了r不等于序列中任何数 因为对任意k r的第k位rk与序列中第k号数的第k位akk不相等 因为r不在序列中 所以 0 1 是不可数集 2020 4 24 26 对角线方法 定理4 3 3中所使用的方法称为对角线方法 a11 a22 a33 r1 r2 r3 123 对角线方法是一种非常有用的方法 2020 4 24 27 连续统问题 已知N是可数集 而 N R 能否找到一个实数集R的子集A 使得 N A R 但又不存在A到R的双射 这个问题称为 连续统问题 现已证明 在现有公理系统中 证明它成立与否都不可能 2020 4 24 28 新春晓信息时代到 处处有电脑 夜来打字声 程序知多少 答曰 诗中的问题是计算机上所有程序有多少 为何如此 有诗为证 计算机 靠程序 它的本事知底细 程序都是符号串 理应是个可数集 程序时时新 落花处处飘 它们同为 0 数数便知道 2020 4 24 29 集合论总结 集合 关系 映射 可数集与不可数集 集合论的主要内容有 2020 4 24 30 集合 基本概念 集合 子集 幂集 集合之间的关系 真 含于 相等 集合的基本运算 并 交 差 和对称差 笛卡尔直积 n个集合的笛卡尔直积是它们的n元有序组的集合 它仍然是个集合 集合的表示 列举法和描述法 2020 4 24 31 关系 关系的概念 A到B的二元关系R是笛卡尔直积A B的子集 关系仍然是集合 关系的表示 仍然可以采用集合的表示方法 若A B是有限集合 或者说R是有限集上的关系 则R的表示还可以采用 关系矩阵和关系图 2020 4 24 32 关系的性质 自反性 x A xRx 反自反性 x A xRx 对称性 x y A 若xRy yRx 反对称性 x y A 若xRy且yRx x y 传递性 x y z A 若xRy且yRz xRz 令R是定义在集合A上的关系 2020 4 24 33 关系的运算 关系是集合 可具有集合的各种运算 复合运算 R S x z y B xRy且ySz 其中 R S分别为A到B和B到C的关系 逆关系 R 1 y x x y R 注意复合运算的逆 R S 1 S 1 R 1 在一个集合A上的关系的幂运算 R0 x x x A Rk Rk 1 R 2020 4 24 34 关系的闭包 某关系的具有某种性质的闭包是 包含该关系的最小的有此性质的关系 依据关系的性质有 r R s R 和t R 即自反闭包 对称闭包和传递闭包 r R R R0 s R R R 1 t R Ri i 1 2020 4 24 35 用关系矩阵实现关系的运算 MR S MR MS MR0为R0的关系矩阵 显然R 1的关系矩阵就是MRT 显然的Rk关系矩阵是MRk MRk 1 MR R的自反闭包为MR MR0 R的对称闭包为MR MRT nR的传递闭包为 M