107 - Lecture 5 Relations

Overview
二元关系的基本性质，包括反身性（reflexive）、对称性（symmetric）、传递性（transitive）和反对称性（antisymmetric）。这些性质是确定一个关系是否为等价关系或偏序关系的基础。

Properties of relations

Let R be a binary relation on a set S,Then:

1. 反身性（Reflexive）
   • 定义：如果对于集合S中的每一个元素x，总是有 (x,x) 属于关系R，那么关系R是反身的。
   • 示例：在集合 {1, 2, 3} 上，关系R = {(1,1),(2,2),(3,3)} 是反身的，因为所有的元素都有自反对的关系。
2. 对称性（Symmetric）
   • 定义：如果对于集合S 中的任意两个元素 a和b，当且仅当(a,b)属于R时(b,a)属于R，那么关系  是R对称的。
   • 示例：在集合 {1, 2, 3} 上，关系R = {(1,2),(2,1),(3,3)} 是对称的，因为 (1,2) 和(2,1) 都存在。
3. 传递性（Transitive）
   • 定义：如果对于集合 S 中的任意三个元素 a,b,c，当 (a,b)属于R 且(b,c)属于R 时，总有（a,c)属于R ，那么关系 R是传递的。
   • 示例：在集合 {1, 2, 3} 上，关系 R = {(1,2),(2,3),(1,3)} 是传递的，因为 (1,2) 和 (2,3) 都存在，则 (1,3)也必须存在。
4. 反对称性（Antisymmetric）
   • 定义：如果对于集合 S 中的任意两个不同的元素 a和 b，当(a,b)属于R 且（b,a)属于R 时，必有 a = b，那么关系 R 是反对称的。
   • 示例：在集合 {1, 2, 3} 上，关系 R = {(1,1),(2,2),(3,3),(1,2)} 是反对称的，因为不存在不同的 a和 b 同时满足 (a,b)属于R且(b,a)属于R 。

Example

Relational closures

闭包操作

三种闭包操作，用来使得一个关系具备反身性、对称性或传递性。
(extend the relation so that it does have some properties)

1. 反身闭包（Reflexive Closure）
   • 将没有自反对的元素添加到关系中，使其成为反身的。(add edges)例如，关系 R = {(1,2)} 在集合 {1, 2, 3} 上的反身闭包为 R’ = {(1,2),(1,1),(2,2),(3,3)}。

(In order to find the reflexive closure of a relation R, we add a loop at each node that does not have one)

对角线关系（也称为自反关系）必须包含集合中所有元素的形式为 (a, a) 的配对。也就是说，如果集合为 {1, 2, 3}，那么对角线关系必须包含 (1, 1)、(2, 2) 和 (3, 3) 这三个对。如果只加上 (1, 1)，那么这个关系就不满足自反性，因为集合中的其他元素（如 2 和 3）没有与自身配对。

Example

2. 对称闭包（Symmetric Closure）
   • 为每个 (a,b)属于R，如果(b,a)不属于R ，则将（b,a) 加入到关系中，使其成为对称的。例如，关系 R = {(1,2)} 的对称闭包为R’ = {(1,2),(2,1)} 。

（add an edge有向边 from a to b where there is already an edge from b to a to
make the relation symmetric)

Example

3. 传递闭包（Transitive Closure）

Paths in directed graphs（有向图中的路径）：

• 图中“路径”（path）是指从顶点(vertex)a到顶点b的一系列相连的边（a sequences of connected edges）。例如，在图中显示了一些起点（start）和终点（end），表示从一个顶点到另一个顶点的路径。
• 如果路径的起点和终点是同一个顶点，则称为“回路”（circuit）或“循环”（cycle）。路径的长度(the length og a path)必须至少为1。(路径长度表示了图中实际走过的边的数量)

Informal definition: if there is apathy from a to b, then there should be ansdge from a to b in the transitive closure.

¥

Formal definition: the transitive closure of a binary relation R on the set S is the smallest transitive relation R^t on S that contains R
• Rᵗ 是传递的(transitive)
• R ⊆ Rᵗ：
• Rᵗ 是包含 R 的最小传递关系：意味着传递闭包包含所有在 R 中的关系，同时添加最少的新关系以满足传递性。

