二元关系

Posted on

关系理论

集合定义

序偶(ordered pair)：两个元素$x,y$按照一定的次序组成的二元组$<x,y>$；

  • $<a,b>=<c,d>\iff a=c,b=d$

$n$重有序组：$n$个元素$a_1,a_2,…,a_n$按照一定的次序组成的$n$元组

笛卡尔积(Cartesian product):对于集合$A,B$，笛卡尔积为如下集合
$$
A\times B={<x,y>|x\in A\wedge y\in B}
$$

  • 不满足交换律：$A\times B \neq B\times A$，但是$\mid A\times B\mid = \mid B\times A\mid = |A|\times|B|$
  • $A\times(B\cup C)=(A\times B)\cup(A\times C)$;
  • $A\times(B\cap C)=(A\times B)\cap(A\times C)$;
  • $A\times B\subseteq C\times D\iff A\sube C,B\sube D$

关系(relation):对于非空集合$A,B$, 称$R$是从$A$到$B$的二元关系$R:A\to B$，如果$R$是$A\times B$的一个子集；

  • 空关系：$R=\varnothing$;
  • 恒等关系：$R=I_A={<x,x>|x\in A}$
  • 全关系：$R=A\times B$
  • $x$对$y$有关系$R$：$<x,y>\in R\iff xRy$
  • 所有可能的关系有$2^{|A||B|}$个

$n$元关系：$A_1\times…\times A_n$的任意子集；

对于$A,B$间的二元关系$R\subseteq C\times D\sube A\times B$;

若$C \sube A,D\sube B$且
$$
C={x\mid x\in A,\exist y\in B,<x,y>\in R}\
D={y\mid y\in B, \exist x\in A, <x,y> \in R}
$$
定义如下概念：

  • 前域$A$
  • 后域$B$
  • 定义域${\rm dom} R=C$
  • 值域${\rm ran} R=D$
  • 域${\rm fid}R =C\cup D$

关系图和关系矩阵

关系可以用关系图表示

  • 若关系定义在不同的集合：用带箭头的二部图表示，由前域指向后域；
  • 若关系定义在某一个集合：用可能有向图表示，可能有自环和重边；；

称$\mathbf M_R =(m_{ij}){m\times n}$为关系$R$的关系矩阵(邻接矩阵)，如果
$$
m{ij}=\begin{cases}1&<a_i,b_j>\in R\0&<a_i,b_j>\notin R \end{cases}
$$
显然这是一个Bool矩阵，对于$\mathbf A,\mathbf B$是$m\times n$的Bool矩阵：

  • 并
    $$
    \mathbf C=\mathbf A\vee \mathbf B=(c_{ij}),c_{ij}=\begin{cases}1&a_{ij}=1\vee b_{ij}=1\0& a_{ij}=0\wedge b_{ij}=0 \end{cases}
    $$

  • 交
    $$
    \mathbf C=\mathbf A\wedge \mathbf B=(c_{ij}),c_{ij}=\begin{cases}1&a_{ij}=1\wedge b_{ij}=1\0& a_{ij}=0\vee b_{ij}=0 \end{cases}
    $$

  • 布尔积
    $$
    \mathbf C=\mathbf A\odot \mathbf B=(c_{ij}),c_{ij}=\begin{cases}1&\exist k,a_{ik}=b_{kj}=1\0&\rm otherwise \end{cases}
    $$

关系表

在关系代数理论中，关系可以用二维表表示；

对于关系$R\sube A_1\times A_2\times \cdots\times A_n$,第$i$个属性代表$A_i$,每一个行/表项为$R$中的元素；

复合运算

对于非空集合$A,B,C$，$R：A\to B,S:B\to C$,称一个从$A$到$C$的关系是复合关系，如果
$$
R \circ S = {<x,z>|x\in A \wedge z\in C\wedge (\exist y)(y\in B\wedge xRy\wedge yRz)}
$$

  • $\varnothing \circ R=R\circ \varnothing=\varnothing$
  • $(R\circ S)\circ T=R\circ(S\circ T)$
  • $I_A \circ R=R\circ I_B$
  • $R\circ (S_1\cup S_2)=(R\circ S_1)\cup (R\circ S_2)$
  • $R\circ (S_1\cap S_2)\sube(R\circ S_1)\cap (R\circ S_2)$
  • $(S_1\cup S_2)\circ R=(S_1\circ R)\cup( S_2\circ R)$
  • $(S_1\cap S_2)\circ R\sube(S_1\circ R)\cap( S_2\circ R)$

