전순서 집합

순서론에서 전순서 집합(全順序集合, 영어: totally ordered set, toset)는 임의의 두 원소를 비교할 수 있는 부분 순서 집합이다. 실수에서는 순서를 줄 수 있지만 허수와 복소수에서는 순서를 줄 수 없다.

정의

원순서 집합 $(X,\lesssim )$이 다음 조건을 만족시킨다면, 원전순서 집합(原全順序集合, 영어: pretotally ordered set, totally preordered set, weakly ordered set)이라고 한다.

• 임의의 $x,y\in X$에 대하여, $x\lesssim y$이거나 $y\lesssim x$이다.

즉, 두 원소가 항상 비교 가능한 원순서 집합이다.

전순서 집합(全順序集合, 영어: totally ordered set, toset)은 원전순서 집합인 부분 순서 집합 $(X,\leq )$이다. 즉, 이항 관계 $\leq$는 다음 세 조건을 만족시킨다.

• (추이성) 만약 $x\leq y\leq z$라면 $x\leq z$
• (반대칭성) 임의의 $x,y\in X$에 대하여, 만약 $x\leq y$이며 $y\leq x$라면 $x=y$
• (완전성) 항상 $x\leq y$이거나 $y\leq x$

도약

전순서 집합 $(X,\leq )$의 도약(跳躍, 영어: jump) $(a,b)\in X^{2}$은 다음 두 조건을 만족시키는 순서쌍이다.

• $a<b$이다.
• $a<c<b$인 $c\in X$가 존재하지 않는다.

도약이 없는 전순서를 조밀 순서라고 한다.

성질

함의 관계

다음과 같은 함의 관계가 성립한다.

전순서 집합	⇒	원전순서 집합
⇓		⇓
부분 순서 집합	⇒	원순서 집합

연산

원순서 집합들의 족 $\{(X_{i},\lesssim _{i})\}_{i\in I}$가 주어졌으며, $I$에 역시 원순서 $\lesssim _{I}$가 부여되었다고 하자. 그렇다면, 분리합집합 $X=\textstyle \bigsqcup _{i\in I}X_{i}$ 위에 다음과 같은 원순서를 정의할 수 있다.

$x_{i}\lesssim y_{j}\iff \left((i\prec _{I}j)\lor \left(i=j\land x_{i}\lesssim _{i}y_{j}\right)\right)\qquad (x_{i}\in X_{i},\;y_{j}\in X_{j})$

이를 $\{(X_{i},\lesssim _{i})\}_{i\in I}$들의 순서합(영어: ordered sum)이라고 한다. (여기서 $i\prec _{I}j$는 $i\lesssim _{I}j\not \lesssim _{I}i$를 뜻하며, $i\sim _{I}j$는 $i\lesssim j\lesssim i$를 뜻한다.)

이에 대하여 다음이 성립한다.

• 만약 $(I,\lesssim _{I})$가 전순서 집합이며, 모든 $(X_{i},\lesssim _{i})$가 원전순서 집합이라면, 그 순서합 $X$ 역시 원전순서 집합이다.
• 만약 $(I,\lesssim _{I})$가 전순서 집합이며, 모든 $(X_{i},\lesssim _{i})$가 전순서 집합이라면, 그 순서합 $X$ 역시 전순서 집합이다.
• 만약 모든 $(X_{i},\lesssim _{i})$가 부분 순서 집합이라면, 그 순서합 $X$ 역시 부분 순서 집합이다.

사전식 순서

 이 부분의 본문은 사전식 순서입니다.

전순서 집합들의 족 $(X_{i},\leq _{i})_{i\in I}$이 주어졌으며, $I$ 위에 정렬 순서가 주어졌을 때, 곱집합 $\prod _{i\in I}X_{i}$ 위에 사전식 순서라는 전순서를 부여할 수 있다.

위상수학적 성질

 이 부분의 본문은 순서 위상입니다.

원전순서 집합에는 순서 위상을 부여하여 위상 공간으로 취급할 수 있다.

