전순서 집합 문서 원본 보기

[[순서론]]에서 '''전순서 집합'''(全順序集合, {{llang|en|totally ordered set, toset}})는 임의의 두 [[원소 (수학)|원소]]를 비교할 수 있는 [[부분 순서 집합]]이다. [[실수]]에서는 순서를 줄 수 있지만 [[허수]]와 [[복소수]]에서는 순서를 줄 수 없다.

== 정의 ==
[[원순서 집합]] <math>(X,\lesssim)</math>이 다음 조건을 만족시킨다면, '''원전순서 집합'''(原全順序集合, {{llang|en|pretotally ordered set}}, {{lang|en|totally preordered set}}, {{lang|en|weakly ordered set}})이라고 한다.
* 임의의 <math>x,y\in X</math>에 대하여, <math>x\lesssim y</math>이거나 <math>y\lesssim x</math>이다.
즉, 두 원소가 항상 비교 가능한 [[원순서 집합]]이다.

'''전순서 집합'''(全順序集合, {{llang|en|totally ordered set}}, {{lang|en|toset}})은 원전순서 집합인 [[부분 순서 집합]] <math>(X,\le)</math>이다. 즉, [[이항 관계]] <math>\le</math>는 다음 세 조건을 만족시킨다.
* ([[추이적 관계|추이성]]) 만약 <math>x\le y\le z</math>라면 <math>x\le z</math>
* ([[반대칭 관계|반대칭성]])  임의의 <math>x,y\in X</math>에 대하여, 만약 <math>x\le y</math>이며 <math>y\le x</math>라면 <math>x=y</math>
* ([[완전 관계|완전성]]) 항상 <math>x\le y</math>이거나 <math>y\le x</math>

=== 도약 ===
전순서 집합 <math>(X,\le)</math>의 '''도약'''(跳躍, {{llang|en|jump}}) <math>(a,b)\in X^2</math>은 다음 두 조건을 만족시키는 [[순서쌍]]이다.
* <math>a<b</math>이다.
* <math>a<c<b</math>인 <math>c\in X</math>가 존재하지 않는다.
도약이 없는 전순서를 [[조밀 순서]]라고 한다.

== 성질 ==
=== 함의 관계 ===
다음과 같은 함의 관계가 성립한다.
:{| style="text-align: center"
| 전순서 집합 || ⇒ || 원전순서 집합
|-
| ⇓ || || ⇓
|-
| [[부분 순서 집합]] || ⇒ || [[원순서 집합]]
|}

=== 연산 ===
[[원순서 집합]]들의 족 <math>\{(X_i,\lesssim_i)\}_{i\in I}</math>가 주어졌으며, <math>I</math>에 역시 [[원순서]] <math>\lesssim_I</math>가 부여되었다고 하자. 그렇다면, [[분리합집합]] <math>X=\textstyle\bigsqcup_{i\in I}X_i</math> 위에 다음과 같은 원순서를 정의할 수 있다.
:<math>x_i\lesssim y_j\iff \left((i\prec_Ij)\lor\left(i=j\land x_i\lesssim_iy_j\right)\right)\qquad(x_i\in X_i,\;y_j\in X_j)</math>
이를 <math>\{(X_i,\lesssim_i)\}_{i\in I}</math>들의 '''순서합'''({{llang|en|ordered sum}})이라고 한다. (여기서 <math>i\prec_Ij</math>는 <math>i\lesssim_Ij\not\lesssim_Ii</math>를 뜻하며, <math>i\sim_Ij</math>는 <math>i\lesssim j\lesssim i</math>를 뜻한다.)

이에 대하여 다음이 성립한다.
* 만약 <math>(I,\lesssim_I)</math>가 전순서 집합이며, 모든 <math>(X_i,\lesssim_i)</math>가 원전순서 집합이라면, 그 순서합 <math>X</math> 역시 원전순서 집합이다.
* 만약 <math>(I,\lesssim_I)</math>가 전순서 집합이며, 모든 <math>(X_i,\lesssim_i)</math>가 전순서 집합이라면, 그 순서합 <math>X</math> 역시 전순서 집합이다.
* 만약 모든 <math>(X_i,\lesssim_i)</math>가 [[부분 순서 집합]]이라면, 그 순서합 <math>X</math> 역시 [[부분 순서 집합]]이다.

