1 序偶与集合的笛卡尔积
1.1 序偶与有序n元组
1.1.1 序偶/有序二元组
由两个对象$x,y$组成的序列称为有序二元组，也称之为序偶，记作$<x,y>$，称$x,y$分别为序偶$<x,y>$的第一元素和第二元素
序偶和集合的区别是序偶有次序，但集合的次序无关紧要
1.1.1.1 序偶相等
设$<x,y><u,v>$是两个序偶，如果$x=u,y=v$则我们称这两个序偶相等，记作$<x,y>=<u,v>$
1.1.2 有序三元组
有序三元组是一个序偶，它的第一个元素也是个序偶，比如$<<a,b>,c>$是一个有序三元组，他也可以被简写成$<a,b,c>$，但$<a,<b,c>>$不是有序三元组
1.1.3 有序n元组
我们可以把上面有序三元组的定义推广到有序n元组，即有序n元组是一个序偶，其第一个元素是一个有序$n-1$元组，记作$<<x_{1},x_{2},\dots,x_{n-1}>,x_{n}>$，简写就是$<x_{1},x_{2},\dots,x_{n}>$
1.1.3.1 有序n元组相等
和序偶一样，要求对应位置的元素全部相等
1.2 集合的笛卡尔积
1.2.1 定义
对于集合$A,B$，由$A$的元素为第一元素，$B$的元素为第二元素组成的全部的序偶的集合，叫做$A,B$的笛卡尔积，记作$A\times B$
$$
A\times B=\left\{ <x,y>|x \in A\land y\in B \right\}
$$
例：设$A=\left\{ 0,1 \right\},B=\left\{ a,b \right\}$求$A\times B,B\times A,A\times A$
Note
$A\times B=\left\{ <0,a>,<0,b>,<1,a>,<1,b> \right\}$
$A\times B=\left\{ <a,0>,<a,1>,<b,0>,<b,1> \right\}$
$A\times A=\left\{ <0,0>,<0,1>,<1,0>,<1,1> \right\}$
既笛卡尔积不满足交换律，也不满足结合律
1.2.2 性质
- 如果$A,B$都是有限集，且$|A|=m,|B|=n$，则$|A\times B|=mn$，即集合作笛卡尔积后得到的序偶的集合的元素数量是两个结合元素数量的积
- $A\times \varnothing=\varnothing\times B=\varnothing$
- $\times$对$\cup,\cap$满足分配律
$$
\begin{align}
A\times(B\cup C)=(A\times B)\cup (A\times C) \\
A\times(B\cap C)=(A\times B)\cap (A\times C)
\end{align}
$$
- 若$C\neq \varnothing$，则$A\subseteq B\Leftrightarrow A \times C\subseteq B\times C\Leftrightarrow C\times A\subseteq C\times B$
- 设$A,B,C,D$为非空集合，则$A\times B\subseteq C\times D\Leftrightarrow A\subseteq C\land B\subseteq D$
- 由于$\times$不满足结合律，所以我们约定
$$
((\dots(A_{1}\times A_{2})\times\dots \times A_{n-1})\times A_{n})=A_{1}\times A_{2}\times\dots \times A_{n}
$$
如果$A_{1}=A_{2}=\dots=A_{n}$，我们可以进一步简写为$A_{1}\times A_{2}\times\dots \times A_{n}=A^{n}$
2 关系及其表示方法
2.1 关系的基本概念
2.1.1 相关
按照某种规则，两个对象或者多个对象之间是有关系的，称这两个对象或者多个对象是相关的
2.1.2 关系的基本概念
设$A,B$是集合，如果$R\subseteq A\times B$，则称$R$是一个从$A$到$B$的二元关系，$R\subseteq A\times B$称$R$是一个$A$上的二元关系，二元关系简称为关系
任何序偶的集合，都可以称之为是一个二元关系，例如
$R=\left\{ <1,a>,<书,车>,<人,树> \right\}$
关系是序偶(点)的集合，关系构成了线、面，这个几何角度有助于我们更好的理解关系
对于$x,y$，它们组成一个序偶$<x,y>$，若它属于一个关系，我们可以这样表示它：
- 后缀表示：$<x,y>\in R$
- 中缀表示：$xRy$
2.1.2.1 关系的定义域
$R\subseteq A\times B$，由所有$<x,y>\in R$的第一个元素组成的集合，称为$R$的定义域，记作$dom R$，即
$$
don(R)=\left\{ x|\exists y(<x,y>\in R) \right\}
$$
2.1.2.2 关系的值域
$R\subseteq A\times B$，由所有$<x,y>\in R$的第二个元素组成的集合，称为$R$的值域，记作$ran R$，即
$$
ran(R)=\left\{ y|\exists x(<x,y>\in R) \right\}
$$
2.1.3 三个特殊关系
2.1.3.1 空关系
$\varnothing\in A\times B$，所以空集也是一个从$A$到$B$的关系，称之为空关系
2.1.3.2 完全关系
对于$A,B$，$A\times B$本身也是一个从$A$到$B$的关系，称之为完全关系(全域关系)
包含集合的笛卡尔积中所有序偶的关系，其关系矩阵全是1
2.1.3.3 恒等关系
$I_{A}\subseteq A\times A$,且$I_{A}=\left\{ <x,x>|x\in A \right\}$，称为$A$上的恒等关系
就是$A$中的每个元素自己和自己组成序偶，这些序偶的集合就是恒等关系
2.1.4 关系的运算
关系是一个序偶的集合，所以集合的运算对于关系来讲也适用
2.2 关系的表示方法
- 枚举法：把所有序偶一一列举出，写在大括号内
- 谓词公式法：用谓词公式表示序偶的第一元素和第二元素之间的关系
- $R=\left\{ <x,y>|x<y \right\}$
- 有向图法：元素为点，关系中的每个序偶都作一条直线从第一元素指向第二元素
- 矩阵表示法：两个有限集$A=\left\{ a_{1},a_{2},\dots,a_{m} \right\}$和$B=\left\{ b_{1},b_{2},\dots,b_{n} \right\}$,$R\subseteq A\times B$，则我们用$m\times n$阶矩阵表示这个关系，$M_{R}=(r_{ij})_{m\times n}$
$$
r_{ij}=\begin{cases}
1 &若<a_{i},b_{j}>\in R\\
0 &若<a_{i},b_{j}>\not\in R
\end{cases}
$$
3 关系的性质
以下讨论均基于在集合$A$上定义的关系
3.1 自反性
$R$是集合$A$中的关系，如果对于$A$中的任意一个元素，都有其与自己组成的序偶在$R$中，则称$R$是$A$中的自反关系，即
$$
R是A中的自反关系\Leftrightarrow \forall x(x \in A\to xRx)
$$
自反关系的特点：
- 有向图的特点：每个节点都有指向自己的环
- 关系矩阵的特点：主对角线都为1
3.2 反自反性
自反性的逆
$R$是集合$A$中的关系，如果对于$A$中的任意一个元素，都没有其与自己组成的序偶在$R$中，则称$R$是$A$中的反自反关系，即
$$
R是A中的反自反关系\Leftrightarrow \forall x(x \in A\to <x,x>\not\in R)
$$
反自反关系的特点：
- 有向图的特点：每个节点都无环
- 关系矩阵的特点：主对角线都为0
3.3 对称性
$R$是集合$A$中的关系，如果对于$A$中的任意两个元素$x,y$，如果关系$R$中有$<x,y>$就必有$<y,x>$，则称$R$是$A$中的对称关系，即
$$
R是A上对称的\Leftrightarrow \forall x\forall y((x\in A\land y\in A\land xRy)\to yRx)
$$
对称关系的特点：
- 有向图的特点：两个节点要么有两条方向相反的边，要么没有边
- 关系矩阵的特点：关系矩阵是以主对角线对称的对称阵
3.4 反对称性
$R$是集合$A$中的关系，如果对于$A$中的任意两个不同元素$x,y$，如果关系$R$中有$<x,y>$就必没有$<y,x>$，则称$R$是$A$中的反对称关系
反对称关系的特点：
- 有向图的特点：两个节点之间最多有一条边
- 关系矩阵的特点：以主对角线为轴对称的两个元素中最多有一个1
3.5 传递性
$R$是集合$A$中的关系，如果对于$A$中的任意三个元素$x,y,z$，如果有$<x,y>,<y,z>$，就有$<x,z>$，则称$R$是$A$中的传递关系，谓词公式为
$$
R在A上是传递的\Leftrightarrow \forall x\forall y\forall z((x\in A\land y\in A\land z\in A\land xRy\land yRz)\to xRz)
$$
由上面的谓词公式我们可以看到，传递性里面有坑，如果前件为假，即$xRy$或者$yRz$中有为假的话，整个蕴含式为真，故前件为假的时候，$R$也是传递的
传递性在有向图和关系矩阵中并不容易识别，必须通过传递性的定义来检查
4 关系的运算
4.1 关系的复合运算
由两个关系可生成一种新的关系，例如
有$a,b,c$三人，$A=\left\{ a,b,c \right\}$，$R$是$A$上的兄妹关系，$S$是$A$上的母子关系
$<a,b>\in R\land<b,c>\in S$
Note
那么$a$和$c$之间就是舅舅和外甥的关系，记作$R\circ S$，称为$R$和$S$的复合
设$R$是$X$到$Y$的关系，$S$是从$Y$到$Z$的关系，则$R$和$S$的复合关系就是从$X$到$Z$的关系，记作$R\circ S$
4.1.1 复合运算的多种计算方法
- 枚举法
- 有向图法
- 谓词公式法：$R$是个函数关系把$X$映射到$Y$，$S$是个函数关系把$Y$映射到$Z$，所以他们的复合其实就是函数的代入过程，把前者代入后者，就可以从$X$映射到$Y$
4.1.2 复合运算的性质
- 不满足交换律
- 满足结合律
- 对于$\cup和\cap$满足分配律：$R\circ(S\cup T)=(R\circ S)\cup(R\circ T)$等
- $R$是从$A$到$B$的关系，则$R\circ I_{B}=I_{A}\circ R=R$，其中$I_{B},I_{A}$分别是$B,A$上的恒等关系
- 由于复合运算满足结合律，所以关系的复合运算可以写成乘幂的形式，并且定义$R^{0}=I_{A}$
设$x,y\in A$，如果$<x,y>\in R^{k}\Leftrightarrow$在$R$的有向图上有从$x$到$y$的路径
4.2 关系的求逆运算
$R$是从$A$到$B$的关系，如果将$R$中的所有序偶的两个元素的位置互换，得到一个从$B$到$A$的关系，称之为$R$的逆关系，记作$R^C$，或$R^{-1}$
$$
R^C=\left\{ <y,x>|<x,y>\in R \right\}
$$
4.2.1 求逆运算的计算
- 把$R$中所有序偶的两个元素的位置调换
- 有向图：把$R$的有向图的所有边的方向颠倒
- 关系矩阵，对$R$的关系矩阵求转置
4.2.2 求逆关系的性质
- $(R^C)^C=R$
- $(R\cup S)^C=R^C\cup S^C$，$(R\cap S)^C=R^C\cap S^c$，$(R-S)^C=R^C-S^C$，$(R\circ S)^C=R^C\circ S^C$
- $R\subseteq S\Leftrightarrow R^C\subseteq S^C$
- $\sim(R)^{C}=\sim R^{C}$
- $R$是$A$上的关系，若要$R$是对称的，当且仅当$R^{C}=R$
其实很多都跟矩阵的转置的运算律完全一样，可以触类旁通
4.3 关系的闭包运算
关系的闭包是通过关系的复合和求逆运算构成的一个新的关系，新关系满足某些特性
这里学习自反闭包，对称闭包和传递闭包
4.3.1 关系闭包运算的定义
自反闭包的定义：对于$A$中的关系$R$，如果$A$上的另一个关系$R’$满足
- $R\subseteq R’$
- $R’$是自反的
- $R’$是包含$R$的最小的那个自反关系
则称$R’$是$R$的自反闭包，记作$r(R)$
同样的定义方法，我们可以定义
- 对称闭包，记作$s(R)$
- 传递闭包，记作$t(R)$
4.3.2 关系闭包运算的计算方法
- 自反闭包：给定$A$中的关系$R$，则$r(R)=R\cup I_{A}$
- 对称闭包：给定$A$中的关系$R$，则$s(R)=R\cup R^{C}$
- 传递闭包：给定$A$中的关系$R$，则$t(R)=R\cup R^{2}\cup R^{3}\cup\dots$
对于传递闭包的计算：关系的复合运算次幂是有周期性的，故它的计算有一定规律，对于元素数量为$n$的有限集合$A$中的关系$R$，并不是真的要算到无穷次幂：
$$
t(R)=R\cup R^{2}\cup \dots \cup R^{n}
$$
Note
题外话：对于$R$的传递闭包，其实计算它就是计算两个节点之间的路径，我们可以基于$R$的关系矩阵，使用Floyd-Warshall算法来计算，这名儿怎么这么熟悉呢，诶嘿嘿，啊~哈哈哈哈哈哈…动态规划来咯哈哈哈
5 几种特殊的二元关系
5.1 等价关系与划分
5.1.1 划分与覆盖
5.1.1.1 基本概念
5.1.1.1.1 覆盖
设$X$是一个非空集合，$A=\left\{ A_{1},A_{2},\dots,A_{n} \right\},A_{i}\neq \varnothing,A_{i}\in X(i=1,2,\dots,n)$，如果满足$A_{1}\cup A_{2}\cup\dots \cup A_{n}=X$，则我们称$A$是集合$X$的一个覆盖
5.1.1.1.2 划分
设$A$是$X$的一个覆盖，且$A_{i}\cap A_{j}=\varnothing(i\neq j,1\leq i,j\leq n)$，则称$A$是$X$的划分，每个$A_{i}$称为这个划分的一个划分类，其实就是把$X$划分成了许多小集合，然后$A$是这些小集合的集合
由上我们知道，划分一定是覆盖，但覆盖不一定是划分，因为每个小$A$集合里可能有重复部分
5.1.1.2 最大划分和最小划分
最小划分：只有一个划分块的划分，这个划分块就是$X$本身，$\left\{ X \right\}$
最大划分：划分块最多的划分，即每个划分块里只有一个元素
5.1.1.3 交叉划分
例：$X$是全体大连理工大学学生的集合，$A,B$都是$X$的划分
$A=\left\{ 大工的男生,大工的女生 \right\}$
$B=\left\{ 陕西籍大工学生,非陕西籍大工学生 \right\}$
Note
若$C=\left\{ 陕西籍大工男生,陕西籍大工女生,非陕西籍大工男生,非陕西籍大工女生 \right\}$
显然$C$也是$X$的划分，且是$A,B$两种划分的交叉划分
若$A,B$都是$X$的划分，则$A_{i}\cap B_{i}$组成的集合$C$，称$C$是$A,B$两种划分的交叉划分
5.1.2 等价关系与等价类
5.1.2.1 等价关系
设$R$是$A$上的关系,若$R$是自反的、对称、传递的，则称$R$是$A$上的等价关系
若$a,b\in A$，$R$是等价关系，$aRb$，则称$a,b$等价
5.1.2.1.1 等价关系的有向图
- 完全关系(全域关系)图
- 等价关系的有向图
等价关系的有向图由若干个独立子图构成，每个独立子图都是完全关系图
所以我们就能通过完全关系图的个数来计算特定元素个数的集合上可以有多少个等价关系
例：$A=\left\{ 1,2,3 \right\}$，问最多能组成多少个等价关系
Note
若由一个完全关系图构成：1,2,3 ；只有一个
若由两个完全关系图构成：{1,2},3、{1,3},2、{2,3},1；三个
若有三个完全关系图构成：{1},{2},{3}；只有一个
所以这个集合上的关系可以有五个等价关系
5.1.2.2 等价类
$R$是$A$上的等价关系，$a\in A$，由$a$确定的集合$[a]_{R}$：
$$
[a]_{R}=\left\{ x|x \in A \land<a,x>\in R \right\}
$$
称这个集合为由$a$形成的$R$等价类，简称$a$等价类
例：$A=\left\{ 1,2,3,4,5,6,7 \right\}$，$R$是$A$上的模3同余关系
Note
$[1]_{R}=\left\{ 1,4,7 \right\}=[4]_{R}=[7]_{R}$ 余数为1的等价类
$[2]_{R}=\left\{ 2,5 \right\}=[5]_{R}$ 余数为2的等价类
$[3]_{R}=\left\{ 3,6 \right\}=[6]_{R}$ 余数为0的等价类
5.1.2.2.1 由等价关系图求等价类
$R$的关系图中每个独立子图上的节点，构成一个等价类，独立子图的个数就是不同的等价类个数
5.1.2.2.2 等价类的性质
$R$是$A$上的等价关系
- 对于任意$a\in A$，如果有$x,y\in[a]_{R}$，则$<x,y>\in R$，意思是同一个等价类里面的元素互有等价关系
- 对于任意$a,b\in A$，若$[a]_{R}\cap[b]_{R}=\varnothing$，当且仅当$<a,b>\not\in R$，意思是不同的等价类的那个$a$，互不等价，这个从关系图上很容易看出，每种等价类是一个独立子图，而独立子图之间没有任何连接
- $[a]_{R}=[b]_{R}$，当且仅当$<a,b>\in R$，其实就是上面一条的逆
- $A$中任何元素$a$，$a$必属于且仅属于一个关于$R$的等价类
- $R$的所有等价类构成的集合是$A$的一个划分念)，这个划分称之为商集
5.1.2.3 商集
$R$是$A$上等价关系，由$R$的所有等价类构成的集合称之为$A$关于$R$的商集。记作$\frac{A}{R}$，即
$$
\frac{A}{R}=\left\{ [a]_{R}|a\in A \right\}
$$
实际上就给出了集合除运算的定义
例：$A=\left\{ 1,2,3,4,5,6,7 \right\}$，$R$是$A$上的模3同余关系，则$\frac{A}{R}=\left\{ [1]_{R},[2]_{R},[3]_{R} \right\}=\left\{ \left\{ 1,4,7 \right\},\left\{ 2,5 \right\} \left\{ 3,6 \right\}\right\}$
5.1.3 由划分确定等价关系
由等价关系我们可以通过商集的形式来确定一个划分，它必有逆运算，即我们如何通过一个划分$A$来求一个等价关系$R$
例：$X=\left\{ 1,2,3,4 \right\}$，$A=\left\{ \left\{ 1,2 \right\},\left\{ 3 \right\} ,\left\{ 4 \right\}\right\}$是$X$的一个划分，求$X$的等价关系$R$，使得$\frac{X}{R}=A$
Note
等价关系是由几个完全关系组成的，所以我们需要把划分还原成完全关系，如下式
$R=\left\{ 1,2 \right\}^{2}\cup \left\{ 3 \right\}^{2}\cup \left\{ 4 \right\}^{2}$
即构造方法：$R=A_{1}^{2}\cup A_{2}^{2}\cup,\dots,\cup A_{n}^{2}$，其中$A_{i}^{2}=A_{i}\times A_{i}$
5.2 相容关系
Caution
施工中，相容关系和等价关系的区别是，相容关系需要关系是自反的、对称的而不要求传递性，故等价关系一定是相容关系，相容关系不一定是等价关系
5.3 序关系
5.3.1 偏序关系
$R$是$A$上的具有自反、反对称和传递性的关系，则称$R$是$A$上的偏序关系，并且称$<A,R>$是偏序集
例：实数集上的$\leq,\geq$以及集合的$\subseteq$都是偏序关系
我们用符号$\preccurlyeq$来泛指任意偏序关系
例：$A=\left\{ 1,2,4,6 \right\},\text{“|”}$是$A$上的整除关系，是一个偏序关系，其关系图如下图
我们可以从图中看出偏序关系的有向图的特点：
- 每个节点都有环(自反性)
- 不同节点之间至多有一条边(反对称性)
- 传递性
5.3.1.1 偏序关系的哈斯图
由于偏序关系的有向图有上述特点，所以我们可以对它进行简化
- 自反性：每个节点都有环，省去
- 反对称性：约定按照第一元素在左、第二元素在右 或 第一元素在下、第二元素在上的位置关系来安置顶点，这样就可以通过元素之间的位置关系来反映它们之间的次序关系，从而省略箭头
- 传递性：如果$<a,b>\in R,<b,c>\in R$，则省略$<a,c>$不画
通过上述关系画的偏序关系的图就叫做哈斯图
5.3.2 全序关系
集合$A$上偏序关系$R$，如果任意$a,b\in A$，都有$a\preccurlyeq b,b\preccurlyeq a$，则称$R$为$A$上的全序关系
实际上意思就是$A$中的任两个元素都有$R$关系，相比与偏序关系来说就是偏序关系中$A$只有部分元素属于$R$关系
5.3.3 偏序集中的重要元素
5.3.3.1 极大元与极小元
设$(P,\preccurlyeq)$是个偏序集，$A\subseteq P$，若$a\in A$，且在$A$中不存在元素$b(b\neq a)$能够使得$a\preccurlyeq b$，则称$a$为$A$中的极大元
Note
小于等于就是一种偏序关系，可以用小于等于来理解，$P$相当于实数集，$A$就是从实数集中取出有限的一部分构成的集合，$a$就是这个集合中最大的元素，它使得$A$中除了它自己，不存在任何一个元素能够大于等于它，所以$a$就是$A$中的极大元
设$(P,\preccurlyeq)$是个偏序集，$A\subseteq P$，若$a\in A$，且在$A$中不存在元素$b(b\neq a)$能够使得$b\preccurlyeq a$，则称$a$为$A$中的极小元，它的理解也同上
极大元和极小元总是存在的，极大元极小元并不要求唯一，同一个元素可以既是极大元又是极小元
5.3.3.2 最大元和最小元
设$(P,\preccurlyeq)$是个偏序集，$A\subseteq P$，若$a\in A$，且$\forall b\in A,b \preccurlyeq a$，则称$a$为$A$中的最大元，若$\forall b\in A,a \preccurlyeq b$，则称$a$为$A$中的最小元
如果子集$A$有最小元最大元，则最大元最小元是唯一的，只要有唯一的极大(小)元，则这个极大(小)元就是其最大(小元)，否则就没有最大(小)元
5.3.3.3 上界和下界
设$(P,\preccurlyeq)$是个偏序集，$A\subseteq P$，若$a\in P$，且$\forall b\in A,b \preccurlyeq a$，则称$a$为$A$的上界，若$\forall b\in A,a \preccurlyeq b$，则称$a$为$A$的下界
上界和下界是放眼到全集$P$的概念，要去全集找
5.3.3.4 上确界和下确界
设$(P,\preccurlyeq)$是个偏序集，$A\subseteq P$，一个$A$的上界$a$对于$\forall A$的上界$b$，都有$a \preccurlyeq b$，则$a$是$A$的上确界，反之则是下确界
上确界就是上界中的最小者，下确界就是下界中的最大者，如果上下确界存在，则他们一定是唯一的
6 函数
6.1 函数的基本概念
6.1.1 概念
对于集合$X,Y$，$f$是从$X$到$Y$的关系，对于任意$x \in X$，都存在唯一的$y\in Y$，使得$<x,y>\in f$，则$f$是从$X$到$Y$的函数(变换、映射)，记作$f:X\to Y$
Note
原像，像，定义域，值域，陪域(值域的全集)高中、线性代数、高数给这些东西都各讲了一遍，离散现在又讲一遍，这里不再赘述，有需要可以自己去查
6.1.2 函数的表示方法
同关系的表示方法，也是有
- 枚举法
- 有向图
- 矩阵：每行必且有且仅有一个1
- 谓词描述法
6.1.3 从X到Y函数的集合
定义$Y^{X}=\left\{ f|f:X\to Y \right\}$，是由所有的从$X$到$Y$函数构成的集合，即把$X$映射到$Y$的不同方法的集合，若$|X|=m,|Y|=n$，所以$|Y^{X}|=|Y|^{|X|}=n^{m}$
6.1.4 特殊函数
6.1.4.1 常值函数
对于不同的$x$，关系$f$对应出来的同一个$y$，这样的函数就是常值函数
6.1.4.2 恒等函数
对于每个$x$，关系$f$对应出来$x$本身，这样的函数就是恒等函数
6.1.5 函数相等
函数相等就是定义域，陪域，关系全部相等的一对函数
6.1.6 函数的类型
- 满射函数：值域等于陪域，即对于陪域中的每个元素，在定义域中都有元素与之对应
- 映内函数：值域是陪域的真子集，即陪域中某些元素，在定义域内没有一个元素与之对应
- 单射函数：不存在定义域内的两个不同元素对应值域中同一个元素的情况，输入和输出是一一对应的
- 双射函数：综合了满射函数和单射函数特点的，叫双射函数
6.2 函数的复合
$f:X\to Y,g:Y\to Z$是函数，则定义
$$
g \circ f=\left\{ <x,z>| x \in X \land z\in Z\land \exists y(y\in Y\land<x,y>\in f\land<y,z>\in g)\right\}
$$
则称$g \circ f$是$f,g$的复合函数
Note
人话：把f代入到了g里，得到了一个新的复合函数，这个函数是$X$和$Z$的对应关系
其实就是$g(f(x))=g \circ f(x)$
6.2.1 函数复合的运算
和关系复合运算计算方法一样，不再赘述
6.2.2 函数复合的性质
- 函数复合满足结合律
- 如果$f,g$满射，则$g \circ f$也满射；如果$f,g$单射，则$g \circ f$也单射；如果$f,g$双射，则$g \circ f$也双射
- $f \circ I_{X} = f,I_{Y} \circ f = f$，$I_{X},I_{Y}$是恒等函数
6.3 逆函数及其性质
6.3.1 定义
若$f:X\to Y$是双射函数，则$f^{C}:Y\to X$也是函数，称之为$f$的逆函数，可以写成$f^{-1}$，$f^{-1}$也是双射函数
$f^{-1}$存在，我们称$f$可逆
如果$f$不是双射函数的话，取逆之后定义域可能会有元素没有对应，或者会有元素对应两个像
6.3.2 性质
- $(f^{-1})^{-1}=f$
- $f^{-1} \circ f=I_{X},f \circ f^{-1}=I_{Y}$
- $(g \circ f)^{-1}=f^{-1} \circ g^{-1}$