전순서 집합

순서론에서 전순서 집합(全順序集合, 영어: 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$의 부분 집합과 순서 동형이다.^{:Theorem 4}

범주론적 성질

전순서 집합과 증가 함수는 구체적 범주 $\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,\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 )$에 대하여, 다음 네 조건이 동치이다.^{:Theorem 6}

• $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}$이라고 한다.^:228 크기 $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)은 다음 조건들을 만족시키는 전순서 집합이다.^{:43–44, Chapter 14}

• 크기가 $\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}$개의 전순서 집합들의 분리합집합과 순서 동형이다.

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

역사

가산 조밀 전순서 집합의 분류 정리^{:§9, 504–507} 와 분해 가능 완비 전순서 집합의 분류 정리^{:§11, 510–512}는 게오르크 칸토어가 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.