链
| 链 | |
|---|---|
| 术语名称 | 链 |
| 英语名称 | chain |
| 长度 | |
|---|---|
| 术语名称 | 长度 |
| 英语名称 | length |
| 高度 | |
|---|---|
| 术语名称 | 高度 |
| 英语名称 | height |
链(chain)指偏序集中的全序子集，表现为其 Hasse 图中一条纵向的路径。 其中的元素个数称为其长度(length)，也有人使用链上的边数，即元素个数减一。 偏序集的最大链元素个数称为偏序集的高度(height)，也有人使用元素个数减一。
链也用于指全序本身，参见全序。
定义
对偏序集 [math]\displaystyle{ (P,\preceq) }[/math] 及其子集 [math]\displaystyle{ C\subseteq P }[/math] ，若 [math]\displaystyle{ (\forall x, y \in C)(x \preceq y \lor y \preceq x) }[/math] ，即 [math]\displaystyle{ \preceq|_C }[/math] 是 [math]\displaystyle{ C }[/math] 上的一个全序，则称 [math]\displaystyle{ C }[/math] 是偏序集中的一个链(chain)。 称链中元素的个数，即 [math]\displaystyle{ \operatorname{card}C }[/math] 为链 [math]\displaystyle{ C }[/math] 的长度(length)。
偏序集 [math]\displaystyle{ (P,\preceq) }[/math] 的全部链中的最大长度（即最大元素个数）称为偏序集 [math]\displaystyle{ (P,\preceq) }[/math] 的高度(height)。
性质
- 链是偏序集的全序子集，任意两个元素都可以比较。
- 空集视为空链。
- 单元素集一定是链，是平凡链。
- 运算性质
- 与反链概念定义正相对
- 相关定理
- Mirsky 定理：偏序集的最小反链划分等于最大链的大小
- Dilworth 定理（偏序集分解定理）：偏序集的最小链划分等于最大反链的大小
| 序理论 | ||
|---|---|---|
| 预序、预序集 | 极大元、极小元 | 最大元、最小元 |
| 上界、下界 | 上确界、下确界 | |
| 方向、有向集 | 半格（并半格、交半格） | 有界半格（有界并半格、有界交半格） |
| 格 | 有界格 | |
| 偏序、偏序集 | Hasse 图 | |
| 链、长度、高度 | 反链、宽度 | |
| Dilworth 定理 | Mirsky 定理 | |