📂집합론

유향집합

정의¹

$(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$는 유향집합이다.

■