本节对应原书 PDF 第 105–111 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

二元关系作为集合，可以进行并、交、相对补、对称差等运算。除此之外，还可以定义其他一些常用的关系运算。

4.2.1 关系的基本运算

定义 4.10　设 R 为二元关系,R 的定义域、值域和域分别记作 \text{dom}R, \text{ran}R, \text{fld}R,其中

\text{dom}R=\{x\mid \exists y(\langle x,y\rangle\in R)\}
\text{ran}R=\{y\mid \exists x(\langle x,y\rangle\in R)\}
\text{fld}R=\text{dom}R\cup \text{ran}R

由定义不难看出，定义域 \text{dom}R 是 R 中所有有序对的第一元素构成的集合，值域 \text{ran}R 是 R 中所有有序对的第二元素构成的集合，\text{fld}R 是 R 中有序对涉及的全体元素的集合。

例 4.8　设 R=\{\langle a,\{b\}\rangle,\langle c,d\rangle,\langle \{a\},\{d\}\rangle,\langle d,\{d\}\rangle\},则

\text{dom}R=\{a,c,\{a\},d\}
\text{ran}R=\{\{b\},d,\{d\}\}
\text{fld}R=\{a,c,\{a\},d,\{b\},\{d\}\}

定义 4.11　设 R 为二元关系,R 的逆记作 R^{-1},其中

R^{-1}=\{\langle y,x\rangle\mid \langle x,y\rangle\in R\}

不难看出，R^{-1} 就是把 R 的每个有序对的两个元素交换以后得到的关系。如果 R 是整数集 \mathbf{Z} 上的小于关系，那么 R^{-1} 就是 \mathbf{Z} 上的大于关系。类似地，整除关系的逆就是倍数关系。

下面定义两个关系的合成运算.

定义 4.12　设 R,S 为二元关系,R 与 S 的合成记作 R\circ S,则

R\circ S=\{\langle x,z\rangle\mid \exists y(\langle x,y\rangle\in R\wedge \langle y,z\rangle\in S)\}

例 4.9　设 R=\{\langle 1,2\rangle,\langle 1,4\rangle,\langle 2,2\rangle,\langle 2,3\rangle\},S=\{\langle 1,1\rangle,\langle 1,3\rangle,\langle 2,3\rangle,\langle 3,2\rangle,\langle 3,3\rangle\},那么有

R\circ S=\{\langle 1,3\rangle,\langle 2,2\rangle,\langle 2,3\rangle\}
S\circ R=\{\langle 1,2\rangle,\langle 1,4\rangle,\langle 3,2\rangle,\langle 3,3\rangle\}

可以把关系看作是一种作用，如果 \langle x,y\rangle\in R，\langle y,z\rangle\in S，那么 x 通过 R 的作用变到 y，y 接着通过 S 的作用又变到 z。这就是说，在 R 和 S 的合成作用下将 x 变到了 z，因此 \langle x,z\rangle\in R\circ S。这里的 y 起到一个中介的作用，如果对于给定的关系 R 和 S，不存在满足这种条件的中介，那么 R\circ S=\varnothing。

从例 4.9 可以看出，合成运算不满足交换律。

怎样求两个关系的合成? 下面介绍两种方法.

第一种方法就是利用关系的图示来计算关系的合成，特别要说明的是，这里的图示指的不是关系图，因为关系图只用于表示 A 上的关系。此外，这种方法只适用于含有有限个有序对的关系。

给定含有 n 个有序对的关系 R，R 的图示由 n 条有向边构成。将 \text{dom}R 中的元素画在左边，\text{ran}R 的元素画在右边，如果对于 x\in \text{dom}R，y\in \text{ran}R，\langle x,y\rangle\in R，那么从代表 x 的结点到代表 y 的结点画一条有向边。所有的 n 条有向边就构成了 R 的图示。

