离散数学：第三次作业

记 $R^+=\bigcup_{k\geqslant1}R^k$ 为传递闭包，$R^*=I_A\cup R^+$ 为自反传递闭包，其中 $I_A=\{(a,a):a\in A\}$。

若 $(a,b)\in R^+$ 且 $(b,c)\in R^+$，则存在 $m,n\geqslant1$ 使 $(a,b)\in R^m$、$(b,c)\in R^n$，于是 $(a,c)\in R^{m+n}\subseteq R^+$。所以 $R^+$ 已经传递，再取传递闭包不增加元素：

同理，$R^*$ 已经自反且传递，再取自反传递闭包也不变：

注意，一般只有 $R^+\circ R^+\subseteq R^+$，不能要求等号。例如 $R=\{(1,2)\}$ 时 $R^+=R$，但 $R^+\circ R^+=\varnothing$。

由 $(1,2),(2,4) \in R,(1,4) \notin R\Rightarrow R$ 不是传递关系 .

自反: $\forall (a,b) \in A\times A,a+b=b+a\Rightarrow ((a,b),(a,b)) \in R$. 对称: $\forall ((a,b),(c,d))\in R,a+d=b+c \Rightarrow c+b=d+a\Rightarrow ((c,d),(a,b)) \in R$. 传递: $\forall ((a,b),(c,d)),((c,d),(e,f))\in R,a+d=b+c,c+f=d+e\Rightarrow a-b=c-d=e-f\Rightarrow a+f=e+b\Rightarrow((a,b),(e,f))\in R$.

自反: $\forall a \in A, (a,a)\in R_1\wedge(a,a) \in R_2\Rightarrow (a,a)\in R_1 \cap R_2$.

对称: $\forall (a,b) \in R_1 \cap R_2,(a,b) \in R_1\wedge (a,b)\in R_2\Rightarrow (b,a) \in R_1\wedge (b,a)\in R_2\\ \Rightarrow (b,a) \in R_1 \cap R_2$.

传递: $\forall (a,b),(b,c) \in R_1\cap R_2,(a,b),(b,c) \in R_1\Rightarrow (a,c) \in R_1$, 同理 $(a,c) \in R_2$, 故 $(a,c) \in R_1\cap R_2$.

设 $\preceq_1$、$\preceq_2$ 分别是 $A$、$B$ 上的偏序，按分量定义 $A\times B$ 上的关系：

自反性。 任取 $(a,b)\in A\times B$。由 $a\preceq_1 a$、$b\preceq_2 b$，得 $(a,b)\preceq_3(a,b)$。

反对称性。 任取 $(a_1,b_1),(a_2,b_2)\in A\times B$，若二者在 $\preceq_3$ 下互相关联，则 $a_1\preceq_1a_2$ 且 $a_2\preceq_1a_1$，$b_1\preceq_2b_2$ 且 $b_2\preceq_2b_1$。由两个分量关系的反对称性，$a_1=a_2$、$b_1=b_2$，故两个有序对相等。

传递性。 任取 $(a_i,b_i)\in A\times B\ (i=1,2,3)$，若 $(a_1,b_1)\preceq_3(a_2,b_2)$ 且 $(a_2,b_2)\preceq_3(a_3,b_3)$，则 $a_1\preceq_1a_2\preceq_1a_3$、$b_1\preceq_2b_2\preceq_2b_3$。 由分量关系的传递性得到 $a_1\preceq_1a_3$、$b_1\preceq_2b_3$，所以 $(a_1,b_1)\preceq_3(a_3,b_3)$。

综上，$\preceq_3$ 是 $A\times B$ 上的偏序（半序）关系。