모든 원전순서 집합은 (순서 위상 아래) 완비 정규 공간이며, 모든 전순서 집합은 하우스도르프 완비 정규 공간이다.

전순서 집합에 대하여, 다음 두 조건이 서로 동치이다.

• 선형 연속체이다.
• 순서 위상을 가했을 때, 연결 공간이다.

완비 전순서 집합은 항상 콤팩트 공간이다.

전순서 집합의 부분 공간은 항상 직교 콤팩트 공간이자 가산 파라콤팩트 공간이다. 전순서 집합이 메타콤팩트 공간이라면, 파라콤팩트 공간이다.

모든 분해 가능 전순서 집합은 항상 사전식 순서를 준 $\mathbb {R} \times 2$의 부분 집합과 순서 동형이다.

범주론적 성질

전순서 집합과 증가 함수는 구체적 범주 $\operatorname {Toset}$를 이룬다. 이는 작은 범주의 범주 $\operatorname {Cat}$의 충만한 부분 범주이다.

공집합이 아닌 유한 전순서 집합들의 범주 $\triangle$는 단체 범주(單體範疇, 영어: simplex category)라고 하며, 그 위의 준층 범주 $\operatorname {PSh} (\triangle )$는 단체 집합이라고 한다. 이는 호모토피 이론에서 매우 중요하게 사용된다.

분류

모든 전순서 집합의 분류는 선택 공리를 추가한 체르멜로-프렝켈 집합론 속에서는 불가능하다. 예를 들어, 비교적 간단한 분류 문제인 수슬린 가설조차 증명하거나 반증할 수 없다. 그러나 특수한 경우에는 다음과 같은 분류 정리가 존재한다.

가산 조밀 전순서 집합

조밀 가산 전순서 집합 $(X,\leq )$은 다음 여섯 전순서 집합 가운데 정확히 하나와 순서 동형이다.

• 공집합
• 한원소 집합
• $\mathbb {Q}$ (유리수의 전순서 집합)
• $\{-\infty \}\sqcup \mathbb {Q}$. 이는 $\mathbb {Q} _{\geq 0}$과 순서 동형이다.
• $\mathbb {Q} \sqcup \{+\infty \}$. 이는 $\mathbb {Q} _{\leq 0}$과 순서 동형이다.
• $\mathbb {Q} \sqcup \{-\infty ,+\infty \}$. 이는 $\mathbb {Q} \cap [0,1]$과 순서 동형이다.

특히, 최대 원소와 최소 원소를 갖지 않는 조밀 가산 무한 전순서 집합 $(X,\leq )$은 항상 $\mathbb {Q}$와 순서 동형이다.

증명:

자명하게, 조밀 가산 전순서 집합은 항상 공집합이거나, 한원소 집합이거나, 가산 무한 집합이다. 자명하게, 조밀 가산 전순서 집합의 최대 원소와 최소 원소를 제거하여도 조밀 가산 전순서 집합이다. 따라서, 최대 원소와 최소 원소를 갖지 않는 조밀 가산 무한 전순서 집합이 서로 순서 동형임을 보이는 것으로 족하다.

최대 원소와 최소 원소를 갖지 않는 두 조밀 가산 무한 전순서 집합

$X=\{x_{0},x_{1},x_{2},\dots \}$

$Y=\{y_{0},y_{1},y_{2},\dots \}$

이 주어졌다고 하자. 그렇다면 순서 동형 $f\colon X\to Y$을 다음과 같이 정의할 수 있다. 먼저 $f\colon \varnothing \to \varnothing$로 놓자. 이제 $X$의 유한 부분 집합 $A$와 $Y$의 유한 부분 집합 $B$ 사이의 순서 동형 $f\colon A\to B$가 주어졌다고 하자. $x$가 $X\setminus A$의 원소 가운데 지표가 가장 작은 하나라고 하자. 그렇다면, $Y$의 조밀성에 따라 $f(x)$를 다음을 만족시키는 $Y\setminus B$의 원소 가운데 지표가 가장 작은 하나로 놓을 수 있다.