为求 R 与 S 的合成，先画出 R 的图示，在这个图示的后面接上 S 的图示。如果 \text{ran}R 与 \text{dom}S 含有共同的元素，那么这个元素只能是同一个结点，而不能画成两个结点。在这个图中如果从 \text{dom}R 的结点 x 经过 2 步有向边到达 \text{ran}S 的结点 z，那么 \langle x,z\rangle\in R\circ S。例 4.9 的 R\circ S 与 S\circ R 的图示见图 4.2。

原书图4.2 R∘S 与 S∘R 的图示

第二种方法是利用关系矩阵的乘法.

考虑例 4.9 中的关系 R 和 S，先将 R 和 S 表示成从一个集合到另一个集合上的关系。因为 \text{dom}R=\{1,2\}，\text{ran}R=\{2,3,4\}，\text{dom}S=\{1,2,3\}，\text{ran}S=\{1,2,3\}，其中 \text{ran}R\cup \text{dom}S=\{1,2,3,4\}，那么将 R 看作从 \text{dom}R 到 \text{ran}R\cup \text{dom}S 的关系，而将 S 看作从 \text{ran}R\cup \text{dom}S 到 \text{ran}S 的关系，因此 R\circ S 就是从 \text{dom}R 到 \text{ran}S 的关系。分别写出 R 和 S 的关系矩阵 M_R 和 M_S，然后计算 M_R 和 M_S 的乘积。注意，元素的相加采用逻辑加，即 1+0=0+1=1+1=1，0+0=0。这样得到的结果矩阵就是关系 R\circ S 的关系矩阵。计算过程如下：

M_RM_S=\begin{bmatrix}0&1&0&1\\0&1&1&0\end{bmatrix}\begin{bmatrix}1&0&1\\0&0&1\\0&1&1\\0&0&0\end{bmatrix}=\begin{bmatrix}0&0&1\\0&1&1\end{bmatrix}

从而得到 R\circ S=\{\langle 1,3\rangle,\langle 2,2\rangle,\langle 2,3\rangle\}，与用图示的方法结果相同。

最后还要说明一点，这里定义的关系合成是有复合运算。换句话说，R\circ S 中的 R 是第一步作用，而右边的 S 是复合上去的第二步作用。有的书中采用了左复合的定义，即

R\circ S=\{\langle x,z\rangle\mid \exists y(\langle x,y\rangle\in S\wedge \langle y,z\rangle\in R)\}

左复合中的 S 是第一步作用，而左边的 R 是复合上去的第二步作用。显然两种定义的计算结果是不一样的。从理论上说，这两种定义都是合理的，正像交通规则，有的国家规定右行，有的国家规定左行一样，只要自己的体系一致就行了。

可以证明关系的运算具有下述性质.

定理 4.1　设 F 是任意的关系,则

(1) (F^{-1})^{-1}=F.

(2) \text{dom}F^{-1}=\text{ran}F, \text{ran}F^{-1}=\text{dom}F.

证明　(1) 任取 \langle x,y\rangle,由逆的定义有

\langle x,y\rangle\in(F^{-1})^{-1}\Leftrightarrow \langle y,x\rangle\in F^{-1}\Leftrightarrow \langle x,y\rangle\in F

所以有 (F^{-1})^{-1}=F.

(2) 任取 x,

x\in \text{dom}F^{-1}\Leftrightarrow \exists y(\langle x,y\rangle\in F^{-1})\Leftrightarrow \exists y(\langle y,x\rangle\in F)\Leftrightarrow x\in \text{ran}F

所以有 \text{dom}F^{-1}=\text{ran}F.

同理可证 \text{ran}F^{-1}=\text{dom}F.

定理 4.1 说明关系的逆是相互的，求逆运算以后定义域与值域互换。

下面的两个定理都与合成运算的性质相关.

定理 4.2　设 F, G, H 是任意的关系,则

(1) (F\circ G)\circ H=F\circ(G\circ H).

(2) (F\circ G)^{-1}=G^{-1}\circ F^{-1}.

证明　(1) 任取 \langle x,y\rangle,

