关系的乘积（合成）.md

设$R,S$是集合$A$上的两个关系，令

$$ R\circ S=\{(x,y)|x\in A,y\in A并且存在一个z\in A使得xRz,zSy\} $$

称关系$R\circ S$为关系$R$和$S$的乘积或合成

可以证明关系的乘法满足结合律

设$R,S$和$T$是集合$A$上的$3$个关系，任取$x,y\in A$，若$x(R\circ S)\circ Ty$，则由关系乘积的定义知，存在$z\in A$使得$xR\circ Sz, zTy$，同样对$xR\circ Sz$必存在$z'\in A$使得$xRz'$，$z'Sz$，故由$z'Sz$和$zTy$知$z'S\circ Ty$，再由$xRz'$得$xR\circ(S\circ T)y$，即证得了关系的乘法满足结合律

同样可以证明关系的乘法不满足交换律

关系的幂

由于关系的乘法运算满足结合律，因此可以用“幂”表示集合上同一个关系的乘积，即

$$ R^n=R\circ R\circ\cdots\circ R $$

规定$R^0=I_A$

---

定理：设$m,n$为任意的自然数，那么

• $R^m\circ R^n=R^{m+n}$
• $(R^m)^n=R^{mn}$

---

定理：设集合$A$的元数为$n$，$R$是$A$上的二元关系，那么存在自然数$i,j(0\le i\lt j \le 2^{n^2})$使得$R^i=R^j$

证明：鸽巢原理即可

---

定理：设$R$是集合$A$上的关系，若存在自然数$i,j(i\lt j)$，使得$R^i=R^j$，则有

• $R^{i+k}=R^{j+k},k\in N$
• $R^{i+kp+m}=R^{i+m},其中k,m\in N,p=j-i$

---

定理：集合$A$上的关系$R$具有传递性的充要条件是$R\circ R\subseteq R$ 证明：

• 必要性：若$R$具有传递性，任取$(x,y)\in R^2$，于是存在$z\in A$，使得$xRz,zRy$，因为$R$是传递的，所以有$xRy$，即$(x,y)\in R$，故$R^2\subseteq R$
• 充分性：若$R^2\subseteq R$，如果$xRy,yRz$，则$xR^2z$，故$xRz$，所以$R$是传递性的