• 각 $a\in A$에 대하여, 만약 $x<a$라면 $f(x)<f(a)$
• 각 $a\in A$에 대하여, 만약 $x>a$라면 $f(x)>f(a)$

이는 $f$를 순서 동형 $f\colon A\cup \{x\}\to B\cup \{f(x)\}$으로 확장한다. 이 방법을 $f^{-1}\colon B\cup \{f(x)\}\to A\cup \{x\}$에 적용하면, 이 순서 동형을 다시 순서 동형 $f\colon A\cup \{x,f^{-1}(y)\}\to B\cup \{f(x),y\}$로 확장할 수 있다. 이를 반복하면 결국 $X$와 $Y$ 사이의 순서 동형을 얻는다.

완비 분해 가능 조밀 전순서 집합

전순서 집합 $(X,\leq )$가 다음 세 조건을 만족시킨다고 하자.

• $X$는 조밀 순서이다.
• $X$에 순서 위상을 가하면, $X$는 분해 가능 공간이다.
• (완비성) 상계와 하계를 갖는 임의의 부분 집합 $A\subseteq X$는 (만약 $A\neq \varnothing$이라면) 상한과 하한을 갖는다.

그렇다면, $X$는 다음 여섯 전순서 집합 가운데 정확히 하나와 순서 동형이다.

• 공집합
• 한원소 집합
• $\mathbb {R}$ (실수의 전순서 집합). 이는 $(0,1)$과 순서 동형이다.
• $\mathbb {R} \sqcup \{+\infty \}$. 이는 $(0,1]$과 순서 동형이다.
• $\mathbb {R} \sqcup \{-\infty \}$. 이는 $[0,1)$과 순서 동형이다.
• ${\bar {\mathbb {R} }}=\mathbb {R} \sqcup \{+\infty ,-\infty \}$ (확장된 실수). 이는 $[0,1]$과 순서 동형이다.

특히, 완비 분해 가능 조밀 무한 전순서 집합은 (순서 동형 아래) 확장된 실수의 전순서 집합 $({\overline {\mathbb {R} }},\leq )$ 밖에 없다.

증명:

$X$가 위 성질들을 만족시킨다고 하자. 분해 가능 공간의 정의에 의하여, 가산 조밀 집합 $D\subseteq X$을 찾을 수 있으며, $D$ 위의 순서는 조밀 순서임을 쉽게 알 수 있다. 따라서 $D$는 위와 같이 6개의 순서형 가운데 하나와 동형이며, $X$는 $D$의 데데킨트 완비화와 순서 동형이다.

마지막 조건을 약화시킬 경우, 이들의 분류는 수슬린 가설에 의하여 좌우되는데, 이는 선택 공리를 추가한 체르멜로-프렝켈 집합론과 독립적인 명제이다.

어떤 전순서 집합 $(X,\leq )$에 대하여, 다음 네 조건이 동치이다.

• $X$는 분해 가능 공간이며, 가산 개의 도약을 갖는다.
• 다음 조건을 만족시키는 가산 집합 $D\subseteq X$가 존재한다.
  • 임의의 $x\in X$에 대하여, $x=\sup\{d\in D\colon d\leq x\}$
• 다음 조건을 만족시키는 가산 집합 $D\subseteq X$가 존재한다.
  • 임의의 $x\in X$에 대하여, $x=\inf\{d\in D\colon d\geq x\}$
• $X$는 $\mathbb {R}$의 부분 집합과 순서 동형이다. 즉, 단사 단조 함수 $f\colon X\to \mathbb {R}$가 존재한다.

유한 집합 위의 (원)전순서

크기 3의 집합 $\{a,b,c\}$ 위에 존재할 수 있는 13개의 원전순서. 여기서 $a<b$는 $a\lesssim b\not \lesssim a$를 뜻한다. 이 가운데 맨 밖의, 검은 색 글씨의 6개는 전순서이다. 중간의, 푸른 색 글씨의 6개는 2개의 동치류들을 갖는 원전순서이다. 가운데의, 붉은 색 글씨의 1개는 1개의 동치류를 갖는 비이산 원순서이다.

