重庆大学离散数学第三章课件

离散数学是计算机科学中的基础学科，特别是在理论和逻辑方面起着至关重要的作用。第三章“集合的基数”深入探讨了集合论中的一个重要概念——基数，这是理解无限集合特别是可数集和不可数集的关键。 我们了解什么是基数。基数是衡量集合中元素数量的一种方式，它不依赖于元素的具体排列顺序。对于有限集，基数就是集合中的元素个数。而在无限集的范畴中，基数的概念就更为复杂。例如，自然数集的基数称为 aleph-null（ℵ₀），表示可以与自然数一一对应的所有集合的基数。而实数集的基数大于自然数集的基数，被称为 aleph-one（ℵ₁）。 在本章的第一节中，介绍了无穷集的概念，特别是两个集合等势的定义。两个集合等势意味着存在一个一一对应的映射，使得它们之间每个元素都能找到唯一对应的元素。等势的集合具有相同的基数，即使它们的元素可能看起来完全不同。此外，通过等势，我们可以区分有限集和无限集。有限集是指可以与一个正整数对应，而无限集则不能。 第二节，重点在于可数集与不可数集。可数集是可以通过一对一的方式与自然数集建立对应关系的无限集，比如整数集、有理数集都是可数集。而不可数集，如实数集，不能与自然数集建立这样的对应。这里还列举了一些关于可数集的重要性质，如可数集的无限子集仍为可数集，有限个可数集的并集也是可数集等。 第三节进一步介绍了集合基数的概念。其中，基数之间的大小关系被明确，例如，两个集合的基数要么相等，要么一个大于另一个，不存在两者都大或都小的情况。Bernstein 定理指出，如果两个集合相互之间的元素都能一一对应，那么这两个集合等势。此外，幂集（集合的所有子集构成的集合）的基数总是大于原集合的基数，这揭示了集合论中的一种基本不等式。 这一章的学习涵盖了集合论的核心内容，包括等势理论、基数的定义和性质，以及如何区分可数集和不可数集。这些知识在算法设计、计算复杂性理论、图论等领域有着广泛的应用，是理解计算机科学中许多高级概念的基础。掌握这部分内容将有助于深入理解和解决涉及无限集合的数学和计算机科学问题。