부분 순서

Partial order. 이항 관계의 특수한 형태로 반사관계(reflexivity), 비대칭관계(antisymmetry), 추이관계(transitivity)를 만족하는 이항 관계를 이른다. 즉 부분 순서 R \subseteq X \times X은 다음 관계를 만족한다:

• \forall a \in X.\, (a,a) \in R;
• \forall a \in X.\, \forall b \in X.\, \left( a \ne b \wedge (a,b) \in R \right) \rightarrow (b,a) \notin R;
• \forall a \in X.\, \forall b \in X.\, \forall c \in X.\, \left( (a,b) \in R \wedge (b,c) \in R \right) \rightarrow (a,c) \in R.

반대로 부분 순서 R이 존재하는 집합 X를 부분 순서 집합(partially ordered set, poset)이라 한다. 부분 순서는 많은 의미에서 비교연산의 일반화이지만 "비교 불가능한 원소"(즉, (a,b) \notin R \wedge (b,a) \notin R인 두 원소 a,\,b \in X)가 존재할 수 있다는 점에서 완전순서와는 차이가 있다.