유한 전순서 집합은 항상 정렬 집합이며, 따라서 그 크기에 따라 완전히 분류된다.

크기 $n$의 유한 집합 위의 원전순서들의 수는 푸비니 수(영어: Fubini number) $F_{n}$이라고 한다. 크기 $n$의 유한 집합 위의 전순서들의 수는 계승 $n!$이다. 이들의 값은 다음과 같다. ((OEIS의 수열 A670), (OEIS의 수열 A142)).

$n$	0	1	2	3	4	5	6	7
$F_{n}$	1	1	3	13	75	541	4683	47293
$n!$	1	1	2	6	24	120	720	5040

예

모든 순서체는 전순서 집합이다. 예를 들어, 실수체 $\mathbb {R}$, 유리수체 $\mathbb {Q}$ 등은 표준적인 순서를 부여하면 전순서 집합을 이룬다. 정수환 $\mathbb {Z}$나 자연수의 모노이드 $\mathbb {N}$ 역시 전순서 집합이다. 이들 집합 가운데, 자연수의 집합을 제외한 나머지는 정렬 집합이 아니다.

아론샤인 직선

아론샤인 직선(영어: Aronszajn line)은 다음 조건들을 만족시키는 전순서 집합이다.

• 크기가 $\aleph _{1}$이다.
• $\omega _{1}$ (최소 비가산 순서수)과 순서 동형인 부분 집합을 갖지 않는다.
• $\omega _{1}^{\operatorname {op} }$ ($\omega _{1}$의 반대 순서)와 순서 동형인 부분 집합을 갖지 않는다.
• $\mathbb {R}$의 비가산 부분 집합과 순서 동형인 부분 집합을 갖지 않는다.

아론샤인 직선의 존재는 선택 공리를 추가한 체르멜로-프렝켈 집합론만으로 보일 수 있다. 아론샤인 직선은 나흐만 아론샤인(폴란드어: Nachman Aronszajn, 1907~1980)이 도입하였다.

컨트리먼 직선

원순서 집합들의 족 $(X,\lesssim )_{i\in I}$이 주어졌을 때, 곱집합 $\textstyle \prod _{i\in I}X_{i}$ 위에 원순서

$x\lesssim y\iff \forall i\in I\colon x_{i}\lesssim y_{i}$

를 줄 수 있다. 마찬가지로, 분리합집합 $\textstyle \bigsqcup _{i\in I}X_{I}$ 위에 원순서

$x\lesssim y\iff \exists i\in I\colon x\in X_{i}\ni y\land x\lesssim _{i}y$

를 줄 수 있다.

컨트리먼 직선(영어: Countryman line)은 다음 조건을 만족시키는 전순서 집합 $(X,\leq )$이다.

• $X$의 집합의 크기는 $\aleph _{1}$이다.
• 임의의 양의 정수 $n$에 대하여, $X^{n}$은 $\aleph _{0}$개의 전순서 집합들의 분리합집합과 순서 동형이다.

컨트리먼 직선의 존재는 선택 공리를 추가한 체르멜로-프렝켈 집합론만으로 보일 수 있으며, 이는 사하론 셸라흐가 증명하였다.

역사

가산 조밀 전순서 집합의 분류 정리 와 분해 가능 완비 전순서 집합의 분류 정리는 게오르크 칸토어가 1895년에 증명하였다.

외부 링크

• “Totally ordered set” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Total order” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Totally ordered set” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• “Total order” (영어). 《nLab》. 
• “Linear order” (영어). 《nLab》. 
• “Definition: total ordering” (영어). 《ProofWiki》. 
• “Definition: totally ordered set” (영어). 《ProofWiki》. 
• “Are all sets totally ordered?” (영어). Math Overflow.