一、关系的定义

1. **二元关系的定义：**集合 $A、B$ 上的二元关系（Binary Relation） $R$ 是笛卡尔乘积 $A\times B$ 的一个子集；集合 $A$ 上的二元关系是笛卡尔乘积 $A\times A$ 的一个子集

   示例：

   

   • $R_|$ 的含义：后者除以前者，商为整数

2. **二元关系的数量：**具有 n 个元素的集合上共存在 $2^{n^2}$ 个二元关系

3. **定义域与值域：**设关系 $R$ 是从集合 $A$ 到 $B$ 的二元关系，则：

   • $R$ 的定义域（Domain）

     $Dom(R)=\set{x\in A|(x,y)\in R\ for\ some\ y\in B}$

   • $R$ 的值域（Range）

     $Ran(R)=\set{y\in B|(x,y)\in R\ for\ some\ x\in A}$

4. **n 元关系的定义：**令 $A_1, A_2, …,A_n$ 都是集合，n 元关系为 $A_1\times A_2\times …\times A_n$ 的一个子集，n 称为它的度（Degree）

5. **复合关系的定义：**设 $R$ 是从集合 $A$ 到 $B$ 的关系， $S$ 是从集合 $B$ 到 $C$ 的关系，则 $R$ 和 $S$ 的复合关系（Composite）定义为：

   

6. 关系的幂的定义： $R^1=R,\ R^{n+1}=R^n\circ R$

7. **反关系的定义：**设 $R$ 是从集合 $A$ 到 $B$ 的关系，则 $R$ 的反关系（Inverse） $R^{-1}$ 是从集合 $B$ 到 $A$ 的关系，定义为：

   $R^{-1}=\set{(y,x)|(x,y)\in R}$

   示例：

   

二、关系的性质

1. 自反性 Reflexive

1. **定义：**设 $R$ 是集合 $A$ 上的关系

   • $R$ 是自反的（Reflexive） $\Leftrightarrow \forall x\in A,(x,x)\in R$
   • $R$ 是反自反的（Irreflexive） $\Leftrightarrow \forall x\in A,(x,x)\notin R$

   示例： $R_{≤},R_=,R_|$ 具有自反性

2. 性质

   • $R$ 是自反的 $\Leftrightarrow R_=\subseteq R$
   • 具有 $n$ 个元素的集合共存在 $2^{n(n-1)}$ 个自反的关系

2. 对称性 Symmetric

1. **定义：**设 $R$ 是集合 $A$ 上的关系

   • $R$ 是对称的（Symmetric）

     $\Leftrightarrow \forall x,y\in A,(x,y)\in R\Rightarrow (y,x)\in R$

   • $R$ 是反对称的（Antisymmetric）

     $\Leftrightarrow \forall x,y\in A,(x,y)\in R\ and\ (y,x)\in R \Rightarrow x=y$

2. 性质

   • $R$ 是对称的 $\Leftrightarrow R^{-1}=R$

   • $R$ 是反对称的 $\Leftrightarrow R\cap R^{-1}\subseteq R_=$

   • 不对称不等同于反对称（例如 $R_=$ 既是对称的，又是反对称的）

   • 具有 $n$ 个元素的集合共存在 $2^n\times 2^{\frac{n(n-1)}{2}}=2^{\frac{n(n+1)}2}$ 个对称的关系

   • 具有 $n$ 个元素的集合共存在 $2^n\times 3^{\frac{n(n-1)}2}$ 个反对称的关系

     解释（反对称关系的数量）：

     • $n$ 表示对角线上元素的个数，对角线上的每个元素 $A$ 有 2 种情况：
       • $(A,A)\in R$
       • $(A,A)\notin R$
     • $\frac{n(n-1)}2$ 表示非对角线上元素的对数，非对角线上的每对元素 $(A,B)$ 有 3 种情况：
       • $(A,B)\in R,(B,A)\notin R$
       • $(A,B)\notin R,(B,A)\in R$
       • $(A,B)\notin R,(B,A)\notin R$

3. 传递性 Transitive

1. **定义：**设 $R$ 是集合 $A$ 上的关系，则 $R$ 是传递的（Transitive）

   $\Leftrightarrow \forall x,y,z\in A((x,y)\in R \land (y,z)\in R)\Rightarrow (x,z)\in R$

   示例： $R_{≤},R_<,R_=,R_|,\subseteq$ 具有传递性

2. 定理： $R$ 具有传递性 $\Leftrightarrow R^n\subseteq R\ for\ n=2,3,…$

   证明：

   

   

三、关系的表示