부분 순서 집합

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

부분 순서 집합은 반사적이고 추이적이며 반대칭적인 이항 관계를 가진 집합이다. 부분 순서 집합은 완전 관계를 추가로 만족하면 전순서 집합이 된다. 부분 순서 집합은 순서 보존 함수, 극대/극소 원소, 상계/하계 등의 개념을 가지며, 연산으로는 반대 순서 집합, 선형합, 직접곱, 사전식 순서 등이 있다. 부분 순서의 수는 집합의 크기에 따라 결정되며, 컴퓨터 과학에서 위상 정렬과 같은 알고리즘에 활용된다.

부분 순서 집합

📚 더 읽어볼만한 페이지

관계 (수학) - 이항 관계
이항 관계는 순서쌍을 원소로 가지는 집합으로, 두 원소 간의 관계를 정의하며, 집합 X와 Y의 데카르트 곱의 부분집합으로 표현되고, 다양한 연산과 성질을 가지며 여러 분야에서 활용된다.
관계 (수학) - 동치 관계
동치 관계는 집합의 원소들 사이에서 반사성, 대칭성, 추이성을 만족하는 이항 관계로서, 집합을 겹치지 않는 부분집합인 동치류로 분할하여 몫집합 개념으로 이어지며 수학의 다양한 분야에서 활용된다.
순서론 - 스콧 위상
스콧 위상은 부분 순서 집합 위에 정의되는 위상으로, 하향 집합과 directed set의 상한에 대해 닫혀있는 집합을 닫힌 집합으로 정의하며, 컴퓨터 과학, 특히 프로그램 의미론에서 연속 함수의 개념을 일반화하고 프로그램의 계산 과정을 모델링하는 데 사용된다.
순서론 - 사전식 순서
사전식 순서는 정렬된 집합의 순서를 일반화하여 곱집합의 순서를 정의하는 데 사용되며, 단어 순서 정렬 방식과 유사하게 다양한 분야에 응용되는 수학적 개념이다.

2. 정의

'부분 순서'라는 용어는 보통 반사적 부분 순서 관계를 가리킨다. 그러나 일부 저자들은 비반사적 부분 순서 관계를 부분 순서라고 부르기도 한다. 엄격 부분 순서와 비엄격 부분 순서는 일대일 대응되므로, 각 엄격 부분 순서에 대응하는 고유한 비엄격 부분 순서가 존재하며 그 반대도 성립한다.

비엄격 부분 순서(반사적 부분 순서)는 집합 $P$ 에서 정의된 동차 관계 ≤이며, 다음 성질을 만족한다.

* [[반사 관계|반사성]]: 모든 $a \in P$ 에 대해, $a \leq a$ 이다.
* [[반대칭 관계|반대칭성]]: $a \leq b$ 이고 $b \leq a$ 이면, $a = b$ 이다.
* [[추이 관계|추이성]]: $a \leq b$ 이고 $b \leq c$ 이면, $a \leq c$ 이다.

엄격 부분 순서(비반사적 부분 순서)는 집합 $P$ 에 대한 동차 관계 $<$ 이며, 다음 조건을 만족한다.

* [[추이 관계|추이성]]: $a < b$ 이고 $b < c$ 이면 $a < c$ 이다.
* [[비반사 관계|비반사성]]: 모든 $a \in P$ 에 대해, $a < a$ 가 아니다.
* [[비대칭 관계|비대칭성]]: $a < b$ 이면, $b < a$ 가 아니다.

추이 관계는 비대칭적인 경우에만 비반사적이므로, 정의에서 비반사성이나 비대칭성 중 하나를 생략해도 동일하다.

집합 $P$ 와 부분 순서 관계 $\leq$ 가 주어지면, $\leq$ , $<$ , $\geq$ , $>$ 네 가지 부분 순서 관계를 정의할 수 있다. 여기서 $<$ 는 $\leq$ 의 비반사적 핵이고, $\geq$ 는 $\leq$ 의 이중 관계이며, $>$ 는 $<$ 의 이중 관계이다.

'순서 집합'이라는 용어는 문맥상 다른 종류의 순서가 아니라는 것이 명확한 경우 '부분 순서 집합'의 줄임말로 사용된다.

