集合

顾名思义，就是一个集合。例如$A = {a,b,c}$， ${1,2,3}$。
空集：空的集合。$\emptyset = { }$
基数：集合中的元素个数，记作$|A|$
幂集：集合的所有子集，组成的集合，记作$P(A)$
如果一个集合有n个元素，那么幂集的元素个数的$2^n$

容斥原理

$$
|A \cup B| = |A| + |B| - |A \cap B|
$$
$$
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|
$$
$$
\left| \overline{A} \cap \overline{B} \cap \overline{C} \right| = |S| - |A \cup B \cup C| , S表示全集
$$
容斥原理常用于集合计数问题

自反、对称、传递

设$A = {a,b,c}$
自反性：对于A中的任意一个元素都存在自反关系（$<a,a>$就是一个自反项）。
$R_{1}={<a,a>, <b,b>, <c,c>}$
非自反性：如果缺失了一些自反项，就不是自反性。
$R_{1}={<a,a>, <b,b>}$
反自反性：不存在任何一项自反关系。
$R_{1}={<a,b>, <a,c>}$
自反闭包：需要补充的缺失项，使它具有自反性
对于 $R_{1}={<a,a>, <b,b>}$， $R_{1}'={<c,c>}$

对称性：对于关系集合$R_1$，如果存在关系$<x,y>$，则必存在其反关系$<y,x>$
$R_{1}={<a,b>, <b,a>}$
$R_{1}={<a,b>, <b,a>, <a,c>, <c,a>}$
反对称性：对于关系集合$R_1$，至少存在：一对关系$<x,y>$，不存在其反关系$<y,x>$
$R_{1}={<a,b>, <b,a>, <a,c>}$
对称闭包：将关系集合$R_1$补全为对称性所需的项

传递性：对于关系集合$R_1$，如果存在关系$<x,y>,<y,z>$，则必存在关系$<x,z>$
$R_{1}={<a,b>,<b,c>,<c,a>}$
非传递性：不是传递性，包括空传递性（不存在任何一对$<x,y>,<y,z>$）
传递闭包：将关系集合$R_1$补全为传递性所需的项

偏序、等价、相容、逆序

偏序关系 = 自反 + 反对称 + 传递
等价关系 = 自反 + 对称 + 传递
相容关系 = 自反 + 对称
拟序关系 = 反自反 + 传递

对于实数集，偏序关系可以理解为$\leq$，等价关系可以理解为$=$，拟序关系可以理解为$<$
相容关系可以理解为是一种特殊的关系，它是相互的关系，例如对于${a,b,c}$，有$<a,b>, <b, c>$，则必有$<b,a>, <c,b>$，但不一定有$<a,c>$

偏序集

偏序集（Partially Ordered Set，简称 Poset）是集合理论中的一个重要概念。它是一个集合，配备了偏序关系，这种关系满足特定的性质。

• 偏序关系 = 自反 + 反对称 + 传递

偏序集的例子：

1. 整数集与常规小于等于关系$(Z, \leq)$
   1. 自反性：对于任意的整数$z$，都满足$z \leq z$
   2. 反对称性：例如对于$3,5$，满足$3 \leq 5$ 但是不满足 $5 \leq 3$
   3. 传递性：对于任意三个整数$a,b,c$， 都满足：如果$a \leq b , b \leq c 则 a \leq c$
2. 集合的包含关系

在偏序集上，可能存在部分元素之间无法比较的情况。例如，在集合${a, b, c}$上，如果 $a \leq b$，且 c 既不小于也不大于 a 和 b，那么这些元素之间没有完全的顺序关系。
全序集是特殊的偏序集，在全序集中，任何两个元素之间都有顺序关系