跳至內容

反鏈

維基百科,自由的百科全書

序理論中,設A是一個偏序集BA的一個子集,若B中任意兩個元素無法相互比較(comparable),則稱B是一條反鏈(Antichain)。為了方便,通常還規定偏序集中的所有單元素子集既是也是反鏈。

用形式化語言表述就是:

是一個偏序集,的子集,則B是A上的反鏈等價於

相關結論

直觀地說,一條反鏈實際上確定了一個偏序集上互相無法比較的若干條鏈。容易看出,全序集上反鏈的最大長度是1。運用鏈和反鏈的概念可以證明如下定理,它刻畫了偏序關係集合劃分之間的關係:

是一個偏序集,設A中鏈的最大長度為n,則A中存在一個由n個反鏈組成的劃分。