\begin{aligned} &\langle x,y\rangle\in(F\circ G)\circ H\\ \Leftrightarrow &\exists t(\langle x,t\rangle\in F\circ G\wedge \langle t,y\rangle\in H)\\ \Leftrightarrow &\exists t(\exists s(\langle x,s\rangle\in F\wedge \langle s,t\rangle\in G)\wedge \langle t,y\rangle\in H)\\ \Leftrightarrow &\exists t\exists s(\langle x,s\rangle\in F\wedge \langle s,t\rangle\in G\wedge \langle t,y\rangle\in H)\\ \Leftrightarrow &\exists s(\langle x,s\rangle\in F\wedge \exists t(\langle s,t\rangle\in G\wedge \langle t,y\rangle\in H))\\ \Leftrightarrow &\exists s(\langle x,s\rangle\in F\wedge \langle s,y\rangle\in G\circ H)\\ \Leftrightarrow &\langle x,y\rangle\in F\circ(G\circ H) \end{aligned}

所以 (F\circ G)\circ H=F\circ(G\circ H).

(2) 任取 \langle x,y\rangle,

\begin{aligned} &\langle x,y\rangle\in(F\circ G)^{-1}\\ \Leftrightarrow &\langle y,x\rangle\in F\circ G\\ \Leftrightarrow &\exists t(\langle y,t\rangle\in F\wedge \langle t,x\rangle\in G)\\ \Leftrightarrow &\exists t(\langle x,t\rangle\in G^{-1}\wedge \langle t,y\rangle\in F^{-1})\\ \Leftrightarrow &\langle x,y\rangle\in G^{-1}\circ F^{-1} \end{aligned}

所以 (F\circ G)^{-1}=G^{-1}\circ F^{-1}.

定理 4.3　设 R 为 A 上的关系,则

R\circ I_A=I_A\circ R=R

证明　任取 \langle x,y\rangle

\begin{aligned} &\langle x,y\rangle\in R\circ I_A\\ \Leftrightarrow &\exists t(\langle x,t\rangle\in R\wedge \langle t,y\rangle\in I_A)\\ \Leftrightarrow &\exists t(\langle x,t\rangle\in R\wedge t=y\wedge y\in A)\\ \Leftrightarrow &\langle x,y\rangle\in R \end{aligned}

从而有 R\circ I_A=R，同理可证 I_A\circ R=R.

定理 4.2 说明合成运算满足结合律，对于多个关系的合成，只要不交换它们的次序，不管谁先参与合成，最后的结果都是一样的。定理 4.3 说明，对于任何 A 上的关系 R，恒等关系对于合成运算是没有贡献的。这里的恒等关系所起的作用，就像普通乘法中的整数 1 一样，不管什么实数 x，x 与 1 相乘总是等于 x。具有这种性质的元素称为运算的单位元。1 是普通乘法的单位元，恒等关系 I_A 是 A 上关系合成运算的单位元。关于单位元的一般性定义将在后面的 14.1.2 节给以介绍。

以上 3 个定理的证明方法都是第 1 章提到的直接证明法。\text{dom}R，\text{ran}R 是集合，R^{-1} 与 R\circ S 是关系。为证明相关的等式，实际上采用的是集合相等的证明方法，即证明相互包含。它们的区别在于，\text{dom}R 与 \text{ran}R 中任取的是元素 x，而 R^{-1} 与 R\circ S 中任取的是有序对 \langle x,y\rangle。

解读：(F\circ G)^{-1}=G^{-1}\circ F^{-1} 里左右顺序要颠倒，这和"先穿袜子再穿鞋，脱的时候先脱鞋再脱袜子"是同一回事。

4.2.2 关系的幂运算

由于关系合成满足结合律，因此可以定义关系的幂运算。这里的关系指的是集合 A 上的关系。

定义 4.13　设 R 为 A 上的关系,n 为自然数,则 R 的 n 次幂定义为:

(1) R^0=\{\langle x,x\rangle\mid x\in A\}=I_A.

(2) R^{n+1}=R^n\circ R.

这个定义是递归的定义。对于 A 上的任何关系 R，R 的最低次幂是 0 次幂，等于 A 上的恒等关系 I_A。由 0 次幂开始，反复使用第(2)条规则，就可以得到 R 的任何正整数次幂。例如，