逆运算

对于非空集合$A,B$，$R:A\to B$,$R$的逆关系是指
$$
R^{-1}:B\to A={<b,a>|<a,b>\in R}
$$

  • $(R\circ S)^{-1}=S^{-1}\circ R^{-1}$
  • $(R\cup S)^{-1}=R^{-1}\cup S^{-1}$
  • $(R\cap S)^{-1}=R^{-1}\cap S^{-1}$
  • $(R- S)^{-1}=R^{-1}- S^{-1}$
  • $\overline R^{-1}=\overline {R^{-1}}$
  • $S\sube R\iff S^{-1}\sube R^{-1}$

逆关系的关系矩阵等于原关系的关系矩阵转置；

幂运算

对非空集合$A$,定义关系$R\sube A\times A$的$n$次幂如下：

  • $R_0=I_A$；
  • $R^1=R$;
  • $R^{n+1}=R^n\circ R=R\circ R^n$

注意到，幂集$R^n$随着$n$增加呈现递减趋势，得出如下定理：
$$
\bigcup_{i=1}^n R^i=\bigcup_{i=1}^{|A|}R^i
$$
proof:只需证明$R^k\sube \bigcup_{i=1}^{|A|}R^i$,注意到定义缩减没必要的复合运算即可；

性质

对于定义在一个集合上的关系，我们考察其自反性，反自反性，对称性，反对称性和传递性；

如果对$\forall x\in A$，都有$<x,x>\in R$,那么称$R$在 $A$上是自反的，关系图上表现为每个结点有自环，关系矩阵上表现为主对角线上全部为1；

  • $R$是自反的$\iff I_A\sube R$

如果对$\forall x\in A$，都有$<x,x>\notin R$，那么称称$R$在 $A$上是反自反的；关系图上表现为每个结点都没有自环，关系矩阵上表现为主对角线上全部为0；

  • $R$是反自反的$\iff R\cap I_A=\varnothing$

如果对$\forall x,y\in A$，都有$<x,y>\in R \iff<y,x>\in R$,那么称$R$在 $A$上是对称的;关系图上表现为任意两个结点要么没有边，要么有两条反向边，关系矩阵上表现为对称矩阵；

  • $R$是对称的$\iff R=R^{-1}$

如果对$\forall x,y\in A$，都有$<x,y>\in R\wedge<y,x>\in R \iff x=y$,那么称$R$在 $A$上是反对称的;关系图上表现为任意两个结点至多一条边，关系矩阵上表现为矩阵自交为0；

  • $R$是反对称的$\iff R\cap R^{-1}\sube I_A$

设$R$是非空集合$R$上的关系．对$\forall x,y,z\in A$，如果$＜x,y＞\in R,＜y,z＞\in R$，那么$＜x,z＞∈R$，则称关系$R$是传递的;关系图上表现为每个结点有自环，关系矩阵上表现为$r_{ij}=r_{jk}=1$必有$r_{ik}=1$；

  • $R$是传递的$\iff R\circ R\sube R$

对于定义在集合$A$上的二元关系$R,S$,考察其保守性：逆运算和交运算保守性好，并，差和复合运算的保守性差；

  • 若$R,S$具有自反性，则$R^{-1},R\cup S,R\cap S,R\circ S$具有自反性；
  • 若$R,S$具有反自反性，则$R^{-1},R\cup S,R\cap S,R- S$具有自反性；
  • 若$R,S$具有对称性，则$R^{-1},R\cup S,R\cap S,R- S$具有自反性；
  • 若$R,S$具有反对称性，则$R^{-1},R\cap S,R- S$具有自反性；
  • 若$R,S$具有传递性，则$R^{-1},,R\cap S$具有传递性；

关系闭包

