集合论
$$
\begin{gather*}
\left \langle \lbrace you,me \rbrace,like \right \rangle \newline
Is \enspace closure?
\end{gather*}
$$
- 集合与关系
- 集合的概念与表示法 (3-1)
- 集合的运算 (3-2)
- 序偶与笛卡尔积 (3-4)
- 关系及其表示 (3-5)
- 关系的性质 (3-6)
- 复合关系和逆关系 (3-7)
- 关系的闭包运算 (3-8)
- 集合的划分和覆盖 (3-9)
- 等价关系与等价类 (3-10)
- 序关系 (3-12)
- 函数
- 函数的概念 (4-1)
- 逆函数和复合函数 (4-2)
主要知识点
Part 1 集合的基础概念
- 集合和元素的概念、表示、关系（属于和不属于）。
- 全集、空集、幂集。
- 集合的势、有限集、无限集的概念。
- 集合间的关系：相等、包含（子集）、真包含（真子集）的概念。
- 集合的运算：并、交、差（相对补）、绝对补、对称差的概念及性质。
- 文式图及应用
Part 2 二元关系
- 序偶（元组）、n元组、笛卡尔积的概念及性质。
- 二元关系的概念、表示方法（集合表示、关系矩阵和关系图）及求解，关系的定义域和值域的概念。
- 二元关系的性质，自反性、反自反性、对称性、反对称性和传递性。
- 关系的运算：基本集合运算、复合关系（右复合）、逆关系、闭包运算。
- 集合覆盖与划分的概念。
Part 3 特殊关系
- 特殊的二元关系：空关系、恒等关系、全域关系、等价关系（等价类、商集）、序关系（偏序关系、全序关系、良序关系）。
- 等价关系：具有自反性、对称性、传递性的关系。等价关系将集合分成若干个等价类，所有等价类的集合就是商集。等价关系与划分。
- 偏序关系：具有自反性、反对称性、传递性的关系。
- 哈斯图。利用哈斯图判断成员的关系，如最小（大）元，极大（小）元，上（下）界，上（下）确界
Part 4 函数
- 函数的定义及其与关系的区别。
- 函数相等的定义。
- 满射、入射（单射）、双射。
- 逆函数的定义及其有关的性质。
- 函数的左复合的定义及其有关的性质。
基础概念
一些基础概念在高中数学中均有所涉及，再此只对其中的部分内容进行列举。
- 说明集合的方法
- 列举法 ：$A= \lbrace a,b,c,d \rbrace$
- 叙述法 ：$S=\lbrace x|x是山东理工大学的学生 \rbrace$
- 与谓词逻辑 : 使用 $p(x)$ 表示任何谓词，则 $A=\lbrace p(x) \rbrace$ 可以表示集合，如果$ p(b) $为真，那么 $b \in A$ ，否则$ b \notin A$
- 集合相等 子集
- 外延性原理：两个集合是相等的，当且仅当他们有相同的成员
- 子集：$A$、$B$为两个集合，假设$A$的每一个元素是$B$的成员，则称$A$为$B$的子集，或$A$包含在$B$内，或$B$包含$A$。记作 $A \subseteq B$ 或者 $B \supseteq A$
- 集合相等的充要条件是两个集合互为子集(主要是用这个进行判断相等)
- 真子集：$A$为$B$的子集，但$B$中有至少一个元素不属于$A$则称$A$为$B$的真子集
- 空集：不包含任何元素的集合，记作$\varnothing$
- 平凡子集： 全集$A$ 和 空集$ \varnothing $
- 全集$E$：在某一范围内所有集合均为$E$的子集，则称该集合$E$为全集
- 幂集： 以$A$中所有子集为元素组成的集合，称为集合$A$的幂集，记作：$P(A)$
- 幂集也是集合
- 若 $|A|=k$，则 $|P(A)| = 2^k$（二项式定理可证）
- 集合的运算
- 交：$\cap$
- 并：$\cup$
- 补：补分为相对补和绝对补
- 相对补: 若 $S$ 为集合 $B$ 对于 $A$ 的补集，则 $S$ 中的元素为所有在集合 $A$ 中但不在集合 $B$ 中的元素，记作 $ A-B $
- 绝对补：全集 $E$ 对于 集合 $A$ 的补集 $E-A$，记作 $\sim A$
- 对称差：只属于两个集合中一个的元素的集合，不能既属于 $A$ 又属于 $B$，记作 $A \oplus B$
- $A \oplus B = (A-B)\cap (B-A)$
- 性质：
- $A\oplus B=B \oplus A$
- $A\oplus \varnothing = A$
- $A\oplus A = \varnothing$
- $A\oplus B = (A\cap \sim B)\cup (\sim A \cap B)$
- $(A\oplus B)\oplus C = A\oplus (B\oplus C)$
- 集合的运算有两个定律：
- 结合律
- $A\cup(B\cap C)=(A\cup B)\cap (A\cup C)$
- $A\cap(B\cup C)=(A\cap B)\cup (A\cap C)$
- 吸收律
- $A\cup(A \cap B)=A$
- $A\cap(A \cup B)=A$
- 结合律
集合的划分与覆盖
看书 P128 定义
划分与覆盖的区别在于：覆盖允许同一个元素在多个分块内，但是划分只能用允许一个元素在一个分块里。
交叉划分：两种不同的划分中的每个元素（分块）的非空交集组成的集合。（P129），交叉划分也是原集合的一种划分。
加细：划分会分成若干的分块，如果 $A$ 中的任意一个分块都可以在 $B$ 中找到一个比他大的集合，那么 $A$ 就是 $B$ 的加细。也就是说，加细中的分块要和原来相同或者是比原来的更小。
真加细：不存在相等的情况。
二元关系
基础知识
- 序偶与元组：
- 两个有次序的元素集合为序偶，如 $\langle x,y\rangle$
- $\langle a,b \rangle = \langle u,v \rangle \leftrightarrow a=u\wedge b=v $ (两个序偶相等，当且仅当元素对应相等)
- 三元组的第一个元素为一个序偶，即$\langle \langle a,b\rangle,c \rangle $ 可写作 $\langle a,b,c \rangle$。在由此推广可以得到 $n$ 元组。
- 注意 $\langle \langle a,b \rangle ,c \rangle = \langle a,b,c \rangle $ 但是 $\langle a, \langle b ,c\rangle \rangle \not = \langle a,b,c \rangle $ ，因为 $\langle a, \langle b ,c\rangle \rangle$ 不是三元组。
- 笛卡尔积/直积 ： $A \times B$
- $|A\times B| = |A|\cdot |B|$
- 一次笛卡尔积运算会得到一个序偶集合，进行多次运算，运算结果是一个 $n$元组集合
- 笛卡尔积运算是可分配的：$(A\cap B)\times C=(A\times C)\cap (B\times C)$
- $A \times A \times A \times A \times A \times A = A^6$
关系
序偶的集合可以确定一个二元关系 $R$，$R$ 中的任一序偶 $\langle x,y \rangle$ 可以记作 $\langle x,y \rangle \in R$ 或者 $xRy$，不在 $R$ 中的任一序偶可以记作 $\langle x,y \rangle \notin R$ 或者 $x\bcancel{R}y$。
对于关系$\langle x,y \rangle$，所有 $x$ 组成的集合 $domR$ 称做 $R$ 的前域（定义域），所有 $y$ 组成的集合 $ranR$ 称作 $R$ 的值域。
任意两个集合$X$与$Y$的直积$X\times Y$的子集$R$称作从$X$到$Y$的关系
全域关系：$X\times Y$
空关系：$\varnothing$
$R$ 在 $X$ 上的二元关系：当$X=Y$时，称$R$为在$X$上的二元关系
注意，二元关系也是集合，二元关系也是集合
恒等关系：$I_X=\lbrace \langle x,x \rangle|x\in X \rbrace$（也就是说，在关系矩阵上呈对角线）
关系矩阵以及关系图：看书
关系的性质
| 自反 | 反自反 | 对称 | 反对称 | 传递 | |
|---|---|---|---|---|---|
| 定义 | 对于每个 $x\in X$ 都有 $xRx$ | 对于每个 $x\in X$ 都有 $x\bcancel{R}x$ | 对于每个 $x,y\in X$ ，每当 $xRy$ 就有 $yRx$ | 对于每个 $x,y\in X$ ，每当 $xRy$ 和 $yRx$ 就有 $x=y$ | 对于任意的 $x,y\in X$，每当 $xRy,yRz$ 时就有 $xRz$ |
| 关系矩阵 | 主对角线均为 1 | 主对角线均为 0 | 关于主对角线对称 | 关于主对角线对称的位置不能同时为 1 （最多只能有一处为 1 | |
| 关系图 | 每个结点都有自回路 | 每个节点都没有自回路 | 任意两个结点之间若有弧线则必定成对出现 | 任意两个结点之间不会出现成对的弧线（可以有自回路） | |
| 其他 | 除了自回路$\langle x,x \rangle$以外，若有$\langle x,y \rangle$则必没有$\langle y,x \rangle$ |
自反、反自反；对称、反对称很容易让人产生非此即彼的误解：
| 自反、反自反 | 对称、反对称 |
|---|
关系的运算
基础运算
$R$ 为从 $X$ 到 $Y$ 的关系，$S$ 为从 $Y$ 到 $Z$ 的关系。
复合关系（右复合）： $R\circ S$ 称为 $R$ 和 $S$ 的复合关系。
合成运算： 从 $R$ 和 $S$ 求 $R\circ S$ 称为关系的合成运算。
注意，$R\circ S \not = S\circ R$
从关系矩阵的角度看，合成运算就是在做矩阵乘法。
多个合成运算的幂运算：
$R\circ R\circ R\circ R = R^{(4)}$
逆关系：将序偶的元素交换顺序
$$
(R\circ S)^c = S^c \circ R^c
$$
闭包运算
闭包运算需要对原有的关系进行扩充，要求 “扩充尽可能少的序偶使其满足自反（对称、传递）的性质”
闭包运算有三种：
| 自反闭包 | 对称闭包 | 传递闭包 | |
|---|---|---|---|
| 记号 | $r(R)$ | $s(R)$ | $t(R)$ |
假设 $R=\lbrace \langle a,b \rangle , \langle a,c \rangle , \langle b,a \rangle \rbrace$ ，如何求闭包：
对于自反闭包只需要补齐关系中所有元素自身对自身的序偶即可，例如：
$$
r(R) = R \cup \lbrace \langle a,a \rangle ,\langle b,b \rangle ,\langle c,c \rangle \rbrace
$$
对于对称闭包只需要将所有序偶调换顺序取交集计科。例如：
$$
s(R) = R \cup \lbrace \langle b,a \rangle ,\langle c,a \rangle , \langle a,b \rangle \rbrace \\
或\\
s(R) = R \cup \lbrace \langle c,a \rangle \rbrace
$$
需要求解传递闭包时要用到Warshall 算法 ，具体步骤详见 P124
简单描述原理就是：我们顺序检查每一列，如果某个位置为 $1$ ，则其序偶为 $\langle i,j \rangle$，我们想要通过这个进行扩展就需要找到 $\langle j,k \rangle$ 或者 $\langle k,i \rangle$ 。我们这里采取的策略是检查是否能找到 $\langle j,k \rangle$ 从而辅助拓展第 $i$ 行。
特殊关系
等价关系
如果关系 $R$ 在 $A$ 上是自反的、对称的、传递的，则 $R$ 为一个等价关系。
等价类是在等价关系的基础上的一个集合，这个集合中的元素不是序偶，而是单个数。例如等价关系 $[a]_R$ 称为元素 $a$ 形成的 $R$ 等价类，其中下标 $R$ 可以省略。
$$
[a]_R = \lbrace x|x\in A, aRx \rbrace
$$
例如对于集合 $T =\lbrace 1,2,3,4\rbrace$ 上的等价关系 $R=\lbrace \langle 1,1 \rangle , \langle 1,4 \rangle ,\langle 4,1 \rangle ,\langle 4,4 \rangle ,\langle 2,2 \rangle ,\langle 2,3 \rangle ,\langle 3,2 \rangle ,\langle 3,3 \rangle \rbrace$，它的所有等价类为：
$$
\begin{align*}
[1]=[4]={1,4}\
[2]=[3]={2,3}
\end{align*}
$$
在等价关系中，由于对称性，因此 $aRb \quad iff \quad [a]=[b]$
商集：集合 $A$ 上的等价关系 $R$ 其等价类集合 $ \lbrace[a]|a\in A\rbrace$ 称为 $A$ 关于 $R$ 的商集，记作$ A/R$
商集和划分有关，商集实际上就是一个划分，通过划分可以求等价（商集），通过等价（商集）也可以求划分。
换句话说，对于一个集合的划分可以决定一种等价关系。
划分求等价关系：每一个分块对自己做笛卡尔积，见P134
偏序关系
如果关系 $R$ 在 $A$ 上是自反的、反对称的、传递的，则 $R$ 为 $A$ 上的一个偏序关系，并记作 $\preccurlyeq$ 。序偶 $\langle A,\preccurlyeq \rangle$ 称作偏序集。
盖住：定义详见P140
简单说，盖住也是一个集合：
$$
COV; A = \lbrace \langle x,y \rangle| x,y\in A, y , 盖住 , x \rbrace
$$
这个集合的元素是一些序偶，这些序偶都是来自集合 $A$，他要满足只存在 $\langle x,y \rangle$ 而不存在 $\langle x,z \rangle ,\langle z,y \rangle $ 也就是这个序偶应当是最小的关系，不能够通过其他的元素“合成”。
这个集合是唯一的
全序关系：
链：集合 $A$ 的一个子集，其中的元素每两个都有关系（在关系图上看就是互相之间都有线相连的结点）
反链： 集合 $A$ 的一个子集，其中的元素每两个之间都没有关系（在关系图上没有连线）
全序关系的定义： P142
哈斯图：
用盖住的性质画出偏序集合图（哈斯图），作图规则为：
- 用小圆圈代表元素
- 如果 $x \preccurlyeq y$ 且 $ x \not = y $ ，则将代表 $y$ 的小圆圈画在代表 $x$ 的小圆圈上
- 如果 $\langle x,y \rangle \in COV ; A$ ，则在 $x$ 和 $y$ 之间用直线连接
- 没有自回路
- 只向上 不向下
- 找极大（小）元、最大（小）元、上（下）界
找关系：
- 极大元、极小元
- 一定存在，但不一定唯一
- 哈斯图的最上一层和最下一层
- 最大元、最小元
- 不一定存在，但是存在一定唯一
- 最上面的一个和最下面的一个
- 上界、下界
- 可以盖住子集中所有的元素，即为上界
- 可以被子集中的所有元素盖住，即为下界
- 这个元素可以是子集中的元素
- 上确界、下确界（最小上界、最大下界）
总结
- 空关系：空集
- 恒等关系：对角线，$\lbrace \langle x,x \rangle |x\in A \rbrace$
- 全域关系 :$A \times B$
- 等价关系（等价类 商集）
- 自反 对称 传递
- 序关系（偏序关系 全序关系）
- 偏序关系：自反 反对称 传递
- 全序关系：集合 $A$ 是一条链
- 哈斯图：极大元极小元、最大元最小元、上下界、上下确界
函数
简单的概念再此省略，几处地点做一下记录。
函数的定义域（前域）必须为整个集合，不能为他的子集（left-total）
满射要求值域为整个 $Y$（right-total）
单射要求为一对一，（right-unique）
既是单射又是满射称为双射
双射的逆函数 $f^c$ 还是双射
函数的复合是左复合（关系的复合是右复合）
满射复合还是满射，单射复合还是单射，双射复合还是双射
逆函数：
$$
\begin{align*}
f^{-1} \circ f =I_X \newline
f \circ f^{-1} =I_Y
\end{align*}
$$