부분 순서

위키백과, 우리 모두의 백과사전.
(부분순서에서 넘어옴)
이동: 둘러보기, 검색
세원소 집합 \{x,y,z\}의 모든 부분집합들의 집합 (멱집합) 위의 포함 관계에 의한 부분 순서를 그린 하세 도형. 같은 높이에 있거나 (\{x\}\{y\}) 화살표 방향대로 나아가 도달하지 못하면 (\{x\}\{y,z\}) 순서가 정해지지 않은 것이다. 임의의 부분 순서 집합 (\mathcal{P}(S),\subseteq)격자를 이룬다.

수학, 특히 순서론에서, 부분 순서 또는 반순서(部分順序, 半順序, 영어: partial order)는 순서, 배열, 정렬 등의 직관적인 개념을 추상화한 이항 관계이다. 부분 순서가 정의된 집합을 그 부분 순서와 같이 부분 순서 집합(部分順序集合, 영어: partially ordered set, poset)이라고 한다. 부분 순서 집합은 모든 원소가 비교 가능할 것을 요구하지 않는다. 모든 원소가 비교가능한 부분 순서를 전순서라고 한다. 유한한 부분 순서 집합은 하세 도형으로 표현할 수 있다.[1]

실생활의 예로, 사람들의 가계도에 의한 순서는 부분 순서이다. 어떤 두 사람은 조상과 후손의 관계이나, 어떤 두 사람들은 그런 관계가 없다.

정의[편집]

일반[편집]

집합 S 위의 이항 관계 {\le}가 다음 조건을 만족시키면 이 이항 관계는 집합 S에 대한 부분 순서이다.

집합과 그 집합에 대해 부분 순서인 이항 관계의 순서쌍 (S,\le)부분 순서 집합이라고 한다.

순부분순서[편집]

일부 문헌에서는 위에서 정의한 순서 관계를 비절대부분순서 또는 비순부분순서(非絶對部分順序, -純-, 영어: non-strict partial order)라고 한다. 또 절대부분순서 또는 순부분순서[2](영어: strict partial order)로 불리는 순서 관계 <를 다음과 같이 정의한다.

  • 모든 s\in Ss<s를 불만족한다. (비반사성)
  • 모든 s,t,u\in S에 대하여, 만약 s<t이며 t<u이면 s<u (추이성)
  • 모든 s,t\in S에 대하여, 만약 s<t이면 \neg(t<s) (비대칭성, 이는 비반사성과 추이성으로부터 추론 가능하다[3])

S 위의 모든 순부분순서와 비순부분순서 사이에는 자명한 일대일 대응이 존재한다.

  • S 상의 비순부분순서 \le에 대응하는 순부분순서 <는 다음과 같다.
    a<b\ \iff\ a\le b\ \text{and}\ a\ne b
  • S 상의 순부분순서 <에 대응하는 비순부분순서 \le는 다음과 같다.
    a\le b\ \iff\ a<b\ \text{or}\ a=b

역관계와 반대순서집합[편집]

부분 순서 관계 \le역관계 \gex\ge y일 필요충분조건이 y\le x임을 만족한다. 이는 여전히 반사성, 대칭성, 추이성을 만족하므로 부분 순서 관계이다. (S,\le)반대 순서 집합 (S,\ge)는 부분 순서 집합에서 집합을 그대로 두고 순서를 그 역관계로 대신한 것이다. >\ge에 대응하는 순부분순서이다.

네 개의 순서 관계 \le,<,\ge,> 중 임의의 하나는 나머지 세 개를 결정짓는다.

범주론[편집]

범주론적으로, 부분 순서 집합 (S,\le)범주로 여길 수 있다. 이 경우

  • (S,\le)의 대상은 S의 원소이다.
  • (S,\le)사상\{(s,t)\in S^2\colon s\le t\}이다. (s,t)s에서 t로 가는 사상이다. 즉, \hom(s,t)는 0개 또는 1개의 원소만을 포함한다.
  • 대상 s\in S의 항등 사상은 (s,s)\in S^2이다.

모형 이론[편집]

모형 이론적으로, 부분 순서는 이항 관계 \le의 언어에 대한, 다음 1차 논리적 공리들로 구성되는 이론이다.

  • \forall a\colon a\le a
  • \forall a\forall b\forall c\colon(a\le b)\land(b\le c)\implies a\le c
  • \forall a\forall b\colon(a\le b)\land(b\le a)\implies a=b

부분 순서의 이론의 모형은 부분 순서 집합이다.