2.1. 순서론적 정의

집합 $X$ 위의 (반사/비절대/비순) 부분 순서는 다음 세 조건을 만족시키는 이항 관계 $\le\subseteq X^2$ 이다.

* (반사 관계) 임의의 $x\in X$ 에 대하여, $x\le x$
* (추이적 관계) 임의의 $x,y,z\in X$ 에 대하여, $x\le y\le z$ 라면 $x\le z$
* (반대칭 관계) 임의의 $x,y\in X$ 에 대하여, $x\le y\le x$ 라면 $x=y$

부분 순서 집합 $(X,\le)$ 은 부분 순서를 갖춘 집합이다. 부분 순서 집합이 다음 조건을 추가로 만족시키면, 전순서 집합이라고 한다.

* (완전 관계) 임의의 $x,y\in X$ 에 대하여, $x\le y$ 이거나 $y\le x$

집합 $X$ 위의 비반사/절대/순 부분 순서는 다음 두 조건을 만족시키는 이항 관계 $<\subseteq X^2$ 이다.

* (비반사 관계) 임의의 $x\in X$ 에 대하여, $x\not$
* (추이적 관계) 임의의 $x,y,z\in X$ 에 대하여, $x 라면 x$

두 조건으로부터 추가로 다음과 같은 성질을 유도할 수 있다.

* (비대칭 관계) 임의의 $x,y\in X$ 에 대하여, $x 라면 y\not$

부분 순서 집합 $(X,<)$ 은 비반사 부분 순서를 갖춘 집합이다. 부분 순서 집합이 다음 조건을 추가로 만족시키면, 전순서 집합이라고 한다.

* (삼분성) 임의의 $x,y,z\in X$ 에 대하여, $x 이거나, x=y 이거나, y$

반사 관계를 통한 정의와 비반사 관계를 통한 정의는 서로 동치이다. 구체적으로, 반사 부분 순서 $\le\subseteq X^2$ 가 주어졌을 때, 이항 관계
: $x$
는 비반사 부분 순서를 이룬다. 반대로, 비반사 부분 순서 $<\subseteq X^2$ 가 주어졌을 때, 이항 관계
: $x\le y\iff x$
는 반사 부분 순서이다. 또한, 두 방향의 대응 관계는 서로의 역이며, 따라서 주어진 집합 위 반사 부분 순서와 비반사 부분 순서 사이의 일대일 대응을 이룬다.

부분 순서 집합 $(X,\le)$ 에서, $x\ge y$ 는 $y\le x$ 를 뜻하는 표기이다. $x>y$ 는 $y 를 뜻한다.$

2.2. 범주론적 정의

범주론에서, 원순서 집합은 작은 얇은 범주와 동치이다. 부분 순서 집합은 뼈대 범주인 작은 얇은 범주이다. 즉, 서로 다른 두 대상은 동형이 아니다.

구체적으로, 임의의 원순서 집합 $(X,\le)$ 은 다음과 같은 범주로 여길 수 있다.

* $(X,\le)$ 의 대상은 $X$ 의 원소이다.
* $(X,\le)$ 의 사상은 다음과 같다. 만약 $x\le y$ 라면, 유일한 사상 $x\to y$ 이 존재한다. 만약 $x\nleq y$ 라면, 사상 $x\to y$ 은 존재하지 않는다.

모든 포셋(그리고 모든 전순서 집합)은 대상 $x$ 와 $y$ 에 대해 $x$ 에서 $y$ 로 가는 사상이 최대 하나 존재하는 범주로 간주될 수 있다. 보다 구체적으로, $x$ ≤ $y$ 일 경우 hom^영어(x, y) = mset^영어(x, y) 이고(그렇지 않으면 공집합), $(y, z) \circ (x, y) = (x, z)$ 이다. 이러한 범주는 때때로 포셋 범주라고 불린다.

포셋들은 그들이 동형일 경우에만 서로 동치이다. 포셋에서, 만약 존재한다면 가장 작은 원소는 초기 대상이고, 가장 큰 원소는 종료 대상이다. 또한, 모든 전순서 집합은 포셋과 동치이다. 마지막으로, 포셋의 모든 부분 범주는 동형에 닫혀있다.