在给定关系添加尽可能少的元素，使关系满足特殊性质，这个过程称为关系闭包；

形式化说，对于定义在非空集合$A$上的关系$R$，若存在定义在$A$上的另一个关系$R’$,使得$R\sube R’$,且满足

  • $R’$是自反的/对称的/传递的
  • 对于任何自反的/对称的/传递的关系$S$,若$R\sube S$,必有$R’\sube S$;

称$R’$为$R$的自反闭包(reflexive closure)/对称闭包(symmetric closure)/传递闭包(transitive closure),记作$r(R)/s(R)/t(R)$;

闭包运算算法：
$$
r(R)=R\cup I_A\
s(R)=R\cup R^{-1}\
t(R)=\bigcup_{i=1}^{|A|} R^i
$$

等价关系

称定义在非空集合$A$上的关系$R$为等价关系，若$R$具有自反性，对称性和传递性；

给定非空集合$A$,称集合$S={S_1,S_2,\cdots,S_n}$构成集合$A$的一个划分(partition),$S_i(1\le i\le n)$称作划分的类(class),若

  • $S_i\sube A,S_i\neq \varnothing,1\le i\le n;$
  • $S_i\cap S_j = \varnothing, i\neq j, 1\le i,j\le n;$
  • $\bigcup_{i=1}^n S_i=A;$

利用等价关系可以将集合划分成互不相交的子集,也即等价类；

对于定义在集合$A$上的等价关系$R$,对$\forall x\in A$,称集合
$$
[x]_R={y\mid y \in A \ \wedge <x,y>\in R}
$$
是$x$生成的关于$R$的等价类(equivalence)，$x$为该类的代表元(generator);

简单来说，在等价关系中，所有与$x$有关系的元素处于同一个等价类中，不难观察以下结论成立

  • 对$\forall x\in A,[x]_R\neq \varnothing;$
  • 对$\forall x,y\in A$, 若$y\in [x]_R$，则$[x]_R=[y]_R$;若$y\notin [x]_R$,则$[x]_R\cap [y]_R=\varnothing$;
  • $\bigcup_{x\in A}[x]_R = A$;

进一步定义集合$A$关于等价关系$R$的商集$A/R$
$$
A/R = {[x]_R\mid x\in A}
$$
商集算法如下：

  1. 若$A$非空，选取$a\in A$,计算$[a]_R$并加入到$A/R$中；
  2. 若$[a]_R\neq A$，更新$A\leftarrow A-[a]_R$,回到1；

显然商集是对$A$的等价划分，由划分也可以生成一种等价关系，如下：

定集合$A$的一个划分$π={S_1，S_2,\cdots, S_n}$，则由该划分确定的关系
$$
R=\bigcup_{i=1}^n (S_i\times S_i)
$$
是$A$上的等价关系,称该关系$ R$为由划分$π$所导出的等价关系;

序关系

称定义在集合$A$上的关系$R$为拟序关系，如果$R$是反自反的，反对称的和传递的，记作小于$<$;

序偶$<A,< >$称为拟序集，改记$<a,b>\in <$为$a< b$,其逆关系大于为$> $也是拟序关系；

称定义在集合$A$上的关系$R$为偏序关系，如果$R$是自反的，反对称的和传递的，记作小于等于$\le$;

序偶$<A,\le>$称为偏序集，改记$<a,b>\in \le$为$a\le b$,其逆关系大于等于为$\ge $也是偏序关系；

规定偏序关系对应的哈斯图(Hasse diagram)如下：

  • 用小圆圈或点表示$ A$中的元素，省掉关系图中所有的自环;
  • 对于$\forall x，y∈A$，若$x≤y$且$x≠y$，则将$x$画在$y$的下方，可省掉关系图中所有边的箭头;
  • 对于$\forall x，y∈A$，若$x≤y$且$x≠y$，且$x$与$y$之间不存在$z\in A$，使得$x≤z，z≤y$，则$x$与$y$之 间用一条线相连，否则无线相连;

image-20241210220139067

