本题干的题目逐字取自原书 PDF 第 127–131 页（印刷 p112–p116），解答逐字取自答案书第 4 章「习题解答与分析」（PDF p88–p92，印刷 p76–p80）。题干与答案书原解答均不进入折叠块；只有 AI 补充的额外说明才放进
:details，且标题标注「AI 生成，非原书」。
4.1 设 A = \{1, 2\}，计算 P(A) \times A.
解 P(A) \times A = \{\langle \varnothing, 1 \rangle, \langle \varnothing, 2 \rangle, \langle \{1\}, 1 \rangle, \langle \{1\}, 2 \rangle, \langle \{2\}, 1 \rangle, \langle \{2\}, 2 \rangle, \langle \{1, 2\}, 1 \rangle, \langle \{1, 2\}, 2 \rangle\}.
4.2 A = \{0, 1\}，B = \{1, 2\}，确定 A \times \{1\} \times B.
解 A \times \{1\} \times B = \{\langle 0, 1, 1 \rangle, \langle 0, 1, 2 \rangle, \langle 1, 1, 1 \rangle, \langle 1, 1, 2 \rangle\}.
4.3 （1）证明 A \subseteq B \wedge C \subseteq D \Rightarrow A \times C \subseteq B \times D.
（2）命题（1）的逆命题是否正确，证明你的结论.
解 （1）任取 \langle x, y \rangle，则
（2）不正确. 反例：A = \varnothing，B = D = \{1\}，C = \{2\}.
4.4 A = \{1, 2, 3\}，B = \{4, 5, 6, 8\}，列出关系 R \subseteq A \times B 中的有序对.
（1）xRy 当且仅当 x 整除 y.
（2）xRy 当且仅当 \gcd(x, y) = 1，即 x 与 y 的最大公约数等于 1.
（3）xRy 当且仅当 x 或 y 为素数.
（4）xRy 当且仅当 x \geqslant y.
（5）xRy 当且仅当 x + y < 8.
解 （1）R = \{\langle 1, 4 \rangle, \langle 1, 5 \rangle, \langle 1, 6 \rangle, \langle 1, 8 \rangle, \langle 2, 4 \rangle, \langle 2, 6 \rangle, \langle 2, 8 \rangle, \langle 3, 6 \rangle\}.
（2）R = \{\langle 1, 4 \rangle, \langle 1, 5 \rangle, \langle 1, 6 \rangle, \langle 1, 8 \rangle, \langle 2, 5 \rangle, \langle 3, 4 \rangle, \langle 3, 5 \rangle, \langle 3, 8 \rangle\}.
（3）R = \{\langle 2, 4 \rangle, \langle 2, 5 \rangle, \langle 2, 6 \rangle, \langle 2, 8 \rangle, \langle 3, 4 \rangle, \langle 3, 5 \rangle, \langle 3, 6 \rangle, \langle 3, 8 \rangle, \langle 1, 5 \rangle\}.
（4）R = \varnothing.
（5）R = \{\langle 1, 4 \rangle, \langle 1, 5 \rangle, \langle 1, 6 \rangle, \langle 2, 4 \rangle, \langle 2, 5 \rangle, \langle 3, 4 \rangle\}.
4.5 设 A = \{1, 2, 3\}，A 上的关系 R = \{\langle x, y \rangle \mid x = y + 1 \text{ 或 } x = y - 1\}，R 的补关系 \overline{R} 也是 A 上的关系，其中 \overline{R} = \{\langle x, y \rangle \mid \langle x, y \rangle \notin R\}. 求 \overline{R}.
解 R = \{\langle 3, 2 \rangle, \langle 2, 3 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle\}.
\overline{R} = \{\langle 1, 1 \rangle, \langle 1, 3 \rangle, \langle 3, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle\}.
4.6 列出关系 R = \{\langle a, b, c, d \rangle \mid a, b, c, d \in \mathbf{Z}^+,\ abcd = 6\} 中所有的有序 4 元组.
解 R = \{\langle 1, 1, 1, 6 \rangle, \langle 1, 1, 6, 1 \rangle, \langle 1, 6, 1, 1 \rangle, \langle 6, 1, 1, 1 \rangle, \langle 1, 1, 2, 3 \rangle, \langle 1, 1, 3, 2 \rangle, \langle 1, 2, 3, 1 \rangle, \langle 1, 3, 2, 1 \rangle, \langle 1, 2, 1, 3 \rangle, \langle 1, 3, 1, 2 \rangle, \langle 2, 1, 1, 3 \rangle, \langle 3, 1, 1, 2 \rangle, \langle 3, 1, 2, 1 \rangle, \langle 2, 1, 3, 1 \rangle, \langle 2, 3, 1, 1 \rangle, \langle 3, 2, 1, 1 \rangle\}.
4.7 设 R 是自然数集 \mathbf{N} 上的关系且满足 xRy 当且仅当 x + 2y = 10，其中 + 为普通加法，计算以下各题.
（1）\operatorname{dom} R.
（2）\operatorname{ran} R.
（3）R^{-1}.
解 R = \{\langle 0, 5 \rangle, \langle 2, 4 \rangle, \langle 4, 3 \rangle, \langle 6, 2 \rangle, \langle 8, 1 \rangle, \langle 10, 0 \rangle\}，则
（1）\operatorname{dom} R = \{0, 2, 4, 6, 8, 10\}.
（2）\operatorname{ran} R = \{0, 1, 2, 3, 4, 5\}.
（3）R^{-1} = \{\langle 5, 0 \rangle, \langle 4, 2 \rangle, \langle 3, 4 \rangle, \langle 2, 6 \rangle, \langle 1, 8 \rangle, \langle 0, 10 \rangle\}.
4.8 设 R = \{\langle a, \{a, \{a\}\} \rangle, \langle \{a\}, a \rangle, \langle a, a \rangle\}，求
（1）R \circ R.
（2）\operatorname{dom} R.
解 （1）R \circ R = \{\langle \{a\}, a \rangle, \langle \{a\}, \{a, \{a\}\} \rangle, \langle a, a \rangle, \langle a, \{a, \{a\}\} \rangle\}.
（2）\operatorname{dom} R = \{a, \{a\}\}.
4.9 设 R, S 都是二元关系，证明：\operatorname{dom}(R \cup S) = \operatorname{dom} R \cup \operatorname{dom} S.
证明 任取 x，则
4.10 设 R = \{\langle \varnothing, \{\varnothing\} \rangle, \langle \{\varnothing\}, \{\varnothing, \{\varnothing\}\} \rangle\}，计算以下各小题.
（1）R^{-1}.
（2）R \circ R.
解 （1）R^{-1} = \{\langle \{\varnothing\}, \varnothing \rangle, \langle \{\varnothing, \{\varnothing\}\}, \{\varnothing\} \rangle\}.
（2）R \circ R = \{\langle \varnothing, \{\varnothing, \{\varnothing\}\} \rangle\}.
4.11 设 R = \{\langle \varnothing, \{\varnothing\} \rangle, \langle \{\varnothing\}, a \rangle, \langle b, \varnothing \rangle\}，求
（1）\operatorname{ran} R.
（2）R \circ R.
解 （1）\operatorname{ran} R = \{a, \varnothing, \{\varnothing\}\}.
（2）R \circ R = \{\langle \varnothing, a \rangle, \langle b, \{\varnothing\} \rangle\}.
4.12 A = \{0, \pm 1, \pm 2, \pm 3, \pm 4\}，R_1，R_2 为 A 上的关系，其中
R_1 = \{\langle x, y \rangle \mid x, y \in A,\ y - 1 < x < y + 2\}.
R_2 = \{\langle x, y \rangle \mid x, y \in A,\ x^2 \leqslant y\}.
令 R_i(x) = \{y \mid xR_i y\}，i = 1, 2，求 R_1(0) 与 R_2(3).
解 由于 y \in R_1(0) \Leftrightarrow x - 2 < y < x + 1，x = 0，y \in A \Leftrightarrow -2 < y < 1，y \in A，于是 R_1(0) = \{-1, 0\}.
由于 y \in R_2(3) \Leftrightarrow 3^2 \leqslant y，y \in A，没有 y 满足这个条件，因此 R_2(3) = \varnothing.
4.13 判断下列各关系是否具有自反性、反自反性、对称性、反对称性、传递性.
（1）R 是自然数集 \mathbf{N} 上的关系，且 xRy 当且仅当 x + y 是偶数.
（2）R 是自然数集 \mathbf{N} 上的关系，且 xRy 当且仅当 x > y 或 y > x.
（3）R 是自然数集 \mathbf{N} 上的关系，且 xRy 当且仅当 |x| + |y| \neq 3.
（4）R 是有理数集 \mathbf{Q} 上的关系，且 xRy 当且仅当 y = x + 2.
（5）R 是自然数集 \mathbf{N} 上的关系，且 xRy 当且仅当 xy = 4.
解 （1）R 仅具有自反性、对称性和传递性.
（2）R 仅具有反自反性和对称性.
（3）R 仅具有自反性和对称性.
（4）R 仅具有反自反性和反对称性.
（5）R 仅具有对称性.
说明：（1）x + x 是偶数，于是 R 是自反的；x + y 为偶数，那么 y + x 也是偶数，于是 R 是对称的；\langle 2, 4 \rangle 与 \langle 4, 2 \rangle 同时属于 R，因此不是反对称的；x + y 是偶数，y + z 是偶数，那么 x + z 也是偶数，于是 R 是传递的.
（2）x < x 不成立，于是 R 不是自反的，而是反自反的；若 x > y 或 y > x，必有 y > x 或 x > y，对称性成立；反对称性不成立，因为 \langle 1, 2 \rangle，\langle 2, 1 \rangle 都属于 R，但是 1 \neq 2；R 不是传递的，因为 \langle 1, 2 \rangle 和 \langle 2, 1 \rangle 都属于 R，但是 \langle 1, 1 \rangle 不属于 R.
（3）是自反的，因为 |x| + |x| = 2x 不等于 3；是对称的，不是反对称的，因为 \langle 1, 3 \rangle，\langle 3, 1 \rangle 属于 R，但是 1 \neq 3；不传递，因为 1 + 0 \neq 3，0 + 2 \neq 3，但是 1 + 2 = 3.
（4）x \neq x + 2，于是 R 是反自反的；若 x = y + 2，一定不会有 y = x + 2，因此 R 不是对称的，而是反对称的；y = x + 2，z = y + 2，那么 z = x + 4，所以 R 不是传递的.
（5）不是自反的，因为 \langle 1, 1 \rangle 不属于 R；不是反自反的，因为 \langle 2, 2 \rangle 属于 R；是对称的，但不是反对称的，\langle 1, 4 \rangle 与 \langle 4, 1 \rangle 都属于 R，但是 1 \neq 4；不传递，因为 \langle 1, 4 \rangle，\langle 4, 1 \rangle 都属于 R，但是 \langle 1, 1 \rangle 不属于 R.
4.14 设集合 A = \{a, b, c\}，R 是 A 上的二元关系，已知 R 的关系矩阵为
（1）写出 R 的集合表达式.
（2）画出 R 的关系图.
（3）说明 R 具有哪些性质.
解 （1）R = \{\langle a, a \rangle, \langle b, b \rangle, \langle b, c \rangle, \langle c, b \rangle, \langle c, c \rangle\}.
（2）关系图如图 4.4 所示.
（3）由关系图不难看出 R 是自反、对称、传递的.
4.15 A = \{0, 1, \cdots, 7\}，\forall x, y \in A，xRy \Leftrightarrow 4 < x - y，说明 R 具有什么性质.
解 R 是反自反的、反对称的、传递的.
说明：对任何 x，4 < x - x 都不成立，R 是反自反的；若 4 < x - y，那么 y - x < -4，不会成立 4 < y - x，关系是反对称的；若 4 < x - y，4 < y - z，那么 4 < 8 < x - z，R 是传递的.
4.16 设 X = \{1, 2, 3\}，R 是 X 上的关系，且 \boldsymbol{M}_R = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}，那么 R 的性质是什么？
解 R 是反对称、传递的.
4.17 设 A = \{a, b, c, d, e, f\}，R 是 A 上的二元关系，其关系定义如下：
R = \{\langle a, b \rangle, \langle b, c \rangle, \langle c, a \rangle, \langle e, f \rangle, \langle f, e \rangle\}
使用关系矩阵法求最小的自然数 s, t 使得 s < t，且 R^s = R^t.
解 设 R 的关系矩阵是 \boldsymbol{M}，则：
\boldsymbol{M}^6 对应的关系是
因此得到 s = 0，t = 6.
4.18 X = \{a, b, c, d\}，X 上的关系 R 如图 4.12 所示. 求 r(R)，s(R)，t(R) 的关系图.
解 R 的自反、对称、传递闭包如图 4.5 所示.
4.19 对于表 4.3 中每个打「\times」的命题给出反例.
解 \cup 运算不保持反对称性与传递性，反例 1：
A = \{1, 2\}，R_1 = \{\langle 1, 2 \rangle\}，R_2 = \{\langle 2, 1 \rangle\}.
- 运算不保持自反性与传递性，反例 2：A = \{1, 2\}，R_1 = E_A，R_2 = I_A.
\circ 运算不保持反自反性，同反例 1.
\circ 运算不保持对称性，反例 3：A = \{1, 2\}，R_1 = \{\langle 1, 1 \rangle\}，R_2 = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle\}.
\circ 运算不保持反对称性，反例 4：A = \{1, 2\}，R_1 = \{\langle 2, 1 \rangle, \langle 1, 1 \rangle\}，R_2 = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle\}.
\circ 运算不保持传递性，反例 5：
A = \{1, 2, 3, 4\}
R_1 = \{\langle 1, 3 \rangle, \langle 2, 4 \rangle\}
R_2 = \{\langle 3, 2 \rangle, \langle 4, 1 \rangle\}
4.20 已知 R \subseteq A \times A 且 A = \{a, b, c\}，R 的关系矩阵为
求传递闭包 t(R) 的关系矩阵 \boldsymbol{M}_t.
解 根据矩阵可以知道 R 是传递的，于是 \boldsymbol{M}_t = \boldsymbol{M}_R.
4.21 设 R 是 A 上自反的关系，
（1）证明 R \circ R^{-1} 是 A 上的自反关系.
（2）证明 R \circ R^{-1} 是 A 上的对称关系.
（3）R \circ R^{-1} 是否为 A 上的传递关系？如果是，给出证明；如果不是，给出反例.
证明 （1）任取 x \in A，则
（2）任取 x, y \in A，则
（3）不一定，反例：A = \{1, 2, 3\}，R = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 2, 2 \rangle, \langle 2, 3 \rangle, \langle 3, 3 \rangle\}，则
R \circ R^{-1} = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 2, 2 \rangle, \langle 2, 3 \rangle, \langle 3, 2 \rangle, \langle 3, 3 \rangle\}
上述关系中含有 \langle 1, 2 \rangle，\langle 2, 3 \rangle，但是没有 \langle 1, 3 \rangle，因此不是传递的.
4.22 指出下面命题证明中的错误.
命题：设 R 是集合 A 上的对称、传递的关系，则 R 是自反的.
证：设 x \in A，根据对称性由 \langle x, y \rangle \in R 得到 \langle y, x \rangle \in R，再使用传递性得到 \langle x, x \rangle \in R. 从而证明了 R 的自反性.
解 在 \langle x, y \rangle \in R 成立的条件下可以推出 \langle x, x \rangle \in R，但是这个条件不一定对 A 上所有的 x 都成立，因此，不能证明对所有的 x \in A 都有 \langle x, x \rangle \in R.
4.23 A = \{1, 2, 3, 4, 5\}，R = \{\langle x, y \rangle \mid x, y \in A \wedge x - y \text{ 可被 } 2 \text{ 整除}\}，简答以下各题.
（1）画出 R 的关系图.
（2）R 是否为 A 上的等价关系？如果是，求出 R 的各等价类.
解 （1）关系图如图 4.6 所示.
（2）是等价关系. 等价类是 [1] = [3] = [5] = \{1, 3, 5\}，[2] = [4] = \{2, 4\}.
4.24 设集合 A = \{1, 2, 3\}，下列关系 R 中哪些不是等价关系？为什么？
A = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle\}
B = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle, \langle 3, 2 \rangle, \langle 2, 3 \rangle\}
C = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle, \langle 1, 3 \rangle\}
D = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 1, 3 \rangle, \langle 3, 1 \rangle, \langle 3, 3 \rangle, \langle 2, 3 \rangle, \langle 3, 2 \rangle\}
解 A 是恒等关系，因此是等价关系；B 是自反、对称、传递的关系，也是等价关系；C 不是等价关系，因为 C 没有对称性；D 是等价关系，因为 D 是全域关系.
4.25 设 A = \{a, b, c, d\}，R = I_A \cup \{\langle a, c \rangle, \langle c, a \rangle, \langle b, d \rangle, \langle d, b \rangle\} 为 A 上的等价关系，求出所有的等价类.
解 根据 R 的定义知道 a 与 c 等价，b 与 d 等价，于是 [a] = [c] = \{a, c\}，[b] = [d] = \{b, d\}.
4.26 R 为自然数集 \mathbf{N} 上的关系，\forall x, y \in \mathbf{N}，xRy \Leftrightarrow 2 \mid (x + y)，试确定 R 引起的 \mathbf{N} 的划分.
解 xRy \Leftrightarrow 2 \mid (x + y) \Leftrightarrow x 与 y 具有相同的奇偶性. 令 A = \{2x \mid x \in \mathbf{N}\}，则划分 = \{A, \mathbf{N} - A\}.
4.27 设 A = \{1, 2, 3, 4, 5\}，A 上的划分 \pi = \{\{1, 2\}, \{3, 4\}, \{5\}\}，给出由 \pi 所诱导出的 A 上的等价关系 R 的集合表达式.
解 R = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 3, 4 \rangle, \langle 4, 3 \rangle\} \cup I_A.
4.28 设 A = \{a, b, c, d, e, f\}，R 是 A 上的二元关系，且 R = \{\langle a, b \rangle, \langle a, c \rangle, \langle e, f \rangle\}. 设 R^* = tsr(R)，则 R^* 是 A 上的等价关系.
（1）写出 R^* 的关系表达式.
（2）写出商集 A/R^*.
解 （1）R^* = \{\langle a, b \rangle, \langle a, c \rangle, \langle b, a \rangle, \langle b, c \rangle, \langle c, a \rangle, \langle c, b \rangle, \langle e, f \rangle, \langle f, e \rangle\} \cup I_A.
（2）A/R^* = \{\{a, b, c\}, \{d\}, \{e, f\}\}.
4.29 设 A = \mathbf{Z}^+ \times \mathbf{Z}^+，在 A 上定义二元关系 R 如下：\langle \langle x, y \rangle, \langle u, v \rangle \rangle \in R 当且仅当 xv = yu，证明 R 是一个等价关系.
证明 任取 \langle x, y \rangle，则
任取 \langle x, y \rangle，\langle u, v \rangle \in \mathbf{Z}^+ \times \mathbf{Z}^+，则
任取 \langle x, y \rangle，\langle u, v \rangle，\langle w, t \rangle \in \mathbf{Z}^+ \times \mathbf{Z}^+，则
4.30 如果集合 A 上的关系 R 是自反的和对称的，则称 R 是 A 上的相容关系. 若 \langle x, y \rangle 属于相容关系 R，则称 x 与 y 相容. 设 B 是 A 的子集，如果 B 中任何两个元素都是彼此相容的，则称 B 为 A 关于 R 的相容性分块. 如果某个相容性分块 B 满足下述性质：\forall x \in A - B，x 不能与 B 的所有元素都相容，那么就称 B 是极大相容性分块. 令 A = \{1, 2, 3, 4, 5\}，R = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 2, 3 \rangle, \langle 3, 2 \rangle, \langle 3, 4 \rangle, \langle 4, 3 \rangle, \langle 3, 5 \rangle, \langle 5, 3 \rangle, \langle 4, 5 \rangle, \langle 5, 4 \rangle\} \cup I_A，则 R 为 A 上的相容关系，求出 A 关于 R 的所有的极大相容性分块.
解 极大相容性分块是 \{1, 2\}，\{2, 3\}，\{3, 4, 5\}.
4.31 A = \{a, b, c, d\}，\pi_i(i = 1, 2, 3, 4) 是 A 的划分，
\pi_1 = \{\{a\}, \{b\}, \{c\}, \{d\}\}
\pi_2 = \{\{a, c\}, \{b, d\}\}
\pi_3 = \{\{a, b\}, \{c\}, \{d\}\}
\pi_4 = \{\{a, b, c, d\}\}
设 \Pi = \{\pi_1, \pi_2, \pi_3, \pi_4\}，\preccurlyeq 为划分的加细关系，即 \pi_i \preccurlyeq \pi_j 当且仅当 \pi_i 的每个划分块都包含在 \pi_j 的某个划分块中，求偏序集 \langle \Pi, \preccurlyeq \rangle 的哈斯图.
解 最细的划分是 \pi_1，最粗的划分是 \pi_4. 哈斯图如图 4.7 所示.
4.32 设 A = \{1, 2, 3, 4, 6, 8, 9\}，偏序集 S = \langle A, \preccurlyeq \rangle，其中 \preccurlyeq 为整除关系.
（1）画出 S 的哈斯图.
（2）找出 \{4, 6\} 的最大下界和最小上界.
解 （1）哈斯图如图 4.8 所示.
（2）\{4, 6\} 的最大下界 2，最小上界不存在.
4.33 A = \{1, 2, 3, 4, 6, 8, 12, 24\}，\langle A, \preccurlyeq \rangle 是偏序集，其中 \preccurlyeq 为整除关系. 画出 \langle A, \preccurlyeq \rangle 的哈斯图.
解 哈斯图如图 4.9 所示.
4.34 图 4.13 是偏序集 \langle X, \preccurlyeq \rangle 的哈斯图.
（1）求 X 和 \preccurlyeq 的集合表达式.
（2）求该偏序集的极大元、极小元、最大元、最小元.
解 （1）X = \{a, b, c, d, e, f\}，则
（2）极大元 e, f；极小元 a；最大元不存在，最小元 a.
4.35 设 A = \{1, 2, 3, 4\}，图 4.14 给出了 A 上的两个偏序关系，试画出它们的哈斯图，并指出每个偏序集的极大元、最大元、极小元、最小元.
解 哈斯图如图 4.10 所示.
（a）极大元与最大元为 1，极小元为 2 和 3，没有最小元.
（b）极大元 2 和 3，没有最大元；极小元和最小元为 4.
4.36 设 A = \{1, 2, 3, 4, 5, 6\}，R 为 A 上的整除关系，A_1 = \{2, 3, 6\}，A_2 = \{2, 3, 5\}，求 A_1 与 A_2 的上界、下界、上确界、下确界.
解 A_1 的上界为 6，最小上界也是 6；A_1 的下界为 1，最大下界也是 1. A_2 没有上界与最小上界；A_2 的下界和最大下界为 1.
4.37 A = \{2, 3, \cdots, 9\}，\preccurlyeq 为 A 上偏序，\forall x, y \in A，x \preccurlyeq y \Leftrightarrow (\alpha(x) < \alpha(y)) \vee (\alpha(x) = \alpha(y) \wedge x \leqslant y). \alpha(x) 表示 x 的互异的质因子个数，画出 \langle A, \preccurlyeq \rangle 的哈斯图.
解 2、3、5、7 为素数，每个数只有 1 个质因子. 4、8、9 中的每个数也只有 1 个质因子. 只有 6 有 2 个质因子，于是 6 是最大元. 哈斯图如图 4.11 所示.
4.38 在 A = \{1, 2, 3\} 上可定义多少个偏序关系？其中有多少个是全序关系？
解 考虑偏序关系的哈斯图. 将这些哈斯图按照偏序关系中的边数进行分类：没有边对应的是恒等关系. 含有 1 条边 \langle i, j \rangle，这样的边对应于从 1、2、3 中选 2 个数的一种选法，由于有 6 种选法，因此有 6 个不同的偏序关系. 含 2 条边的全序关系有 6 种，对应于 1、2、3 的 6 个排列，而含 2 条边的非全序的偏序关系或者有 1 个极大元和 2 个极小元；或者有 2 个极大元和 1 个极小元，总共也是 6 种. 综合上述，3 元集合上有 19 个不同的偏序关系，其中 6 个是全序关系.
4.39 （1）设 R 为 A 上的偏序关系，证明 R - I_A 为 A 上的拟序关系.
（2）设 S 为 A 上的拟序关系，证明 S \cup I_A 为 A 上的偏序关系.
证明 （1）假若存在 x \in A，使得 \langle x, x \rangle \in R - I_A，那么必有 \langle x, x \rangle \notin I_A，于是 x \notin A，与 x \in A 矛盾. 这就证明了 R - I_A 是反自反的.
任取 \langle x, y \rangle，\langle y, z \rangle，则
如果 x = z，那么就有 \langle x, y \rangle \in R，\langle y, x \rangle \in R，且 x \neq y，与 R 为反对称关系矛盾. 所以 \langle x, z \rangle \notin I_A. 于是得到 \langle x, z \rangle \in R - I_A. 综合上述，R - I_A 具有反自反性和传递性，是 A 上的拟序关系.
（2）显然 S \cup I_A 为 A 上的自反关系. 任取 \langle x, y \rangle \in S \cup I_A，如果 x \neq y，那么 \langle x, y \rangle \in S，由于 S 的反对称性，一定有 \langle y, x \rangle \notin S，于是得到 \langle y, x \rangle \notin S \cup I_A. 如果 x = y，那么 \langle x, y \rangle \in S \cup I_A 且 \langle y, x \rangle \in S \cup I_A 蕴含 x = y. 于是 S \cup I_A 是反对称的. 最后证明传递性. 任取 \langle x, y \rangle，\langle y, z \rangle，则
综合上述，S \cup I_A 具有自反、反对称和传递性，是 A 上的偏序关系.
4.40 设 \langle A, \preccurlyeq \rangle 是偏序集，且它的最大反链的长度是 n，证明如果将它分解成链，则链的条数至少是 n.
证明 设 A 是偏序集中最大的反链，A 含有 n 个元素. 假若偏序集能够分解成 n - 1 条链，根据鸽巢原理（见主教材定理 4.4 的证明），A 的 n 个元素中必有 2 个元素取自同一条链. 于是，这 2 个元素可比，与 A 为反链矛盾.