2.3. 위상수학적 정의

위상수학에서, 원순서 집합의 개념은 알렉산드로프 공간의 개념과 동치이다. 이 경우, 원순서 집합 $(X,\le)$ 에 대하여, 다음 두 조건은 서로 동치이다.
* $(X,\le)$ 는 부분 순서 집합이다.
* $(X,\le)$ 에 대응하는 알렉산드로프 공간은 콜모고로프 공간이다.
따라서, 부분 순서 집합의 개념은 콜모고로프 공간인 알렉산드로프 공간의 개념과 동치이다. 사실, 서로 수반 함자를 이루는 두 함자 $\operatorname{Proset}\leftrightarrows\operatorname{Top}$ 를 적절히 제한하면, 부분 순서 집합의 범주 $\operatorname{Poset}$ 와 콜모고로프 공간의 범주 $\operatorname{Kolm}$ 사이의 한 쌍의 수반 함자
: $\operatorname{Poset}\leftrightarrows\operatorname{Kolm}$
를 얻는다. 또한, $\operatorname{Kolm}$ 대신 콜모고로프 알렉산드로프 공간의 범주를 사용하면, 두 범주 사이의 동형을 얻는다.
부분 순서 집합에 위상 공간의 구조가 주어진 경우, $\{ (a,b) : a \le b \}$ 가 위상 곱 공간 $P \times P$ 의 닫힌 집합이라고 가정하는 것이 일반적이다. 이러한 가정 하에서 부분 순서 관계는 $\lim_{i \to \infty} a_i = a,$ , $\lim_{i \to \infty} b_i = b,$ 이고, 모든 $i$ 에 대해 $a_i \leq b_i,$ 이면 $a \leq b.$ 와 같이 극한에서 잘 동작한다.

3. 순서 보존 함수

두 부분 순서 집합 $(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^영어)라고 한다.

두 집합 사이의 순서 동형. 왼쪽은 120의 약수들의 집합 위의, 약수 관계에 의한 부분 순서. 오른쪽은 120의 소수 거듭제곱 꼴 약수들의 집합 위의, 부분 집합 관계에 의한 부분 순서.

예를 들어, 자연수 집합(약수 관계에 의한 부분 순서)에서 그 멱집합(포함 관계에 의한 부분 순서)으로 가는 함수

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)

으로 제한하면 순서 동형이 된다. 집합과 멱집합 사이의 순서 동형은 더 넓은 의미의 부분 순서인 분배 격자로 일반화할 수 있다(버코프의 표현 정리 참조).

4. 극값

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

의 멱집합에서 공집합과 자기 자신을 제외한 집합. 위의 세 원소는 극대 원소이며, 아래의 세 원소는 극소 원소이다. 최대 원소와 최소 원소는 존재하지 않는다. 는 부분 집합 의 상계이다.

약수 관계에 의한 순서를 부여한 음이 아닌 정수 집합. 최대 원소는 0, 최소 원소는 1.

* 최대 원소와 최소 원소: 모든 원소보다 크거나 같은 원소를 최대 원소, 모든 원소보다 작거나 같은 원소를 최소 원소라고 한다. 부분 순서 집합은 최대 원소와 최소 원소를 각각 많아야 하나씩 가질 수 있다.
* 극대 원소와 극소 원소: 어떤 원소보다도 큰 원소가 없을 때, 그 원소를 극대 원소라고 한다. 어떤 원소보다도 작은 원소가 없을 때, 그 원소를 극소 원소라고 한다. 최대 원소가 존재하면 유일한 극대 원소가 되지만, 그렇지 않은 경우 극대 원소는 여러 개 있을 수 있다. 극소 원소와 최소 원소의 관계도 마찬가지이다.
* 상계와 하계: 부분 집합의 모든 원소보다 크거나 같은 원소를 상계, 모든 원소보다 작거나 같은 원소를 하계라고 한다. 상계와 하계는 그 부분 집합에 속하지 않을 수 있다.

