反鎖
概要
反鎖（antichain）とは、半順序集合では相異なる元が互いに比較できない部分集合をいう。強制法では、相異なる条件が共通の強化を持たない部分集合を指す。後者は前者より強い条件である。極大反鎖は、どの条件もそのいずれかの元と両立する反鎖であり、可算鎖条件やジェネリックフィルターの定義に現れる。
反鎖とは
反鎖（antichain）は、半順序集合の中で、二つずつが互いに比較できない元の集まりである。強制法では、より強い条件を共通に持たない元の集まりを反鎖と呼ぶ。後者の条件は前者より強いので、文脈による違いに注意が必要である（Dil50、Jec03 Chapter 14）。どちらの定義でも、ひとつの元だけからなる集合と空集合は反鎖になる。
順序論での定義
半順序集合 $(P,\leq)$ の部分集合 $A$ について、相異なる $a,b\in A$ がどちらも $a\leq b$ と $b\leq a$ を満たさないとき、$A$ を順序論的な反鎖という。
半順序集合 $(P,\leq)$ の部分集合 $A$ が反鎖であるとは、任意の相異なる $a,b\in A$ について
$$
a\nleq b\quad\text{かつ}\quad b\nleq a
$$
が成り立つことである。
この定義は、順序を逆にしても変わらない。$a$ と $b$ が比較できるかどうかは、上界・下界の向きを取り替えても同じだからである。ただし、反鎖は「隣接した元」や「順序に沿って並べた列」ではない。集合の中のどの二元も比較できないことを同時に要求する。
たとえば、$\mathcal P(\{1,2\})$ を包含関係で順序づけると、$\{\{1\},\{2\}\}$ は反鎖である。$\{1\}$ と $\{2\}$ は互いに包含しない。より一般に、有限集合 $S$ の部分集合のうち元の個数が同じものを集めると、順序論的な反鎖になる。相異なる二つの有限集合が同じ大きさなら、一方が他方を真に含むことはできないためである。
一方、包含関係で並べた $\mathcal P(\{1,2\})$ では、$\emptyset\subseteq\{1\}\subseteq\{1,2\}$ は鎖である。鎖では任意の二元を比較できる。反鎖と鎖は、同じ半順序集合の構造を異なる方向から測る道具である。
有限半順序集合の幅は反鎖の元の個数の最大値である。たとえば上の四元からなる部分集合の順序では、$\{\{1\},\{2\}\}$ が二元の反鎖であり、幅は $2$ である。三元の反鎖はない。$\emptyset$ はほかのどの部分集合とも比較でき、$\{1,2\}$ も同様だからである。
Dilworthの定理は、有限半順序集合の幅が、全体を鎖に分割するために必要な鎖の最小個数と等しいことを述べる（Dil50 Theorem 1.1）。等号のうち、一方向には簡単な理由がある。反鎖の二元を同じ鎖に入れることはできないから、$k$ 元の反鎖を含む順序集合を鎖で覆うには少なくとも $k$ 個の鎖が要る。逆向きに幅と同じ個数の鎖だけで分割できることが Dilworth の定理の本質である。
強制法での定義
強制概念 $\mathbb P$ では、$p\leq q$ を「$p$ は $q$ 以上に強い」と読む。二条件 $p,q$ が両立するとは、ある $r\in\mathbb P$ が $r\leq p$ かつ $r\leq q$ を満たすことである。このような $r$ がないとき、二条件は非両立である。
$A\subseteq\mathbb P$ が強制法の反鎖であるとは、$A$ の相異なる二条件がすべて非両立であることである。
強制法の反鎖は順序論的な反鎖である。逆は一般には成り立たない。
相異なる $p,q$ が比較できるとする。たとえば $p\leq q$ なら、$p$ 自身が $p$ と $q$ の共通の強化になる。従って非両立な二条件は比較できず、強制法の反鎖は順序論的な反鎖である。
逆を否定する例として、$P=\mathcal P(\{1,2\})$ に包含順序を入れる。$p=\{1\}$ と $q=\{2\}$ は比較できないが、$\emptyset\subseteq p,q$ である。従って $\{p,q\}$ は順序論的な反鎖であっても強制法の反鎖ではない。
この例では、空集合がすべての条件の共通の強化になっている。そのため、この順序をそのまま強制概念とみなすと、相異なる二条件からなる強制法の反鎖は一つもない。反鎖を数える前に、条件の順序と「共通の強化」の意味を確かめる必要がある。
有限部分関数による判定
強制法に実際に現れる例として、$\operatorname{Fn}(\omega,2)$ を自然数から $\{0,1\}$ への有限部分関数の集合とする。$p\leq q$ は $p\supseteq q$、すなわち $p$ が $q$ の指定値をすべて保ったまま定義域を広げることを意味する。この順序は集合としての包含関係とは逆である。空関数が最も弱い条件になる。
$p,q\in\operatorname{Fn}(\omega,2)$ が両立するための必要十分条件は、共通の定義域のすべての点で同じ値を取ることである。このとき $p\cup q$ が両方の共通の強化になる。
両立するとし、$r\leq p,q$ を取る。$r$ は両方を延長する関数なので、$n\in\operatorname{dom}(p)\cap\operatorname{dom}(q)$ では $p(n)=r(n)=q(n)$ でなければならない。
逆に、共通の定義域で値が一致するとする。このとき集合としての和 $p\cup q$ は関数であり、二つの有限集合の和だから定義域も有限である。ゆえに $p\cup q\in\operatorname{Fn}(\omega,2)$ であり、$p\cup q\leq p,q$ を満たす。
$p=\{(0,0)\}$ と $q=\{(0,1)\}$ は同じ入力に異なる値を指定するので非両立である。一方、$p$ と $s=\{(1,1)\}$ は比較できないが、$p\cup s$ が共通の強化である。異なる入力についての指定は両立しうる。ここでも比較不能性だけでは強制法の反鎖を判定できない。
有限集合 $E\subseteq\omega$ に対し、$\operatorname{dom}(p)=E$ である条件を全部集めた集合を $A_E$ と書く。$A_E$ の相異なる二元は $E$ のどこかで値が異なるので非両立である。$A_E$ は $2^{|E|}$ 個の条件からなる反鎖である。後述するように、この反鎖は極大でもある。
有限の反鎖だけでなく、無限の反鎖もある。各 $n\in\omega$ について、$p_n$ を $n$ 未満の各自然数に $0$、$n$ に $1$ を割り当てる条件とする。$m< n$ なら $p_m(m)=1$ だが $p_n(m)=0$ なので、$p_m$ と $p_n$ は非両立である。したがって $\{p_n:n\in\omega\}$ は可算無限の反鎖である。この構成は、有限部分関数の全体が可算であっても反鎖がすべて有限になるわけではないことを示す。
極大反鎖と稠密性
強制法の反鎖 $A$ が極大であるとは、それを真に含む反鎖がないことである。言い換えると、包含関係でこれ以上大きくできない反鎖である。強制概念の部分集合 $D$ について、どの条件も $D$ のある元と両立するとき、$D$ を前稠密という。これは、各 $p$ の下に $D$ の元が直接あることを求める通常の稠密性より弱い。強制法の「前稠密」は位相空間の稠密性とは別の順序に関する概念である。
強制法の反鎖 $A$ が極大であることと、$A$ が前稠密であることは同値である。
$A$ が極大であるとする。$A$ のどの元とも両立しない条件 $p$ があれば、$p\notin A$ であり、$A\cup\{p\}$ は $A$ を真に含む反鎖となって矛盾する。従ってどの条件も $A$ のある元と両立する。
逆に $A$ が前稠密とする。$A$ の外のどの条件 $p$ も、$A$ のある元 $a$ と両立する。すると $A\cup\{p\}$ は反鎖にならない。よって $A$ は極大である。
先の $A_E$ は極大である。任意の有限部分関数 $p$ に対し、$E$ 上で $p$ がすでに指定した値を保ち、未指定の点には任意の値を割り当てた関数 $a:E\to\{0,1\}$ を選べる。$p$ と $a$ は共通の定義域で一致するので両立する。従って $A_E$ は前稠密である。特に $E=\emptyset$ なら、$A_E$ は空関数一つだけからなる極大反鎖である。
この $A_E$ は一般に稠密ではない。たとえば $E=\{0\}$、$p=\{(1,0)\}$ とすると、$A_E$ の元はどれも点 $1$ で値を指定しないため、$p$ 以下の条件ではない。しかし $p$ と両立する元は $A_E$ にある。この例で稠密性と前稠密性の違いが具体的に見える。$A_E$ の元をさらに強化して得る条件全体は稠密になり、後述の $D_A$ がその一般形である。
「極大反鎖がある」と述べるときには、どの条件からも作れるのかも問題になる。ZFC では選択公理と同値な Zorn の補題を使って、任意の反鎖を極大反鎖まで拡張できる。ただし、この存在定理は反鎖の元を具体的に列挙するものではない。
ZFC のもとで、強制概念 $\mathbb P$ の任意の反鎖 $B$ は、ある極大反鎖 $A$ に含まれる。
$B$ を含む反鎖全体を包含関係で順序づける。この集合は $B$ を含むから空でない。包含関係で全順序になる反鎖の族 $\mathcal C$ を取ると、その和集合 $C=\bigcup\mathcal C$ はなお反鎖である。実際、$C$ の二元 $p,q$ はそれぞれ $\mathcal C$ のある元に属し、その二つの反鎖は包含関係で比較できる。したがって $p,q$ は両方とも大きい方の反鎖に属し、非両立である。$C$ は $\mathcal C$ の上界である。Zorn の補題により、$B$ を含む反鎖全体には極大元 $A$ があり、これは $\mathbb P$ 全体の中でも極大反鎖である。
非空部分集合の強制での見え方
順序論と強制法の二つの定義の違いは、部分集合の例でもはっきり現れる。空でない集合 $S$ に対し、$\mathbb P=\mathcal P(S)\setminus\{\emptyset\}$ を包含関係で順序づける。条件は $S$ の空でない部分集合であり、より小さい集合ほど強い条件とみなす。先に扱った $\mathcal P(\{1,2\})$ と違い、空集合を条件から除いている。この一箇所の変更で、両立性の意味が変わる。
$p,q\in\mathbb P$ が両立することと $p\cap q\ne\emptyset$ は同値である。したがって $\mathbb P$ の反鎖は、空でない部分集合が二つずつ交わらない族である。そのような反鎖が極大であることと、その族の和集合が $S$ になることも同値である。
$p$ と $q$ に共通の強化 $r$ があれば、$r$ は空でなく $r\subseteq p\cap q$ だから、$p\cap q$ も空でない。逆に $p\cap q$ が空でなければ、それ自身が $\mathbb P$ の条件であり、$p,q$ の共通の強化になる。よって非両立性は交わりが空であることと一致する。
いま $A$ が反鎖で、その和集合が $S$ であるとする。任意の条件 $p$ から点 $s\in p$ を一つ取ると、$s$ は $A$ のある元 $a$ に入る。従って $p\cap a\ne\emptyset$ であり、$p$ は $a$ と両立する。$A$ は前稠密なので極大である。逆に $\bigcup A\ne S$ なら、和集合に入らない点 $s\in S$ を取り、条件 $\{s\}$ を考える。これは $A$ のどの元とも交わらないから、$A\cup\{\{s\}\}$ はより大きな反鎖になる。ゆえに $A$ は極大ではない。
この強制概念の極大反鎖は、$S$ の分割にちょうど対応する。一方、順序論的な反鎖は、包含関係で比較不能な集合族であり、集合どうしが交わっていてもよい。たとえば $S=\{1,2,3\}$ で $\{1,2\}$ と $\{2,3\}$ は比較不能だが、交わり $\{2\}$ が共通の強化を与える。非両立性を考えるときは、順序集合に最小元を含めるかどうかも重要である。空集合を含めればどの二条件も両立し、除けば交わりの有無が効く。
同じ発想はブール代数の零元でない元を条件とする強制にも使える。二条件の積（共通部分に相当する元）が零元でなければ、その積が共通の強化になる。従ってこの文脈の反鎖は、異なる二元の積が常に零元になる族である。順序で比較できないというだけでは、積が零元になるとは限らない。
この例は、強制法の極大反鎖についても「極大」と「最大」の違いを示す。$S=\{1,2\}$ なら、一つの条件だけからなる $\{S\}$ は極大反鎖である。どの非空部分集合も $S$ と交わるからである。しかし $\{\{1\},\{2\}\}$ も極大反鎖であり、こちらの方が元の個数は多い。極大反鎖の大きさは一意には決まらない。
極大という語は包含関係についての極大性を表す。反鎖の元の個数が最大であるという意味ではない。たとえば三元 $a,b,c$ からなる順序集合で $a< b$、$a< c$ とし、$b,c$ は比較不能とする。順序論的な反鎖 $\{a\}$ は極大だが、$\{b,c\}$ より小さい。強制法でも極大性はまず包含関係で定める。
極大反鎖 $A$ に対して
$$
D_A=\{q\in\mathbb P:\text{ある }a\in A\text{ について }q\leq a\}
$$
とおくと、$D_A$ は稠密である。実際、どの $p$ も $A$ のある $a$ と両立するので、共通の強化 $q\leq p,a$ があり、$q\in D_A$ となる。この構成により、極大反鎖はジェネリック性を調べる手段になる。
$M$ を基礎モデル、$\mathbb P\in M$ を強制概念、$G$ を $M$ 上のジェネリックフィルターとする。$M$ に属する極大反鎖 $A$ に対し、$G\cap A$ はちょうど一元を持つ。
$A$ が極大なので、上の $D_A$ は稠密であり、$A,\mathbb P\in M$ から $D_A\in M$ でもある。ジェネリック性により $G$ は $D_A$ と交わる。$q\in G\cap D_A$ を取れば、ある $a\in A$ について $q\leq a$ である。フィルターの上方閉性から $a\in G$ となるので、$G\cap A$ は空でない。
一方、相異なる $a,b\in G\cap A$ があれば、フィルターの有向性から共通の強化 $r\in G$ が存在する。しかし $A$ は反鎖であり $a,b$ は非両立だから矛盾する。従って交点は一元だけである。
この命題の逆向きも、定義を適切にそろえれば成り立つ。基礎モデルに属するすべての極大反鎖に交わるフィルターは、基礎モデルに属するすべての稠密集合と交わる。稠密集合の中に極大反鎖を選べることを用いる（Jec03 Definition 14.1 とその直後）。したがって「極大反鎖を一つ選ぶ」は、ジェネリックフィルターにとって「その中の一条件を決める」という意味を持つ。
極大性は強制概念全体だけでなく、一つの条件 $p$ の下でも考えられる。$\mathbb P{\downarrow}p=\{q\in\mathbb P:q\leq p\}$ の中で極大な反鎖は「$p$ の下の極大反鎖」である。この語は、$p$ と両立しない条件を覆うことまで要求しない。反鎖がどの順序集合の中で極大なのかを指定することは、強制法の議論で重要である。
可算鎖条件との関係
可算鎖条件（ccc）は、強制概念のすべての反鎖が高々可算であるという条件である。ここで数える反鎖は、比較不能な条件の集合ではなく、非両立な条件の集合である。この区別が定義に直接影響する。
たとえば $\operatorname{Fn}(\omega,2)$ は条件全体が可算なので ccc を満たす。それでも有限集合 $E$ を大きくすれば、上の $A_E$ としていくらでも大きい有限の極大反鎖を作れる。ccc は反鎖の大きさに一つの有限上界があるとは主張せず、非可算な反鎖だけを禁じる。
ccc は強制拡大で基数と共終数を保つための代表的な十分条件となる。新しい関数の各入力に対する値を決める条件を極大反鎖で整理すると、可能な値の候補は高々可算個に制限される。この観察が保存定理の証明の出発点である（Jec03 Definition 14.33、Theorem 14.34）。
用語の使い分け
- 順序論の反鎖では、二元が順序で比較できないことを調べる。有限順序集合の幅や鎖への分割で使う。
- 強制法の反鎖では、二条件が共通の強化を持たないことを調べる。極大反鎖、ジェネリックフィルター、ccc で使う。
- 二条件が非両立なら比較不能である。しかし比較不能であっても共通の強化を持つことがある。有限部分関数の例では、異なる入力に対する指定がその典型である。
- 極大は包含関係でこれ以上増やせないという意味であり、元の個数が最大という意味ではない。
条件を外したときの反例
thm-antichain-maximal と thm-antichain-generic の仮定を一つずつ外すと結論が崩れることを、有限の強制概念で確かめる。以下では $S=\{1,2,3\}$ または $S=\{1,2\}$ とし、$\mathbb P=\mathcal P(S)\setminus\{\emptyset\}$ を包含関係で順序づけた強制概念を使う。thm-antichain-powerset により、二条件が両立することは交わりが空でないことと同じである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 「非両立」（強制法の反鎖）を「比較不能」（順序論的な反鎖）に弱める | $S=\{1,2,3\}$、$A=\{\{1,2\},\{2,3\},\{1,3\}\}$、$G=\{p:2\in p\}$ | ジェネリックフィルターとの交点がちょうど一元であること |
| $A$ が極大であること | $S=\{1,2,3\}$、$A=\{\{1\}\}$、$G=\{p:2\in p\}$ | 交点が空でないこと |
| $G$ がジェネリックであること | $S=\{1,2\}$、$A=\{\{1\},\{2\}\}$、$G=\{S\}$ | 交点が空でないこと |
| $A$ が反鎖であること | $\mathbb P$ 全体（前稠密な集合として） | 前稠密なら極大反鎖であること |
| 強制法の反鎖を順序論的な反鎖に取り替える（thm-antichain-distinction の逆） | 空集合も条件に含めた $\mathcal P(\{1,2\})$ の $\{\{1\},\{2\}\}$（$\emptyset$ が共通の強化） | 順序論的な反鎖が強制法の反鎖であること |
$S=\{1,2,3\}$ とする。$\mathbb P$ は有限なので、どの基礎モデル $M$ にも属する。一点集合全体 $\{\{1\},\{2\},\{3\}\}$ は稠密である（どの条件も一点集合を部分集合に含む）ので、ジェネリックフィルターは一点集合を一つ含み、フィルターの上方閉性と有向性から $G=\{p\in\mathbb P:s\in p\}$ の形になる。逆に $G=\{p:2\in p\}$ はフィルターであり、どの稠密集合 $D$ も $\{2\}$ 以下の条件、つまり $\{2\}$ 自身を含むので $D$ と交わる。したがって $G$ は $M$ 上ジェネリックである。
$A=\{\{1,2\},\{2,3\},\{1,3\}\}$ の三元は二つずつ包含関係で比較できないので、順序論的な反鎖である。さらに順序論的に極大である。$S$ 自身は三元すべてを含み、一点集合はどれも $A$ のある元に含まれるから、$A$ に加えられる元はない。しかし $\{1,2\}\cap\{2,3\}=\{2\}\ne\emptyset$ なので、この二元は両立しており、$A$ は強制法の反鎖ではない。実際 $G\cap A=\{\{1,2\},\{2,3\}\}$ は二元からなる。破るのは「反鎖の二元は非両立」という仮定であり、崩れるのは交点の一意性である。
上と同じ $S=\{1,2,3\}$、$G=\{p:2\in p\}$ をとる。$A=\{\{1\}\}$ は一元だけなので強制法の反鎖である。しかし $\{2\}$ は $\{1\}$ と交わらず、$A\cup\{\{2\}\}$ はより大きな反鎖だから $A$ は極大でない（thm-antichain-powerset の判定では $\bigcup A=\{1\}\ne S$）。$\{1\}$ は $2$ を含まないので $G\cap A=\emptyset$ である。破るのは極大性であり、崩れるのは交点が空でないことである。
$S=\{1,2\}$ とし、$G=\{S\}$ とおく。$G$ は上方閉で、有向性も自明に満たすのでフィルターである。$A=\{\{1\},\{2\}\}$ は二つずつ交わらず和集合が $S$ なので、thm-antichain-powerset により極大反鎖である。しかし $G\cap A=\emptyset$ である。$G$ は稠密集合 $D_A=\{\{1\},\{2\}\}$ と交わらないので、ジェネリックでない。破るのはジェネリック性であり、崩れるのは交点が空でないことである。
thm-antichain-maximal は「反鎖 $A$ について」極大性と前稠密性が同値であると述べる。反鎖であるという仮定を外すと、前稠密であっても極大反鎖とは限らない。どの強制概念 $\mathbb P$ でも $\mathbb P$ 自身は前稠密である（各 $p$ は $p$ 自身と両立する）。しかし $S=\{1,2\}$ の $\mathbb P$ では $\{1\}$ と $S$ が両立するので、$\mathbb P$ は反鎖ではない。
関連項目
- 前提: 半順序集合, 強制概念
- 接続: Dilworthの定理, 可算鎖条件, 強制法, ジェネリックフィルター
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
