アンチチェーン

数学の順序理論の分野では、反鎖とは、部分順序集合の部分集合であって、その部分集合内の任意の異なる2つの要素が比較不可能であるような集合のことである。

有限半順序集合における最大の反鎖のサイズは、その幅として知られています。ディルワースの定理によれば、これは集合を分割できる最小の鎖（全順序部分集合）の数にも等しくなります。同様に、ミルスキーの定理によれば、有限半順序集合の高さ（最長の鎖の長さ）は、集合を分割できる最小の反鎖の数に等しくなります。

有限半順序集合におけるすべての反鎖の族には、結合操作と出会い操作を与えることができ、分配束となる。集合包含関係によって順序付けられた有限集合のすべての部分集合からなる半順序系の場合、反鎖はスペルナー族と呼ばれ 、その束はデデキント数の要素を持つ自由分配束となる。より一般的には、有限半順序集合の反鎖の数を数えることは#P完全である。

させて${\displaystyle S}$部分的に順序付けられた集合である。2つの要素${\displaystyle a}$そして${\displaystyle b}$半順序集合の は、次の場合に比較可能であると呼ばれる。${\displaystyle a\leq b}$または${\displaystyle b\leq a.}$2 つの要素が比較できない場合、それらは比較不可能と呼ばれます。つまり、${\displaystyle x}$そして${\displaystyle y}$どちらも比較できない${\displaystyle x\leq y}$または${\displaystyle y\leq x.}$

チェーン${\displaystyle S}$部分集合である${\displaystyle C\subseteq S}$各要素のペアが比較可能であること、つまり、${\displaystyle C}$は完全に秩序立っている。${\displaystyle S}$部分集合である${\displaystyle A\subseteq S}$ここでは、異なる要素の各ペアは比較不可能である。つまり、異なる要素の 2 つの間には順序関係がない。${\displaystyle A.}$ （ただし、著者によっては「反鎖」という用語を強い反鎖、すなわち、半順序集合のどの要素も反鎖の異なる2つの要素より小さくならないような部分集合という意味で使用する場合もある。）

極大アンチチェーンとは、他のどのアンチチェーンの真部分集合でもないアンチチェーンのことです。最大アンチチェーンとは、他のすべてのアンチチェーンの濃度以上であるアンチチェーンのことです。半順序集合の幅は、最大アンチチェーンの濃度です。どのアンチチェーンも、最大で 1 つの要素でどのチェーンとも交差することができます。したがって、順序の要素を分割できる場合、${\displaystyle k}$チェーンの場合、オーダーの幅は最大で${\displaystyle k}$（アンチチェーンが${\displaystyle k}$要素は、鳩の巣原理によ​​り、同じ鎖に属する要素が 2 つ存在することになり、矛盾が生じる。ディルワースの定理は、この限界は常に達成可能であると述べている。常に反鎖が存在し、要素を鎖に分割することで、鎖の数が反鎖内の要素の数に等しくなり、したがって幅にも等しくなければならない。^{[ 1 ]}同様に、半順序の高さを鎖の最大濃度として定義することができる。ミルスキーの定理は、有限の高さを持つ任意の半順序において、高さは順序を分割できる反鎖の最小数に等しいと述べている。^{[ 2 ]}

部分集合の包含順序における反鎖${\displaystyle n}$要素集合はスペルナー族として知られています。異なるスペルナー族の数はデデキント数^{[ 3 ]}で数えられ、最初のいくつかの数は

2、3、6、20、168、7581、7828354、2414682040998、56130437228687557907788 （ OEISの配列A000372）。

空集合でさえ、その冪集合には2つの反連鎖が存在する。1つは単一の集合（空集合自体）を含む反連鎖であり、もう1つは集合を全く含まない反連鎖である。

アンチチェーン${\displaystyle A}$下位セットに対応$${\displaystyle L_{A}=\{x:\exists y\in A{\mbox{ such that }}x\leq y\}.}$$ 有限半順序（より一般的には昇鎖条件を満たす半順序）では、すべての下位集合はこの形式をとります。任意の2つの下位集合の和集合は別の下位集合であり、和集合演算は反鎖上の結合演算に次のように対応します。 $${\displaystyle A\vee B=\{x\in A\cup B:\nexists y\in A\cup B{\mbox{ such that }}x<y\}.}$$同様に、下位集合の交差に対応する、反鎖上の 出会い演算 を定義することができる。$${\displaystyle A\wedge B=\{x\in L_{A}\cap L_{B}:\nexists y\in L_{A}\cap L_{B}{\mbox{ such that }}x<y\}.}$$ 集合の有限部分集合のすべての有限反鎖に対する結合および出会い操作${\displaystyle X}$分配束を定義する。自由分配束は、${\displaystyle X.}$分配束に関するバーコフの表現定理は、すべての有限分配束は、有限半順序の反鎖に対する結合および交わり演算、または同等に、半順序の下位集合に対する和集合および積集合演算によって表現できると述べている。^{[ 4 ]}

有限の半順序集合では、最大反鎖（およびそのサイズ、つまり与えられた半順序集合の幅）は多項式時間で見つけることができます。^{[ 5 ]} 与えられた半順序集合内の反鎖の数を数えることは#P完全です。^{[ 6 ]}

• ワイススタイン、エリック・W. 「アンチチェーン」 . MathWorld .
• 「アンチチェーン」。PlanetMath 。