부분 순서

partial order

순서 관계의 일종으로, 임의의 두 원소 사이의 대소 관계가 항상 정의되는 것이 아닌 일부만 정의된 이항 관계를 의미한다. 전순서(total order) 집합을 배경으로 하는 해석학 등과 다르게 부분 순서는 집합론, 이산수학, 범주론에서 주로 등장한다.

집합 $X$ 위에 정의된 이항 관계 $\preceq$에 대해

위 조건을 모두 만족한다면, $\preceq$를 부분 순서(partial order) 또는 부분 순서 관계(partial order relation)라고 하고, $(X,\preceq)$를 부분 순서 집합(partially ordered set), 또는 줄여서 poset이라고 한다.[1] 여느 관계와 마찬가지로, 가리키는 대상이 명확하다면 순서쌍 대신 $X$를 부분 순서 집합이라 부르기도 한다.

부분 순서 집합 $X$의 부분집합 $C\subset X$가 $X$에서 정의된 순서 관계 $\prec$ 위에서 전순서 집합을 이룰 때, $C$를 $X$의 사슬(chain)이라 한다.

선택공리와 동치인 명제 중 하우스도르프 극대 원리가 있는데, 이걸 사용하면 모든 부분 순서 집합이 극대 사슬을 가진다는 사실을 알 수 있다. 정확히는 부분 순서 집합의 사슬들을 모은 집합에 부분집합 관계를 순서로 정의했을 때, 극대(maximal) 원소가 존재한다는 뜻이다. 선택공리에서 초른의 보조정리와 극대 원리를 유도하고, 여기에서 정렬 정리(well-ordering thm)를 유도하면서 되돌아오는 게 일반적인 집합론 수업의 하이라이트 부분 중 하나.

두 집합의 곱집합(cartesian product)에서 파생되는 부분 순서 관계. $(A,\preceq_A)$와 $(B,\preceq_B)$ 모두 부분 순서 집합이라고 가정하자. 이 둘의 곱집합 $A\times B$ 위의 이항관계 $\preceq_{A\times B}$를

와 같이 정의할 때, $(A\times B,\preceq_{A\times B})$는 부분 순서 집합을 이룬다. 증명은 다음과 같다. 우선 $\forall a\preceq a,\forall b\preceq b$이므로 $(a,b)\preceq(a,b)$는 자명하다. 또한 $(a,b)\preceq(a',b')$라는 것은 정의에 따라 $a\preceq a'\land b\preceq b'$이며 반대의 경우도 마찬가지로 $(a',b')\preceq(a,b)$라면 $a'\preceq a\land b'\preceq b$이다. 이 둘이 모두 참일 경우 $(a\preceq a'\land a'\preceq a)\land(b\preceq b'\land b'\preceq b)$ 따라서 $a=a'\land b=b'$이며, 이는 $(a,b)=(b,b')$과 같이 나타낼 수 있으므로 반대칭성 또한 성립한다. 마찬가지로 $(a,b)\preceq(a',b')\land(a',b')\preceq(a'',b'')$일 경우 $a\preceq a'\land a'\preceq a''\to a\preceq a''$이며, 이는 $b$도 마찬가지다. 따라서 $(a,b)\preceq(a'',b'')$이므로 추이성 역시 만족한다.

유한 부분 순서를 표현할 때 가장 널리 쓰이는 도표로 하세 다이어그램이 존재한다. 개별 원소의 반사는 자명하므로 모두 생략하고[2], 어떤 원소가 다른 원소보다 클 경우, 둘을 선분으로 연결하고 큰 원소를 위에 놓는다. 또한 복잡하지 않게끔 추이적으로 유도되는 선분은 생략한다.

이산수학에서는 그래프나 트리 형태에 조건을 일부 수정해 표현하기도 하며, 범주론에서는 부분 순서 자체가 특수한 범주로 표현되는 것도 가능하다. 후자의 경우, monotone morphism을 가지는 $\bf{Poset}$이 아니라 하나의 poset 자체를 범주로 보는 경우를 말한다.

가장 유명한 예시 중 하나로, 집합의 부분집합 관계 $\subset$은 부분 순서를 이룬다. 증명은 다음과 같다. 우선 모든 집합은 자기 자신의 부분집합이므로 반사성을 만족하며, 임의의 두 집합이 서로의 부분집합이라면 ZFC 공리계의 외연 공리(axiom of extensionality)에 의해 상등이다. $A$가 $B$의 부분집합일 것의 필요충분조건이 $\forall a\in A$가 $a\in B$일 것이므로, $A\subset B$이고 $B\subset C$라면 $\forall a\in A$는 $a\in C$이다. 따라서 추이성 역시 성립한다.

또 다른 예시로 약수 관계가 있다. 기본적으로 모든 수는 자기 자신으로 나누어 떨어지며, $a|b\land b|a$라는 것은 $a$의 소인수가 모두 $b$에 속하며, 동시에 $b$의 소인수가 모두 $a$에 속한다는 뜻이므로 $a=b$이다. 비슷하게 $a|b|c$라면 $a$의 소인수가 $c$에도 속한다는 뜻이므로 $a|c$가 성립하며, 따라서 추이성 역시 만족한다.