부분 순서 집합

위키백과, 우리 모두의 백과사전.

세원소 집합 x, y, z}멱집합 위의 부분 집합 관계에 의한 부분 순서를 그린 하세 도형. 같은 높이에 있거나 (x}y}) 화살표 방향대로 나아가 도달하지 못하면 (x}y, z}) 순서가 정해지지 않은 것이다.

순서론에서 부분 순서(部分順序, 영어: partial order) 또는 반순서(半順序)는 순서·나열 등의 개념을 추상화한 이항 관계이다. 부분 순서를 갖춘 집합부분 순서 집합(部分順序集合, 영어: partially ordered set, poset)이라고 한다. 이는 전순서 집합과 달리 모든 원소가 비교 가능할 필요는 없으며, 원순서 집합과 달리 순서가 같은 여러 원소는 존재하지 않아야 한다. 유한 부분 순서 집합은 하세 도형을 통해 나타낼 수 있다.[1] 예를 들어, 가계도에서의 관계는 부분 순서이다. 어떤 두 사람은 조상과 후손의 관계이나, 어떤 두 사람은 서로가 서로의 후손이 아니며, 어떤 이도 다른 이의 조상이자 후손일 수는 없다.

정의[편집]

순서론적 정의[편집]

집합 위의 이항 관계 가 다음 조건들을 만족시키면, 이를 위의 (비절대) 부분 순서((非絶對)部分順序, 영어: (non-strict) partial order)라고 한다.

  • (반사 관계) 임의의 에 대하여,
  • (추이적 관계) 임의의 에 대하여, 라면
  • (반대칭 관계) 임의의 에 대하여, 라면

집합 위의 이항 관계 가 다음 조건들을 만족시키면, 이를 위의 절대 부분 순서(絶對部分順序, 영어: strict partial order) 또는 순부분 순서(純部分順序)라고 한다.

  • (비반사 관계) 임의의 에 대하여,
  • (추이적 관계) 임의의 에 대하여, 라면
  • (비대칭 관계) 임의의 에 대하여, 라면

이들 가운데 비대칭 관계 조건은 나머지 조건들로부터 유도 가능하다.[2]

부분 순서 가 주어졌을 때, 다음과 같이 정의한 이항 관계 는 절대 부분 순서이다.

절대 부분 순서 가 주어졌을 때, 다음과 같이 정의한 이항 관계 는 부분 순서이다.

부분 순서를 갖춘 집합 부분 순서 집합이라고 한다. 부분 순서의 정의에 삼분성(임의의 두 원소의 비교 가능성)을 추가하면 전순서의 정의를 얻는다.

범주론적 정의[편집]

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

  • 의 대상은 의 원소이다.
  • 사상이다. 에서 로 가는 사상이다. 즉, 는 0개 또는 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를 하계로 가지며 상계가 존재하지 않는다.

연산[편집]

ℕ×ℕ 위의 사전식 순서
ℕ×ℕ 위의 직접곱 순서
ℕ×ℕ 위의, 절대 순서 직접곱의 반사 폐포. (3, 3)보다 큰 원소들은 (3, 3)과 빨간 선으로 이어져있고, (3, 3)보다 작은 원소들은 (3, 3)과 초록 선으로 이어져 있다.

반대 순서 집합[편집]

부분 순서 집합 이 주어졌을 때, 위에 다음과 같은 부분 순서 를 정의할 수 있다.

이 경우, 반대 순서 집합이라고 한다.

부분 순서 · 절대 부분 순서 · 반대 부분 순서 · 반대 부분 순서의 절대 부분 순서 가운데 임의의 하나가 결정되면, 나머지 셋 역시 결정된다.

선형합[편집]

부분 순서 집합의 전순서 집합 이 주어졌을 때, 분리 합집합 위에 다음과 같은 부분 순서 를 정의할 수 있다.

이를 선형합(영어: linear sum)이라고 한다.

직접곱[편집]

부분 순서 집합의 족 이 주어졌을 때, 곱집합 위에 다음과 같은 부분 순서 를 정의할 수 있다.

이 경우, 직접곱(영어: direct product)이라고 한다.

절대 부분 순서의 직접곱의 반사 폐포[편집]

마찬가지로, 절대 부분 순서 집합의 직접곱을 정의할 수 있으며, 이에 대응하는, 곱집합 위의 부분 순서는 다음과 같다.

사전식 순서[편집]

부분 순서 집합의 정렬 집합 이 주어졌을 때, 곱집합 위에 다음과 같은 이항 관계 를 정의할 수 있다.

이를 사전식 순서라고 한다.

성질[편집]

부분 순서의 수[편집]

크기 의 집합 위의 부분 순서의 수는 다음과 같다. ()

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

크기 의 집합 위의 부분 순서의 동형류의 수는 다음과 같다. ()

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. 2012년 7월 27일에 확인함. A partially ordered set is conveniently represented by a Hasse diagram... 
  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. ISBN 0-521-66351-2. 

외부 링크[편집]