1、⛺偏序关系和偏序集
⛲偏序关系
定义：定义在集合 S 上的关系 R，如果它是自反的、反对称的和传递的，就称为偏序（或 偏序关系）。
❗注意：在一个集合的偏序关系中，并不是任何2个元素之间都具有偏序关系，例如 aRb cRd,但是 a与c之间可能不具有偏序关系R
⛲偏序（关系）的例子
证明是否是偏序，要依次验证自反性、反对称性、传递性满足与否
a. “大于或等于” 关系
证明：“ 大于或等于 ” ( ≥ )关系是整数集合上的偏序关系。
🔴解：
自反性： 对所有整数 a 有 a ≥ a，✔️
反对称性： 如果 a ≥ b 且 b ≥ a，那么 a = b，✔️
传递性： 因为 a ≥ b 且 b ≥ c 蕴涵 a ≥ c，✔️
综上所述， ≥ 关系是整数集上的偏序关系
b. “整除” 关系
证明：“ 整除 ”（ | ）关系是正整数集合上的偏序关系。
🔴解：
自反性： 对所有整数 a，有 a | a，✔️
反对称性： 如果 a 和 b 是正整数，且有 a | b 和 b | a，那么 a = b，✔️
传递性： 假设 a 整除 b 并且 b 整除 c。则有正整数 k 和 l 使得 b = ak 和 c = bl 成立。因此，c = a(kl)，所以 a 整除 c，✔️
综上所述， 整除 关系是正整数集合上的偏序关系
c. “包含” 关系
证明：集合的包含（⊆）关系 是定义在集合 S 的幂集上的偏序。
🔴解：
自反性： 只要 A 是 S 的子集，就有 A ⊆ A，✔️
反对称性： A ⊆ B 和 B ⊆ A 蕴涵 A = B，✔️
传递性： A ⊆ B 和 B ⊆ C 蕴涵 A ⊆ C，✔️
综上所述， 包含关系是定义在集合 S 的幂集上的偏序。
🎬偏序集
集合 S 与定义在其上的偏序关系R 一起称为偏序集，记作 (S, R)。
集合 S 中的成员称为偏序集的元素
🎬可比性（comparability）
" ≼ " 符号
符号" ≼ " 用于表示任何偏序集中的关系。
在不同的偏序集中，会使用不同的符号表示偏序，如≤、⊆ 和 │
👉然而，我们需要一个符号用来表示任意一个偏序集中的序关系：
通常，在一个偏序集 (S，R)中，记号a ≼ b表示( a , b )∈R。使用这个记号是由于 “ 小于或等于 ” 关系是偏序关系的范例，而且符号" ≼ " 和 " ≤ "很相似。
(注意符号" ≼ " 用来表示任意偏序集中的关系，并不仅仅是“小于或等于”关系)
❗当 a 与 b 是偏序集 (S， ≼ ) 的元素时，不一定有 a ≤ b 或 b ≤ a
例如，在偏序集 ( P(Z)，⊆ ) 中，{1，2}与{1，3}没有关系，反之亦然，因为没有一个集合被另一个集合包含。
a. 可比 & 不可比
定义：偏序集 (S, ≼) 中的元素 a 和 b 称为可比的，如果 a ≼ b 或 b ≼ a。
当 a 和 b 是 S 中的元素并且既没有 a ≼ b，也没有 b ≼ a，则称 a 与 b 是不可比的（incomparable）。
❗注意：这里的“ ≼ ” 不同于 “ ≤ ”，写的时候要尽可能弯一点，便于区分
“ ≼ ”：
“ ≤ ”：
b. 全序（ =线序 ）
定义：如果(S, ≼)是偏序集，且 S 中的每对元素都是可比的，则 S 称为全序集（totally ordered set）或线序集（linearly ordered set），且 " ≼ " 称为全序或线序。
一个全序集也称为链（chain）
c. 良序集、良序归纳原理及其应用
良序集定义：
对于偏序集( S, ≼ )，如果 " ≼ "是全序，并且 S 的每个非空子集都有一个最小元素，就称它为良序集（well-ordered set）。
（良序是对于结构很好的全序（线序）而言的）
良序归纳原理：
设S是一个良序集。如果（归纳步骤）对所有y∈𝑆，如果 P(x) 对所有 x∈𝑆 且 x ≺ y 为真，则P(y)为真，那么P(x)对所有的 x∈𝑆 为真
（证明：假设P(x)不对所有的x∈𝑆为真。那么存在一个元素 y∈𝑆，使得P(y)为假。于是集合A = {x∈𝑆|P(x)为假} 是非空集合。因为S是良序的，所以A有最小元素a, 根据a是选自A的最小元素，对所有 x∈𝑆 且 x ≺ a 都有 P(x) 为真。由归纳步骤得P(a)为真。这个矛盾就证明了P(x)必须对所有的x∈𝑆为真。）
良序归纳原理的应用：
比数学归纳法更简单，使用良序归纳法进行证明时，不需要基础步骤
因为若 x0 是良序集的最小元素，由归纳步骤可知 P(x0) 为真。因为不存在 x∈S 且x≺x0，所以P(x) 对所有 x∈S 且 x≺x0 为真
🎬偏序集的例子
a. 可比
在偏序集 ( Z+ , | )中，整数 3 和 9 是可比的吗？5 和 7 是可比的吗？
🔴解：
整数 3 和 9 是可比的，因为 3|9
整数 5 和 7 是不可比的，因为 5不可整除7，且 7 不可整除 5
b. 全序
全序：每对元素都是可比的
①偏序集（Z，≤ ）是全序集，因为只要a，b是整数，就有a ≤ b 或者b ≤ a
②偏序集（Z+，| ）不是全序集，因为它包含不可比的元素，比如 3 和 5
c. 良序集
正整数的有序对的集合：Z+ × Z+，与 ≼ 构成良序集（因为存在最小元素），其中如果a1 < b1 ，或如果a1 = b1且a2 < b2 ，则（a1 ，a2 ）≼（b1 ，b2 ）
集合 Z 与通常的 ≤ 不是良序的，因为 Z 中包含负整数集合，而负整数集合中没有最小元素
2、⛺字典序（Lexicographic Orderings）
定义：给定两个偏序集 ( A1 , ≼1 ) 和 ( A2, ≼2 ) ，在 A1 × A2 上的字典顺序 ≼ 定义为 (a1, a2) 小于 (b1, b2)，即 (a1, a2) ≺ (b1, b2)，或者a1 ≺ 1 b1，或者 a1 = b1 且 a2 ≺2 b2
(把相等增加到 A1 × A2 的序 ≺ 上，就得到一个偏序 ≼ )
例：考虑由小写英语组成的字符串的集合。使用字母在字母表中的顺序，可以构造在字符串的集合上的字典顺序。这与字典中使用的顺序相同。
🔴
discreet ≺ discrete，因为字符串在第7位出现不同字母，且 e ≺ t
discreet ≺ discreetness，因为这两个字符串前8个字母相同，但是第二个字符串更长
