有向集合
概要
有向集合（directed set）とは、空でない集合 $D$ 上の反射律・推移律を満たす二項関係 $\le$（前順序）であって、任意の二元 $a,b\in D$ に対して $a\le c$ かつ $b\le c$ となる元 $c\in D$（共通の上界）が存在するもののことである。反対称律は要求しないので、一般には順序集合とは限らない。自然数全体が持つ「どんな二つの添字よりも先の添字がある」という性質だけを取り出した構造であり、自然数の通常の順序、集合の有限部分集合を包含で並べたもの、位相空間の一点の近傍全体を逆包含で並べたものが典型例である。位相空間論では点列を一般化するネットの添字集合として、圏論では直極限（余極限）の添字圏として現れ、点列だけでは記述できない一般の位相空間の収束や帰納的な構成を扱う基盤となる。
定義
集合 $D$ とその上の二項関係 $\le$ の組 $(D,\le)$ が有向集合（directed set）であるとは、次の条件を満たすことをいう。
- $D\neq\emptyset$。
- 反射律：任意の $a\in D$ に対して $a\le a$。
- 推移律：$a\le b$ かつ $b\le c$ ならば $a\le c$。
- 有向性（directedness）：任意の $a,b\in D$ に対して、ある $c\in D$ が存在して $a\le c$ かつ $b\le c$ が成り立つ。
条件 2・3 を満たす関係を $D$ 上の前順序（preorder）という。すなわち有向集合とは、前順序を持つ空でない集合であって、さらに有向性を満たすもののことである。順序集合の定義と異なり、反対称律（$a\le b$ かつ $b\le a$ ならば $a=b$）は要求しない。条件 4 の $c$ を $a,b$ の上界（upper bound）という。$a\le b$ を $b\ge a$ とも書く。
有向集合 $(D,\le)$ の部分集合 $M\subset D$ が共終（cofinal）であるとは、任意の $a\in D$ に対して、ある $m\in M$ が存在して $a\le m$ となることをいう。
直感
有向集合は、数列の添字集合 $\mathbb{N}$ が持つ「どんな二つの添字よりも先の添字が必ず存在する」という性質だけを取り出した構造である。元が一列に並んでいる必要はなく、比較できない二つの元があってもよいが、それらの「両方より先」へ合流して進める地点が必ずある。$a\le b$ を「$b$ は $a$ より先の時刻である」「$b$ は $a$ より精度の高い近似である」と読むと、有向性は「二つの近似があれば両方を改良する近似がある」ことを意味する。この性質だけがあれば、「十分先ではつねに」という極限の言い回しが可能になり、ネットの収束や直極限の構成に使える。
例と反例
自然数全体 $\mathbb{N}=\{0,1,2,\ldots\}$ に通常の大小関係 $\le$ を入れた $(\mathbb{N},\le)$ は有向集合である。任意の $a,b\in\mathbb{N}$ に対し $c:=\max(a,b)$ とすれば $a\le c$ かつ $b\le c$ が成り立つ。点列の添字集合はこの有向集合であり、有向集合はこの「先に進める」という性質だけを抜き出した一般化にあたる。
$a\in\mathbb{R}$ を固定し、$D:=\mathbb{R}\setminus\{a\}$ 上に
$$
x\le y\ :\Longleftrightarrow\ |x-a|\ge|y-a|
$$
と定める（$a$ に近いほど「先」とみなす）。反射律・推移律は $\ge$ のそれから従い、任意の $x,y\in D$ に対して $|x-a|$、$|y-a|$ の小さい方を与える元が共通の上界になるので、$(D,\le)$ は有向集合である。一方 $a+1\le a-1$ かつ $a-1\le a+1$ であるが $a+1\neq a-1$ なので反対称律は成り立たず、これは順序集合ではない有向集合の例である。関数 $f\colon D\to\mathbb{R}$ の $x\to a$ における極限 $\lim_{x\to a}f(x)=L$ は、この有向集合を添字集合とするネット $(f(x))_{x\in D}$ が $L$ に収束することにほかならない。
集合 $X$ の有限部分集合全体を $\mathcal{P}_{\mathrm{fin}}(X)$ とし、包含関係 $\subset$ で順序づけると $(\mathcal{P}_{\mathrm{fin}}(X),\subset)$ は有向集合である。$F_1,F_2\in\mathcal{P}_{\mathrm{fin}}(X)$ に対し $F_1\cup F_2$ は有限集合であり、$F_1\subset F_1\cup F_2$ かつ $F_2\subset F_1\cup F_2$ を満たす上界を与える。$X$ が二元以上を持てば異なる一元集合どうしは互いに包含し合わないので比較不能な組があり、これは全順序集合ではない。級数の無条件収束は、この有向集合上で部分和 $\sum_{n\in F}a_n$ を並べたネットの収束として定義される。
位相空間 $X$ の点 $x$ の近傍系 $\mathcal{N}(x)$（$x$ の近傍全体）を、通常の包含とは逆向きの関係
$$
U\le V\ :\Longleftrightarrow\ U\supset V
$$
で順序づけると、$(\mathcal{N}(x),\le)$ は有向集合である。二つの近傍 $U,V\in\mathcal{N}(x)$ の共通部分 $U\cap V$ もまた $x$ の近傍であり、$U\le U\cap V$ かつ $V\le U\cap V$ を満たす。集合が小さいほど点 $x$ に「近い」添字とみなす、という読み方である。この有向集合は、点列だけでは記述しきれない一般の位相空間における収束をネットで扱う際の土台になる（ネット）。
二元集合 $D=\{a,b\}$ に、$a\le a$ と $b\le b$ だけが成り立つ関係を入れる。これは反射律・推移律を満たす（満たす性質：前順序である）が、$a$ と $b$ の共通の上界となる $c\in D$ は存在しない（満たさない性質：有向性）。したがって $(D,\le)$ は有向集合ではなく、「前順序 ⇒ 有向集合」という含意は成り立たない。前順序であることは有向集合であるための必要条件にすぎない。同様に、正の整数全体 $\mathbb{Z}_{>0}$ を「$a$ が $b$ を割り切る」という関係 $a\mid b$ で順序づけたものは有向集合である（$a,b$ の上界として $ab$ がとれる）が、部分集合 $\{2,3\}$ に制限すると有向性が失われる。有向集合の部分集合は、誘導される前順序について有向集合とは限らない。
性質
$D$ を空でない集合、$\le$ を $D$ 上の前順序とする。次は同値である。
- $(D,\le)$ は有向集合である。
- $D$ の任意の空でない有限部分集合 $F$ に対して、ある $c\in D$ が存在して、すべての $x\in F$ について $x\le c$ が成り立つ。
(1 ⇒ 2) $|F|$ に関する帰納法（数学的帰納法）で示す。$F=\{x\}$ のときは反射律より $c:=x$ が求める上界である。$|F|=n+1\ (n\ge1)$ とし、$x\in F$ を一つ選んで $F':=F\setminus\{x\}$ とおくと $|F'|=n$ であり、帰納法の仮定より $F'$ の上界 $c'\in D$ がとれる。有向性より $c'$ と $x$ の共通の上界 $c\in D$ が存在する。$F'$ の各元 $y$ に対し $y\le c'$ かつ $c'\le c$ なので推移律より $y\le c$、また $x\le c$ でもあるから、$c$ は $F$ 全体の上界である。
(2 ⇒ 1) $D\neq\emptyset$ と反射律・推移律は仮定の通りである。任意の $a,b\in D$ に対し、空でない有限集合 $F:=\{a,b\}$ に条件 2 を適用して得られる $c$ が $a\le c$ かつ $b\le c$ を満たすので、有向性が成り立つ。$\square$
$(D,\le)$ を空でない全順序集合とする。このとき $(D,\le)$ は有向集合である。
順序集合は反射律・推移律を満たすので $\le$ は前順序である。任意の $a,b\in D$ をとると、全順序性より $a\le b$ または $b\le a$ が成り立つ。前者のとき $c:=b$ とおくと、反射律 $b\le b$ とあわせて $a\le c$ かつ $b\le c$。後者のとき $c:=a$ とおけば同様である。よって有向性が成り立つ。$\square$
$(D_1,\le_1)$、$(D_2,\le_2)$ を有向集合とする。直積集合 $D_1\times D_2$ 上に
$$
(a_1,a_2)\le(b_1,b_2)\ :\Longleftrightarrow\ a_1\le_1 b_1\ \text{かつ}\ a_2\le_2 b_2
$$
と定めると、$(D_1\times D_2,\le)$ は有向集合である。
$D_1,D_2\neq\emptyset$ より $D_1\times D_2\neq\emptyset$ である。反射律は、$\le_1$、$\le_2$ の反射律から $a_1\le_1 a_1$ かつ $a_2\le_2 a_2$、すなわち $(a_1,a_2)\le(a_1,a_2)$ となることによる。推移律は、$(a_1,a_2)\le(b_1,b_2)$ かつ $(b_1,b_2)\le(c_1,c_2)$ のとき、成分ごとの推移律から $a_1\le_1 c_1$ と $a_2\le_2 c_2$ が従い $(a_1,a_2)\le(c_1,c_2)$ となることによる。
有向性を示す。$(a_1,a_2),(b_1,b_2)\in D_1\times D_2$ を任意にとる。$D_1$ の有向性より $a_1,b_1$ の上界 $c_1\in D_1$ が、$D_2$ の有向性より $a_2,b_2$ の上界 $c_2\in D_2$ が存在する。このとき成分ごとの不等式から $(a_1,a_2)\le(c_1,c_2)$ かつ $(b_1,b_2)\le(c_1,c_2)$ が成り立つので、$(c_1,c_2)$ が求める共通の上界である。$\square$
$(D,\le)$ を有向集合、$M\subset D$ を共終部分集合とする。$M$ に $\le$ を制限した $(M,\le)$ は有向集合である。
$D\neq\emptyset$ なので $a\in D$ がとれ、共終性より $a\le m$ となる $m\in M$ が存在するから $M\neq\emptyset$ である。反射律・推移律は $D$ から $M$ に遺伝する。$m_1,m_2\in M$ に対し、$D$ の有向性より $m_1\le c$ かつ $m_2\le c$ となる $c\in D$ があり、共終性より $c\le m$ となる $m\in M$ がある。推移律より $m_1\le m$ かつ $m_2\le m$ なので、$m\in M$ が $M$ の中での共通の上界である。$\square$
補足：使われ方と流儀
位相空間論では、有向集合 $D$ を添字集合とする点の族 $(x_d)_{d\in D}$ をネット（Moore–Smith 列）と呼ぶ。点列は $D=\mathbb{N}$ の場合のネットである。第1可算公理を満たさない空間では可算な添字集合では「細かさ」が足りず、ex-directed-set-neighborhood のような大きな有向集合が必要になる。有向集合とネットは Moore と Smith により極限概念の一般理論として導入された（MS22、Kel75 第 2 章）。共終部分集合は、点列の部分列を一般化した部分ネット（部分ネット。ネットを参照）を定義する際の基礎となる（prop-directed-set-cofinal-directed により、共終部分集合に制限したネットは再びネットである）。
積分論では、区間の分割全体を細分の関係で有向集合として組織し、Riemann和の極限をこの有向集合上のネットの極限として述べ直せる。「分割を細かくする」操作は、どんな二つの分割にも共通の細分が存在するという有向性の具体例である。
順序論の例を補うと、束は任意の二元が上限を持つので有向集合であり、フィルター（フィルター）は逆包含で有向集合をなす（ex-directed-set-neighborhood の近傍系はその特別な場合である）。
圏論では、有向集合 $(D,\le)$ を、$a\le b$ のときかつそのときに限り $a$ から $b$ への射がちょうど一本存在する薄い圏とみなせる。有向性は「任意の二対象に対して両方から射が伸びる共通の対象が存在する」という条件にあたり、有向集合はフィルター付き圏（filtered category）の代表例である。有向集合を添字圏とする余極限は直極限（direct limit）と呼ばれ、局所化や代数的閉包など帰納的な構成に頻出する（Mac98 第 IX 章 §1）。
本記事では有向集合を空でないものと定めたが、反射律・推移律・有向性は $D=\emptyset$ に対しても全称命題が空虚に真となるため形式的には成り立つ。空集合を有向集合として許すかどうかは文献により分かれる。空の有向集合を添字集合とするネットは元を持たない退化した族になり、収束の議論で例外的な扱いが必要になるため、本記事では非空性を公理に含めた。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
