3.3 双射函数与集合的基数
本章目录 · 1 节
本章导读
本节用双射讨论集合的势:有限集可以逐个计数,无限集则用是否能够一一对应来比较。一个集合是另一个集合的真子集,并不自动说明它的基数更小;偶数集就与全部自然数等势。
定义3.3.1:若存在从 到 的双射,称 等势,记 ;不存在这样的双射记 。证明等势应给出双射或满足相关定理的单射,不能只凭图形上看起来“差不多多”。
【例3.3.1】依次建立教材中的六组等势关系。
解:(1),使用上一节 时映到 、 时映到 的双射。
(2)。按坐标和 从小到大,每条斜线上再按 排列:。在第 条斜线前共有 个点,所以从0计数得到双射
对给定 ,唯一选择 使 ,再令 ,便得到唯一的原像,因而不仅没有重复,也没有遗漏。
(3)。把 ()排成表,沿教材图的路径遍历,并跳过所有此前出现过的相同有理数。例如 是同一个数,只记录第一次; 也只能记录一次。每个分数所在格点终会被访问,跳过重复后每个有理数恰出现一次。
(4),取 ;自变量角度位于 ,正切严格递增且覆盖全部实数,逆映射为 。
(5)。把 这条可数链向后移动两位,其他点保持不变,具体为 (),其他 取 。输出中的 分别由端点补上,其余二进分点各由唯一的前一项得到,不在该链上的点仍只对应自身;所以既没有冲突也没有遗漏。把 写明,是为了避免 与单列的 分支重叠。
(6)对实数 ,,取 ;开区间同样可用此仿射映射。区间必须非退化,单点区间不与全部实数等势。
【例3.3.2】证明任意集合 都满足 。
证明:把子集 送到其特征函数 。若 ,存在元素只属于其中之一,两特征函数在该点取值不同,所以单射。对任意 ,取 ,便有 ,所以满射。两种构造互相恢复;包括 时,左右都只有一个元素的情形。
(例完)
定理3.3.1:等势具有自反性、对称性、传递性。 给出 ;双射的反函数给出 ;两个双射复合给出 。因此自然数、整数、有理数、自然数对等势;实数、非退化实数区间也等势。两组是否彼此等势,需要另行证明。
定理3.3.2(康托尔定理):,并且任意集合 都满足 。这两项均可用对角线法证明。
第一项只需证明闭区间 不可列出为一个穷尽序列。假设全部数依次为 ,统一选择不以无限多个9结尾的小数表示,单独允许端点1写成 。令 为第 个数的小数第 位,构造 ,其中 时取 , 时取 。新数只用1、2,不存在末尾无限9造成的双重表示;它与每个 在指定一位不同,故从序列中漏出,矛盾。端点1的小数表示须单列说明,不能把 内所有数不加例外地写作 。
第二项对任意 ,构造 。若 满射,则有 使 ,从而 ,矛盾。所以不存在从 到其幂集的满射,更不存在双射。这里 仍是 的正常子集,矛盾来自假设的满射,不是说这个子集不能定义。
定义3.3.2:若存在从 到 的单射,称 优势于 。为清楚显示比较方向,以下写 ;若还不等势,写 。比较的对象是基数,而不是原集合的包含关系。总有 ,由 给出单射;结合康托尔定理得到严格不等式。
定理3.3.3:基数比较具有自反性和传递性;若同时有从 到 和从 到 的单射,则 。最后一项称为康托尔—伯恩斯坦定理,不要求这两个单射恰好互为反函数。教材略去的构造可补充如下:给定单射 ,令 ,。在 上定义 ,在 上定义 。第二分支合法,因为 不含 ,且 在其像上可逆。 与 不交:若 且 ,便与 矛盾;两部分也覆盖 ,因 时 不可能属于 。每一分支单射,故 是所需双射。
由此证明 :把实数的规范二进制展开(不取无限1结尾的表示)送到位序列,给出一个单射,但它不是满射,例如被排除的 位序列不会出现。反向把二进位序列 编成十进制小数 ;该数在 内,而且只含0、1,不同序列不能因进位而变成同一个数,所以也是单射。使用伯恩斯坦定理即得等势,再与区间等势合成得到其与实数等势。
定义3.3.3:记 ( 时为空)。与某个 等势的集合称为有穷集,其余称无穷集。有限集合对应的自然数 唯一。
定义3.3.4:有限集的基数定义为对应的 ; 与 均表示基数。自然数集的基数记为 。教材将实数集的基数记作不带下标的 ;这里同时采用通常更易辨认的连续统记号 ,两种记号在本节指同一个基数,不可误当成 。
定义3.3.5: 等价于存在双射;小于等于等价于存在单射;严格小于还要求不等势。于是 ,,并有 。任意集合的幂集基数都更大,故不存在最大的基数;不能据此认定连续统恰为自然数集基数之后的紧邻基数。
定义3.3.6:满足 的集合称为可数集或可列集,本书包括有限集和空集;与自然数集等势时称可数无限。实数集不可数。可数集的子集可数,两个可数集的并与积可数,可数个可数集的并可数;在通常集合论框架下,把每组排成一行再按对角线遍历,并略过重复,就说明了最后一项。无穷集的幂集不可数:若原集已不可数,其幂集包含原集的单射像;若原集可数无限,则由康托尔定理严格大于 。不能把“可数个集合的并”误换成“可数个集合的无限笛卡儿积”,后者可能不可数。
【例3.3.3】求三组集合的基数。
解:(1)单词BASEBALL中的不同字母组成 ,基数为5,重复字母不重复计数。(2)同时满足 和 的实数不存在,所以基数为0;两个条件是同时满足,不是任选一个。(3) 有4个元素,。
【例3.3.4】,其中 ,求 。
解:将 列为 ,将 列为 ,定义 。自然数除以 的商与余数唯一,所以既单射又满射,结果为 。条件 必须保留;若 为空,积为空,其基数为0。
