📂集合論

方向性集合

定義 ¹

$(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$は有向集合である。

■