$<A,\le>$是偏序集，$B$是$ A$的任何一个子集，若存在元素$b∈B$，使得

  • 对$\forall x\in B$，都有$x≤b$，则称$b$为$B$的最大元;
  • 对$\forall x\in B$，都有$x≥b$，则称$b$为$B$的最小元;
  • 对$\forall x\in B$，满足 $x≥b\Rightarrow x=b$，则称$b$为$B$的极大元;
  • 对$\forall x\in B$，满足$x≤b\Rightarrow x=b$，则称$b$为$B$的极小元.

若存在元素$a\in A$，使得

  • 对$\forall x\in B$，都有$x≤a$，则称$a$为$B$的上界（upper bound）;
  • 对$\forall x\in B$，都有$x≥a$，则称$a$为$B$的下界（lower bound）;
  • 设元素$a’\in A$是$B$的一个上界，对$B$的任何一个上界$a\in A$，若均有$a≥a’$，则称$a’$为$B$的上确界.记为 $a’=\sup B$;
  • 设元素$a’\in A$是$B$的一个下界，对$B$的任何一个下界$a\in A$，若均有$a\ge a’$，则称$a’$为$B$的下确界.记为 $a’=\inf B$;

进一步有以下结论：

$<A,\le>$是偏序集，$B$是$ A$的任何一个子集

  • 若最大元$b$存在，则同时是极大元，上界，上确界；若$A$中的一个上界$a\in B$，则$a$是$B$的最大元；
  • 若最小元$b$存在，则同时是极小元，下界，下确界；若$A$中的一个下界$a\in B$，则$a$是$B$的最小元；

对于有限子集$B$,最大元/最小元若存在，则一定唯一，且是唯一极大元/极小元；若上确界/下确界存在，则上确界/下确界唯一；

对偏序关系$<A,\le>$来说，若$\forall x,y\in A$，总有$x\le y$或$y\le x$其一成立，则$\le $为全序关系/线序(linear order)；

$<A,\le>$为全序集，其哈斯图表现为一条线；

对偏序关系$<A,\le>$来说，若$A$中任意非空子集均有最小元，则$\le$为良序关系(well order)；

$<A,\le>$为良序集，良序关系一定是偏序关系，反之则不然，良序关系一定是全序关系，反之则不然；

函数

称关系$f$为集合$A$到集合$B$的函数/映射(function/mapping)，记作$f:A\to B$,若对于每个$x\in A$,存在唯一的$y\in B$, 使得$<x,y>\in f$;

  • 定义域${\rm dom}f=A$;
  • 值域${\rm ran}f = B$;
  • $<x,y>\in f$改记为$y=f(x)$,自变量为$x$，函数值为$y$;

即任意可能的输入集合$A$对应输出集合$B$；

称$f$是从$A$到$B$的单射(injection),若对于$\forall x_1,x_2\in A$,均有$f(x_1)\neq f(x_2)$;

称$f$是从$A$到$B$的满射(surjection)，若${\rm ran}f=B$,即对$\forall y\in B$,$\exist x\in A,s.t.y = f(x)$；

称$f$是从$A$到$B$的双射(bijection)，若$f$既是单射又是满射；

当双射$f$定义在$A\to A$上时，称$f$是集合$A$上的变换(transform)；

若函数$f:A\to A\ s.t. \forall x\in A,f(x)=x$,称$f$是$A$上的恒等函数$\boldsymbol I_A$;

若函数$f:A\to B\ s.t.\exist b\in B,\forall x\in A,f(x)=b$,称$f$是$A$上的常值函数；

若定义$A$为全集$U={u_1,u_2,\cdots, u_n}$的一个子集，则子集$A$的特征函数定义为
$$
f_A(u_i)=\begin{cases}
1&,u_i\in A;\
0&,u_i\notin A.
\end{cases}
$$
若变换$\sigma:A\to A$定义在有限集合上，则称$\sigma$为$A$上的置换/排列(permutation),$n$称作置换的阶(order),通常如下表示：
$$
\sigma=\left(\begin{array}{c}
a_1&a_2&\cdots&a_n\
\sigma(a_1)&\sigma(a_2)&\cdots&\sigma(a_n)
\end{array}\right)
$$
不同置换个数为$n!$个；