有向集合
数学における有向集合（ゆうこうしゅうごう、directed set）、有向前順序集合 (directed preordered set) あるいはフィルター付き集合 (filtered set) とは、空でない集合 A と反射的かつ推移的な二項関係（つまり前順序）≤ との組 (A, ≤) であって、さらに任意の二元が上界を持つ、すなわち A の任意の元 a, b に対して、A の元 c で a ≤ c かつ b ≤ c を満たすものが必ず存在するものをいう[1]。
有向集合は空でない全順序集合の一般化、すなわち任意の全順序集合は有向集合となるが、一方で必ずしも全ての半順序集合が有向集合となるわけではない。位相空間論において有向集合は列の概念を一般化する有向点族（ネット）の概念を定義するのに用いられ、それにより解析学で用いられる様々な極限の概念を統一的に扱うことが可能になる。有向集合から抽象代数学あるいはもっと一般の圏論における直極限の概念が生じる。
同値な定義
上記のものとは同値だが別な定義の仕方もある。すなわち、前順序集合 A の任意の有限集合が上界を持つとき、A は有向集合であるという。先の定義はこの定義を含意する。実際、空集合に対しては、A が空でないから A に存在する任意の元が空集合の上界になるし、空でない有限集合については、二元ごとの上界を求める操作を繰り返せば、その元の数に関する帰納法で上界の存在を示せる。
例
有向集合の例には以下のようなものが挙げられる。
- 自然数全体の成す集合 N に通常の大小関係による順序 ≤ を入れたものは有向集合である（さらに全順序集合でもある）。
- 自然数の対全体の成す集合 N × N に順序を<math>(n_0, n_1) \le (m_0, m_1) \iff n_0 \le m_0 \wedge n_1 \le m_1</math>で定めると有向集合にすることができる。
- 実数 x0 に対して、それ以外の実数全体の成す集合 R ∖ {x0} は<math>a\le b\iff |a - x_0| \ge |b - x_0|</math>とおくことにより有向集合となる。この状況は実数が「x0 へ向かう向き」を持つという。これは半順序でも全順序でもないような有向集合の例になっている。
- 半順序集合だが有向集合でないような（自明な）例として、集合 {a, b} に順序関係として a ≤ a および b ≤ b のみが成り立つものが挙げられる。もう少し自明でないような例としては、先に挙げた「x0 へ向き付けられた実数」の例を少し変更して、x0 に関して同じ側にある二元のみに順序関係を制限したものを考えればよい。
- T が位相空間で、x0 が T の元とすると、x0 の近傍全体の成す集合は U ≤ V ⇔ U ⊇ V とおくことにより有向集合となる。つまり、
- 任意の U に対して U は自分自身を含むから U ≤ U が成り立つ。
- 任意の U, V, W に対して、U が V を含み V が W を含むならば U は W を含むから、U ≤ V かつ V ≤ W ならば U ≤ W が成り立つ。
- 任意の U, V に対して、U も V も U ∩ V を含むから、U ≤ U ∩ V かつ V ≤ U ∩ V を満たす集合 U ∩ V が取れる。
- 半順序集合 P において、各元の任意の下方閉包、すなわち P の固定された元 x に対して {a ∈ P | a ≤ x} の形に書ける集合は全て、有向集合である。
半束との対比
有向集合は（結び）半束よりも一般の概念である。すなわち、任意の結び半束は、二元の結びをそれらの上限とみることにより有向集合となる。しかし逆は成り立たない。例えば {1000, 0001, 1101, 1011, 1111} にビットごとの順序（例えば 1000 ≤ 1011 は成り立つが 1000 ≤ 0001 は成り立たない）を入れた順序集合において、二元集合 {1000, 0001} は三つの上界を持つが、その中で最小のものは存在しない。
有向部分集合
有向集合における順序関係は、反対称であることを要求されないから、従って有向集合は必ずしも半順序ではない。しかし「有向集合」という用語を半順序集合の文脈で用いることも多く、その場合に半順序集合 (P, ≤) の部分集合 A が有向部分集合 (directed subset) であるというのを、P における順序によって A 自身が有向集合となることと定める。言い換えれば、有向部分集合とは、空でない部分集合で、任意の二元が上界を持つものをいう（ここで、A の元についての順序関係は P からくるものであるから、反射性と推移性を明示的に要求せずとも、実際にはそれらの性質が成り立っている）。
半順序集合の有向部分集合は下方閉であることは要求しない。半順序集合の部分集合が有向部分集合であるための必要十分条件は、その下方閉包がイデアルとなることである。有向集合の定義は「上方に有向な」集合（任意の二元が上界を持つ）に対するものになっているけれども、同様に任意の二元が下界を持つという「下方有向集合」を定義することもできる。半順序集合の部分集合が下方有向集合となるための必要十分条件は、その上方閉包がフィルターとなることである。
部分有向集合は、有向完備半順序を研究する領域理論において用いられる[2]。有向完備半順序とは、その任意の上方有向集合が上限を持つような半順序集合である。この文脈では、部分有向集合はやはり収斂列の一般化を与える。
関連項目
注記
参考文献
- テンプレート:Cite book日本語訳: テンプレート:Cite book
- Gierz, Hofmann, Keimel, et al. (2003), Continuous Lattices and Domains, Cambridge University Press. ISBN 0521803381.