[편집]

모든 전순서는 부분 순서이다. 예를 들어, 자연수 집합 \mathbb N이나 정수 집합 \mathbb Z, 유리수 집합 \mathbb Q, 실수 집합 \mathbb R 위의 표준적인 순서는 전순서이므로 부분 순서이다.

집합 S멱집합 \mathcal P(S) 위의 포함 관계 \subseteq는 부분 순서이며, 만약 S가 두 개 이상의 원소를 갖는다면 이는 전순서가 아니다. 또한, 이를 \mathcal P(S)의 부분 집합에 국한시켜도 역시 부분 순서를 이룬다. 예를 들어,

등등은 특정한 부분 집합들의 집합이므로 포함 관계를 통해 부분 순서를 갖는다.

부분수열에 의한 관계는 특정한 집합 (예를 들어 어떤 수열의 부분수열들의 집합, 집합 X의 원소를 항으로 하는 수열들의 집합) 위의 부분 순서이다. 이는 일반적으로 전순서가 아니다. 이와 비슷하게 문자열들의 집합에서 부속문자열에 의한 관계는 부분 순서이다.

양의 정수의 집합 \mathbb Z^+ 위의 약수 관계 \mid(a\mid bab의 약수라는 의미)는 부분 순서이며, 이는 전순서가 아니다.

비순환 유향그래프의 꼭짓점들의 집합은 도달가능성에 의한 부분 순서를 가진다.

부분 순서 집합 S수열 공간 S^{\N}에 정의된 성분별 순서는 부분 순서이다.

(a_n)_{n\in\N}\le(b_n)_{n\in\N}\ \iff\ \forall n\in\N:a_n\le b_n

순서 보존과 순서 동형[편집]

두 부분 순서 집합 (S,\le), (T,\le) 사이의 순서 보존 사상 (또는 단조 함수) f:S\to T는 임의의 x,y\in S에 대해 x\le y이면 f(x)\le f(y)임을 만족하는 함수이다. 즉, 이는 부분 순서 관계를 지닌 두 구조 사이의 준동형이다.

임의의 x,y\in S에 대해 f(x)\le f(y)이면 x\le y라는 조건(순서 반사 사상(영어: order-reflecting map))을 추가로 만족하면, 즉 임의의 x,y\in S에 대해 x\le yf(x)\le f(y)가 동치이면, fST 사이의 순서 매입 사상이라고 하고, 두 부분 순서 집합 S,T 간에 순서 매입 사상이 존재할 때 ST에 매입 (또는 끼워넣기) 가능하다고 한다.

또 추가로 순서 매입 사상 f전단사 함수이면, f순서 동형 사상이라고 하며 순서 동형 사상이 존재하는 두 부분 순서 집합 S,T를 순서 동형이라고 한다.

예를 들어, 자연수 집합(약수 관계에 의한 부분 순서)에서 그 멱집합(포함 관계에 의한 부분 순서)으로 가는 함수 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)으로 제한하면 순서 동형이 된다. 집합과 멱집합 사이의 순서 동형은 더 넓은 의미의 부분 순서인 분배 격자로 일반화할 수 있다. 버코프의 표현 정리 참조.

극값[편집]

부분 순서 집합 P에는 최대 · 최소, 극대 · 극소, 상계 · 하계의 개념이 존재한다.

최대 원소와 최소 원소
모든 a\in P에 대해 g\ge ag\in PP의 최대 원소라고 한다. 모든 a\in P에 대해 l\le al\in PP의 최소 원소라고 한다. 부분 순서 집합은 최대 · 최소 원소를 많아야 하나씩 가질 수 있다.
극대 원소와 극소 원소
a>Ma\in P가 존재하지 않는 M\in PP의 극대 원소라고 한다. a<ma\in P가 존재하지 않는 m\in PP의 극소 원소라고 한다. 만약 최대 원소가 존재한다면 그가 바로 유일한 극대 원소이다. 그렇지 않은 경우 극대 원소는 여러 개 있을 수 있다. 극소 원소와 최소 원소 사이에도 비슷한 관계가 있다.
상계와 하계
P의 부분집합 A에 대하여, A의 상계 xa\le x를 모든 a\in A에 대해 성립하게 하는 P의 원소이다. A의 하계 xa\ge x를 모든 a\in A에 대해 성립하게 하는 P의 원소이다. 상계와 하계 모두 A에 속하지 않을 수 있다. A의 최대 원소와 최소 원소가 존재한다면, 그들은 각각 A의 하나의 상계, 하계이다.

