偏序关系

集合 A 上的关系 R 称为偏序关系，如果它满足以下三个性质

1. 关系 R 是自反的，即 aRa ∀ a∈A。
2. 关系 R 是反对称的，即 aRb 和 bRa ⟹ a = b。
3. 关系 R 是传递的，即 aRb 和 bRc ⟹ aRc。

例 1： 证明关系 (x, y) ∈ R（如果 x ≥ y）在正整数集合上定义的是偏序关系。

解： 考虑一个集合 A = {1, 2, 3, 4}，包含四个正整数。 找到这个集合的关系，例如 R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3), (1, 1), (2, 2), (3, 3), (4, 4)}。

自反性： 对于每个 a ∈ A，该关系是自反的。 (a, a) ∈ R，即 (1, 1), (2, 2), (3, 3), (4, 4) ∈ R。

反对称性： 该关系是反对称的，因为当 (a, b) 和 (b, a) ∈ R 时，我们有 a = b。

传递性： 该关系是传递的，因为当 (a, b) 和 (b, c) ∈ R 时，我们有 (a, c) ∈ R。

例： (4, 2) ∈ R 且 (2, 1) ∈ R，表示 (4, 1) ∈ R。

由于该关系是自反的、反对称的和传递的。 因此，它是一个偏序关系。

例 2： 证明在 N 上定义的“整除”关系是一个偏序关系。

解决方案

自反性： 我们有 a 整除 a，∀ a∈N。 因此，“整除”关系是自反的。

反对称性： 设 a, b, c ∈N，使得 a 整除 b。 这意味着 b 整除 a 当且仅当 a = b。 因此，该关系是反对称的。

传递性： 设 a, b, c ∈N，使得 a 整除 b 且 b 整除 c。

那么 a 整除 c。 因此，该关系是传递的。 因此，由于该关系是自反的、反对称的和传递的，因此“整除”关系是一个偏序关系。

例 3： (a) 集合包含关系 ⊆ 是偏序关系或任何集合的集合，因为集合包含具有三个所需的属性

1. 对于任何集合 A，A ⊆ A。
2. 如果 A ⊆ B 且 B ⊆ A，则 B = A。
3. 如果 A ⊆ B 且 B ⊆ C，则 A ⊆ C

(b) 实数集 R 上的关系 ≤ 是自反的、反对称的和传递的。

(c) 关系 ≤ 是一个偏序关系。

n 元关系

通过 n 元关系，我们指的是有序的 n 元组的集合。 对于任何集合 S，积集 Sⁿ 的子集称为 S 上的 n 元关系。 特别地，S³ 的子集称为 S 上的三元关系。

偏序集 (POSET)

集合 A 连同集合 A 上的偏序关系 R，表示为 (A, R)，称为偏序集或 POSET。

全序关系

考虑集合 A 上的关系 R。 如果对于所有 a, b ∈ A，我们也有 (a, b) ∈ R 或 (b, a) ∈ R 或 a = b，则关系 R 被称为集合 A 上的全序关系。

例： 证明在正整数集 N 上定义的“<”（小于）关系既不是等价关系也不是偏序关系，但却是全序关系。

解决方案

自反性： 设 a ∈ N，则 a < a
⟹ “<”不是自反的。

由于关系“<”（小于）不是自反的，它既不是等价关系也不是偏序关系。

但是，对于所有 a, b ∈ N，我们都有 a < b 或 b < a 或 a = b。 因此，该关系是全序关系。

等价类

考虑集合 A 上的等价关系 R。 元素 a ∈ A 的等价类是 A 中与元素 a 相关的元素的集合。 它表示为 [a]。

例： 设 R 是集合 A = {4, 5, 6, 7} 上定义的等价关系，定义为
                  R = {(4, 4), (5, 5), (6, 6), (7, 7), (4, 6), (6, 4)}。

确定其等价类。

解： 等价类如下所示
                    {4} = {6} = {4, 6}
                    {5} = {5}
                    {7} = {7}.

循环关系

考虑集合 A 上的二元关系 R。 如果 (a, b) ∈ R 且 (b, c) ∈ R 意味着 (c, a) ∈ R，则关系 R 称为循环的。

例： 考虑 R 是一个等价关系。 证明 R 是自反的和循环的。

解： 自反性：由于关系 R 是等价关系。 因此，自反性是等价关系的性质。 因此，R 是自反的。

循环性： 设 (a, b) ∈ R 且 (b, c) ∈ R
                  ⇒ (a, c) ∈ R       (∵ R 是传递的)
                  ⇒ (c, a) ∈ R       (∵ R 是对称的)

因此，R 是循环的。

相容关系

集合 A 上的二元关系 R，如果它是自反的和对称的，则称为相容关系。

每个等价关系都是相容的，但每个相容关系不一定是等价的。

例： 一组朋友是相容的，但可能不是等价关系。

朋友       朋友
a → b,       b → c     但可能 a 和 c 不是朋友。