==== 사전식 순서 ====
{{본문|사전식 순서}}
[[전순서 집합]]들의 족 <math>(X_i,\le_i)_{i\in I}</math>이 주어졌으며, <math>I</math> 위에 [[정렬 순서]]가 주어졌을 때, 곱집합 <math>\prod_{i\in I}X_i</math> 위에 '''[[사전식 순서]]'''라는 전순서를 부여할 수 있다.

=== 위상수학적 성질 ===
{{본문|순서 위상}}
원전순서 집합에는 [[순서 위상]]을 부여하여 [[위상 공간 (수학)|위상 공간]]으로 취급할 수 있다.

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

전순서 집합에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* [[선형 연속체]]이다.
* [[순서 위상]]을 가했을 때, [[연결 공간]]이다.

[[완비 격자|완비]] 전순서 집합은 항상 [[콤팩트 공간]]이다.

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

모든 [[분해 가능 공간|분해 가능]] 전순서 집합은 항상 [[사전식 순서]]를 준 <math>\mathbb R\times2</math>의 부분 집합과 순서 동형이다.<ref name="Geschke"/>{{rp|Theorem 4}}

=== 범주론적 성질 ===
전순서 집합과 [[증가 함수]]는 [[구체적 범주]] <math>\operatorname{Toset}</math>를 이룬다. 이는 [[작은 범주]]의 범주 <math>\operatorname{Cat}</math>의 [[충만한 부분 범주]]이다.

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

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

=== 가산 조밀 전순서 집합 ===
[[조밀 순서|조밀]] [[가산 집합|가산]] 전순서 집합 <math>(X,\le)</math>은 다음 여섯 [[전순서 집합]] 가운데 정확히 하나와 순서 동형이다.
* [[공집합]]
* [[한원소 집합]]
* <math>\mathbb Q</math> ([[유리수]]의 전순서 집합)
* <math>\{-\infty\}\sqcup\mathbb Q</math>. 이는 <math>\mathbb Q_{\ge0}</math>과 순서 동형이다.
* <math>\mathbb Q\sqcup\{+\infty\}</math>. 이는 <math>\mathbb Q_{\le0}</math>과 순서 동형이다.
* <math>\mathbb Q\sqcup\{-\infty,+\infty\}</math>. 이는 <math>\mathbb Q\cap[0,1]</math>과 순서 동형이다.

특히, [[최대 원소]]와 [[최소 원소]]를 갖지 않는 [[분해 가능 공간|분해 가능]] [[조밀 순서|조밀]] [[가산 집합|가산]] 전순서 집합 <math>(X,\le)</math>은 항상 <math>\mathbb Q</math>와 순서 동형이다.

=== 완비 분해 가능 조밀 전순서 집합 ===
전순서 집합 <math>(X,\le)</math>가 다음 세 조건을 만족시킨다고 하자.
* <math>X</math>는 [[조밀 순서]]이다.
* <math>X</math>에 [[순서 위상]]을 가하면, <math>X</math>는 [[분해 가능 공간]]이다.
* (완비성) [[상계 (수학)|상계]]와 [[하계 (수학)|하계]]를 갖는 임의의 [[부분 집합]] <math>A\subseteq X</math>는 (만약 <math>A\ne\varnothing</math>이라면) [[상한]]과 [[하한]]을 갖는다.
그렇다면, <math>X</math>는 다음 여섯 전순서 집합 가운데 정확히 하나와 순서 동형이다.
* [[공집합]]
* [[한원소 집합]]
* <math>\mathbb R</math> ([[실수]]의 전순서 집합). 이는 <math>(0,1)</math>과 순서 동형이다.
* <math>\mathbb R\sqcup\{+\infty\}</math>. 이는 <math>(0,1]</math>과 순서 동형이다.
* <math>\mathbb R\sqcup\{-\infty\}</math>. 이는 <math>[0,1)</math>과 순서 동형이다.
* <math>\bar{\mathbb R}=\mathbb R\sqcup\{+\infty,-\infty\}</math> ([[확장된 실수]]). 이는 <math>[0,1]</math>과 순서 동형이다.
특히, [[완비 격자|완비]] [[분해 가능 공간|분해 가능]] [[조밀 순서|조밀]] [[무한 집합|무한]] 전순서 집합은 (순서 동형 아래) [[확장된 실수]]의 전순서 집합 <math>(\overline{\mathbb R},\le)</math> 밖에 없다.
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
<math>X</math>가 위 성질들을 만족시킨다고 하자. [[분해 가능 공간]]의 정의에 의하여, [[가산 집합|가산]] [[조밀 집합]] <math>D\subseteq X</math>을 찾을 수 있으며, <math>D</math> 위의 순서는 [[조밀 순서]]임을 쉽게 알 수 있다. 따라서 <math>D</math>는 위와 같이 6개의 순서형 가운데 하나와 동형이며, <math>X</math>는 <math>D</math>의 데데킨트 완비화와 순서 동형이다.
</div></div>

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

