[이산수학] 부분 순서 관계 (partially ordered relation)

부분 순서 관계

부분 순서 관계 (partially ordered relation): 집합 $A$에 대한 관계 $R$이 반사 관계, 반대칭 관계, 추이 관계인 경우. 또한 $R$이 $A$에 대한 부분 순서 관계이면 순서쌍 ($A, R$)을 부분 순서 집합(partially order set, Poset)이라고 함

 

전순서 관계

비교 가능 (comparable): 부분 순서 집합 ($A$, $\preceq$)에서 $A$의 원소 $a, b$가 $a \preceq b$ 또는 $b \preceq a$일 때의 $a, b$
전순서 집합 (totally ordered set): $A$의 모든 원소들이 비교 가능한 집합
전순서 관계 (totally ordered relation): 전순서 집합에서의 부분 순서 관계

 

곱 부분 순서 관계

곱 부분 순서 관계 (product partial ordered relation)
$(A, \preceq)$와 $(B, \preceq)$가 부분 순서 집합이면 $(A \times B, \preceq)$도 부분 순서 집합이고, 이를 곱 부분 순서 관계라고 함

 

사전식 순서

사전식 순서 (lexicographic order)
($A$, $\preceq$)와 ($B$, $\preceq$)를 부분 순서 집합이라고 할 때 곱 부분 순서 집합 $A \times B$ 위에 존재하는 부분 순서 관계. 사전에 쓰이는 알파벳 순의 정렬 방법

 

하세 도표

부분 순서 집합을 그림으로 나타날 때는 하세 도표를 이용합니다.

하세 도표 (Hasse diagram): 화살표는 표시하지 않고 모든 연결선을 트리와 같이 모두 아래 방향을 향하도록 그림. 순환은 표시하지 않고 집합 $A$의 원소 $x, y, z$에서 $x \lesssim y$이고 $y \lesssim z$를 만족하는 $y$가 존재하지 않을 경우에만 $x$에서 $z$로의 연결선을 그려줌