离散数学 课件 4.6 基数的比较

第四章函数4.6基数的比较ComparingCardinalities目录CONTENTS01基数比较的定义如何用“入射”来定义基数的“小于等于”。02核心定理Zermelo定理与CBS定理。03定理应用通过实例学习如何使用CBS定理。04基数层级有限、可数与连续统的基数关系。定义4.14：基数的比较关系▍定义Statement若从集合A到集合B存在一个入射，则称A的基数不大于B的基数，记作K[A]≤K[B]。若从集合A到集合B存在一个入射，但不存在双射，则称集合A的基数小于集合B的基数，记作K[A]<K[B]。直观理解·Intuition“存在一个入射”意味着集合A中的每个元素都能在集合B中找到一个唯一的“代表”，但B中可能有元素没有被A中的元素映射到。这形象地说明了“B至少和A一样大”，即B的“规模”不少于A。核心思想·CoreIdea将基数的比较问题，从寻找“双射”的难题，转化为了寻找“入射”的问题。在集合论的证明中，寻找入射通常比寻找双射要更容易实现，这为证明无穷集合的基数关系提供了一个强有力的工具。定理4.16：Zermelo定理（三歧性定理）设A和B是任意集合，则以下三条必有一条且仅有一条成立:1.K[A]<K[B]2.K[B]<K[A]3.K[A]=K[B]三歧性(Trichotomy)该性质明确了任意两个集合的基数关系是唯一且清晰的：它们要么等势，要么一个严格优于另一个。这彻底排除了集合间“无法比较大小”的模糊状态，是比较无穷集合基数的逻辑前提。集合论的基石作为选择公理的一个等价命题，该定理确保了基数构成一个全序集。这使得我们可以像处理有限自然数那样，在无限的基数世界中建立“大小”的秩序，是实分析与集合论中进行无穷论证的关键支撑。定理4.17：Cantor-Schröder-Bernstein(CBS)定理定理陈述：设A和B是任意两个集合,如果K[A]≤K[B]且K[B]≤K[A],则K[A]=K[B]。化繁为简将构造一个复杂的双射问题，分解为构造两个相对简单的入射问题，极大降低了证明难度。实用性强在集合论与实分析等领域的实际证明中，找到两个方向的入射通常比直接找到一个双射要容易得多。例题4.15：证明[0,1]与(0,1)基数相同01证明K[(0,1)]≤K[[0,1]]定义函数f:(0,1)→[0,1]，其中f(x)=x。

该函数是一个恒等函数，显然满足入射（单射）的定义，即不同的输入对应不同的输出。02证明K[[0,1]]≤K[(0,1)]

03应用CBS定理结合步骤1和步骤2，我们已经证明了两个集合的基数满足双向不等式。

根据CBS定理，可以得出最终结论：K[(0,1)]=K[[0,1]]例题4.16：可数集与连续统的笛卡尔积问题陈述：设A=N，B=(0,1)，K[A]=ℵ0，K[B]=ℵ，试证明：

K[A×B]=ℵ01证明K[A×B]≤ℵ构造一个单射（入射）函数f:A×B。

令f(n,x)=n+x。显然，对于任意不同的有序对，其像均不同，故f是单射。02证明ℵ≤K[A×B]构造一个单射函数g:(0,1)→A×B。

令g(x)=<0,x>。显然，该映射将不同的实数映射到不同的有序对，故g是单射。03应用CBS定理得出结论结合上述两个方向的单射，根据康托尔-伯恩斯坦-施罗德(CBS)定理，可直接推导出：K[A×B]=ℵ定理4.18：有限、可数与连续统的基数层级定理陈述设A是有限集合，则K[A]<ℵ₀<ℵ。证明思路1.证明K[A]<ℵ₀：有限集可以单射入自然数集N，但二者之间不存在双射关系。2.证明ℵ₀<ℵ：自然数集N可以单射入实数集R，但二者之间不存在双射关系（康托尔对角线法）。层级结论有限集基数<可数无限集基数(ℵ₀)<连续统基数(ℵ)无穷集合的基数层级ℵ₀(阿列夫零)代表可数集的“大小”，

ℵ(阿列夫)代表连续统的“大小”，它们属于不同的无穷层级。定理4.19：无限集的最小基数THEOREM4.19若集合A为无限集，则ℵ0≤K[A]核心含义任何无限集合都至少包含一个可数无限的子集。这意味着可数无限集N的基数ℵ0是所有无限基数中最小的一个，它构成了我们度量无穷大小的“基准”。证明思路根据定义，无限集不能与任何有限集等势。通过选择公理，可以递归地从无限集中选出一个元素序列，构成一个可数无限的子集。这直接证明了无限集的基数必然大于或等于ℵ0。定理4.20：Cantor定理与无穷的无限层次▍定理表述设S是一个集合,P(S)

是集合S的幂集,则K[S]<K[P(S)]。即任意集合的幂集的基数，都严格大于该集合本身的基数。不存在最大基数这意味着基数序列无穷无尽。从任何集合S出发，通过不断取幂集，能得到一个严格递增的序列：

K[S]<K[𝒫(S)]无穷的层次性彻底打破了传统直觉：“无穷”并不是一个单一、笼统的概念。它揭示了无穷集合之间也存在着大小之分，存在着不同的“层次”。本节核心要点回顾基数比较通过“入射”定义了基数间的大小关系：

K[A]≤K[B]和K[A]<K[B]。Zermelo定理保证了任意两个集合的基数都可以比较，即集合基数满足三歧性。CBS定理证明两个集合基数相等的核心工具：

若存在双向单射，则存在双射，即|A