离散数学

0. 集合论

集合构成的集合称为集合族。

用叉乘表示笛卡尔积。

幂集 $\mathcal P(X)$ 是集合 $X$ 所有子集构成的集合族，记作 $2^X$。

集合 $A,B$ 的对称差记作 $A\operatorname{\triangle}B=(A\operatorname{\backslash}B)\cup (B\operatorname{\backslash}A)$。

0.1 集合的运算

从 $X$ 到 $Y$ 的一个（有序）关系是指一个 $R\subset X\times Y$。

$A$ 上有一些特殊的关系：

• 自反：$(x,x)\in R$。
• 反自反：$(x,x)\not\in R$。
• 对称：$(x,y)\in R\Rightarrow (y,x)\in R$。
• 反对称：$\forall x\ne y$，$(x,y)\in R,(y,x)\in R$ 不同时成立。
• 传递。

以及空关系 $\varnothing$，全域关系 $A\times A$，恒等关系 $I_a=\{(x,x)\mid x\in A\}$。

0.3 映射

0.4 势

对于集合 $A,B$，如果存在一个从 $A$ 到 $B$ 的一一映射，则称集合 $A$ 和 $B$ 对等，记作 $A\sim B$，称 $A$ 和 $B$ 有相同的势（基数）。

设 $\mathbb N$ 的基数是 $\aleph_0$（阿列夫零），如果一个集合 $A$ 的势是 $\aleph_0$，那么 $A$ 是可数集。