예를 들어 양의 정수 집합에서 약수 관계를 생각하면, 1은 최소 원소이다. 최대 원소는 존재하지 않는다. 여기에 0을 추가하면 0이 최대 원소가 된다. 1보다 큰 정수만 생각하면 최소 원소가 없어지고, 모든 소수가 극소 원소가 된다. 집합

\{2,3,5,10\}

은 상계 60을 가지며 하계는 없다. 2의 거듭제곱 집합은 2를 하계로 가지며 상계는 없다.

4.1. 최대 원소와 최소 원소

모든 $a\in P$ 에 대해 $g\ge a$ 인 $g\in P$ 를 $P$ 의 최대 원소라고 한다. 모든 $a\in P$ 에 대해 $l\le a$ 인 $l\in P$ 를 $P$ 의 최소 원소라고 한다. 부분 순서 집합은 최대 · 최소 원소를 많아야 하나씩 가질 수 있다.

예를 들어 양의 정수 집합과 약수 관계로 이루어진 부분 순서 집합 $(\Z^+,|)$ 을 생각하면, 1은 그의 최소 원소이다. 여기에 0을 추가하면 0이 최대 원소가 된다.

4.2. 극대 원소와 극소 원소

$P$ 가 부분 순서 집합일 때, 다음 개념들이 정의된다.

* 극대 원소: $a > M$ 인 $a\in P$ 가 존재하지 않는 $M\in P$ 를 $P$ 의 극대 원소라고 한다.
* 극소 원소: $a < m$ 인 $a\in P$ 가 존재하지 않는 $m\in P$ 를 $P$ 의 극소 원소라고 한다.

최대 원소가 존재하면 그 원소가 유일한 극대 원소가 된다. 그렇지 않은 경우 극대 원소는 여러 개 있을 수 있다. 극소 원소와 최소 원소 사이에도 비슷한 관계가 성립한다.

예를 들어 양의 정수 집합에서 약수 관계를 생각했을 때, 1은 최소 원소이다. 최대 원소와 극대 원소는 존재하지 않는다. 여기에 0을 추가하면, 0은 최대 원소가 된다. 1보다 큰 정수만 생각하면, 최소 원소가 없어지며, 모든 소수가 극소 원소가 된다.

그림 5 가장 큰 원소와 가장 작은 원소가 제거된 위의 그림. 이 축소된 부분 순서 집합에서, 원소의 맨 위 행은 모두 극대 원소이고, 맨 아래 행은 모두 극소 원소이지만, 가장 큰 원소와 가장 작은 원소는 없다. — **그림 5** 가장 큰 원소와 가장 작은 원소가 제거된 위의 그림. 이 축소된 부분 순서 집합에서, 원소의 맨 위 행은 모두 극대 원소이고, 맨 아래 행은 모두 극소 원소이지만, 가장 큰 원소와 가장 작은 원소는 없다.

그림 6 음이 아닌 정수를 약수 관계에 따라 정렬 — **그림 6** 음이 아닌 정수를 약수 관계에 따라 정렬

4.3. 상계와 하계

부분 순서 집합 $P$ 의 부분 집합 $A$ 에 대하여, $A$ 의 상계(upper bound) $x$ 는 모든 $a\in A$ 에 대해 $a\le x$ 를 만족하는 $P$ 의 원소이다. $A$ 의 하계(lower bound) $x$ 는 모든 $a\in A$ 에 대해 $a\ge x$ 를 만족하는 $P$ 의 원소이다. 상계와 하계는 $A$ 에 속하지 않아도 된다. $A$ 의 최대 원소와 최소 원소가 존재한다면, 각각 $A$ 의 상계와 하계가 된다.

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

양의 정수를 약수 관계에 따라 정렬하면, 1은 다른 모든 원소를 나누는 가장 작은 원소이다. 이 부분 순서 집합은 가장 큰 원소를 가지지 않는다. 극대 원소도 없는데, 임의의 g는 2g를 나누고, 이는 g와 다르므로 g는 극대가 아니다. 숫자 1을 제외하고 1보다 큰 원소에서 약수 관계를 유지하면, 결과는 가장 작은 원소가 없지만, 임의의 소수는 극소 원소이다. 이 부분 순서 집합에서 60은 부분 집합

