부분 순서 집합

세 원소 집합의 멱집합 \mathcal P(\\{x,y,z\\}) 위의, 포함 관계에 의한 부분 순서를 그린 [[하세 도형]] 순서론에서 **부분 순서 집합**(部分順序集合, partially ordered set, poset) 또는 **반순서**(半順序)는 먼저와 나중, 크고 작음, 멀고 가까움, 좋고 나쁨, 선호 등의 순서적 개념을 추상화한 이항 관계를 갖춘 집합이다. 사람들 사이의 조상-후손 관계를 예로 들 수 있다. 부분 순서 집합은 비교 불가능한 두 원소를 가질 수 있다. 예를 들어, 어떤 두 사람은 둘 다 상대방의 조상이 아닐 수 있다. 또한, 부분 순서는 추이적 관계이어야 하며 (조상의 조상은 조상), 반대칭적이어야 한다 (동시에 조상이자 후손일 수 없음). 부분 순서는 반사적인 것(3\le 3, 3\le10에서의 \le)과 비반사적인 것(5\nless5, 5y는 y를 뜻한다.
## 범주론적 정의
범주론적으로, 원순서 집합의 개념은 작은 얇은 범주의 개념과 동치이다. 구체적으로, 임의의 원순서 집합 (X,\le)은 다음과 같은 범주로 여길 수 있다. * (X,\le)의 대상은 X의 원소이다. * (X,\le)의 사상은 다음과 같다. 만약 x\le y라면, 유일한 사상 x\to y이 존재한다. 만약 x\nleq y라면, 사상 x\to y은 존재하지 않는다. 이 경우, **부분 순서 집합**은 다음 조건을 추가로 만족시키는 작은 얇은 범주이다. * 뼈대 범주이다. 즉, 서로 다른 두 대상은 동형이 아니다.
## 위상수학적 정의
위상수학에서, 원순서 집합의 개념은 알렉산드로프 공간의 개념과 동치이다. 이 경우, 원순서 집합 (X,\le)에 대하여, 다음 두 조건이 서로 동치이다. * (X,\le)는 부분 순서 집합이다. * (X,\le)에 대응하는 알렉산드로프 공간은 콜모고로프 공간이다. 따라서, 부분 순서 집합의 개념은 콜모고로프 공간인 알렉산드로프 공간의 개념과 동치이다. 사실, 서로 수반 함자를 이루는 두 함자 \operatorname{Proset}\leftrightarrows\operatorname{Top}를 적절히 제한하면, 부분 순서 집합의 범주 \operatorname{Poset}와 콜모고로프 공간의 범주 \operatorname{Kolm} 사이의 한 쌍의 수반 함자 :\operatorname{Poset}\leftrightarrows\operatorname{Kolm} 를 얻는다. 또한, \operatorname{Kolm} 대신 콜모고로프 알렉산드로프 공간의 범주를 사용하면, 두 범주 사이의 동형을 얻는다.
## 순서 보존 함수
순서 반사 함수가 아닌 순서 보존 함수의 예 두 집합 사이의 순서 동형. 왼쪽은 120의 약수들의 집합 위의, 약수 관계에 의한 부분 순서. 오른쪽은 120의 소수 거듭제곱 꼴 약수들의 집합 위의, 부분 집합 관계에 의한 부분 순서. 두 부분 순서 집합 (X,\le), (Y,\le) 사이의 함수 f\colon X\to Y가 다음 조건을 만족시키면, **순서 보존 함수**(order-preserving map)라고 한다. * 임의의 x,y\in X에 대하여, x\le y라면 f(x)\le f(y) 또한, f가 다음 조건을 만족시키면, **순서 반사 함수**(order-reflecting map)라고 한다. * 임의의 x,y\in X에 대하여, f(x)\le f(y)라면 x\le y 또한, 순서 보존 순서 반사 함수를 **순서 매입**(order-embedding)라고 하며, 전사 순서 매입를 **순서 동형**(order isomorphism)라고 한다. 예를 들어, 자연수 집합(약수 관계에 의한 부분 순서)에서 그 멱집합(포함 관계에 의한 부분 순서)으로 가는 함수 f:\N\to\mathcal{P}(\N)가 임의의 자연수를 소인수들의 집합으로 대응시킨다면, 이는 순서 보존 사상이다. 임의의 자연수는 그의 약수의 소인수를 소인수로 가지기에 그러하다. 하지만 이는 단사가 아니며 (f(6)=f(12)=\\{2,3\\}) 순서 반사도 아니다(\\{2,3\\}\subseteq\\{2,3\\}, 하지만 12\not\le 6). 자연수를 소수 거듭제곱 형식의 약수들의 집합으로 대응시키는 함수 g:\N\to\mathcal{P}(\N)는 순서 보존, 순서 반사이며 따라서 순서 매입이다, 전단사가 아니므로 (\\{4\\}의 역상이 존재하지 않는다) 순서 동형은 아니다. 그러나 공역을 g(\N)으로 제한하면 순서 동형이 된다. 집합과 멱집합 사이의 순서 동형은 더 넓은 의미의 부분 순서인 분배 격자로 일반화할 수 있다(버코프의 표현 정리 참조).
## 극값
*y*의 상계이다. 약수 관계에 의한 순서를 부여한 음이 아닌 정수 집합. 최대 원소는 0, 최소 원소는 1. 부분 순서 집합 P에는 최대 · 최소, 극대 · 극소, 상계 · 하계의 개념이 존재한다. ; 최대 원소와 최소 원소 : 모든 a\in P에 대해 g\ge a인 g\in P를 P의 최대 원소라고 한다. 모든 a\in P에 대해 l\le a인 l\in P를 P의 최소 원소라고 한다. 부분 순서 집합은 최대 · 최소 원소를 많아야 하나씩 가질 수 있다. ; 극대 원소와 극소 원소 : a>M인 a\in P가 존재하지 않는 M\in P를 P의 극대 원소라고 한다. a인 a\in P가 존재하지 않는 m\in P를 P의 극소 원소라고 한다. 만약 최대 원소가 존재한다면 그가 바로 유일한 극대 원소이다. 그렇지 않은 경우 극대 원소는 여러 개 있을 수 있다. 극소 원소와 최소 원소 사이에도 비슷한 관계가 있다. ; 상계와 하계 : P의 부분집합 A에 대하여, A의 상계 x는 a\le x를 모든 a\in A에 대해 성립하게 하는 P의 원소이다. A의 하계 x는 a\ge x를 모든 a\in A에 대해 성립하게 하는 P의 원소이다. 상계와 하계 모두 A에 속하지 않을 수 있다. A의 최대 원소와 최소 원소가 존재한다면, 그들은 각각 A의 하나의 상계, 하계이다. 예를 들어 양의 정수 집합과 약수 관계로 이루어진 부분 순서 집합 (\Z^+,|)를 생각하면, 1은 그의 최소 원소이다. 최대 원소와 극대 원소는 존재치 않는다. 여기에 0을 추가하면 0이 최대 원소가 된다. 1보다 큰 정수만을 생각하면, 최소 원소가 존재하지 않게 되고, 모든 소수가 극소 원소가 된다. 이러한 집합에서, 부분 집합 \\{2,3,5,10\\}은 상계 60을 가지며 하계는 존재하지 않는다. 2의 거듭제곱들의 집합은 2를 하계로 가지며 상계가 존재하지 않는다.
# 연산
ℕ×ℕ 위의 사전식 순서 ℕ×ℕ 위의 직접곱 순서 ℕ×ℕ 위의, 절대 순서 직접곱의 반사 폐포. (3, 3)보다 큰 원소들은 (3, 3)과 빨간 선으로 이어져있고, (3, 3)보다 작은 원소들은 (3, 3)과 초록 선으로 이어져 있다.
## 반대 순서 집합
부분 순서 집합 (X,\le)이 주어졌을 때, X 위에 다음과 같은 부분 순서 \ge를 정의할 수 있다. :x\ge y\iff y\le x\qquad(x,y\in X) 이 경우, (X,\ge)를 (X,\le)의 **반대 순서 집합**이라고 한다. 부분 순서 \le · 절대 부분 순서 가운데 임의의 하나가 결정되면, 나머지 셋 역시 결정된다.
## 선형합
부분 순서 집합의 전순서 집합 (\\{(X_i,\le_i)\\}_{i\in I},\le)이 주어졌을 때, 분리 합집합 \textstyle\sqcup_{i\in I}X_i 위에 다음과 같은 부분 순서 \le를 정의할 수 있다. :x\le y\iff i 이를 **선형합**(linear sum)이라고 한다.
## 직접곱
부분 순서 집합의 족 \\{(X_i,\le_i)\\}_{i\in I}이 주어졌을 때, 곱집합 \textstyle\prod_{i\in I}X_i 위에 다음과 같은 부분 순서 \le를 정의할 수 있다. :(x_i)_{i\in I}\le(y_i)_{i\in I}\iff\forall i\in I\colon x_i\le y_i\qquad(x_i,y_i\in X_i) 이 경우, \textstyle(\prod_{i\in I}X_i,\le)를 \\{(X_i,\le_i)\\}_{i\in I}의 **직접곱**(direct product)이라고 한다.
## 절대 부분 순서의 직접곱의 반사 폐포
마찬가지로, 절대 부분 순서 집합의 직접곱을 정의할 수 있으며, 이에 대응하는, 곱집합 위의 부분 순서는 다음과 같다. :(x_i)_{i\in I}\le(y_i)_{i\in I}\iff(x_i)_{i\in I}=(y_i)_{i\in I}\lor\forall i\in I\colon x_i
## 사전식 순서
부분 순서 집합의 정렬 집합 (\\{(X_i,\le_i)\\}_{i\in I},\le)이 주어졌을 때, 곱집합 \textstyle\prod_{i\in I}X_i 위에 다음과 같은 이항 관계 \le를 정의할 수 있다. :(x_i)_{i\in I}\le(y_i)_{i\in I}\iff(x_i)_{i\in I}=(y_i)_{i\in I}\lor x_{\min\\{i\colon x_i\ne y_i\\ 이를 **사전식 순서**라고 한다.
# 성질

## 부분 순서의 수
크기 n의 집합 위의 부분 순서의 수는 다음과 같다. (n=0,1,2,\dots) :1, 1, 3, 19, 219, 4231, 130023, ... A1035 크기 n의 집합 위의 부분 순서의 동형류의 수는 다음과 같다. (n=0,1,2,\dots) :1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284, ... A112
# 예
모든 전순서는 부분 순서이다. 예를 들어, 자연수 집합 \mathbb N이나 정수 집합 \mathbb Z, 유리수 집합 \mathbb Q, 실수 집합 \mathbb R 위의 표준적인 순서는 전순서이므로 부분 순서이다. 집합 S의 멱집합 \mathcal P(S) 위의 포함 관계 \subseteq는 부분 순서이며, 만약 S가 두 개 이상의 원소를 갖는다면 이는 전순서가 아니다. 또한, 이를 \mathcal P(S)의 부분 집합에 국한시켜도 역시 부분 순서를 이룬다. 예를 들어, * 군의 부분군들의 집합 * 벡터 공간의 부분 벡터 공간들의 집합 * 환의 아이디얼들의 집합 * 그래프의 부합들의 집합 등등은 특정한 부분 집합들의 집합이므로 포함 관계를 통해 부분 순서를 갖는다. 부분수열에 의한 관계는 특정한 집합 (예를 들어 어떤 수열의 부분수열들의 집합, 집합 X의 원소를 항으로 하는 수열들의 집합) 위의 부분 순서이다. 이는 일반적으로 전순서가 아니다. 이와 비슷하게 문자열들의 집합에서 부속문자열에 의한 관계는 부분 순서이다. 양의 정수의 집합 \mathbb Z^+ 위의 약수 관계 \mid(a\mid b는 a가 b의 약수라는 의미)는 부분 순서이며, 이는 전순서가 아니다. 비순환 유향그래프의 꼭짓점들의 집합은 도달가능성에 의한 부분 순서를 가진다. 부분 순서 집합 S의 수열 공간 S^{\N}에 정의된 성분별 순서는 부분 순서이다. :(a_n)_{n\in\N}\le(b_n)_{n\in\N}\ \iff\ \forall n\in\N:a_n\le b_n
# 응용
부분 순서 \le\subseteq X^2에 대하여, 전순서 \le\subseteq\le^*\subseteq X^2를 \le의 선형 확장이라고 한다. 예를 들어, 부분 순서 집합의 직접곱의 한 가지 선형 확장은 사전식 순서이다. 선택 공리 아래, 임의의 부분 순서는 선형 확장을 갖는다. 컴퓨터 과학에서, 위상 정렬은 부분 순서의 선형 확장을 구하는 알고리즘이다.