特殊关系

零、预备知识

1、二元关系的相关概念

• 序偶
• 笛卡尔积
• 二元关系
• 关系的表示法：集合，关系图，关系矩阵
• 空关系，全关系，恒等关系

2、关系的运算

• 交，并，差，补
• 复合运算$R\circ S$
• 逆运算
• 幂运算

3、关系的性质

• 自反性，反自反性
• 对称性，反对称性
• 传递性

一、相容关系

1、相容关系的定义

定义：设$R$是定义在非空集合$A$上的关系，如果$R$是自反的、对称的，则称$R$是$A$上的相容关系。

判断方法：$R$是相容关系$\iff$$R$同时具有自反性和对称性，绘制关系图和关系矩阵可以方便判断。例如，某相容关系$R$的关系矩阵如下图。

$$\begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}$$

2、集合的覆盖

定义：给定非空集合$A$，设有集合$S= \{ A_{1},A_{2},\cdots ,A_{m} \}$ 。如果

$$(1)A_{i}\subseteq A \text{且} A_{i}\ne \emptyset ,i=1,2,\cdots,m;$$

$$(2){\textstyle \bigcup_{i=1}^{m}} A_{i}=A。$$

则$S$被称作集合$A$的一个覆盖。
例如$\{ \{a,b,d\},\{c,f\},\{e\} \}$和$\{ \{a\},\{b\},\{c,d,e\},\{f\} \}$两个集合都是$A=\{a,b,c,d,e,f\}$的覆盖

注意：一个集合的覆盖不是唯一的。

定理：给定集合$A$的一个覆盖$S= \{ A_{1},A_{2},\cdots ,A_{m} \}$ ，设：

$$R＝(A_{1}×A_{1})\cup (A_{2}×A_{2})\cup \cdots \cup (A_{n}×A_{n})$$

则$R$是$A$上的相容关系。

注意：不同的覆盖可能构造出相同的相容关系。

二、等价关系

1、等价关系的定义

定义：设$R$是定义在非空集合$A$上的关系，如果$R$是自反的、对称的、传递的，则称$R$为$A$上的等价关系。

判断方法：$R$是等价关系$\iff$$R$同时具有自反性、对称性和传递性。通常使用关系图来判断，等价关系一般描述某一群体所共有的性质，例如一袋彩虹糖中的同色关系，人群中的同姓关系，整数集中以$n$为模的同余关系等。

同余关系：设$n$为正整数，考虑整数集合$Z$上的以$n$为模的同余关系如下：

$$R= \{ <x,y>\mid {x,y∈Z}\wedge n\mid (x-y) \}$$

一般来说，记$xRy$为$x\equiv y(\bmod n)$，称为同余式。
即$x\equiv y(\bmod n) \iff x \bmod n=y \bmod n$

2、集合的划分

定义：给定非空集合$A$，设有集合$S= \{ A_{1},A_{2},\cdots ,A_{m} \}$。如果满足
$(1)A_{i}\subseteq A\text{且}A_{i}\ne \emptyset ,i=1,2,3,\cdots ,m;$
$(2)A_{i}\cap A_{j}=\emptyset,i\ne j,i,j=1,2,3,\cdots ,m;$
$(3){\textstyle \bigcup_{i=1}^{m}} A_{i}=A$
则称$S$为集合$A$的一个划分(Partition)，而$A_{1},A_{2},\cdots ,A_{m}$叫做这个划分的块(Block)或类(Class)。

注意：集合的划分一定是该集合的一个覆盖，反之不然。

3、等价类与商集

定义：设$R$是非空集合$A$上的等价关系，对$\forall x\in R$，称集合

$$[x]_{R}= \{ y\mid y\in A\wedge \langle x,y \rangle \in R \}$$

为$x$关于$R$的等价类(Equivalence Class)，或叫作由$x$生成的一个$R$等价类，其中$x$称为$[x]_{R}$的生成元(或叫代表元，或典型元)(Generator) 。例如$[李白]_{同姓关系}= \{ x\mid x姓李 \}$

等价类$[x]_{R}$的计算方法：对$A$中的任意$x$，找出以$x$为第一元素的所有序偶，将其第二元素构成集合，这个集合就是$[x]_{R}$。

定理：设$R$是非空集合$A$上的等价关系，则有下面的结论成立。
$(1)对\forall x\in A,[x]_{R}\ne \emptyset$
$(2)对\forall x\in A,\forall y\in A, 如果y\in [x]_{R},则有[x]_{R}=[y]_{R};如果y\notin [x]_{R}, 则有[x]_{R}\cap [y]_{R}=\emptyset$
$(3) {\textstyle \bigcup_{x\in A}^{}} [x]_{R}=A$

