集合论部分包括以下章节：
- 第1章 数学语言与证明方法
- 第4章 关系
- 第5章 函数
本部分需要先了解到古典集合论的相关内容，从而对集合与集合之间的关系进行描述。
🤔 集合论部分的特点是，所有的数学元素都可以用集合来表示，比如关系是有序对的集合，而函数则是特殊的关系。这于初等数学的理解是不同的。
数学语言与证明方法
特殊的集合运算
简单的就不列出了
集合的相对补：$A-B={ x | x\in A \and x \notin B}$
集合的绝对补：$\sim{A}=E-A$
集合的对称差：$A\oplus B=(A-B)\cap(B-A)$
🤔 对称差类似于异或运算
关系
有序对和笛卡尔积
两个元素按照一定次序构成的二元组称为一个有序对，记作 $\left\langle x, y\right\rangle$，区分第一元素和第二元素。
设集合$A,B$定义$A$和$B$的笛卡尔积$A\times B$
$$
A \times B = {\left\langle a, b \right\rangle|a\in A \and b \in B}
$$
🤔 笛卡尔积的性质显而易见了兄弟们
二元关系
若集合满足以下条件之一：
- 集合非空，它的元素都是有序对
- 集合是空集
则该集合是一个二元关系，简称关系，记作$R$。若$\left\langle x,y \right\rangle \in R$，则可记作$xRy$。
🤔 $xRy$可以看成是逻辑值
集合间定义关系
从$A$到$B$的二元关系，$A$上的二元关系
重要关系
全域关系
$$
E_A={\langle x,y\rangle|x\in A\land y\in A}=A\times A
$$
恒等关系
$$
I_A={\langle x,x\rangle|x\in A}
$$
关系的表示
集合表达
🤔 有序对的集合列举
关系图
$A$上关系$R$的关系图是有向无权图$G_R=\langle A,R\rangle$，其中 A 为 G 的节点集
关系矩阵
设$R$是从$A$到$B$的关系，$R$ 的关系矩阵是布尔矩阵$M_R=(r_{ij}){m\times n}$，其中$r{ij}=1\Leftrightarrow \langle x_i,y_j\rangle\in R $。
关系运算
关系基本运算
由于关系本身是有序对的集合，因此所有的集合运算都能适用。
关系特殊运算
定义域：$domR$，关系$R$中第一元素的集合
值域：$ranR$，关系$R$中第二元素的集合
域：$fldR$，关系种第一元素和第二元素的集合
逆：$R^{-1}={\langle y,x\rangle|\langle x,y\rangle\in R}$
合成：$R\circ S={\langle x,z\rangle|\exists y(\langle x,y\rangle\in R\land\langle y,z\rangle\in S)}$
运算定理
定理1：设$$F$$是任意的关系，则
- $(F^{-1})^{-1}=F$
- $domF^{-1}=ranF,ranF^{-1}=domF$
定理2：设$$F,G,H$$是任意的关系，则
- $(F\circ G)\circ H=F\circ(G\circ H)$
- $(F\circ G)^{-1}=G^{-1}\circ F^{-1}$
定理3：设$$R$$为$$A$$上的关系，则
- $R\circ I_A=I_A\circ R=R$
幂运算
设$$R$$为$$A$$上的关系，则$$R$$的 n 次幂的定义为
- $$R^0={\langle x,x\rangle|x\in A}=I_A$$
- $$R^{n+1}=R^n\circ R$$
🤔 这里可以用于关系的矩阵运算
关系的性质
🤔 重难点，这里衍生出了特殊的关系
定义及判别
自反
设$R$为$A$上的关系，有
- 若$\forall x(x\in A\rightarrow\langle x,x\rangle \in R)$，则称$R$在$A$上自反
- 若$\forall x(x\in A\rightarrow\langle x,x\rangle \notin R)$，则称$R$在$A$上反自反
自反：对角线全为 1
反自反：对角线全为 0
除空关系外，一个关系不可能同时是自反和反自反的
对称
设$R$为$A$上的关系，有
- 若 $\forall x\forall y(x,y\in A\ \land\langle x,y\rangle \in R\rightarrow \langle y,x\rangle\in R)$，则称$R$在$A$上对称
- 若 $\forall x\forall y(x,y\in A\ \land\langle x,y\rangle \in R\land \langle y,x\rangle\in R\rightarrow x=y)$，则称$R$在$A$上反对称
对称：每个元素要么自我相等要么两两相反
反对称：每个元素不能两两相反（但可以自我相等）
一个关系可以同时是对称和反对称的
传递
设$R$为$A$上的关系，有
$$
\forall x\forall y\forall z(x,y,z\in A\land \langle x,y\rangle\in R\land \langle y,z\rangle\in R\rightarrow \langle x,z\rangle\in R)
$$
则称$R$是传递的
判别
关系的闭包
设$R$为$A$上的关系，若$R$不具有某种性质，可以通过在$R$中加入最少数量的有序对来补充$R$，使其具有某种性质
定义
设$R$为非空集合$A$上的关系，$R$的自反（对称或传递）闭包是$A$上的关系$R’$，使$R’$满足以下条件
- $R’$是自反的（对称的或传递的）
- $R\subseteq R’$
- 对$A$上任何包含$R$的自反（对称或传递）关系$R’’$有$R’\subseteq R’’$
自反闭包：$r(R)$
对称闭包：$s(R)$
传递闭包：$t(R)$
理解
想使一个关系拥有某一性质，向其中尽量少地添加一些有序对，形成的新关系称为闭包。
定理
设$R$为$A$上的关系，有
- $r(R)=R\cup R^0$
- $s(R)=R\cup R^{-1}$
- $t(R)=R\cup R^2\cup R^3\cup\ldots$
用矩阵关系表示
- $M_r=M+E$
- $M_S=M+M’$
- $M_t=M+M^2+M^3+\ldots$
用图关系表示
- $G_r$：在图$G$中每一个缺少环的结点都加一个环
- $G_s$：将$G$中的单向边变成双向边
- $G_t$：
Warshall算法
🤔 必考必考，行加到列对应1所在行上。
深入理解一下，第$n$行对应的是$n$号元为第一元素的关系$\left\langle #n,b \right\rangle$，而$n$列对应的是$n$号元为第二元素的关系$\left\langle a,#n \right\rangle$，加上以后就表示关系的合成，因此能够构造出传递闭包。
等价
等价关系
设$R$为非空集合$A$上的关系，若$R$是自反的，对称的，传递的，则称$R$为$A$上的等价关系，
对于任何元素 $x,y\in A$，若$xRy$，则称 x, y 等价，记为$x\sim y$
等价类和商集
定义
按某一等价关系，将A的元素划分成若干个子集，彼此等价的元素被分在同一个子集里，这些子集称作这个等价关系产生的等价类。记作$[x]$
性质
- $\forall x\in A,[x]$是$A$的非空子集
- $\forall x,y\in A$，如果$xRy$，则$[x]=[y]$
- $\forall x,y\in A$，如果$xRy$不成立，则$[x]$与$[y]$不交
- $\bigcup_{x\in A}[x]=A$，即$A$中元素构成的所有等价类的并集等于$A$
商集
$A$上的全体等价类构成的集合称作$A$关于等价关系$R$的商集，记作$A/R$，即
$$
A/R={[x]_R|x\in A}
$$
集合的划分
定义
设$A$为非空集合，若$A$的子集族 $\pi(\pi\subseteq P(A))$满足下面条件
- $\emptyset\notin\pi$（无空集）
- $\forall x\forall y(x,y\in\pi\land x\neq y\rightarrow x\cap y=\emptyset)$（元素无公共部分）
- $\bigcup_{x\in\pi}x=A$（拼起来是完整的）
则$\pi$称是$A$的一个划分，称$\pi$中的元素为$A$的划分块
- 商集$A/R$就是$A$的一个划分，所以又可以定义商集$R$
$$
R={\langle x,y\rangle|x,y\in A\land x与y在\pi 的同一划分块中 }
$$
偏序
偏序关系
非空集合$A$上的自反、反对称和传递的关系称为$A$上的偏序关系，简称偏序，记作$\preceq$
若$\langle x,y\rangle\in\preceq$，则记作$x\preceq y$，读作 x “小于等于” y
可比
设 $R$ 为非空集合 $A$ 上的偏序关系，$\forall x,y\in A$，若$x\preceq y\lor y\preceq x$，则称 x 与 y 可比
拟序
设$R$为非空集合$A$上的偏序关系，若$R$是反自反的和传递的，则称$R$是$A$上的拟序关系，简称为拟序，记作$\prec$
全序
设$R$为非空集合$A$上的偏序关系，$\forall x,y\in A$，x与y都是可比的，则称$R$为全序关系，简称全序（或线序）
覆盖
设$R$为非空集合$A$上的偏序关系，$\forall x,y\in A$，若$x\prec y$且不存在$z\in A$使得$x\prec z\prec y$，则称y覆盖x
定义偏序关系$R$的一个子关系——覆盖关系$T$
$
T={\langle x,y\rangle|\langle x,y\rangle\in R且y覆盖x}
$
$T$的自反传递闭包$rt(T)$就等于$R$
偏序集
集合$A$和$A$上的偏序关系$\preceq$一起叫做偏序集，记作$\langle A,\preceq\rangle$
哈斯图
定义
利用偏序自反、反对称、传递性简化的关系图
特点
- 每个结点没有环
- 两个联通结点之间的序关系通过结点位置的高低表示，位置低的元素顺序在前
- 具有覆盖关系的两个结点之间连边
特殊元素或子集
设$\langle A,\preceq\rangle$为偏序集，$B\subseteq A,y\in B$
- 若$\forall x(x\in B\rightarrow y\preceq x) $成立，则称$y$为$B$的最小元
- 若$\forall x(x\in B\rightarrow x\preceq y) $成立，则称$y$为$B$的最大元
- 若$\forall x(x\in B\land x\preceq y\rightarrow x=y) $成立，则称$y$为$B$的极小元
- 若$\forall x(x\in B\land y\preceq x\rightarrow x=y) $成立，则称$y$为$B$的极大元
有性质如下
- 对于有穷集，极小元和极大元一定存在，还可能存在多个
- 最小元和最大元不一定存在，如果存在一定唯一
- 最小元一定是极小元，最大元一定是极大元
- 孤立结点既是极小元，也是极大元
设$\langle A,\preceq\rangle$为偏序集，$B\subseteq A,y\in A$
- 若$\forall x(x\in B\rightarrow x\preceq y) $成立，则称$y$为$B$的上界
- 若$\forall x(x\in B\rightarrow y\preceq x) $成立，则称$y$为$B$的下界
- 令$C={y|y为B的上界}$，则称$C$的最小元为$B$的最小上界或上确界
- 令$D={y|y为B的下界}$，则称$D$的最大元为$B$的最大下界或下确界
有性质如下
- 上界，下界，最大下界，最小上界不一定存在
- 如果下界，上界存在，也不一定是唯一的
- 最大下界，最小上界如果存在，则是唯一的
- 子集$B$的最小元就是他的最大下界，最大元就是他的最小上界；反之不对
理解
最小元素就是在子集中处于最低层且每个元素通过图中路径都可以找到它且它的下面没有元素。
极大元素就是在子集中它的上面没有元素。
极小元素就是在子集中它的下面没有元素。
（记住：这里如果是子集，应当将子集当成一个单独的整体，而不受全集的影响。）
上届：所有子集内的元素沿着路径向上都可以找到的元素（这里包括子集和子集以外的元素）。根据上面所说的话，我们可以断定上届也可以是子集内的元素。
下届：所有子集内的元素沿着路径向下都可以找到的元素（这里包括子集和子集以外的元素）。根据上面所说的话，我们可以断定下届也可以是子集内的元素。
上确界：这里我们可以将上届元素看成一个独立的整体，而上确界就是这个集合的最小元，我们称为最小上届。根据上面所说的话，我们可以断定上届也可以是上确界。
下确界：这里我们可以将下届元素看成一个独立的整体，而下确界就是这个集合的最大元，我们称为最大下届。根据上面所说的话，我们可以断定下届也可以是下确界。
特殊子集
设$\langle A,\preceq\rangle$为偏序集，$B\subseteq A$
- 若$\forall x,y\in B$，$x$与$y$都是可比的，则称$B$是$A$中的一条链，$B$中的元素个数称为链的长度。
- 若$\forall x,y\in B,x\neq y$，$x$与$y$都是不可比的，则称$B$是$A$中的一条反链，$B$中的元素个数称为反链的长度。
有定理
- 设$\langle A,\preceq\rangle$为偏序集，若$A$中最长链的长度为$n$，则该偏序集可以分解为$n$条不相交的反链
函数
基本概念
函数是一种特殊的关系，若$f:A\rightarrow B$且满足以下条件，则称$f$为函数关系，简称函数：
- $domf=A$
- $ranf\subseteq B$
B上A
所有从$A$到$B$的函数的集合记作 $B^A$，符号化表示为：
$$
B^A={f|f:A\rightarrow B}
$$
重要实例
像和原像
函数特殊运算
反函数，合成
