slide 9: Classifying relations 关系分类
一些记号
对于 元关系 的成员的表述是：。
有时，前缀记号（prefix notation）更方便。比如，如果想要说 与关系 有关，可以写作 。
对于二元关系，中缀记号更简单，比如：。常见的数字的比较关系运算符（大于、小于、等），就是中缀记号。
邻接矩阵
邻接矩阵（adjacency matrix）可以用来表示一个有限的二元关系。这里邻接矩阵当中的每个元素都是 bool 类型。当且仅当 ，。
使用邻接矩阵表示关系，则关系的运算操作可以对应到矩阵：
| 关系操作 | 对应矩阵操作 |
|---|---|
| 关系应用 application | 矩阵乘法 |
| 关系组合 composition | 矩阵乘法 |
| 逆关系 inverse | 矩阵转置 |
| 关系求并 union | 矩阵按元与（加法） |
| 关系求交 intersection | 矩阵按元或（乘法） |
注意邻接矩阵的运算当中，都是布尔运算，。
比如：
- 求 EZ 的 parent，就是「isParent」矩阵乘以「EZ」矩阵
- 求 EZ 或 H 的 parent，就是「isParent」矩阵乘以「EZ 或 H」矩阵
- 求 H 的 children，就是「isParent」的转置矩阵乘以「H」矩阵
- 「isGrandParent」矩阵，相当于「isParent」乘以「isParent」（关系组合）
自反关系 reflexive relation
若 是一个集合，则关系 称为 的*单位关系（identity relation on ）。
对于二元关系 ，若满足 ，则 叫做自反关系。也就是说，自反关系的每个元素都能对应到自己本身。
若一个二元关系 ，满足 ，则此时 称作反自反关系（irreflexive relation）。也就是说，反自反关系，自己本身永远无法对应到自己。
对称关系 symmetric relation
若二元关系 满足 ，则 是对称关系。这意味着，若 当中包含了 ，就一定同时包含着 。
反对称关系（antisymmetric relation）是指，仅在 的时候，关系中才会同时含有 和 。因此，反对称关系可能是自反的，但是自反关系不是反对称。
如果一个关系，既是反对称关系又是反自反关系，则它叫做非对称关系（asymmetric）。
非对称关系（Asymmetric）与反对称关系（Antisymmetric）的差异在于：反对称关系容许自反性 ，而非对称关系不允许。如上述的「小于等于关系」即是反对称关系的一例。
自反关系和对称关系的概括
| 关系 | 数学表示 |
|---|---|
| 自反 reflexive | |
| 反自反 irreflexive | |
| 对称 symmetric | |
| 反对称 antisymmetric | |
| 非对称 asymmetric |
| 关系 | 自反 | 反自反 | 对称 | 反对称 | 非对称 |
|---|---|---|---|---|---|
| ✗ | ✓ | ✗ | ✓ | ✓ | |
| ✗ | ✓ | ✗ | ✓ | ✓ | |
| ✓ | ✗ | ✓ | ✓ | ✗ | |
| ✗ | ✓ | ✓ | ✗ | ✗ | |
| ✓ | ✗ | ✗ | ✓ | ✗ | |
| ✓ | ✗ | ✗ | ✓ | ✗ |
传递关系 transitive 和等价关系 equivalence
若关系 满足 且还满足 ，则称 是传递关系（transitive）。
自反、传递、反对称的关系，都称为偏序（partial order），无环。 另外，若对于所有的 ，都至少满足 和 其中之一，则这是一个全关系（total relation），满足完全性。注意，完全性是包含了自反性的。
满足传递、反对称、完全性的关系是全序关系，是一条链。由于完全性，全序关系是满足完全性的偏序关系。
顺带提一句：Wikipedia 上面说，偏序分为非严格偏序和严格偏序两种。上面的偏序是指非严格偏序，而严格偏序是反自反的。
任何自反、传递、对称的关系，都称为等价关系（equivalence）。
集合划分 partition of a set
集合 的划分是 的非空子集的集合，使得每个 的元素 都只包含在这些子集的其中一个内。即：collectively exhaustive 且 mutually exclusive。
- 彻底穷举 collectively exhaustive：
- 相互排斥 mutually exclusive：
在数学中，假设在一个集合 上定义一个等价关系（用 来表示），则 中的某个元素 的等价类（equivalence class）就是在 中等价于 的所有元素所形成的子集：。
等价类的概念有助于从已经构造了的集合构造新集合。在 中的给定等价关系 的所有等价类的集合表示为 并叫做 除以 的商集（quotient set）。
因为等价关系的 在 中和任何两个等价类要么相等要么不相交的性质。得出 的所有等价类的集合形成 的划分：所有 的元素属于一且唯一的等价类。反过来， 的所有划分也定义了在 上等价关系。
举例说明：如果 是轿车的集合，而 是「颜色相同」的等价类，则一个特定等价类由所有绿色轿车组成。 自然的被认同于所有轿车颜色的集合。
再举个例子：用模运算在自然数集合下，生成了三个等价类
因此， 构成了 的集合划分。