\{2, 3, 5, 10\}

의 상계(최소 상계는 아님)이며, 하계를 가지지 않는다(1이 부분 순서 집합에 없으므로). 2는 2의 거듭제곱 부분 집합의 하계이며, 상계를 가지지 않는다. 0을 포함하면, 이것이 가장 큰 원소가 되는데, 이는 모든 정수의 배수이기 때문이다(그림 6 참조).

5. 연산

부분 순서 집합에는 다음과 같은 연산들을 정의할 수 있다.

* 반대 순서 집합: 부분 순서 집합 $(X, \le)$ 이 주어졌을 때, $X$ 위에 $x \ge y \iff y \le x \qquad (x, y \in X)$ 와 같이 정의된 새로운 부분 순서 $\ge$ 를 $(X, \le)$ 의 반대 순서 집합이라고 한다.
* 선형합: 전순서 집합 $(\{(X_i,\le_i)\}_{i\in I},\le)$ 이 주어졌을 때, 분리 합집합 $\textstyle\sqcup_{i\in I}X_i$ 위에 $x\le y\iff i 와 같이 정의된 부분 순서 \le 를$ 선형합이라고 한다.
* 직접곱: 부분 순서 집합의 족 $\{(X_i,\le_i)\}_{i\in I}$ 이 주어졌을 때, 곱집합 $\textstyle\prod_{i\in I}X_i$ 위에 $(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)$ 와 같이 정의된 부분 순서 $\le$ 를 $\{(X_i,\le_i)\}_{i\in I}$ 의 직접곱이라고 한다.
* 절대 부분 순서의 직접곱의 반사 폐포: 절대 부분 순서의 직접곱에 대응하는 부분 순서는 $(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$ 위에 $(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\}} 와 같이 정의된 이항 관계 \le 를$ [[사전식 순서]]라고 한다.

5.1. 반대 순서 집합

부분 순서 집합 $(X,\le)$ 이 주어졌을 때, $X$ 위에 다음과 같은 부분 순서 $\ge$ 를 정의할 수 있다.

: $x\ge y\iff y\le x\qquad(x,y\in X)$

이 경우, $(X,\ge)$ 를 $(X,\le)$ 의 반대 순서 집합이라고 한다.

부분 순서 관계 $R$ 의 쌍대(또는 반대) $R^{\text{op}}$ 는 $R$ 의 역관계로 설정하여 정의되며, 즉 $x R^{\text{op}} y$ 는 $y R x$ 인 경우에만 해당한다. 비엄격 부분 순서의 쌍대는 비엄격 부분 순서이며, 엄격 부분 순서의 쌍대는 엄격 부분 순서이다. 관계의 쌍대의 쌍대는 원래의 관계이다.

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

5.2. 선형합

부분 순서 집합의 전순서 집합 $(\{(X_i,\le_i)\}_{i\in I},\le)$ 이 주어졌을 때, 분리 합집합 $\textstyle\sqcup_{i\in I}X_i$ 위에 다음과 같은 부분 순서 $\le$ 를 정의할 수 있다.
: $x\le y\iff i$
이를 선형합(linear sum^영어)이라고 한다.

두 (상호소외적인) 부분 순서 집합을 결합하는 또 다른 방법은 순서 합 (또는 선형 합)이다. 이는 기본 집합 X와 Y의 합집합에서 다음 순서로 정의된다. a ≤_Z b는 다음의 경우에만 성립한다.

* a, b ∈ X이며 a ≤_X b, 또는
* a, b ∈ Y이며 a ≤_Y b, 또는
* a ∈ X이고 b ∈ Y.

두 부분 순서 집합이 전순서 집합이면, 그들의 순서 합도 전순서 집합이다.

5.3. 직접곱

