偏序集

满足自反、反对称、传递关系的集合;定义可比性、链、反链、极值、上下界与覆盖关系。

标签 数学 / 偏序集 / 序理论

定义

设 𝑃 是集合,≤ 是 𝑃 上的二元关系。若 ≤ 满足以下三条,则称它是 𝑃 上的偏序关系,(𝑃,≤) 是偏序集:

  • 自反性:对任意 𝑥∈𝑃,𝑥≤𝑥;
  • 反对称性:若 𝑥≤𝑦 且 𝑦≤𝑥,则 𝑥=𝑦;
  • 传递性:若 𝑥≤𝑦 且 𝑦≤𝑧,则 𝑥≤𝑧。

严格偏序由

𝑥<𝑦≝𝑥≤𝑦∧𝑥≠𝑦

定义。

可比性、链与反链

若 𝑥≤𝑦 或 𝑦≤𝑥,称 𝑥 与 𝑦 可比;否则不可比。

若 𝑃 中任意两个元素都可比,则 ≤ 是全序,(𝑃,≤) 是链。

若 𝑆⊆𝑃 中任意两个不同元素都不可比,则 𝑆 是反链。

极值与界

设 𝑆⊆𝑃 非空。

  • 极小元:𝑥∈𝑆 是极小元,若不存在 𝑦∈𝑆 使 𝑦<𝑥。
  • 极大元:𝑥∈𝑆 是极大元,若不存在 𝑦∈𝑆 使 𝑥<𝑦。
  • 最小元:𝑥∈𝑆 是最小元,若对任意 𝑦∈𝑆,𝑥≤𝑦。
  • 最大元:𝑥∈𝑆 是最大元,若对任意 𝑦∈𝑆,𝑦≤𝑥。

设 𝑆⊆𝑃。若 𝑢∈𝑃 满足对任意 𝑥∈𝑆 都有 𝑥≤𝑢,则称 𝑢 是 𝑆 的上界;若 𝑙∈𝑃 满足对任意 𝑥∈𝑆 都有 𝑙≤𝑥,则称 𝑙 是 𝑆 的下界。

若 𝑆 的所有上界中存在最小者,则称它为 𝑆 的上确界,记作 sup𝑆;若 𝑆 的所有下界中存在最大者,则称它为下确界,记作 inf𝑆。

覆盖关系

若 𝑥<𝑦,且不存在 𝑧 使 𝑥<𝑧<𝑦,则称 𝑦 覆盖 𝑥,记作 𝑥≺𝑦。

源码位置