세원소 집합 x , y , z } 의 멱집합 위의 부분 집합 관계에 의한 부분 순서를 그린 하세 도형 . 같은 높이에 있거나 (x } 와 y } ) 화살표 방향대로 나아가 도달하지 못하면 (x } 와 y , z } ) 순서가 정해지지 않은 것이다.
순서론 에서 부분 순서 (部分順序, 영어 : partial order ) 또는 반순서 (半順序)는 순서·나열 등의 개념을 추상화한 이항 관계 이다. 부분 순서를 갖춘 집합 을 부분 순서 집합 (部分順序集合, 영어 : partially ordered set, poset )이라고 한다. 이는 전순서 집합 과 달리 모든 원소가 비교 가능할 필요는 없으며, 원순서 집합 과 달리 순서가 같은 여러 원소는 존재하지 않아야 한다. 유한 부분 순서 집합은 하세 도형 을 통해 나타낼 수 있다.[1] 예를 들어, 가계도 에서의 관계는 부분 순서이다. 어떤 두 사람은 조상과 후손의 관계이나, 어떤 두 사람은 서로가 서로의 후손이 아니며, 어떤 이도 다른 이의 조상이자 후손일 수는 없다.
집합
X
{\displaystyle X}
위의 이항 관계
≤
{\displaystyle \leq }
가 다음 조건들을 만족시키면, 이를
X
{\displaystyle X}
위의 (비절대) 부분 순서 ((非絶對)部分順序, 영어 : (non-strict) partial order )라고 한다.
(반사 관계 ) 임의의
x
∈
X
{\displaystyle x\in X}
에 대하여,
x
≤
x
{\displaystyle x\leq x}
(추이적 관계 ) 임의의
x
,
y
,
z
∈
X
{\displaystyle x,y,z\in X}
에 대하여,
x
≤
y
≤
z
{\displaystyle x\leq y\leq z}
라면
x
≤
z
{\displaystyle x\leq z}
(반대칭 관계 ) 임의의
x
,
y
∈
X
{\displaystyle x,y\in X}
에 대하여,
x
≤
y
≤
x
{\displaystyle x\leq y\leq x}
라면
x
=
y
{\displaystyle x=y}
집합
X
{\displaystyle X}
위의 이항 관계
<
{\displaystyle <}
가 다음 조건들을 만족시키면, 이를
X
{\displaystyle X}
위의 절대 부분 순서 (絶對部分順序, 영어 : strict partial order ) 또는 순부분 순서 (純部分順序)라고 한다.
(비반사 관계 ) 임의의
x
∈
X
{\displaystyle x\in X}
에 대하여,
x
≮
x
{\displaystyle x\not <x}
(추이적 관계 ) 임의의
x
,
y
,
z
∈
X
{\displaystyle x,y,z\in X}
에 대하여,
x
<
y
<
z
{\displaystyle x<y<z}
라면
x
<
z
{\displaystyle x<z}
(비대칭 관계 ) 임의의
x
,
y
∈
X
{\displaystyle x,y\in X}
에 대하여,
x
<
y
{\displaystyle x<y}
라면
y
≮
x
{\displaystyle y\not <x}
이들 가운데 비대칭 관계 조건은 나머지 조건들로부터 유도 가능하다.[2]
부분 순서
≤⊆
X
2
{\displaystyle \leq \subseteq X^{2}}
가 주어졌을 때, 다음과 같이 정의한 이항 관계
<⊆
X
2
{\displaystyle <\subseteq X^{2}}
는 절대 부분 순서이다.
x
<
y
⟺
x
≤
y
≠
x
(
x
,
y
∈
X
)
{\displaystyle x<y\iff x\leq y\neq x\qquad (x,y\in X)}
절대 부분 순서
<⊆
X
2
{\displaystyle <\subseteq X^{2}}
가 주어졌을 때, 다음과 같이 정의한 이항 관계
≤⊆
X
2
{\displaystyle \leq \subseteq X^{2}}
는 부분 순서이다.
x
≤
y
⟺
x
<
y
∨
x
=
y
(
x
,
y
∈
X
)
{\displaystyle x\leq y\iff x<y\lor x=y(x,y\in X)}
부분 순서를 갖춘 집합
(
X
,
≤
)
{\displaystyle (X,\leq )}
을 부분 순서 집합 이라고 한다. 부분 순서의 정의에 삼분성(임의의 두 원소의 비교 가능성)을 추가하면 전순서 의 정의를 얻는다.
범주론 적으로, 부분 순서 집합
(
X
,
≤
)
{\displaystyle (X,\leq )}
는 범주 로 여길 수 있다. 이 경우
(
X
,
≤
)
{\displaystyle (X,\leq )}
의 대상은
X
{\displaystyle X}
의 원소이다.
(
X
,
≤
)
{\displaystyle (X,\leq )}
의 사상 은
{
(
x
,
y
)
∈
X
2
:
x
≤
y
}
{\displaystyle \{(x,y)\in X^{2}\colon x\leq y\}}
이다.
(
x
,
y
)
{\displaystyle (x,y)}
는
x
{\displaystyle x}
에서
y
{\displaystyle y}
로 가는 사상이다. 즉,
hom
(
x
,
y
)
{\displaystyle \hom(x,y)}
는 0개 또는 1개의 원소만을 포함한다.
대상
x
∈
X
{\displaystyle x\in X}
의 항등 사상은
(
x
,
x
)
∈
X
2
{\displaystyle (x,x)\in X^{2}}
이다.
순서 반사 함수가 아닌 순서 보존 함수의 예
두 집합 사이의 순서 동형. 왼쪽은 120의 약수들의 집합 위의, 약수 관계에 의한 부분 순서. 오른쪽은 120의 소수 거듭제곱 꼴 약수들의 집합 위의, 부분 집합 관계에 의한 부분 순서.
두 부분 순서 집합
(
X
,
≤
)
{\displaystyle (X,\leq )}
,
(
Y
,
≤
)
{\displaystyle (Y,\leq )}
사이의 함수
f
:
X
→
Y
{\displaystyle f\colon X\to Y}
가 다음 조건을 만족시키면, 순서 보존 함수 (영어 : order-preserving map )라고 한다.
임의의
x
,
y
∈
X
{\displaystyle x,y\in X}
에 대하여,
x
≤
y
{\displaystyle x\leq y}
라면
f
(
x
)
≤
f
(
y
)
{\displaystyle f(x)\leq f(y)}
또한,
f
{\displaystyle f}
가 다음 조건을 만족시키면, 순서 반사 함수 (영어 : order-reflecting map )라고 한다.
임의의
x
,
y
∈
X
{\displaystyle x,y\in X}
에 대하여,
f
(
x
)
≤
f
(
y
)
{\displaystyle f(x)\leq f(y)}
라면
x
≤
y
{\displaystyle x\leq y}
또한, 순서 보존 순서 반사 함수를 순서 매입 (영어 : order-embedding )라고 하며, 전사 순서 매입를 순서 동형 (영어 : order isomorphism )라고 한다.
예를 들어, 자연수 집합(약수 관계에 의한 부분 순서)에서 그 멱집합 (포함 관계에 의한 부분 순서)으로 가는 함수
f
:
N
→
P
(
N
)
{\displaystyle f:\mathbb {N} \to {\mathcal {P}}(\mathbb {N} )}
가 임의의 자연수를 소인수 들의 집합으로 대응시킨다면, 이는 순서 보존 사상이다. 임의의 자연수는 그의 약수의 소인수를 소인수로 가지기에 그러하다. 하지만 이는 단사 가 아니며 (
f
(
6
)
=
f
(
12
)
=
{
2
,
3
}
{\displaystyle f(6)=f(12)=\{2,3\}}
) 순서 반사도 아니다(
{
2
,
3
}
⊆
{
2
,
3
}
{\displaystyle \{2,3\}\subseteq \{2,3\}}
, 하지만
12
≰
6
{\displaystyle 12\not \leq 6}
). 자연수를 소수 거듭제곱 형식의 약수들의 집합으로 대응시키는 함수
g
:
N
→
P
(
N
)
{\displaystyle g:\mathbb {N} \to {\mathcal {P}}(\mathbb {N} )}
는 순서 보존, 순서 반사이며 따라서 순서 매입이다, 전단사가 아니므로 (
{
4
}
{\displaystyle \{4\}}
의 역상이 존재하지 않는다) 순서 동형은 아니다. 그러나 공역 을
g
(
N
)
{\displaystyle g(\mathbb {N} )}
으로 제한하면 순서 동형이 된다. 집합과 멱집합 사이의 순서 동형은 더 넓은 의미의 부분 순서인 분배 격자 로 일반화할 수 있다(버코프의 표현 정리 참조).
x , y , z } 의 멱집합에서 공집합과 자기 자신을 제외한 집합. 위의 세 원소는 극대 원소이며, 아래의 세 원소는 극소 원소이다. 최대 원소와 최소 원소는 존재하지 않는다. x , y } 는 부분 집합 x }, y }} 의 상계이다.
약수 관계에 의한 순서를 부여한 음이 아닌 정수 집합. 최대 원소는 0, 최소 원소는 1.
부분 순서 집합
P
{\displaystyle P}
에는 최대 · 최소 , 극대 · 극소 , 상계 · 하계 의 개념이 존재한다.
최대 원소와 최소 원소
모든
a
∈
P
{\displaystyle a\in P}
에 대해
g
≥
a
{\displaystyle g\geq a}
인
g
∈
P
{\displaystyle g\in P}
를
P
{\displaystyle P}
의 최대 원소라고 한다. 모든
a
∈
P
{\displaystyle a\in P}
에 대해
l
≤
a
{\displaystyle l\leq a}
인
l
∈
P
{\displaystyle l\in P}
를
P
{\displaystyle P}
의 최소 원소라고 한다. 부분 순서 집합은 최대 · 최소 원소를 많아야 하나씩 가질 수 있다.
극대 원소와 극소 원소
a
>
M
{\displaystyle a>M}
인
a
∈
P
{\displaystyle a\in P}
가 존재하지 않는
M
∈
P
{\displaystyle M\in P}
를
P
{\displaystyle P}
의 극대 원소라고 한다.
a
<
m
{\displaystyle a<m}
인
a
∈
P
{\displaystyle a\in P}
가 존재하지 않는
m
∈
P
{\displaystyle m\in P}
를
P
{\displaystyle P}
의 극소 원소라고 한다. 만약 최대 원소가 존재한다면 그가 바로 유일한 극대 원소이다. 그렇지 않은 경우 극대 원소는 여러 개 있을 수 있다. 극소 원소와 최소 원소 사이에도 비슷한 관계가 있다.
상계와 하계
P
{\displaystyle P}
의 부분집합
A
{\displaystyle A}
에 대하여,
A
{\displaystyle A}
의 상계
x
{\displaystyle x}
는
a
≤
x
{\displaystyle a\leq x}
를 모든
a
∈
A
{\displaystyle a\in A}
에 대해 성립하게 하는
P
{\displaystyle P}
의 원소이다.
A
{\displaystyle A}
의 하계
x
{\displaystyle x}
는
a
≥
x
{\displaystyle a\geq x}
를 모든
a
∈
A
{\displaystyle a\in A}
에 대해 성립하게 하는
P
{\displaystyle P}
의 원소이다. 상계와 하계 모두
A
{\displaystyle A}
에 속하지 않을 수 있다.
A
{\displaystyle A}
의 최대 원소와 최소 원소가 존재한다면, 그들은 각각
A
{\displaystyle A}
의 하나의 상계, 하계이다.
예를 들어 양의 정수 집합과 약수 관계로 이루어진 부분 순서 집합
(
Z
+
,
|
)
{\displaystyle (\mathbb {Z} ^{+},|)}
를 생각하면, 1은 그의 최소 원소이다. 최대 원소와 극대 원소는 존재치 않는다. 여기에 0을 추가하면 0이 최대 원소가 된다. 1보다 큰 정수만을 생각하면, 최소 원소가 존재하지 않게 되고, 모든 소수 가 극소 원소가 된다. 이러한 집합에서, 부분 집합
{
2
,
3
,
5
,
10
}
{\displaystyle \{2,3,5,10\}}
은 상계 60을 가지며 하계는 존재하지 않는다. 2의 거듭제곱들의 집합은 2를 하계로 가지며 상계가 존재하지 않는다.
ℕ×ℕ 위의 사전식 순서
ℕ×ℕ 위의 직접곱 순서
ℕ×ℕ 위의, 절대 순서 직접곱의 반사 폐포 . (3, 3)보다 큰 원소들은 (3, 3)과 빨간 선으로 이어져있고, (3, 3)보다 작은 원소들은 (3, 3)과 초록 선으로 이어져 있다.
부분 순서 집합
(
X
,
≤
)
{\displaystyle (X,\leq )}
이 주어졌을 때,
X
{\displaystyle X}
위에 다음과 같은 부분 순서
≥
{\displaystyle \geq }
를 정의할 수 있다.
x
≥
y
⟺
y
≤
x
(
x
,
y
∈
X
)
{\displaystyle x\geq y\iff y\leq x\qquad (x,y\in X)}
이 경우,
(
X
,
≥
)
{\displaystyle (X,\geq )}
를
(
X
,
≤
)
{\displaystyle (X,\leq )}
의 반대 순서 집합 이라고 한다.
부분 순서
≤
{\displaystyle \leq }
· 절대 부분 순서
<
{\displaystyle <}
· 반대 부분 순서
≥
{\displaystyle \geq }
· 반대 부분 순서의 절대 부분 순서
>
{\displaystyle >}
가운데 임의의 하나가 결정되면, 나머지 셋 역시 결정된다.
부분 순서 집합의 전순서 집합
(
{
(
X
i
,
≤
i
)
}
i
∈
I
,
≤
)
{\displaystyle (\{(X_{i},\leq _{i})\}_{i\in I},\leq )}
이 주어졌을 때, 분리 합집합
⊔
i
∈
I
X
i
{\displaystyle \textstyle \sqcup _{i\in I}X_{i}}
위에 다음과 같은 부분 순서
≤
{\displaystyle \leq }
를 정의할 수 있다.
x
≤
y
⟺
i
<
j
∨
(
i
=
j
∧
x
≤
y
)
(
x
∈
X
i
,
y
∈
X
j
)
{\displaystyle x\leq y\iff i<j\lor (i=j\land x\leq y)\qquad (x\in X_{i},\;y\in X_{j})}
이를 선형합 (영어 : linear sum )이라고 한다.
부분 순서 집합의 족
{
(
X
i
,
≤
i
)
}
i
∈
I
{\displaystyle \{(X_{i},\leq _{i})\}_{i\in I}}
이 주어졌을 때, 곱집합
∏
i
∈
I
X
i
{\displaystyle \textstyle \prod _{i\in I}X_{i}}
위에 다음과 같은 부분 순서
≤
{\displaystyle \leq }
를 정의할 수 있다.
(
x
i
)
i
∈
I
≤
(
y
i
)
i
∈
I
⟺
∀
i
∈
I
:
x
i
≤
y
i
(
x
i
,
y
i
∈
X
i
)
{\displaystyle (x_{i})_{i\in I}\leq (y_{i})_{i\in I}\iff \forall i\in I\colon x_{i}\leq y_{i}\qquad (x_{i},y_{i}\in X_{i})}
이 경우,
(
∏
i
∈
I
X
i
,
≤
)
{\displaystyle \textstyle (\prod _{i\in I}X_{i},\leq )}
를
{
(
X
i
,
≤
i
)
}
i
∈
I
{\displaystyle \{(X_{i},\leq _{i})\}_{i\in I}}
의 직접곱 (영어 : direct product )이라고 한다.
마찬가지로, 절대 부분 순서 집합의 직접곱을 정의할 수 있으며, 이에 대응하는, 곱집합 위의 부분 순서는 다음과 같다.
(
x
i
)
i
∈
I
≤
(
y
i
)
i
∈
I
⟺
(
x
i
)
i
∈
I
=
(
y
i
)
i
∈
I
∨
∀
i
∈
I
:
x
i
<
y
i
(
x
i
,
y
i
∈
X
i
)
{\displaystyle (x_{i})_{i\in I}\leq (y_{i})_{i\in I}\iff (x_{i})_{i\in I}=(y_{i})_{i\in I}\lor \forall i\in I\colon x_{i}<y_{i}\qquad (x_{i},y_{i}\in X_{i})}
부분 순서 집합의 정렬 집합
(
{
(
X
i
,
≤
i
)
}
i
∈
I
,
≤
)
{\displaystyle (\{(X_{i},\leq _{i})\}_{i\in I},\leq )}
이 주어졌을 때, 곱집합
∏
i
∈
I
X
i
{\displaystyle \textstyle \prod _{i\in I}X_{i}}
위에 다음과 같은 이항 관계
≤
{\displaystyle \leq }
를 정의할 수 있다.
(
x
i
)
i
∈
I
≤
(
y
i
)
i
∈
I
⟺
(
x
i
)
i
∈
I
=
(
y
i
)
i
∈
I
∨
x
min
{
i
:
x
i
≠
y
i
}
<
y
min
{
i
:
x
i
≠
y
i
}
(
x
i
,
y
i
∈
X
i
)
{\displaystyle (x_{i})_{i\in I}\leq (y_{i})_{i\in I}\iff (x_{i})_{i\in I}=(y_{i})_{i\in I}\lor x_{\min\{i\colon x_{i}\neq y_{i}\}}<y_{\min\{i\colon x_{i}\neq y_{i}\}}\qquad (x_{i},y_{i}\in X_{i})}
이를 사전식 순서 라고 한다.
크기
n
{\displaystyle n}
의 집합 위의 부분 순서의 수는 다음과 같다. (
n
=
0
,
1
,
2
,
…
{\displaystyle n=0,1,2,\dots }
)
1, 1, 3, 19, 219, 4231, 130023, ... (OEIS 의 수열 A1035 )
크기
n
{\displaystyle n}
의 집합 위의 부분 순서의 동형류의 수는 다음과 같다. (
n
=
0
,
1
,
2
,
…
{\displaystyle n=0,1,2,\dots }
)
1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284, ... (OEIS 의 수열 A112 )
모든 전순서 는 부분 순서이다. 예를 들어, 자연수 집합
N
{\displaystyle \mathbb {N} }
이나 정수 집합
Z
{\displaystyle \mathbb {Z} }
, 유리수 집합
Q
{\displaystyle \mathbb {Q} }
, 실수 집합
R
{\displaystyle \mathbb {R} }
위의 표준적인 순서는 전순서이므로 부분 순서이다.
집합
S
{\displaystyle S}
의 멱집합
P
(
S
)
{\displaystyle {\mathcal {P}}(S)}
위의 포함 관계
⊆
{\displaystyle \subseteq }
는 부분 순서이며, 만약
S
{\displaystyle S}
가 두 개 이상의 원소를 갖는다면 이는 전순서 가 아니다. 또한, 이를
P
(
S
)
{\displaystyle {\mathcal {P}}(S)}
의 부분 집합에 국한시켜도 역시 부분 순서를 이룬다. 예를 들어,
등등은 특정한 부분 집합들의 집합이므로 포함 관계를 통해 부분 순서를 갖는다.
부분수열 에 의한 관계는 특정한 집합 (예를 들어 어떤 수열의 부분수열들의 집합, 집합
X
{\displaystyle X}
의 원소를 항으로 하는 수열들의 집합) 위의 부분 순서이다. 이는 일반적으로 전순서가 아니다. 이와 비슷하게 문자열 들의 집합에서 부속문자열 에 의한 관계는 부분 순서이다.
양의 정수의 집합
Z
+
{\displaystyle \mathbb {Z} ^{+}}
위의 약수 관계
∣
{\displaystyle \mid }
(
a
∣
b
{\displaystyle a\mid b}
는
a
{\displaystyle a}
가
b
{\displaystyle b}
의 약수라는 의미)는 부분 순서이며, 이는 전순서가 아니다.
비순환 유향그래프 의 꼭짓점들의 집합은 도달가능성 에 의한 부분 순서를 가진다.
부분 순서 집합
S
{\displaystyle S}
의 수열 공간
S
N
{\displaystyle S^{\mathbb {N} }}
에 정의된 성분별 순서 는 부분 순서이다.
(
a
n
)
n
∈
N
≤
(
b
n
)
n
∈
N
⟺
∀
n
∈
N
:
a
n
≤
b
n
{\displaystyle (a_{n})_{n\in \mathbb {N} }\leq (b_{n})_{n\in \mathbb {N} }\ \iff \ \forall n\in \mathbb {N} :a_{n}\leq b_{n}}
부분 순서
≤⊆
X
2
{\displaystyle \leq \subseteq X^{2}}
에 대하여, 전순서
≤⊆
≤
∗
⊆
X
2
{\displaystyle \leq \subseteq \leq ^{*}\subseteq X^{2}}
를
≤
{\displaystyle \leq }
의 선형 확장이라고 한다. 예를 들어, 부분 순서 집합의 직접곱의 한 가지 선형 확장은 사전식 순서이다. 선택 공리 아래, 임의의 부분 순서는 선형 확장을 갖는다. 컴퓨터 과학 에서, 위상 정렬 은 부분 순서의 선형 확장을 구하는 알고리즘 이다.
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. ISBN 0-521-66351-2 .