세원소 집합 x, y, z}의 멱집합 위의 부분 집합 관계에 의한 부분 순서를 그린 하세 도형. 같은 높이에 있거나 (x}와 y}) 화살표 방향대로 나아가 도달하지 못하면 (x}와 y, z}) 순서가 정해지지 않은 것이다.
순서론에서 부분 순서(部分順序, 영어: partial order) 또는 반순서(半順序)는 순서·나열 등의 개념을 추상화한 이항 관계이다. 부분 순서를 갖춘 집합을 부분 순서 집합(部分順序集合, 영어: partially ordered set, poset)이라고 한다. 이는 전순서 집합과 달리 모든 원소가 비교 가능할 필요는 없으며, 원순서 집합과 달리 순서가 같은 여러 원소는 존재하지 않아야 한다. 유한 부분 순서 집합은 하세 도형을 통해 나타낼 수 있다.[1] 예를 들어, 가계도에서의 관계는 부분 순서이다. 어떤 두 사람은 조상과 후손의 관계이나, 어떤 두 사람은 서로가 서로의 후손이 아니며, 어떤 이도 다른 이의 조상이자 후손일 수는 없다.
순서 반사 함수가 아닌 순서 보존 함수의 예두 집합 사이의 순서 동형. 왼쪽은 120의 약수들의 집합 위의, 약수 관계에 의한 부분 순서. 오른쪽은 120의 소수 거듭제곱 꼴 약수들의 집합 위의, 부분 집합 관계에 의한 부분 순서.
두 부분 순서 집합 , 사이의 함수 가 다음 조건을 만족시키면, 순서 보존 함수(영어: order-preserving map)라고 한다.
임의의 에 대하여, 라면
또한, 가 다음 조건을 만족시키면, 순서 반사 함수(영어: order-reflecting map)라고 한다.
임의의 에 대하여, 라면
또한, 순서 보존 순서 반사 함수를 순서 매입(영어: order-embedding)라고 하며, 전사 순서 매입를 순서 동형(영어: order isomorphism)라고 한다.
예를 들어, 자연수 집합(약수 관계에 의한 부분 순서)에서 그 멱집합(포함 관계에 의한 부분 순서)으로 가는 함수 가 임의의 자연수를 소인수들의 집합으로 대응시킨다면, 이는 순서 보존 사상이다. 임의의 자연수는 그의 약수의 소인수를 소인수로 가지기에 그러하다. 하지만 이는 단사가 아니며 () 순서 반사도 아니다(, 하지만 ). 자연수를 소수 거듭제곱 형식의 약수들의 집합으로 대응시키는 함수 는 순서 보존, 순서 반사이며 따라서 순서 매입이다, 전단사가 아니므로 (의 역상이 존재하지 않는다) 순서 동형은 아니다. 그러나 공역을 으로 제한하면 순서 동형이 된다. 집합과 멱집합 사이의 순서 동형은 더 넓은 의미의 부분 순서인 분배 격자로 일반화할 수 있다(버코프의 표현 정리 참조).
x, y, z}의 멱집합에서 공집합과 자기 자신을 제외한 집합. 위의 세 원소는 극대 원소이며, 아래의 세 원소는 극소 원소이다. 최대 원소와 최소 원소는 존재하지 않는다. x, y}는 부분 집합 x}, y}}의 상계이다.약수 관계에 의한 순서를 부여한 음이 아닌 정수 집합. 최대 원소는 0, 최소 원소는 1.
인 가 존재하지 않는 를 의 극대 원소라고 한다. 인 가 존재하지 않는 를 의 극소 원소라고 한다. 만약 최대 원소가 존재한다면 그가 바로 유일한 극대 원소이다. 그렇지 않은 경우 극대 원소는 여러 개 있을 수 있다. 극소 원소와 최소 원소 사이에도 비슷한 관계가 있다.
의 부분집합 에 대하여, 의 상계 는 를 모든 에 대해 성립하게 하는 의 원소이다. 의 하계 는 를 모든 에 대해 성립하게 하는 의 원소이다. 상계와 하계 모두 에 속하지 않을 수 있다. 의 최대 원소와 최소 원소가 존재한다면, 그들은 각각 의 하나의 상계, 하계이다.
예를 들어 양의 정수 집합과 약수 관계로 이루어진 부분 순서 집합 를 생각하면, 1은 그의 최소 원소이다. 최대 원소와 극대 원소는 존재치 않는다. 여기에 0을 추가하면 0이 최대 원소가 된다. 1보다 큰 정수만을 생각하면, 최소 원소가 존재하지 않게 되고, 모든 소수가 극소 원소가 된다. 이러한 집합에서, 부분 집합 은 상계 60을 가지며 하계는 존재하지 않는다. 2의 거듭제곱들의 집합은 2를 하계로 가지며 상계가 존재하지 않는다.
부분 순서 에 대하여, 전순서를 의 선형 확장이라고 한다. 예를 들어, 부분 순서 집합의 직접곱의 한 가지 선형 확장은 사전식 순서이다. 선택 공리 아래, 임의의 부분 순서는 선형 확장을 갖는다. 컴퓨터 과학에서, 위상 정렬은 부분 순서의 선형 확장을 구하는 알고리즘이다.
↑Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). 《Transitive Closures of Binary Relations I》(PDF) (영어). Prague: School of Mathematics - Physics Charles University. 1쪽. 2013년 11월 2일에 원본 문서(PDF)에서 보존된 문서. 2013년 8월 20일에 확인함. Lemma 1.1 (iv).
Deshpande, Jayant V. (1968). “On Continuity of a Partial Order”. 《Proceedings of the American Mathematical Society》 (영어) 19 (2): 383–386. doi:10.1090/S0002-9939-1968-0236071-7.
Schröder, Bernd S. W. (2003). 《Ordered Sets: An Introduction》 (영어). Birkhäuser, Boston.
Stanley, Richard P. 《Enumerative Combinatorics 1》. Cambridge Studies in Advanced Mathematics (영어) 49. Cambridge University Press. ISBN0-521-66351-2.