集合论

参考资料

• 电科大离散数学 - 标准离散数学 - 3
• 离散数学及其应用 - 翻译版, 包括 "离散数学" 和组合数学 / 初等数论 /... - 4

概念

• 高中集合
• 集合: 组合 / 关系 / 图 / 有限状态机 / 基数
• 函数 / 笛卡尔积 (两个集合所有元素之间的关系)
• A 可数等价于: \(|A| = |\mathbb{N}| \Rightarrow \aleph_0\)
• 连续统假设: \(\not\exists\ \kappa\ \ \aleph_0 < \kappa < 2^{\aleph_0} = \aleph_1 = |\mathbb{R}|\)
• 矩阵
• 笛卡尔积: \(A \times B = {(a,b) \mid a \in A, b \in B}\)
• 幂集: \(\mathcal{P}(A) = { S \mid S \subseteq A }\)

关系

• \(R \subseteq A \times B\)
• 显然, 函数是关系的一种特殊情况
• 常用 0-1 矩阵与图表示关系

到自身的关系性质

• \(\forall a \in A,\ (a,a) \in R\) 自反
• \((a,b) \in R \Rightarrow (b,a) \in R\) 对称
• \((a,b) \in R \land (b,c) \in R \Rightarrow (a,c) \in R\) 传递
• 以上全满足为等价关系, 其中元素的集合为等价类
• 还有反对称与反自反
• 对于关系 R, 能使 R 满足自反, 对称, 传递的最小超集为 R 的自反, 对称, 传递闭包
• \([a] = { x \in S \mid x \sim a }\) a的等价类 (在某个等价关系下相等的元素的集合)

关系性质

• \(S \circ R = {(a,c) \mid \exists b, (a,b) \in R \land (b,c) \in S}\) 复合运算
• \(R^{n+1} = R^n \circ R\) 幂运算

序

• 若 R 是自反的, 反对称的, 传递的, 则称 R 为偏序,\((S,R)\) 为一个偏序集
• 若 S 中所有元素可比, 则称 R 是全序,S 为一个全序集, 亦称链
• 链 S 的非空子集都有最小元素, 则称 S 是良序集
• 偏序可以用哈塞图表示, 节省许多边
• 若偏序集每对元素都有最小上界与最大下界, 则该偏序集为格