어떤 전순서 집합 <math>(X,\le)</math>에 대하여, 다음 네 조건이 동치이다.<ref name="Geschke">{{저널 인용|arxiv=1606.00338|제목=Separable linear orders and universality|이름=Stefan|성=Geschke|날짜=2016|bibcode=2016arXiv160600338G|언어=en}}</ref>{{rp|Theorem 6}}
* <math>X</math>는 [[분해 가능 공간]]이며, 가산 개의 도약을 갖는다.
* 다음 조건을 만족시키는 [[가산 집합]] <math>D\subseteq X</math>가 존재한다.
** 임의의 <math>x\in X</math>에 대하여, <math>x=\sup\{d\in D\colon d\le x\}</math>
* 다음 조건을 만족시키는 [[가산 집합]] <math>D\subseteq X</math>가 존재한다.
** 임의의 <math>x\in X</math>에 대하여, <math>x=\inf\{d\in D\colon d\ge x\}</math>
* <math>X</math>는 <math>\mathbb R</math>의 [[부분 집합]]과 순서 동형이다. 즉, [[단사 함수|단사]] [[단조 함수]] <math>f\colon X\to\mathbb R</math>가 존재한다.

=== 유한 집합 위의 (원)전순서 ===
[[파일:13-Weak-Orders.svg|섬네일|right|크기 3의 집합 <math>\{a,b,c\}</math> 위에 존재할 수 있는 13개의 원전순서. 여기서 <math>a<b</math>는 <math>a\lesssim b\not\lesssim a</math>를 뜻한다. 이 가운데 맨 밖의, 검은 색 글씨의 6개는 전순서이다. 중간의, 푸른 색 글씨의 6개는 2개의 [[동치류]]들을 갖는 원전순서이다. 가운데의, 붉은 색 글씨의 1개는 1개의 동치류를 갖는 비이산 원순서이다.]]
유한 전순서 집합은 항상 [[정렬 집합]]이며, 따라서 그 크기에 따라 완전히 분류된다.

크기 <math>n</math>의 [[유한 집합]] 위의 원전순서들의 수는 '''푸비니 수'''({{llang|en|Fubini number}}) <math>F_n</math>이라고 한다.<ref>{{서적 인용|이름=Louis|성=Comtet|제목=Advanced combinatorics: The art of finite and infinite expansions|출판사=Reidel Publishing Company|위치=Dordrecht|날짜=1974|zbl= 0283.05001|언어=en}}</ref>{{rp|228}} 크기 <math>n</math>의 유한 집합 위의 전순서들의 수는 [[계승 (수학)|계승]] <math>n!</math>이다. 이들의 값은 다음과 같다. ({{OEIS|A670}}, {{OEIS|A142}}).
{| class="wikitable" style="text-align: right"
|-
! <math>n</math>
| 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
! <math>F_n</math>
|  1 || 1 || 3 || 13 || 75 || 541 || 4683 || 47293
|-
! <math>n!</math>
| 1 || 1 || 2 || 6 || 24 || 120 || 720 || 5040
|}


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