定义：设$R$是非空集合$A$上的等价关系，由$R$确定的一切等价类构成的集合，称为集合$A$上关于$R$的商集(Quotient Set)，记为$A/R$，即

$$A/R= \{ [x]_{R}\mid x\in A \}$$

商集实际上是以等价关系$R$对集合$A$的一个划分。

商集$A/R$的计算步骤：
(1)任选A中一个元素$a$，计算$[a]_{R}$。
(2)如果$[a]_{R}\ne A$，任选一个元素$b\in A−[a]_{R}$，计算$[b]_{R}$。
(3)如果$[a]_{R}\cup [b]_{R}\ne A$，任选一个元素$c\in A−[a]_{R}−[b]_{R}$，计算$[c]_{R}$
以此类推，直到$A$中所有元素都包含在计算出的等价类中。

4、等价关系与划分的关系

设R是非空集合$A$上的等价关系，则$A$对$R$的商集$A/R$是$A$的一个划分，称之为由$R$所导出的等价划分。
给定集合$A$的一个划分$\Pi= \{ A_{1},A_{2},\cdots ,A_{n} \}$， 则由该划分确定的关系
$R＝(A_{1}×A_{1})\cup (A_{2}×A_{2})\cup \cdots \cup (A_{n}×A_{n})$是$A$上的等价关系, 称此关系$R$为由划分$\Pi$所导出的等价关系。
总之，集合$A$上的等价关系与集合$A$的划分是一一对应的。

题型：求出与划分对应的等价关系

三、次序关系

1、拟序关系

定义：设$R$是非空集合$A$上的关系，如果$R$是反自反、反对称和传递的，则称$R$是$A$上的拟序关系(Quasi-Order Relation)，简称拟序，记为"$<$"，读作“小于”，并将“$\langle a,b \rangle \in <$”记为“$a＜b$”。
序偶$\langle A,< \rangle$称为拟序集(Quasi-Order Set)。

判断方法：$R$是拟序关系$\iff$$R$同时具有反自反性、反对称性和传递性$\iff$$R$同时具有反自反性和传递性。即如果一个关系具有反自反性和传递性，那么它一定具有反对称性，这一点通过反证法即可证明。

题型：拟序关系的判断和证明

2、偏序关系

定义：设$R$是非空集合$A$上的关系，如果$R$是自反的、反对称的和传递的，则称R是A上的偏序关系(Partial Order Relation)，简称偏序，记为“$\le$”，读作“小于等于”，并将“$\langle a,b \rangle \in \le$”记为“$a\le b$”。
序偶$\langle A,\le \rangle$称为偏序集(PartialOrder Set)。

判断方法：$R$是偏序关系$\iff$$R$同时具有自反性、反对称性和传递性。一般通过观察关系图的特点来判断。

注意：“$\le$”$-$“$I_{A}$”=“$<$”，“$<$”$\cup$"$I_{A}$“=”$\le$"，$I_{A}$为$A$上的恒等关系。

题型：偏序关系的判断与证明

哈斯图(Hasse Diagram)：通过以下方式对偏序关系的关系图进行简化得到关系R的哈斯图。
(1)省略自反性：去掉关系图中所有的自环。
(2)省略反对称性：若$\langle x,y \rangle \in R$，则将x画在y的下方，去掉该边的箭头。
(3)省略传递性：若$\langle x,y \rangle \in R$且$\langle y,z \rangle \in R$，则去掉$\langle x,z \rangle$所在的边。
注意：只有偏序关系才有哈斯图。

集合的最元与极元：设$\langle A,\le \rangle$是偏序集，$B$是$A$的非空子集，
(1)如果$\exists b(b\in B\wedge \forall x(x\in B\to x\le b))=1$，则称$b$为$B$的最大元素，简称最大元；
(2)如果$\exists b(b\in B\wedge \forall x(x\in B\to b\le x))=1$，则称$b$为$B$的最小元素，简称最小元；
(3)如果$\exists b(b\in B\wedge \forall x(x\in B\wedge b\le x\to x=b))=1$，则称$b$为$B$的极大元素，简称极大元；
(4)如果$\exists b(b\in B\wedge \forall x(x\in B\wedge x\le b\to x=b))=1$，则称$b$为$B$的极小元素，简称极小元。

