📂Set Theory

Directed Set

Definition ¹

Let $(A, \le)$ be a partially ordered set. If for any $a, b \in A$ there exists $c \in A$ satisfying $a \le c$ and $b \le c$, then $(A, \le)$ is called a directed set .

Explanation

• A totally ordered set is a directed set.

• For the set $X$, the power set $P(X)$ with the subset relation $\subset$ as a partial order on $(P(X), \subset)$ is a directed set.

  For any $A, B \in P(X)$, it holds that $A, B \subset A\cup B$.

To specify up to the condition of being a partially ordered set in the definition, it can be detailed as follows. For $a, b, c \in A$:

1. $\forall a,\ a \le a$ (Reflexivity)
2. $a \le b \land b \le c \implies a \le c$ (Transitivity)
3. $a \le b \land b \le a \implies a = b$ (Antisymmetry)
4. $\text{For some }a, b \in A,\ \exist\ d \text{ such that } a \le d \land b \le d$

From any element in $A$, it is a set where it is possible to eventually reach a singular destination. For example, the following sets form a directed set.

$$\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*}$$

Depicted in a diagram, it looks as follows.

Cofinality

Definition

Let $(A, \le)$ be a partially ordered set. Let it be $B \subset A$. If for every $a \in A$, there exists $b \in B$ that satisfies $a \le b$, then $B$ is said to be cofinal in $A$.

Theorem

If $B$ is cofinal in the directed set $A$, then $B$ is a directed set.

Proof

Since $A$ is a directed set, for any $a, b \in B \subset A$, there exists a $c \in A$ satisfying $a, b \le c$. Since $A$ and $B$ are cofinal, there exists $d \in B$ such that $c \le d$. Therefore, for any $a, b \in B$, there exists $d \in B$ satisfying $a, b \le d$, making $B$ a directed set.

■