集合论预备知识：基础概念与常用结论

"这篇资料主要涉及的是图论学习前的预备知识，特别是集合论的基本概念和性质。集合、关系、函数以及复杂度是这一部分的重点。集合论是数学的一个基础分支，它研究的对象是集合，不论集合内的元素具体为何种事物，只关注它们的集合属性。" 在计算机科学中，集合论扮演着至关重要的角色。它为程序设计语言、数据结构、形式语言等提供了理论基础。集合论的基本概念包括子集、幂集、以及集合的分类。例如，我们可以将二十六个英文字母视为一个集合，所有的自然数作为一个集合，甚至是特定人群如重庆邮电大学计算机学院2010级的本科学生也可以被视为一个集合。 集合的元素是组成集合的单位，可以是单一的数值、字符，甚至是其他集合。我们用小写字母表示元素，比如集合A={a,c,b}。元素与集合的关系用"∈"（属于）和"∉"（不属于）表示，例如，如果2是正偶数集合的一部分，那么2∈A，而1∉A。 集合的特性包括其确定性，即集合不依赖于元素的排列或重复出现，例如{a,a,b,c,d,c}等同于{a,b,c,d}。此外，集合可以包含其他集合作为元素，形成集合族或集合类，如A={{1,2,3},{8,9,6}}。集合中的元素可能有特定的关联，也可能相互独立。 集合的大小或元素数量称为元数，用"|"符号表示。例如，如果我们有一个包含三个元素的集合，可以说|A|=3。对于不含任何元素的集合，我们称之为空集，记作∅。 描述中的其它常用结论是集合运算的性质，包括交集、并集、差集以及对称差的性质。这些性质在处理集合问题时非常有用： 1. 交集的性质：A∩B是A和B共有的元素，所以A∩B总是包含在A和B中，即A∩B⊆A且A∩B⊆B。 2. 并集的性质：A∪B包含A和B的所有元素，因此A⊆A∪B且B⊆A∪B。 3. 差集的性质：A-B是属于A但不属于B的元素，所以A-B⊆A，同时A-B=A∩~B，其中~B表示B的补集。 4. 等价关系：A∪B=B当且仅当A⊆B，同时也意味着A∩B=A且A-B=∅。 5. 对称差的交换性：A与B的对称差AB等于B与A的对称差BA。 6. 分配律：对称差运算满足分配律，(AB)C=A(BC)。 7. 基本对角线性质：空集与任何集合的对称差等于该集合本身，即A∅=A，而集合与其自身的对称差为空集，AA=∅。 8. 传递性质：如果A的对称差B等于B的对称差C，那么B必须等于C，即AB=AC→B=C。 掌握这些集合论的基本概念和性质，对于理解图论和其他高级数学概念至关重要，因为它们构成了许多复杂算法和数据结构的基础。