判断方法：
(1)$b$是$B$的最大元$\iff$$b$是$B$对应哈斯图的唯一最上端。
(2)$b$是$B$的最小元$\iff$$b$是$B$对应哈斯图的唯一最下端。
(3)$b$是$B$的极大元$\iff$在$B$对应的哈斯图中，$b$的上面没有其他元素。
(4)$b$是$B$的极小元$\iff$在$B$对应的哈斯图中，$b$的下面没有其他元素。

题型：哈斯图的绘制和最大元、最小元、极大元、极小元的确定

3、全序关系

定义：设$\langle A,\le \rangle$是一个偏序关系，若对$\forall x \in A,\forall y \in A$，总有$x\le y$或$y\le x$之一成立，则称关系“$\le$”为全序关系（Total Order Relation）或者线序关系（Linear Order Relation），简称全序或者线序。称$\langle A,\le \rangle$为全序集（Total Order Set）或者线序集，或者链（Chain）。

判断方法：如果$R$是偏序关系且对$\forall x \in A,\forall y \in A$，总有$x\le y$或$y\le x$之一成立；或者偏序关系的哈斯图是一条单链。那么该关系为全序关系。

4、良序关系

定义：设$\langle A,\le \rangle$是一偏序集，若A的任何一个非空子集都有最小元，则称“$\le$”为良序关系（Well Order Rrelation），简称良序，此时$\langle A,\le \rangle$称为良序集（Well Order Set）。

判断方法：如果$R$是偏序关系且$A$的任意非空子集都有最小元；或者$R$是有限的全序关系。那么该关系为良序关系。

区别：对于全序关系，只需要满足完全性(Totality)，即对任意$a,b\in A$，必有$a\le b$或$b\le a$ 。而良序关系要求任何非空子集（包括无限子集）都有最小元素。例如整数集上的$\le$关系是全序关系，而不是良序关系。而自然数集上的$\le$关系既是全序关系，也是良序关系。有限全序集一定是良序集。

题型：全序关系与良序关系的判断

四、函数

1、函数的基本概念

定义：设$f$是集合$A$到$B$的关系，如果对每个$x\in A$，都存在唯一的$y\in B$，使得$\langle x,y \rangle \in f$，则称关系$f$为$A$到$B$的函数(Function)(或映射(Mapping) )，记为$f: A\to B$。
其中$A$为函数$f$的定义域，记为$domf=A$；$f(A)$为函数f的值域，记为$ranf=f(A)$。当$\langle x,y \rangle \in f$时，通常记为$y=f(x)$，这时称$x$为函数$f$的自变量，$y$为$x$在$f$下的函数值(或象)， 也称$x$为$y$在$f$下的原象。

注意：函数是一种特殊的关系，对于$A$中任意一个$x$，$B$都有唯一确定的$y$与之对应，否则不能称之为函数。例如一个计算机程序，任意的一个输入，一定会有唯一的输出，因此可以把计算机的输入-输出过程看出函数。

通常，将从A到B的一切函数构成的集合记为$B^{A}$： $B^{A}= \{ f\mid f:A\to B \}$。

