反链

维基百科,自由的百科全书
跳转至: 导航搜索

设A是定义了偏序关系的一个集合,B为A的一个子集,若B中任意两个元素无法确定偏序关系,则称B是一条反链(Antichain)。为了方便,通常还规定A的所有单元素子集B既是也是反链。

用谓词逻辑的语言表述就是:

\left \langle A,\geqslant \right \rangle是一个偏序集,B \subseteq A,则B是A上的反链等价于:

\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。运用链和反链的概念可以证明如下定理,它刻画了偏序关系集合划分之间的关系:

\left \langle A, \geqslant \right \rangle是一个偏序集,设A中链的最大长度为n,则A中存在一个由n个反链组成的划分。