R^1=R^0\circ R=R
R^2=R^1\circ R=R\circ R
R^3=R^2\circ R=(R\circ R)\circ R=R\circ R\circ R
\vdots

由定义 4.13 可以知道，对于 A 上的任何关系 R_1 和 R_2，它们的 0 次幂都是相等的，即 R_1^0=R_2^0=I_A。R 的 n 次幂就是 n 个 R 的合成。

怎样求出关系 R 的 n 次幂? 这与关系 R 的表示法有关，不同的表示，求法也不同。如果关系是用集合表达式给出的，那么可以采用关系图示的方法。为求 R 的 n 次幂，将 R 的图示复制 n 次，第 i 个图示从第 i 层的 A 中的结点到达第 i+1 层的 A 中的结点。如果从第一层 A 中的结点 x，经过 n 步长的有向路径，可以到达最后一层(n+1 层)A 中的结点 y，那么 \langle x,y\rangle\in R^n。如果 R 是用矩阵 M_R 表示的，那么只需计算 M_R 的 n 次方，这就是 R^n 的关系矩阵。利用关系图求关系幂的方法可能是最方便的。下面给出具体的做法。

设 R 的关系图是 G_R，先在 R^n 的关系图 G' 中画出与 G_R 相同的 n 个顶点，然后顺序考察 G_R 的每个结点 x。如果结点 x 到 y 有一条长为 n 的有向通路，那么就在 G' 中加上一条从 x 到 y 的边。注意，当 x=y 时，得到的是一个过 x 的环。当所有的结点都检查过，G' 中的边都添加完毕，就得到 R^n 的关系图。请看下面的例子。

例 4.10　设 A=\{a,b,c,d\}, R=\{\langle a,b\rangle,\langle b,a\rangle,\langle b,c\rangle,\langle c,d\rangle\},求 R 的各次幂,分别用矩阵和关系图表示.

解　R 的关系矩阵为

M=\begin{bmatrix}0&1&0&0\\1&0&1&0\\0&0&0&1\\0&0&0&0\end{bmatrix}

则 R^2 的关系矩阵是

M^2=\begin{bmatrix}0&1&0&0\\1&0&1&0\\0&0&0&1\\0&0&0&0\end{bmatrix}\begin{bmatrix}0&1&0&0\\1&0&1&0\\0&0&0&1\\0&0&0&0\end{bmatrix}=\begin{bmatrix}1&0&1&0\\0&1&0&1\\0&0&0&0\\0&0&0&0\end{bmatrix}

同理 R^3 和 R^4 的矩阵是

M^3=\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&0&0&0\\0&0&0&0\end{bmatrix},\quad M^4=\begin{bmatrix}1&0&1&0\\0&1&0&1\\0&0&0&0\\0&0&0&0\end{bmatrix}

因此 M^4=M^2，即 R^4=R^2。于是可以得到

R^2=R^4=R^6=\cdots,\quad R^3=R^5=R^7=\cdots

而 R^0，即 I_A 的关系矩阵是

M^0=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}

用关系图的方法得到 R^0, R^1, R^2, R^3,\cdots 的关系图如图 4.3 所示.

原书图4.3 R^0 到 R^3 的关系图

可以证明以下关于幂运算的性质.

定理 4.4　设 A 为 n 元集, R 是 A 上的关系,则存在自然数 s 和 t,使得 R^s=R^t.

证明　R 为 A 上的关系，由于 |A|=n，A 上的不同关系只有 2^{n^2} 个。列出 R 的各次幂

R^0,R^1,R^2,\cdots,R^{2^{n^2}},\cdots

当所列出的幂的个数超过 A 上关系的总数 2^{n^2} 时，这些幂中必有两个幂相等，即存在自然数 s 和 t 使得 R^s=R^t.

在定理 4.4 的证明中实际上用到了鸽巢原理。鸽巢原理的简单形式表述如下：把 n+1 只鸽子放入 n 个巢中，那么存在一个巢，使得其中至少有 2 只或者 2 只以上的鸽子。鸽巢原理是组合学的重要原理，在许多涉及组合存在性问题的证明中有着重要的应用。

