부분 순서 집합

순서론에서 부분 순서(部分順序, ) 또는 반순서(半順序)는 순서·나열 등의 개념을 추상화한 이항 관계이다. 부분 순서를 갖춘 집합을 부분 순서 집합(部分順序集合, )이라고 한다. 이는 전순서 집합과 달리 모든 원소가 비교 가능할 필요는 없으며, 원순서 집합과 달리 순서가 같은 여러 원소는 존재하지 않아야 한다. 유한 부분 순서 집합은 하세 도형을 통해 나타낼 수 있다. 예를 들어, 가계도에서의 관계는 부분 순서이다. 어떤 두 사람은 조상과 후손의 관계이나, 어떤 두 사람은 서로가 서로의 후손이 아니며, 어떤 이도 다른 이의 조상이자 후손일 수는 없다.
정의.
순서론적 정의.
집합 formula_1 위의 이항 관계 formula_2가 다음 조건들을 만족시키면, 이를 formula_1 위의 (비절대) 부분 순서((非絶對)部分順序, )라고 한다.
집합 formula_1 위의 이항 관계 formula_13가 다음 조건들을 만족시키면, 이를 formula_1 위의 절대 부분 순서(絶對部分順序, ) 또는 순부분 순서(純部分順序)라고 한다.
이들 가운데 비대칭 관계 조건은 나머지 조건들로부터 유도 가능하다.
부분 순서 formula_23가 주어졌을 때, 다음과 같이 정의한 이항 관계 formula_24는 절대 부분 순서이다.
절대 부분 순서 formula_24가 주어졌을 때, 다음과 같이 정의한 이항 관계 formula_23는 부분 순서이다.
부분 순서를 갖춘 집합 formula_29을 부분 순서 집합이라고 한다. 부분 순서의 정의에 삼분성(임의의 두 원소의 비교 가능성)을 추가하면 전순서의 정의를 얻는다.
범주론적 정의.
범주론적으로, 부분 순서 집합 formula_29는 범주로 여길 수 있다. 이 경우
순서 보존 함수.
두 부분 순서 집합 formula_29, formula_42 사이의 함수 formula_43가 다음 조건을 만족시키면, 순서 보존 함수()라고 한다.
또한, formula_47가 다음 조건을 만족시키면, 순서 반사 함수()라고 한다.
또한, 순서 보존 순서 반사 함수를 순서 매입()라고 하며, 전사 순서 매입를 순서 동형()라고 한다.
예를 들어, 자연수 집합(약수 관계에 의한 부분 순서)에서 그 멱집합(포함 관계에 의한 부분 순서)으로 가는 함수 formula_51가 임의의 자연수를 소인수들의 집합으로 대응시킨다면, 이는 순서 보존 사상이다. 임의의 자연수는 그의 약수의 소인수를 소인수로 가지기에 그러하다. 하지만 이는 단사가 아니며 (formula_52) 순서 반사도 아니다(formula_53, 하지만 formula_54). 자연수를 소수 거듭제곱 형식의 약수들의 집합으로 대응시키는 함수 formula_55는 순서 보존, 순서 반사이며 따라서 순서 매입이다, 전단사가 아니므로 (formula_56의 역상이 존재하지 않는다) 순서 동형은 아니다. 그러나 공역을 formula_57으로 제한하면 순서 동형이 된다. 집합과 멱집합 사이의 순서 동형은 더 넓은 의미의 부분 순서인 분배 격자로 일반화할 수 있다(버코프의 표현 정리 참조).
극값.
부분 순서 집합 formula_58에는 최대 · 최소, 극대 · 극소, 상계 · 하계의 개념이 존재한다.
예를 들어 양의 정수 집합과 약수 관계로 이루어진 부분 순서 집합 formula_90를 생각하면, 1은 그의 최소 원소이다. 최대 원소와 극대 원소는 존재치 않는다. 여기에 0을 추가하면 0이 최대 원소가 된다. 1보다 큰 정수만을 생각하면, 최소 원소가 존재하지 않게 되고, 모든 소수가 극소 원소가 된다. 이러한 집합에서, 부분 집합 formula_91은 상계 60을 가지며 하계는 존재하지 않는다. 2의 거듭제곱들의 집합은 2를 하계로 가지며 상계가 존재하지 않는다.
연산.
반대 순서 집합.
부분 순서 집합 formula_29이 주어졌을 때, formula_1 위에 다음과 같은 부분 순서 formula_94를 정의할 수 있다.
이 경우, formula_96를 formula_29의 반대 순서 집합이라고 한다.
부분 순서 formula_2 · 절대 부분 순서 formula_13 · 반대 부분 순서 formula_94 · 반대 부분 순서의 절대 부분 순서 formula_101 가운데 임의의 하나가 결정되면, 나머지 셋 역시 결정된다.
선형합.
부분 순서 집합의 전순서 집합 formula_102이 주어졌을 때, 분리 합집합 formula_103 위에 다음과 같은 부분 순서 formula_2를 정의할 수 있다.
이를 선형합()이라고 한다.
직접곱.
부분 순서 집합의 족 formula_106이 주어졌을 때, 곱집합 formula_107 위에 다음과 같은 부분 순서 formula_2를 정의할 수 있다.
이 경우, formula_110를 formula_106의 직접곱()이라고 한다.
절대 부분 순서의 직접곱의 반사 폐포.
마찬가지로, 절대 부분 순서 집합의 직접곱을 정의할 수 있으며, 이에 대응하는, 곱집합 위의 부분 순서는 다음과 같다.
사전식 순서.
부분 순서 집합의 정렬 집합 formula_102이 주어졌을 때, 곱집합 formula_107 위에 다음과 같은 이항 관계 formula_2를 정의할 수 있다.
이를 사전식 순서라고 한다.
성질.
부분 순서의 수.
크기 formula_117의 집합 위의 부분 순서의 수는 다음과 같다. (formula_118)
크기 formula_117의 집합 위의 부분 순서의 동형류의 수는 다음과 같다. (formula_118)
예.
모든 전순서는 부분 순서이다. 예를 들어, 자연수 집합 formula_121이나 정수 집합 formula_122, 유리수 집합 formula_123, 실수 집합 formula_124 위의 표준적인 순서는 전순서이므로 부분 순서이다.
집합 formula_125의 멱집합 formula_126 위의 포함 관계 formula_127는 부분 순서이며, 만약 formula_125가 두 개 이상의 원소를 갖는다면 이는 전순서가 아니다. 또한, 이를 formula_126의 부분 집합에 국한시켜도 역시 부분 순서를 이룬다. 예를 들어,
등등은 특정한 부분 집합들의 집합이므로 포함 관계를 통해 부분 순서를 갖는다.
부분수열에 의한 관계는 특정한 집합 (예를 들어 어떤 수열의 부분수열들의 집합, 집합 formula_1의 원소를 항으로 하는 수열들의 집합) 위의 부분 순서이다. 이는 일반적으로 전순서가 아니다. 이와 비슷하게 문자열들의 집합에서 부속문자열에 의한 관계는 부분 순서이다.
양의 정수의 집합 formula_131 위의 약수 관계 formula_132(formula_133는 formula_134가 formula_135의 약수라는 의미)는 부분 순서이며, 이는 전순서가 아니다.
비순환 유향그래프의 꼭짓점들의 집합은 도달가능성에 의한 부분 순서를 가진다.
부분 순서 집합 formula_125의 수열 공간 formula_137에 정의된 성분별 순서는 부분 순서이다.
응용.
부분 순서 formula_23에 대하여, 전순서 formula_140를 formula_2의 선형 확장이라고 한다. 예를 들어, 부분 순서 집합의 직접곱의 한 가지 선형 확장은 사전식 순서이다. 선택 공리 아래, 임의의 부분 순서는 선형 확장을 갖는다. 컴퓨터 과학에서, 위상 정렬은 부분 순서의 선형 확장을 구하는 알고리즘이다.