예를 들어 양의 정수 집합과 약수 관계로 이루어진 부분 순서 집합 (\Z^+,|)를 생각하면, 1은 그의 최소 원소이다. 최대 원소와 극대 원소는 존재치 않는다. 여기에 0을 추가하면 0이 최대 원소가 된다. 1보다 큰 정수만을 생각하면, 최소 원소가 존재하지 않게 되고, 모든 소수가 극소 원소가 된다. 이러한 집합에서, 부분 집합 \{2,3,5,10\}은 상계 60을 가지며 하계는 존재하지 않는다. 2의 거듭제곱들의 집합은 2를 하계로 가지며 상계가 존재하지 않는다.

곱집합 위의 부분 순서[편집]

두 부분 순서 집합 X,Y에 의하여, 곱집합 X\times Y 위에 새로운 부분 순서들을 정의할 수 있다.

사전식 순서
(a,b)<(c,d)\ \iff\ a<c\ \text{or}\ (a=c\ \text{and}\ b<d)
두 부분순서의 직접곱 (순서곱)
(a,b)\le(c,d)\ \iff\ a\le c\ \text{and}\ b\le d
두 순부분순서의 직접곱의 반사폐포
(a,b)\le(c,d)\ \iff\ (a<c\ \text{and}\ b<d)\ \text{or}\ (a=c\ \text{and}\ b=d)

세 개념 모두 세 개 이상의 부분 순서로 확장 가능하다.

부분 순서의 합[편집]

위의 순서곱과 비슷한 개념으로 순서합(영어: ordinal sum, linear sum) Z=X\oplus Y이 있다. 이는 XY분리합집합에 부분 순서를 정의한 것으로, 다음 세 조건 중 하나를 만족하는 것을 a<_Zb로 정의한다.

  • a,b\in X,a<_Xb
  • a,b\in Y,a<_Yb
  • a\in X,b\in Y

분리합집합의 정의가 X\sqcup Y=(\{0\}\times X)\cup(\{1\}\times Y)라고 했을 때, 순서합을 사전식 순서와 비슷하게 정의할 수도 있다.

(a_1,a_2)<(b_1,b_2)\ \iff\ a_1<b_1\ \text{or}\ (a_1=b_1\ \text{and}\ a_2<b_2)

더 많은 개수의 부분 순서의 순서합도 비슷하게 정의 가능하다.

정렬 순서의 순서합은 여전히 정렬 순서이다.

선형 확장[편집]

S 위의 부분 순서 \le,\le^*에 대해, \le^*\le확장(영어: extension)이라 함은 x\le y를 만족하는 x,y는 항상 x\le^*y도 만족한다는 말이다. 이항 관계를 관계를 만족하는 두 대상의 순서쌍들의 집합으로서 정의할 때, 이는 다음과 같은 말이다.

\le\ \subseteq\ \le^*

부분 순서 \le선형 확장 \le^*선형 순서(즉 전순서)인 확장이다. 예를 들어, 전순서 집합 X,Y사전식 순서는 그들의 순서곱의 선형 확장이다. 선택 공리리의 전제 하에, 임의의 부분 순서는 선형 확장 가능하다, 즉 그를 포함하는 전순서가 존재한다(순서 확장 원리).

컴퓨터 과학에서, 위상 정렬은 부분 순서의 선형 확장을 구하는 알고리즘이다.

부분 순서의 수[편집]

크기가 n인 유한 집합 위의 부분 순서의 수는 다음과 같다. (n=0,1,2,\dots)

1, 1, 3, 19, 219, 4231, 130023, … (OEIS의 수열 A1035)

크기가 n인 유한 집합 위의 부분 순서의 동형류의 수는 다음과 같다. (n=0,1,2,\dots)

1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284, … (OEIS의 수열 A112)

같이 보기[편집]

각주[편집]

  1. Merrifield, Richard E.; Simmons, Howard E. (1989). 《Topological Methods in Chemistry》 (영어). New York: John Wiley & Sons. 28쪽. ISBN 0-471-83817-9. 27 July 2012에 확인함. A partially ordered set is conveniently represented by a Hasse diagram... 
  2. partial order strict partial order - 대한수학회 수학용어
  3. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). 《Transitive Closures of Binary Relations I》 (영어). Prague: School of Mathematics - Physics Charles University. 1쪽.  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. ISBN 0-521-66351-2. 

바깥 고리[편집]