📂집합론

부분순서 집합

정의 ¹

1. 집합 $A$ 에서의 관계 $\le$ 가 반사적, 추이적, 반대칭적이면 $\le$를 부분순서^{partial order}이라 하고 $(A,\le)$ 를 부분순서 집합^{partial ordered set} 이라고 부른다. 다시 말해, $A$ 가 부분순서 집합이라는 것은 모든 원소 $a,b,c \in A$ 에 대해 다음을 만족하는 것이다: $$\begin{align*} a \le a & \text{ (reflexivity) } \\ a \le b \land b \le c \implies a \le c & \text{ (transitivity) } \\ a \le b \land b \le a \implies a = b & \text{ (antisymmetry) } \end{align*}$$
2. 부분순서집합 $(A, \le)$ 가 주어져 있을 때 모든 $a,b \in A$ 에 대해 $a \le b$ 혹은 $b \le a$ 면 $\le$ 를 $A$ 에서의 전순서^{total order}, $(A,\le)$ 를 전순서 집합^{totally ordered set}이라 한다.

설명

부분순서(집합)은 반순서(집합)으로도 번역된다. 부분순서의 표기로는 $\preceq$^\preceq도 사용된다.

정의에서 $\le$ 는 단지 기호일 뿐, 반드시 크기를 비교하는 부등호일 필요가 없다. 물론 부등호나 포함관계는 부분순서가 될 수 있지만, 그 역이 성립하는 것은 아니다. 가령 알파벳에서 a 다음은 b고, 단지 기호를 쓰면 $a \le b$ 와 같이 나타내도 상관 없다. 실제로 컴퓨터 공학에서 a는 아스키 코드 $0000001_{(2)}$ 에 대응되고 b는 아스키 코드 $00000010_{(2)}$ 에 대응되고, 이러한 2진수의 대소관계로 문자간의 순서도 나타낼 수 있다.

사실 전순서 집합은 의무교육을 받은 사람이라면 익숙하게 떠올릴 수 있을 것이고 오히려 그렇지 않은 집합이 바로 떠오르지 않을 수 있다. 전순서 집합의 좋은 예로는 자연수의 집합 $\mathbb{N}$ 이 그러하며, 이는 정수의 집합 $\mathbb{Z}$, 유리수의 집합 $\mathbb{Q}$, 실수의 집합 $\mathbb{R}$ 역시 다를 것이 없다. 그러나 한 걸음 더 나아가서 복소수 $\mathbb{C}$ 가 되면 자연스러운 순서는 딱히 정의되어 있지 않다.

전순서를 정의하기 전에 부분순서를 정의하는 것은 그 편이 수학적으로 훨씬 자연스럽기 때문이다. 다음과 같은 다섯 개의 집합들 $$\begin{align*} A &= \left\{ 1 \right\} \\ B &= \left\{ 1,2 \right\} \\ C &= \left\{ 1,3 \right\} \\ D &= \left\{ 1,2,3 \right\}\\ E &= \left\{ 1,2,4 \right\} \end{align*}$$ 에 대해 집합의 포함관계를 생각해보면 다음이 성립하는 것을 확인할 수 있다. $$A \subset B \subset D \\ A \subset B \subset E \\ A \subset C \subset D$$ 그림으로 보면 이 복잡한 모양을 한 눈에 확인할 수 있다.

혹은 다른 예시로 다음과 같은 여섯 개의 집합들에 대해서 보면, $$\begin{align*} A^{\prime} &= \left\{ 1 \right\} \\ B^{\prime} &= \left\{ 1,2 \right\} \\ C^{\prime} &= \left\{ 1,3 \right\} \\ D^{\prime} &= \left\{ 1,2,4 \right\}\\ E^{\prime} &= \left\{ 5 \right\}\\ F^{\prime} &= \left\{ 2, 5 \right\} \end{align*}$$ $$A^{\prime} \subset B^{\prime} \subset D^{\prime} \\ A^{\prime} \subset C^{\prime} \\ E^{\prime} \subset F^{\prime}$$ 그림으로는 다음과 같다.

사실 이러한 비선형적 형태는 우리 일상에서도 자주 찾아볼 수 있을만큼 자연스러운 관계를 나타내고 있다. 새삼 다시 생각해보면 오히려 모조리 선형적으로 물리고 물리는 관계가 이상할지도 모른다. 심지어 자연수의 집합 $\mathbb{N}$ 조차 폰 노이만의 구성법에 따르면 ‘직관적’이라는 표현과는 다소 거리가 있다. 그래서 전순서는 단지 부분순서가 집합 전체에서 선형적으로 정의되는 관계로 말하는 게 더 편할 수 있는 것이다.