부분 순서 집합의 족 $\{(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^영어)이라고 한다.

--
--
--

강도가 증가하는 순서, 즉 쌍의 집합이 감소하는 순서로, 두 개의 부분 순서 집합의 데카르트 곱에 대한 가능한 부분 순서 중 3개는 다음과 같다(그림 4 참조).

* 사전식 순서: (a, b) ≤ (c, d)는 a < c 이거나 (a = c 및 b ≤ d)인 경우이다.
* 곱 순서: (a, b) ≤ (c, d)는 a ≤ c이고 b ≤ d인 경우이다.
* 해당되는 엄격한 순서의 직접 곱의 반사적 폐포: (a, b) ≤ (c, d)는 (a < c 및 b < d)이거나 (a = c 및 b = d)인 경우이다.

세 가지 모두 두 개 이상의 집합의 데카르트 곱에 대해 유사하게 정의할 수 있다.

동일한 체에 대한 순서 벡터 공간에 적용하면 각 경우에도 순서 벡터 공간이 된다.

5.4. 절대 부분 순서의 직접곱의 반사 폐포

절대 부분 순서의 직접곱에 대응하는 부분 순서는 다음과 같다.

: $(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$

5.5. 사전식 순서

부분 순서 집합의 정렬 집합 $(\{(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\}}$

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

--
--
--

강도가 증가하는 순서(쌍의 집합이 감소하는 순서)로, 두 개의 부분 순서 집합의 데카르트 곱에 대한 가능한 부분 순서 중 3개는 다음과 같다(그림 4 참조).

* 사전식 순서: (a, b) ≤ (c, d)는 a < c 이거나 (a = c 이고 b ≤ d)인 경우이다.
* 곱 순서: (a, b) ≤ (c, d)는 a ≤ c이고 b ≤ d인 경우이다.
* 해당하는 엄격한 순서의 직접 곱의 반사적 폐포: (a, b) ≤ (c, d)는 (a < c 이고 b < d)이거나 (a = c 이고 b = d)인 경우이다.

세 가지 모두 두 개 이상의 집합의 데카르트 곱에 대해 유사하게 정의할 수 있다.

동일한 체에 대한 순서 벡터 공간에 적용하면 각 경우에도 순서 벡터 공간이 된다.

전순서 집합의 데카르트 곱에 대한 순서도 참조.

6. 성질

(주어진 원본 소스, 요약, 하위 섹션 내용이 모두 비어 있으므로, 작성할 내용이 없습니다.)

6.1. 부분 순서의 수

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

👆

좌우로 밀어서 보기

부분 순서의 수
n>\| 0 \|\| 1 \|\| 2 \|\| 3 \|\| 4 \|\| 5 \|\| 6 \|\| ...
\| 1 \|\| 1 \|\| 3 \|\| 19 \|\| 219 \|\| 4231 \|\| 130023 \|\| ...

👆

좌우로 밀어서 보기

부분 순서의 동형류의 수
n>\| 0 \|\| 1 \|\| 2 \|\| 3 \|\| 4 \|\| 5 \|\| 6 \|\| 7 \|\| 8 \|\| 9 \|\| 10 \|\| ...
\| 1 \|\| 1 \|\| 2 \|\| 5 \|\| 16 \|\| 63 \|\| 318 \|\| 2045 \|\| 16999 \|\| 183231 \|\| 2567284 \|\| ...

엄격한 부분 순서의 개수는 부분 순서의 개수와 같다.

7. 예

* 모든 전순서는 부분 순서이다. 예를 들어, 자연수, 정수, 유리수, 실수 집합 위의 표준적인 순서는 전순서이므로 부분 순서이다.
* 집합 $S$ 의 멱집합 위의 포함 관계는 부분 순서이며, $S$ 가 두 개 이상의 원소를 갖는다면 이는 전순서가 아니다.
* 군의 부분군들의 집합
* 벡터 공간의 부분 벡터 공간들의 집합
* 환의 아이디얼들의 집합
* 그래프의 부합들의 집합
* 부분수열에 의한 관계는 특정한 집합 위에서 부분 순서이다.
* 양의 정수의 집합 위의 약수 관계는 부분 순서이다.
* 비순환 유향그래프의 꼭짓점들의 집합은 도달가능성에 의한 부분 순서를 가진다.
* 부분 순서 집합의 수열 공간에 정의된 성분별 순서는 부분 순서이다.

8. 응용

컴퓨터 과학에서 위상 정렬은 방향 비순환 그래프의 도달성 순서로 표현되는 부분 순서의 선형 확장을 구하는 알고리즘이다.