类型：
(1)如果$\forall x_{1}\forall x_{2}(x_{1}\in A \wedge x_{2}\in A\wedge x_{1}\ne x_{2}\to f(x_{1})\ne f(x_{2}))=1$或者$\forall x_{1}\forall x_{2}(x_{1}\in A \wedge x_{2}\in A\wedge f(x_{1})=f(x_{2})\to x_{1}=x_{2})=1$，则称$f$为从$A$到$B$的单射
或一对一映射。
(2)如果$ranf=B$或者$\forall y(y\in B\to \exists x(x\in A\wedge f(x)=y)=1$，则称$f$为从$A$到$B$的满射或从$A$到$B$上的映射。
(3)如果$f$既是单射，又是满射，则称$f$为从$A$到$B$的双射或一一映射。
(4)如果$A＝B$，则称$f$为$A$上的函数；当$A$上的函数$f$是双射时，称$f$为变换（或置换）。

定理：设$A$，$B$是有限集合，且$| A | = | B |$，$f$是$A$到$B$的函数，则$f$是单射当且仅当$f$是满射。

题型：函数类型的判断、构造和证明

一些特殊函数：
(1)如果$A=B$，且对$\forall x\in A$，都有$f(x)=x$，则称$f$为$A$上的恒等函数，记为$I_{A}$。
(2)如果$\exists b\in B$，且对$\forall x\in A$，都有$f(x)=b$，则称$f$为常值函数。
(3)设$A$是全集$U= \{ u_{1},u_{2},\cdots ,u_{n} \}$的一个子集，则子集$A$的特征函数定义为从$U$到$\{0,1\}$的一个函数$f_{A}(u_{i})$，其中$f_{A}(u_{i})=\begin{cases} 1 & u_{i} \in A \\ 0 & u_{i} \notin A\end{cases}$。
(4)对有理数$x$，$f(x)$为大于等于$x$的最小的整数，则称$f(x)$为上取整函数 (强取整函数)，记为$f(x)= \lceil x \rceil$；
(5)对有理数x，f(x)为小于等于$x$的最大的整数，则称$f(x)$为下取整函数 (弱取整函数)，记为$f(x)= \lfloor x \rfloor$；
(6)如果$f(x)$是集合$A$到集合$B＝ \{ 0,1 \}$上的函数，则称$f(x)$为布尔函数。
(7)设$A= \{ a_{1},a_{2},\cdots,a_{n} \}$是有限集合。从$A$到$A$的双射函数称为$A$上的置换或排列(Permutation)，记为$P:A\to A$，$n$称为置换的阶(Order)。$n$阶置换$P:A\to A$常表示为$P=\begin{pmatrix} a_1 & a_2 & a_3 & \cdots & a_n\\ P(a_1) & P(a_2) & P(a_3) & \cdots & P(a_n)\end{pmatrix}$。

2、函数的运算

复合运算：设$f:A\to B，g:B\to C$是两个函数，如果$f$与$g$的复合关系
$f\circ g= \{ \langle x,z \rangle \mid x\in A \wedge z\in C \wedge \exists y(y\in B \wedge \langle x,y \rangle \in f \wedge \langle y,z \rangle \in g) \}$
是从$A$到$C$的函数，则称$f\circ g$为$f$与$g$的复合函数。

注意：两个函数能够进行复合运算的条件是$ranf \subseteq domg$。复合运算满足结合律。

定理：设$f$和$g$分别是$A$到$B$和从$B$到$C$的函数，则：
(1) 如$f,g$是满射，则$f\circ g$也是从$A$到$C$满射；
(2) 如$f,g$是单射，则$f\circ g$也是从$A$到$C$单射；
(3) 如$f,g$是双射，则$f\circ g$也是从$A$到$C$双射。
(4)如$f\circ g$是$A$到$C$的满射，则$g$是$B$到$C$的满射；
(5)如$f\circ g$是$A$到$C$的单射，则$f$是$A$到$B$的单射；
(6)如$f\circ g$是$A$到$C$的双射，则$f$是$A$到$B$的单射，$g$是$B$到$C$的满射。

题型：$f\circ g$的计算

逆运算：设$f:A\to B$的函数。如果$f^{-1}= \{ \langle y,x \rangle \mid x\in A\wedge y\in B\wedge \langle x,y \rangle \in f \}$是从$B$到$A$的函数，则称$f^{-1}:B\to A$是函数$f$的逆函数(Inverse Function)。

注意：并不是所有的函数都能进行逆运算，只有双射函数才有逆函数。

定理：设$f$是$A$到$B$的双射函数，则：
(1)$f^{-1}\circ f=I_{B}$
(2)$f\circ f^{-1}=I_{A}$
(3)$I_{A}\circ f=f\circ I_{B}=f$

五、习题

1、关系类型的判断与证明

对于相容关系、等价关系、拟序关系、偏序关系的判断，可以通过画出关系矩阵和关系图来分析关系的五大性质，例如

• 自反性：关系矩阵的主对角线均为1或者关系图的每个节点都有自环；
• 反自反性：关系矩阵的主对角线均为0或者关系图的每个节点都没有自环；
• 对称性：关系矩阵对称或者关系图中两个节点之间不能只有一条边；
• 反对称性：关系矩阵对称位置乘积为0或者关系图中两个节点之间最多有一条边；
• 传递性：检查关系图中矢量三角形是否完备。
  对于相容关系、等价关系、拟序关系、偏序关系的证明，结合定义及五大关系的定义进行证明。

2、函数类型的判断与证明

对于单射、满射、双射、变换的判断和证明，首先应把握对应的定义，其次要善于利用其对应的必要条件，在证伪时很有用。

• 单射：变量不同，则函数值一定不同；或者函数值相同，则变量一定相同；或者当有限集$|A|=|B|$时$f$是满射。
• 满射：$B$中的每一个值都有其$A$中的对应值；或者$ranf=B$；或者当有限集$|A|=|B|$时f是单射。
• 双射：同时是单射和满射；或者当有限集$| A | = | B |$时f是单射或满射。
• 变换：双射且$A=B$。