tuples指的是由两个元素组成的有序对，用来表示关系中的元素对。例如，关系 R = {(1,1), (1,2), (2,3)} 中的每个元素对 (a, b) 都是一个tuple

•	为每对 (a,b)和 (b,c)添加 (a,c)，使其成为传递的。例如，关系 R = {(1,2),(2,3)} 的传递闭包为 R' = {(1,2),(2,3),(1,3)}。

Example

偏序关系与Hasse图

1. 偏序关系（Partial Order）

•	偏序关系要求反身性、反对称性和传递性。一个集合 S 及其上的偏序关系构成偏序集（Poset）。

A set S with a partial ordering R is called a partially ordered set, or poset
Denoted by (S,R)
• 示例：在整数集 Z上，关系 <= 是偏序的，记为（Z,<=) 因为它满足反身性、反对称性和传递性。
• 反身性：对于任何整数 x ，有 x <= x 成立。
• 反对称性：如果 x <= y 且 y <= x ，则 x 必须等于 y 。
• 传递性：如果 x <= y 且 y <= z ，则 x <= z 。

>= is the partial ordering on the set of integers.

在偏序关系中，元素之间的比较并不一定是全局的。也就是说，并非集合中的所有元素都必须能够进行比较
偏序关系允许某些元素之间的关系是不确定的，而全序关系则要求集合中的任意两个元素都可以比较（即对于任意的 a 和 b ，要么 a >= b ，要么 b <= a ）。

例子：

假设有一个集合 S = {1, 2, 3} ，定义关系 R 为“整数的整除关系”，即 a<= b 当且仅当 a 能整除 b 。这个关系在集合 S 上可以表示为：

•	 1 <= 2 （因为 1 能整除 2）
•	 1 <= 3 （因为 1 能整除 3）

但没有 2 <= 3 ，也没有 3 <= 2 ，因为 2 不能整除 3，3 也不能整除 2。

2. Hasse图（Hasse Diagram）

A visual depiction of a partially ordered set
• 是一种用于表示偏序集的图形。Hasse图中元素用一个节点(node/vertes)表示，如果x是y的直接前驱，则在x 和y之间连接一条边(a straight-line segment)，且 y 位于x 上方。

1.(1,1),(1,2),(1,3)……（6,18),(12,12),(18,18)
• 示例：关系“x整除y”的Hasse图显示了集合 {1, 2, 3, 6, 12, 18} 中的整除关系。图中，节点表示集合的元素，连接的边表示整除关系，例如 1 是 2 和 3 的前驱

在 Hasse 图中，两点之间不应该有水平线连接（joined by a horizontal line)
连接线通常是向上的斜线或垂直线，这表明一个节点位于另一个节点的上方（在偏序关系中更大）。水平线则会给人一种误导，暗示两个元素之间没有明显的顺序关系。

More examples

Comparable/ Incomparable

可比较和不可比较元素
• 在偏序集中，如果元素 a 和 b 满足 (a \blacktriangleright b) 或 (b \blacktriangleright a)，则称它们是可比较的（comparable）。如果 a 和 b 都不满足这两个关系，那么它们就是不可比较的（incomparable）。

Predecessor, immediate predecessor and successor

注： 2 是 6 的直接前驱，因为没有其他元素可以整除 6 同时又能被 2 整除。

Totally ordered

完全序关系

完全序（Total Order），即在偏序集 (S,<=)中，每对元素a和b 都是可比较(comparable)的（即 a<= b或 b<=a）。

• 如果一个偏序集 ((S, \preceq)) 中的任意两个元素都是可比较的（comparable），那么这个集合 S 就被称为全序集或线性序集。
• 一个全序集也可以称为链（chain）
S is called totally ordered or linearly order
<= is called a total order or a linear order
A totally ordered set is also called a chain

Example

•	示例：在整数集上<= 是完全序的，而集合 {1, 2, 3} 的“整除”关系则不是完全序的，因为并非所有元素都是可比较的。