查看“︁反链”︁的源代码

[[分类:序理论]]{{DEFAULTSORT:fan3lian4}}
{{#seo:
|keywords=反链, 偏序集, 偏序集的宽度
|description=本文介绍序理论中反链的概念、定义和性质，包括反链的宽度和偏序集的宽度，以及反链相关的定理，
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2024-02-28
}}
{{InfoBox
|name=反链
|eng_name=antichain
}}
{{InfoBox
|name=宽度
|eng_name=width
}}
'''反链'''('''antichain''')指[[偏序集]]中的不可比子集，表现为其 [[Hasse 图]]中不存在纵向连线关系的结点。
其中的元素数称为其'''宽度'''('''width''')。
偏序集的最大反链宽度也称为偏序集的'''宽度'''('''width''')。

== 定义 ==

对偏序集 <math>(P,\preceq)</math> 及其子集 <math>A\subseteq P</math> ，若 <math>(\forall x, y \in A)(x\neq y \rightarrow x \npreceq y \land y \npreceq x)</math> ，即 <math>\preceq|_A</math> 是 <math>A</math> 上的一个[[恒等关系]]，则称 <math>A</math> 是偏序集中的一个'''反链'''('''antichain''')。
称反链中元素的个数，即 <math>\operatorname{card}A</math> 为其'''宽度'''('''width''')。

偏序集 <math>(P,\preceq)</math> 的全部反链中的最大宽度称为偏序集 <math>(P,\preceq)</math> 的'''宽度'''('''width''')。

== 性质 ==

反链具有以下重要性质：

* 反链是偏序集中的不可比子集，任意两个不同元素都不可比较。
** 空集视为空反链。
** 单元素集一定是反链，是平凡反链。
* 运算性质
** 反链的[[子集]]仍是反链
** 反链的[[交集]]仍是反链
* 与[[链]]概念定义正相对
* 相关定理
** [[Dilworth 定理]]（偏序集分解定理）：偏序集的最小链划分等于最大反链的大小
** [[Mirsky 定理]]：偏序集的最小反链划分等于最大链的大小
** [[Sperner 定理]]：在幂集格中，最大反链由大小居中的子集构成


{{序理论}}