📂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 a set $X$, the pair $(P(X), \subset)$, obtained by giving the power set $P(X)$ the set inclusion relation $\subset$ as a partial order, is a directed set.

  For any $A, B \in P(X)$, we have $A, B \subset A\cup B$.

Writing out the definition concretely, including the condition of being a partially ordered set, gives the following. 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$

It is a set in which, no matter which element of $A$ one starts from, one can eventually reach a single destination. For instance, 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 as a diagram, it looks as follows.

Cofinal

Definition

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

Theorem

If $B$ is cofinal in a 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 $c \in A$ satisfying $a, b \le c$. But since $A$ and $B$ are cofinal, there exists $d \in B$ with $c \le d$. That is, for any $a, b \in B$ there exists $d \in B$ satisfying $a, b \le d$, so $B$ is a directed set.

■