反链

关于与「反链」標題相近或相同的条目，請見「反向链接」。

在序理論中，设A是一个偏序集，B为A的一个子集，若B中任意两个元素无法相互比較（comparable），则称B是一条反链（Antichain）。为了方便，通常还规定偏序集中的所有单元素子集既是链也是反链。

用形式化语言表述就是：

设${\displaystyle (A,\geqslant )}$是一个偏序集，${\displaystyle B}$是${\displaystyle A}$的子集，则B是A上的反链等价于

${\displaystyle \forall x\forall y\left((x\in B\wedge y\in B)\rightarrow \neg \left(x\geqslant y\vee y\geqslant x\right)\right)}$

相关结论

直观地说，一条反链实际上确定了一个偏序集上互相无法比较的若干条链。容易看出，全序集上反链的最大长度是1。运用链和反链的概念可以证明如下定理，它刻画了偏序关系与集合划分之间的关系：

设${\displaystyle (A,\geqslant )}$是一个偏序集，设A中链的最大长度为n，则A中存在一个由n个反链组成的划分。