定理 4.4 说明有穷集合上的关系 R 只有有限多个不同的幂.

定理 4.5　设 R 是 A 上的关系, m,n\in\mathbf{N},则

(1) R^m\circ R^n=R^{m+n}.

(2) (R^m)^n=R^{mn}.

证明　用归纳法.

(1) 对于任意给定的 m\in\mathbf{N},施归纳于 n.

若 n=0,则有

R^m\circ R^0=R^m\circ I_A=R^m=R^{m+0}

假设 R^m\circ R^n=R^{m+n},则有

R^m\circ R^{n+1}=R^m\circ(R^n\circ R)=(R^m\circ R^n)\circ R=R^{m+n+1}

所以对一切 m,n\in\mathbf{N} 有 R^m\circ R^n=R^{m+n}.

(2) 对于任意给定的 m\in\mathbf{N},施归纳于 n.

若 n=0,则有

(R^m)^0=I_A=R^0=R^{m\times 0}

假设 (R^m)^n=R^{mn},则有

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

所以对一切 m,n\in\mathbf{N} 有 (R^m)^n=R^{mn}.

以上定理采用的证明方法是第 1 章提到的数学归纳法。归纳基础是对 n=0 验证命题为真。归纳步骤是由命题对 n 为真推出对 n+1 也为真。当命题中存在多个自然数时，一般是选择其中的一个自然数进行归纳。这就是说，对其他的自然数要任意给定，然后对选中的那个自然数进行归纳。比如任意给定 m，然后对 n 进行归纳。

定理 4.6　设 R 是 A 上的关系,若存在自然数 s,t(s<t) 使得 R^s=R^t,则

(1) 对任何 k\in\mathbf{N} 有 R^{s+k}=R^{t+k}.

(2) 对任何 k,i\in\mathbf{N} 有 R^{s+kp+i}=R^{s+i},其中 p=t-s.

(3) 令 S=\{R^0,R^1,\cdots,R^{t-1}\},则对于任意的 q\in\mathbf{N} 有 R^q\in S.

证明　(1) R^{s+k}=R^s\circ R^k=R^t\circ R^k=R^{t+k}.

(2) 对 k 归纳.

若 k=0,则有　R^{s+0p+i}=R^{s+i}

假设 R^{s+kp+i}=R^{s+i},其中 p=t-s,则

R^{s+(k+1)p+i}=R^{s+kp+i+p}=R^{s+kp+i}\circ R^p=R^{s+i}\circ R^p=R^{s+p+i}=R^{s+t-s+i}=R^{t+i}=R^{s+i}

由归纳法命题得证.

(3) 任取 q\in\mathbf{N},若 q<t,显然有 R^q\in S. 若 q\geqslant t,则根据除法定义存在自然数 k 和 i,使得 q=s+kp+i,其中 0\leqslant i\leqslant p-1. 于是

R^q=R^{s+kp+i}=R^{s+i}

而

s+i\leqslant s+p-1=s+t-s-1=t-1

这就证明了 R^q\in S.

定理 4.6 给出了 R 的不同幂的个数的一个上界。就是说，如果 R^s=R^t，那么 R 的不同的幂至多有 t 个。如果 s 和 t 是使得 R^s=R^t 成立的最小的自然数，那么 R 恰好有 t 个不同的幂。这里的 t-s 可以看作是幂变化的周期。利用幂的周期性，在某些情况下可以将 R 的比较高的幂化简成比较低的幂。回顾例 4.10，由于 R^2=R^4，因此 R 的不同的幂至多是 4 个，即 R^0,R^1,R^2,R^3。利用这个性质，有 R^{100}=R^2。

解读：R^0=I_A 与"R 的 0 次方是 1"的类比一致——I_A 是合成运算的单位元；由于有穷集上关系只有 2^{n^2} 个，幂序列必然出现重复，重复一旦出现，后面就周期性循环。