2
2024.6.2补天ing
离散数学2024-03-29第3-5节 (zju.edu.cn)
SET
集合元素不管顺序，不管重复，都是同一个集合
元素可以有限个也可以无限个
cardinality 元素的基数，就是集合元素个数
有两个需要注意的运算符
运算律
是不是和命题代数几乎一模一样
实际上集合代数和命题代数都是布尔代数的同构
Power set and Cartesian products
S 的力集表示为 \(P(S)\) 或 \(2^S\)，包含所有 \(S\) 的子集，类似函数依赖的闭包概念
力集的基数大于原来的集合，无论是有限集的还是无限集都是这样
笛卡尔积用于构造带结构的集合， ordered n-tuple
二元的 tuple 叫序偶 ordered pairs
1不对，如果A或B为空集就不行了，空集参与的笛卡尔积结果一定是空集
2对
3对
4不对，A和D为空集的时候就不对了
有限集与无限集的基数
容错原理：
举个容错原理的例子，主要是注意这种求or的，不要忘记去掉相交的部分
我们尝试将有限集的基数推广到无限集
两个集合有相同的基数，当且仅当两者之间能建立一一对应的序列，这两个集合也叫做等价关系
啊，死去的数分和线代开始攻击我
可以看见，有限集是找不到一个真子集与其全集（proper set）基数相同的，而无限集可以
无限集可以分为可数的和不可数的，可数的就是和自然数集 \(\mathbb{N}\) 有相同基数的
上面举的例子里，整数集可数，有理数集可数，前者是{0，1，-1，2，-2，...}，后者表示为两素数之商
\(\mathbb{N} \times \mathbb{N}\) 也是可数的
可数不可数，形式上来说就是可不可以给元素下标，不可数的元素是不能设置下标的
- 可数无限集是最小的无限集，任意无限集都能找到比其更小的可数无限集
- 对于任意无限集，我们每次从中随机取一个元素放入新集合，并依次赋予下标，以此类推，可得到可数无限子集
- 有限个可数集之并也可数
- 可数个可数集之并也可数
我们下面想证明有所谓的不可数的集合存在，就从实数集下刀
右边那个下标为0的，是自然数集的基数
牛皮
函数
函数就是一个集合到另一个集合的映射，且前者作为定义域所有元素都要参与映射
- 单射，即两个映射结果不会相同
- 满射，即值域为整个集合
- 一一对应，单射+满射
还有两个取整符号，平时用取整的就是 floor，往下取整
还有bound符号
首先是上界符号
还有下界符号
上下界相同，那么阶数相同
