📂集合論

有向集合

定義¹

$(A, \le)$を半順序集合とする。任意の$a, b \in A$に対して$a \le c$、$b \le c$を満たす$c \in A$が存在すれば、$(A, \le)$を有向集合^{directed set}という。

説明

• 全順序集合は有向集合である。

• 集合$X$に対して、べき集合$P(X)$上に集合の包含関係$\subset$を半順序として与えた$(P(X), \subset)$は有向集合である。

  任意の$A, B \in P(X)$に対して、$A, B \subset A\cup B$である。

定義において半順序集合である条件まで一緒に具体的に書き出すと次の通りである。$a, b, c \in A$について、

1. $\forall a,\ a \le a$ (反射性)
2. $a \le b \land b \le c \implies a \le c$ (推移性)
3. $a \le b \land b \le a \implies a = b$ (反対称性)
4. $\text{For some }a, b \in A,\ \exist\ d \text{ such that } a \le d \land b \le d$

$A$のどの元から始めても、結局は一つの終着点に到達できる集合である。例えば次の集合たちは有向集合をなす。

$$ \begin{align*} A &= \left\{ 1 \right\} \\ B &= \left\{ 1,2 \right\} \\ C &= \left\{ 1,3 \right\} \\ D &= \left\{ 1,2,3 \right\} \\ E &= \left\{ 4 \right\} \\ F &= \left\{ 5 \right\} \\ G &= \left\{ 4, 5 \right\} \\ H &= \left\{ 1, 2, 3, 4, 5 \right\} \\ I &= \left\{ 6 \right\} \\ J &= \left\{ 1, 2, 3, 4, 5, 6 \right\} \\ \end{align*} $$

図で見ると次の通りである。

共終

定義

$(A, \le)$を半順序集合とする。$B \subset A$とする。すべての$a \in A$に対して、$a \le b$を満たす$b \in B$が存在すれば、$B$が$A$において共終である^cofinalという。

定理

$B$が有向集合$A$において共終であれば、$B$は有向集合である。

証明

$A$が有向集合であるので、任意の$a, b \in B \subset A$に対して$a, b \le c$を満たす$c \in A$が存在する。ところが$A$と$B$が共終であるので、$c \le d$である$d \in B$が存在する。つまり、任意の$a, b \in B$に対して$a, b \le d$を満たす$d \in B$が存在するので、$B$は有向集合である。

■