14. 관계와 부분 순서 (Relations and Partial Orders)

관계 $R$은 집합 $A$와 집합 $B$의 곱집합의 부분집합이다.

$$R\subseteq A\times B$$

곱집합은 집합 $A$와 $B$의 조합으로 다음과 같이 정의된다.

$$ \{a, b\}\times \{c, d\} = \{(a, c), (a, d), (b, c), (b, d) \}$$

관계는 이 곱집합의 부분집합인데, 예를들어 집합 $A$가 학생의 집합이고, $B$가 수강 과목의 집합일 때, 백지오가 이산수학을 수강하는 관계를 다음과 같이 나타낼 수 있다.

$$ (\text{백지오}, \text{Discrete Math}) \in R,_\text{(백지오)}R_\text{(Discrete Math)} $$

관계  $R$이 정의하는 것은 상황에 따라 달라지는데, 수학적 표기법으로 다음과 같이 나타낼 수 있다.

$$ A = \mathbb{Z}: xRy \iff x \equiv y \mod(5)$$

이때, $\iff$ 뒤에 있는 것이 관계 $R$의 정의가 된다. 예를들어, 위 $R$은 $(6, 1)$에 대해 성립하고, $(4, 5)$에 대해서는 성립하지 않는다.

관계의 그래프 표현

집합 $A$에 대한 관계 $R$은 유향 그래프 $G=(V, E)$로 표현될 수 있다. $V=A, E=R$을 나타낸다.
어렵게 생각할 것 없는게, 우리가 드라마 등에서 쉽게 접하는 관계도도 이 일종이다.

출처: TVN

여러가지 관계들

• 모든 $x\in A$에 대하여, $xRx$가 성립할 경우 반사^Reflexive라고 한다.
• 모든 $x, y \in A$에 대하여, $xRy \rightarrow yRx$일 경우 대칭^Symmetric이라고 한다.
• 모든 $x, y \in A$에 대하여, $xRy \wedge yRx \rightarrow x=y$일 경우 비대칭^{Anti-Symmetric}이라고 한다.
• 모든 $x, y, z \in A$에 대하여, $xRy \wedge yRz \rightarrow xRz$일 경우, 추이^Transitive라고 한다.

	반사	대칭	비대칭	추이	특이사항
$x\equiv y \mod(5)$	Y	Y	N	Y	동치 관계
$x | y$	Y	N	Y	Y
$x\leq y$	Y	N	Y	Y	부분 순서 관계

동치^Equivalence 관계

동치 관계에서는 반사, 대칭, 추이가 성립된다. 동치 클래스는 $[x]$와 같이 표현되며, $xRy$가 성립되는 모든 y를 의미한다.

예를들어, $R$이 $x\equiv y \mod (5)$일 때 $[7]$은 아래와 같다.

$$[7] = \{\cdots , -3, 2, 7, 12, \cdots \}\\
[7] = [-3] = [2] $$

부분 순서^{Partial Order} 관계

집합 $A$의 분할^partition $\{A_1, A_2, \cdots, A_n\}$은 $A_1 \cup A_2 \cup \cdots \cup A_n \subseteq A$이며, 다른 집합과 원소가 중복되지 않고, 공집합이 아닌 집합들을 말한다.

어떤 관계가 반사, 비대칭, 추이를 만족할 경우 약한 부분 순서^{weak partial order} 관계이고, 비반사, 비대칭, 추이를 만족할 경우 강한 부분 순서^{strong partial order} 관계이다.

비반사란, $x$가 $x$와의 관계를 갖는 것을 불허하는 조건이다.

부분 순서 관계는 $\preccurlyeq$ 기호로 나타내고, $(A, \preccurlyeq)$ 집합은 부분 순서 집합^poset이라고 한다.
부분 순서 집합 $(A, \preccurlyeq)$는 노드 집합 $A$와 간선 집합 $\preccurlyeq$를 갖는 유향 그래프이다.

하세 도형^{Hasse Diagram}

부분 순서 집합 $(A, \preccurlyeq)$의 하세 도형은 self-loop와 추이 연결 간선을 제외하고 노드 $A$와 간선 집합을 이용해 그린 도형이다.

부분 순서 집합에는 셀프 루프는 있으나, 이외에 방향 사이클은 존재하지 않는다. 이러한 부분 순서 집합에서 셀프 루프를 제외하면 방향 비순환 그래프 DAG가 된다.

$a\preccurlyeq b$ 혹은 $b\preccurlyeq a$인 경우, $a, b$가 비교 가능^comparable하다고 한다. 반대 경우에는 비교 불가^incomparable하다고 한다.

전순서^{Total Order} 관계

모든 원소 쌍이 비교 가능한 부분 순서 관계를 전순서 관계라고 한다.
부분 순서를 전순서로 변환하는 것을 위상 정렬^{Topological Sort}이라고 한다.

부분 순서 집합 $(A, \preccurlyeq)$를 위상 정렬한 결과는 전순서 집합 $(A, \preccurlyeq_T)$이다. $(\preccurlyeq \subseteq \preccurlyeq_T)$

모든 유한 부분 순서 집합은 위상 정렬이 가능하다.

$x\in A$에 대해, $y\preccurlyeq x$이고 $x$와 다른 $y$가 존재하면 minimal이라 하고, $x\preccurlyeq y$이면 maximal이라 한다.

증명: 모든 유한 부분 순서 집합은 위상 순서를 갖는다.

보조 증명: 모든 유한 부분 순서 집합은 Minimal 원소를 갖는다.

체인이 각기 다른 원소 $a_1 \preccurlyeq a_2 \preccurlyeq \cdots \preccurlyeq a_t$들의 시퀀스이고, $t$가 체인의 길이라 하자.

$a_1 \preccurlyeq \cdots \preccurlyeq a_n$이 최대 길이의 체인이라 할 때,

$\exists a \not \in \{a_1, \cdots, a_n\} \text{ and } a\preccurlyeq a_1$ 라면,

$a\preccurlyeq a_1 \preccurlyeq \cdots \preccurlyeq a_n$이 존재할 수 없으므로, (최대 길이보다 긴 체인이므로) 성립하지 않는다.

$\exists a \in \{a_1, \cdots, a_n\} \text{ and } a\preccurlyeq a_1$이면,

$a\preccurlyeq a_1 \preccurlyeq \cdots \preccurlyeq a \preccurlyeq, \preccurlyeq a_n$으로 사이클이 존재하므로, 성립하지 않는다.

보조 증명에 의해, $a_1$은 항상 minimal 원소가 된다.

이제 어떤 부분 순서 집합 $p$에서 minimal 원소를 $a_1$을 제거해도 $p$는 여전히 부분 순서 집합이므로, 부분 순서 집합 전체에 위상 순서가 존재함이 귀납적으로 증명된다.