一、笛卡尔积和二元关系

1. 有序对

• 有序对：$n$ 个元素 $a_1, a_2, \cdots, a_n$ 的有序聚集被称为有序 $n$ 元组，记为 $(a_1, a_2, \cdots, a_n)$。当 $n=2$ 时称为有序对。
  • 有序对是相等的，当且仅当对应元素都相等。即 $(a, b) = (c, d) \Leftrightarrow a=b \wedge c=d$。

2. 笛卡尔积

• 笛卡尔积：$A \times B = \{ (a, b) \, | \, (a \in A) \wedge (b \in B) \}$。

  • 笛卡尔积是非交换的，即 $A \times B \ne B \times A$，除非 $A=B \vee A=\empty \vee B=\empty$。

  • 笛卡尔积是非结合的，即一般 $(A \times B) \times C \ne A \times (B \times C)$。

  • 笛卡尔积有分配律。如 $A \times (B \cap C) = (A \times B) \cap (A \times C)$，左右都有分配律；并集和交集都有分配律。

  • $| A \times B | = |A| |B|$。

  • 对于 $n$ 个集合也可定义 $n$ 维笛卡尔积。比如：

    $$ {\mathscr D}(A_1, A_2, \cdots, A_k) = \left\{ (a_1, a_2, \cdots, a_k) \, \left| \, \bigwedge_{i=1}^{k} (a_i \in A_i) \right. \right\} $$

• 无序积：$A \,\&\, B = \{ \{ a, b \} \, | \, (a \in A) \wedge (b \in B) \}$。

3. 二元关系

• 二元关系：$A \times B$ 笛卡尔积的子集被称为 $A$ 到 $B$ 的二元关系（或简称关系）。

  下面一般省略 $x \in A, y \in B, z \in C$。

  • 对于一个二元关系 $F$，$(x, y) \in F \Leftrightarrow xFy$。比如对于小于号而言，$(2, 15) \in [<] \Leftrightarrow 2 < 15$。

  • $A$ 到自身的二元关系，被叫做自关系。

  • 由于 $|{\mathscr P}(A \times B)| = 2^{|A| |B|}$，$A$ 到 $B$ 可建立 $2^{|A| |B|}$ 种不同的二元关系。其中一些特殊的关系有：

    • 空关系 $\empty$。
    • 全域关系 $E_{A \to B} = A\times B$。
    • 恒等关系（只有自关系有）$I_A = \{ (x, x) \, | \, x \in A \}$。

  • 关系的各种域：

    • 前域：$A$。
    • 后域（陪域）：$B$。
    • 关系的定义域：${\rm dom} \, F = \{ x \, | \, \exists y (x F y)\}$
    • 关系的值域：${\rm ran} \, F = \{ y \, | \, \exists x (x F y)\}$
    • 关系的域：${\rm fld} \, F = {\rm dom} \, F \cup {\rm ran} \, F$。

  • $F$ 是弱单根的：$\forall y \in B, \forall x_1, x_2 \in A, x_1Fy \wedge x_2Fy \to x_1 = x_2$。

    • 可以简记为：$\forall y \in B, (\nexists \vee \exists!) x \in A, xFy$。
      • 其中量词 $(\nexists \vee \exists!)$ 表示要么不存在，要么唯一存在。
    • $F$ 是强单根的：$\forall y \in B, \exists! x \in A, xFy$。
      • 也就是弱单值性加上 ${\rm ran} \, F = B$。

  • $F$ 是弱单值的（部分函数的）：$\forall x \in A, \forall y_1, y_2 \in B, xFy_1 \wedge xFy_2 \to y_1 = y_2$。

    • 等价于：$\forall x \in A, (\nexists \vee \exists!) y \in B, xFy$。
    • $F$ 是强单值的（函数的）：$\forall x \in A, \exists! y \in B, xFy$。
      • 也就是弱单值性加上 ${\rm dom} \, F = A$。

• 关系矩阵：$A = \{ a_1, a_2, \cdots, a_n \}, B = \{ b_1, b_2, \cdots, b_m \}, R \subseteq A \times B$，那么可以建立关系矩阵 ${\mathscr M}(R)$ 为一个 ${\mathbb B}^{N \times M}$ 矩阵：

  $$ r_{ij} = {\mathscr M}(R)[i, j] = \begin{cases}

  1, & a_i R b_j \\

  0, & {\rm otherwise}

  \end{cases} $$

  • 矩阵转置对应逆关系：${\mathscr M}(R^{-1}) = {\mathscr M}^{\rm T}(R)$。
  • 矩阵的逻辑乘（加法用或代替，乘法用且代替）对应关系的复合：${\mathscr M}(G \circ F) = {\mathscr M}(F) {\mathscr M}(G)$ 。

• 关系图：用顶点和边表示，即为 ${\mathscr G}(R)$。

4. 关系的运算

• $F$ 的逆关系：设 $F \sube A\times B$，它的逆关系为 $F^{-1} = \{ (y, x) \, | \, xFy \}$。
• $F$ 与 $G$ 的复合关系：设 $F \subseteq A \times B$、$G \subseteq B \times C$，它们的复合为 $G \circ F = \{ (x, z) \, | \, \exists y (xFy \wedge yGz) \}$。
  • 注意其从右向左结合，最右边的最先运算。
  • 复合运算有结合律，即 $H \circ (G \circ F) = (H \circ G) \circ F$。
  • $(G \circ F)^{-1} = F^{-1} \circ G^{-1}$。
  • 自关系 $F$ 的 $n$ 次幂定义为 $n$ 个 $F$ 的复合。
    • 有 $F^m \circ F^n = F^{m+n}, \ (F^m)^n = F^{mn}$。
• $F$ 在集合 $A_0\subseteq A$ 下的限制：$F |A_0 = \{ (x, y) \, | \, xFy \wedge x \in A_0 \}$。
• $F$ 在集合 $A_0\subseteq A$ 下的象：$F(A_0) = {\rm ran} (F | A_0)$。

二、自关系的自反、对称、传递及闭包

1. 自关系的自反、对称、传递性质

i. 自反与反自反性

• 自关系 $F$ 是自反的 (reflexive)：$\forall x \in A, \, x F x$。
  • 充要条件：
    • $I_A \subset F$。
    • ${\mathscr M}(F)$ 主对角线上元素全为 $1$。
    • ${\mathscr G}(F)$ 每个顶点处均有自环。
  • 比如：$\le, \ge$ 是自反的。