=== 아론샤인 직선 ===
'''아론샤인 직선'''({{llang|en|Aronszajn line}})은 다음 조건들을 만족시키는 전순서 집합이다.<ref>{{서적 인용|제목=Discovering modern set theory II: set-theoretic tools for every mathematician|이름=Winfried|성=Just|이름2=Martin|성2=Weese|날짜=1997|출판사=American Mathematical Society|총서=Graduate Studies in Mathematics|isbn=978-0-8218-0528-2|권=18|url=http://bookstore.ams.org/gsm-18/|zbl=0887.03036|언어=en}}</ref>{{rp|43–44, Chapter 14}}
* [[집합의 크기|크기]]가 <math>\aleph_1</math>이다.
* <math>\omega_1</math> (최소 비가산 [[순서수]])과 순서 동형인 부분 집합을 갖지 않는다.
* <math>\omega_1^{\operatorname{op}}</math> (<math>\omega_1</math>의 반대 순서)와 순서 동형인 부분 집합을 갖지 않는다.
* <math>\mathbb R</math>의 [[비가산]] 부분 집합과 순서 동형인 부분 집합을 갖지 않는다.
아론샤인 직선의 존재는 [[선택 공리]]를 추가한 [[체르멜로-프렝켈 집합론]]만으로 보일 수 있다. 아론샤인 직선은 나흐만 아론샤인({{llang|pl|Nachman Aronszajn}}, 1907~1980)이 도입하였다.

=== 컨트리먼 직선 ===
원순서 집합들의 족 <math>(X,\lesssim)_{i\in I}</math>이 주어졌을 때, [[곱집합]] <math>\textstyle\prod_{i\in I}X_i</math> 위에 [[원순서]]
:<math>x\lesssim y\iff\forall i\in I\colon x_i\lesssim y_i</math>
를 줄 수 있다. 마찬가지로, [[분리합집합]] <math>\textstyle\bigsqcup_{i\in I}X_I</math> 위에 [[원순서]]
:<math>x\lesssim y\iff\exists i\in I\colon x\in X_i\ni y\land x\lesssim_iy</math>
를 줄 수 있다.

'''컨트리먼 직선'''({{llang|en|Countryman line}})은 다음 조건을 만족시키는 전순서 집합 <math>(X,\le)</math>이다.
* <math>X</math>의 [[집합의 크기]]는 <math>\aleph_1</math>이다.
* 임의의 양의 정수 <math>n</math>에 대하여, <math>X^n</math>은 <math>\aleph_0</math>개의 전순서 집합들의 [[분리합집합]]과 순서 동형이다.
컨트리먼 직선의 존재는 [[선택 공리]]를 추가한 [[체르멜로-프렝켈 집합론]]만으로 보일 수 있으며, 이는 [[사하론 셸라흐]]가 증명하였다.<ref>{{저널 인용|제목=Decomposing uncountable squares to countably many chains|저널=Journal of Combinatorial Theory Series A|issn=0097-3165|이름=Saharon|성=Shelah|저자링크=사하론 셸라흐|doi=10.1016/0097-3165(76)90053-4|권=21|호=1|날짜=1976-07|쪽=110–114|언어=en}}</ref>

== 역사 ==
가산 조밀 전순서 집합의 분류 정리<ref name="Cantor">{{저널 인용|성=Cantor |이름=Georg |저자링크=게오르크 칸토어|year=1895 |url=http://www.digizeitschriften.de/dms/resolveppn/?PID=GDZPPN00225557X |title=Beiträge zur Begründung der transfiniten Mengenlehre (Erster Artikel) |journal=Mathematische Annalen |volume=46 | 호=4 | pages=481–512 |doi=10.1007/bf02124929 | issn=0025-5831 | 언어=de }}</ref>{{rp|§9, 504–507}}
와 [[분해 가능 공간|분해 가능]] [[완비 격자|완비]] 전순서 집합의 분류 정리<ref name="Cantor"/>{{rp|§11, 510–512}}는 [[게오르크 칸토어]]가 1895년에 증명하였다.
== 각주 ==
{{각주}}

== 외부 링크 ==
{{위키공용분류|Weak ordering|원전순서}}
* {{eom|title=Totally ordered set}}
* {{매스월드|id=TotalOrder|title=Total order}}
* {{매스월드|id=TotallyOrderedSet|title=Totally ordered set}}
* {{nlab|id=total order|title=Total order}}
* {{nlab|id=linear order|title=Linear order}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Total_Ordering|제목=Definition: total ordering|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Totally_Ordered_Set|제목=Definition: totally ordered set|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=http://mathoverflow.net/questions/37272/are-all-sets-totally-ordered|제목=Are all sets totally ordered?|출판사=Math Overflow|언어=en}}

{{전거 통제}}
{{위키데이터 속성 추적}}

[[분류:순서론]]