정렬 원순서 집합 문서 원본 보기

{{위키데이터 속성 추적}}
[[순서론]]과 [[집합론]]에서 '''정렬 원순서 집합'''(整列原順序集合, {{llang|en|well preordered set, well quasiordered set}})은 모든 부분 집합이 양의 정수 개의 [[극소 원소]] [[동치류]]를 갖는 [[원순서 집합]]이다. 정렬 원순서 집합 위에서는 [[초한 귀납법]]이 가능하다. 정렬 원순서 집합 가운데 [[전순서 집합]]인 것 (즉, 모든 부분 집합이 [[최소 원소]]를 갖는 [[전순서 집합]])을 '''정렬 전순서 집합'''(整列全順序集合, {{llang|en|well (totally) ordered set, woset}}) 또는 단순히 '''정렬 집합'''(整列集合)이라고 한다. 이들의 동형류는 [[순서수]]를 이룬다.

== 정의 ==
=== 정렬 원순서 집합 ===
[[원순서 집합]] <math>(X,\lesssim)</math>에 대하여 다음 다섯 조건들이 서로 [[동치]]이며, 이를 만족시키는 원순서 집합을 '''정렬 원순서 집합'''(整列原順序集合, {{llang|en|well preordered set}})이라고 한다.
* 임의의 무한 열 <math>(x_i)_{i\in\mathbb N}\subseteq X</math>에 대하여, <math>i<j</math>이자 <math>x_i\lesssim x_j</math>인 <math>i,j\in\mathbb N</math>이 존재한다.<ref name="Gallier"/>{{rp|202, Definition 2.3}}
* 임의의 무한 열은 무한 증가 부분열을 갖는다. 즉, <math>(x_i)_{i\in\mathbb N}\subseteq X</math>에 대하여, <math>x_{f(0)}\lesssim x_{f(1)}\lesssim x_{f(2)}\lesssim\cdots</math>가 되는 [[증가 함수]] <math>f\colon\mathbb N\to\mathbb N</math>가 존재한다.<ref name="Gallier"/>{{rp|Lemma 2.5(2)}}<ref name="Kruskal"/>{{rp|298}}
* (유한 개의 극소 원소의 존재) 임의의 [[부분 집합]] <math>S\subseteq X</math>에 대하여, 만약 <math>S\ne\varnothing</math>이라면, <math>S</math>는 (하나 이상의) [[극소 원소]]들을 가지며, <math>S</math>의 [[극소 원소]]들의 [[동치류]]의 수는 유한하다.
* <math>\mathcal P(X)</math> 위의 [[원순서]] <math>S\lesssim^\star T\iff S\subseteq\downarrow T</math>를 정의하였을 때, [[이항 관계]] <math>S\prec^\star T\iff S\lesssim^\star T\not\lesssim^\star S</math>는 [[정초 관계]]이다.<ref>{{저널 인용|성=Forster|이름=Thomas|날짜=2003|제목=Better-quasi-orderings and coinduction|저널=Theoretical Computer Science|권=309|호=1–3|쪽=111–123|doi=10.1016/S0304-3975(03)00131-2|issn=0304-3975|언어=en}}</ref>{{rp|116, Remark 5}} (여기서 <math>\downarrow</math>는 [[하폐포]]를 뜻한다.)
* 다음 두 조건이 성립한다.<ref name="Gallier"/>{{rp|202, Lemma 2.4(2)}}<ref name="Kruskal">{{저널 인용 | last=Kruskal |first= Joseph B. | title=The theory of well-quasi-ordering: a frequently discovered concept | journal=Journal of Combinatorial Theory Series A | 날짜=1972-11 | volume=13 | 호=3 | pages=297–305 | doi=10.1016/0097-3165(72)90063-5 | zbl=0244.06002 | 언어=en}}</ref>{{rp|298}}
** <math>X</math> 속의 모든 [[반사슬]]은 [[유한 집합]]이다.
** ([[내림 사슬 조건]]) <math>X</math> 속의 모든 감소열 <math>x_0\gtrsim x_1\gtrsim x_2\gtrsim\cdots</math>에 대하여, 모든 <math>i,j\ge N</math>에 대하여 <math>x_i\sim x_j</math>가 되는 <math>N\in\mathbb N</math>이 존재한다.
여기서 <math>x\sim y</math>는 <math>x\lesssim y\lesssim x</math>를 뜻한다.

정렬 원순서 집합인 [[부분 순서 집합]]을 '''정렬 부분 순서 집합'''(整列部分順序集合, {{llang|en|well partially ordered set}})이라고 한다. 정렬 원순서 집합인 [[전순서 집합]]을 '''정렬 전순서 집합'''(整列全順序集合, {{llang|en|well totally ordered set}}) 또는 '''정렬 집합'''({{llang|en|well ordered set}})이라고 한다. 즉, [[전순서 집합]] <math>(X,\le)</math>에 대하여 다음 조건들이 서로 [[동치]]이며, 이를 만족시키는 전순서 집합을 '''정렬 전순서 집합'''이라고 한다.
* 임의의 열 <math>(x_i)_{i\in\mathbb N}\subseteq X</math>에 대하여, <math>i<j</math>이자 <math>x_i\le x_j</math>인 <math>i,j\in\mathbb N</math>이 존재한다.
* 임의의 열 <math>(x_i)_{i\in\mathbb N}\subseteq X</math>은 증가 부분열을 갖는다.
* ([[최소 원소]]의 존재) 임의의 [[부분 집합]] <math>S\subseteq X</math>에 대하여, 만약 <math>S\ne\varnothing</math>이라면, <math>S</math>는 [[최소 원소]]를 갖는다.
* ([[내림 사슬 조건]]) <math>X</math> 속의 모든 감소열 <math>x_0\ge x_1\ge x_2\ge\cdots</math>에 대하여, 모든 <math>i,j\ge N</math>에 대하여 <math>x_i\sim x_j</math>가 되는 <math>N\in\mathbb N</math>이 존재한다.
* [[나무 (집합론)|집합론적 나무]]를 이룬다.
* 어떤 [[순서수]]와 순서 동형이다.

=== 시뮬레이션 ===
두 정렬 원순서 집합 <math>(S,\lesssim_S)</math>, <math>(T,\lesssim_T)</math> 사이의 '''시뮬레이션'''({{llang|en|simulation}}) <math>f\colon S\to T</math>는 다음 성질들을 만족시키는 [[함수]]이다.
* ([[증가 함수]]) 만약 <math>s,s'\in S</math>에 대하여 <math>s\lesssim s'</math>라면, <math>f(s)\lesssim f(s')</math>이다.
* <math>f(S)\subseteq T</math>는 [[하집합]]이다. 즉, 임의의 <math>s\in S</math> 및 <math>t\in T</math>에 대하여, 만약 <math>t\lesssim f(s)</math>라면 <math>f(s')=t</math>인 <math>s'\in S</math>가 존재한다.

정렬 전순서 집합과 시뮬레이션들의 [[범주 (수학)|범주]]는 [[순서수]]의 [[얇은 범주]]와 [[범주의 동치|동치]]이다.

정렬 전순서의 '''동형'''은 정렬 전순서와 시뮬레이션의 범주에서의 동형이다. 이 동형에 대한 [[동치류]]를 '''순서형'''(順序型, {{llang|en|order type}})이라고 한다. [[순서수]]는 각 순서형의 표준적인 대표원을 제공한다.

== 성질 ==
=== 함의 관계 ===
다음과 같은 함의 관계가 성립한다.
:{| style="text-align: center"
| 정렬 전순서 집합
| colspan=5 | ⟹ ||정렬 원전순서 집합
|-
|-
| || ⇘
| colspan=3 | || ⇙
|-
| || || [[전순서 집합]] || ⇒ || 원전순서 집합
|-
| ⇓ || || ⇓ || || ⇓ || || ⇓
|-
| || || [[부분 순서 집합]] || ⇒ || [[원순서 집합]]
|-
| || ⇗
| colspan=3 | || ⇖
|-
| 정렬 부분 순서 집합
| colspan=5 | ⟹ ||정렬 원순서 집합
|}

=== 정렬 전순서 집합 ===
정렬 전순서 집합 <math>(S,\le)</math>의 부분 집합 <math>A\subset S</math>이 주어졌을 때, <math>(A,\le)</math> 역시 정렬 전순서 집합이다.

서로 동형인 두 정렬 전순서 집합은 같은 [[집합의 크기]]를 갖는다. 반대로, [[집합의 크기]]가 같은 두 유한 정렬 전순서 집합은 서로 동형이다. 반면, 집합의 크기가 같지만 서로 다른 무한 정렬 전순서 집합이 존재한다. 예를 들어, [[순서수]] <math>\omega</math>에 대응하는 정렬 전순서 집합과 [[순서수]] <math>\omega+1</math>에 대응하는 정렬 전순서 집합은 서로 동형이지 않다.

=== 정렬 원순서 집합 ===
정렬 원순서 집합들의 유한 족 <math>(X_i,\lesssim_i)_{i=1}^n</math>이 주어졌다고 하자. 그렇다면, [[분리합집합]] <math>\textstyle\bigsqcup_{i=1}^nX_i</math> 위에 순서
:<math>x\lesssim y\iff\exists i\in\{1,\dots,n\}\colon(x\in X_i\land y\in X_i\land x\lesssim_iy)</math>
를 줄 수 있다. 이 역시 정렬 원순서 집합이다.

정렬 원순서 집합들의 유한 족 <math>(X_i,\lesssim_i)_{i=1}^n</math>이 주어졌다고 하자. 그렇다면, [[곱집합]] <math>\textstyle\prod_{i=1}^nX_i</math> 위에 순서
:<math>(x_1,x_2,\dots,x_n)\lesssim(y_i,y_2,\dots,y_n)\iff\left(\forall i\in\{1,\dots,n\}\colon x_i\lesssim y_i\right)</math>
를 준다면, <math>\textstyle(\prod_{i=1}^nX_i,\lesssim)</math> 역시 정렬 원순서 집합이다 ('''딕슨 보조 정리''' {{llang|en|Dickson’s lemma}}).<ref>{{저널 인용|이름=L. E.|성=Dickson|저자링크=레너드 유진 딕슨|제목=Finiteness of the odd perfect and primitive abundant numbers with ''n'' distinct prime factors|저널= American Journal of Mathematics|권=35|호=4|날짜=1913-10|쪽=413–422|jstor=2370405|doi=10.2307/2370405|언어=en}}</ref><ref name="Gallier"/>{{rp|203, Lemma 2.6}}
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
[[수학적 귀납법]]을 통해 <math>n=2</math>인 경우를 증명하면 족하다. (<math>n=0</math>은 자명하다.) <math>X\times Y</math> 속의 점렬 <math>(x_k,y_k)_{k=0}^\infty</math>이 주어졌다고 하자. 이제,
:<math>(x_{f(k)})_{k=0}^\infty</math>
가 <math>(x_k)_{k=0}^\infty</math>의 증가 부분열이라고 하자. 또한,
:<math>(y_{f(g(k))})_{k=0}^\infty</math>
가 <math>(y_{f(k)})_{k=0}^\infty</math>의 증가 부분열이라고 하자. 그렇다면
:<math>(x_{f(g(k))},y_{f(g(k))})_{k=0}^\infty</math>
는 <math>(x_k,y_k)_{k=0}^\infty</math>의 증가 부분열이다.
</div></div>

=== 정렬 정리 ===
'''정렬 정리'''(整列定理, {{llang|en|well-ordering theorem}})에 따르면, 모든 집합은 적어도 하나 이상의 정렬 전순서를 갖는다. (다만, 이 정렬 전순서는 구체적으로 명시하지 못할 수 있다.) 다시 말해, 임의의 [[집합의 크기|크기]]를 갖는 [[순서수]]가 존재한다. 이를 통해, 임의의 집합 위에 [[초한 귀납법]]을 적용할 수 있다. 사실, [[1차 논리]]의 [[체르멜로-프렝켈 집합론]]에서, 정렬 정리는 [[선택 공리]] 및 [[초른 보조정리]]와 서로 [[동치]]이다. 즉, [[체르멜로-프렝켈 집합론]]의 공리들로, 이 셋 가운데 하나가 주어지면 나머지 둘을 증명할 수 있다.
<div class="mw-collapsible mw-collapsed toccolours">
'''증명 ([[초른 보조정리]] ⇒ 정렬 정리):'''
<div class="mw-collapsible-content">
임의의 집합 <math>X</math>가 주어졌다고 하자. <math>X</math>의 [[부분 집합]]들 위의 정렬 전순서 집합 <math>W(X)</math>를 생각하자. 여기에 다음과 같은 [[부분 순서]]를 주자.
* <math>(A,\le_A)\le(B,\le_B)</math>는 <math>A\subset B</math>이며 또한 포함 사상 <math>A\hookrightarrow B</math>가 시뮬레이션인 것과 동치이다.
이에 따라 <math>W(X)</math>는 [[부분 순서 집합]]을 이룬다.

<math>W(X)</math>의 임의의 [[사슬 (순서론)|사슬]] <math>\{(X_i,\le_i)\}_{i\in I}</math>에 대하여, <math>\textstyle\bigcup_{i\in I}X_i</math>는 사슬의 [[상계]]이다. 따라서, <math>W(X)</math>의 모든 사슬은 [[상계]]를 갖는다.

따라서, [[초른 보조정리]]에 따라 <math>W(X)</math>는 [[극대 원소]] <math>(\tilde X,\le_{\tilde X})\in W(X)</math>를 갖는다.

[[귀류법]]을 사용하여, 만약 <math>\tilde X\subsetneq X</math>라고 하자. 그렇다면 <math>x_0\in\tilde X\setminus X</math>가 존재하는데, 이 경우 <math>\tilde X\cup\{x_0\}</math> 위에 다음과 같은 정렬 전순서를 줄 수 있다.
:<math>x\le y\iff(x,y\in\tilde X\land x\le_{\tilde X}y)\lor(y=x_0)</math>
즉, <math>x_0</math>이 <math>\tilde X</math>의 모든 원소보다 더 크다. 이 정렬 전순서를 주었을 때,
:<math>\tilde X<\{x_0\}\cup\tilde X</math>
이므로 <math>\tilde X</math>는 [[극대 원소]]일 수 없다. 즉, <math>\tilde X=X</math>이며, <math>\le_{\tilde X}</math>는 <math>X</math> 위의 정렬 전순서이다.
</div></div>
<div class="mw-collapsible mw-collapsed toccolours">
'''증명 (정렬 정리 ⇒ [[선택 공리]]):'''
<div class="mw-collapsible-content">
정렬 정리를 가정하자. [[공집합]]이 아닌 집합들의 [[집합족]] <math>\mathcal S</math>가 주어졌다고 하자. 정렬 정리를 사용하여, <math>\bigcup\mathcal S</math>에 정렬 전순서를 주자. 이 경우, 함수
:<math>\min\colon\mathcal S\to\bigcup\mathcal S</math>
:<math>\min\colon S\in\mathcal S\mapsto \min S</math>
는 <math>\mathcal S</math> 위의 선택 함수이므로, [[선택 공리]]는 참이다.
</div></div>

[[폰 노이만-베르나이스-괴델 집합론]]이나 [[모스-켈리 집합론]]과 같은, [[모임 (집합론)|모임]]을 다루는 이론에서는 모든 [[모임 (집합론)|모임]]이 정렬 전순서를 갖는지에 대하여 생각할 수 있다. ([[선택 공리]]를 제외한) 이들 체계에서는 다음 두 조건이 서로 동치이다.
* 모든 [[모임 (집합론)|모임]]은 정렬 전순서를 갖는다.
* (대역적 선택 공리 {{llang|en|axiom of global choice}}) 공집합이 아닌 [[집합]]들을 원소로 하는 모든 [[모임 (집합론)|모임]]은 선택 함수를 갖는다.

== 예 ==
=== 정렬 전순서 집합 ===
모든 [[유한 집합|유한]] [[원순서 집합]]은 (자명하게) 정렬 원순서 집합을 이룬다.<ref name="Gallier"/>{{rp|203}} 특히, [[자연수]] 집합의 표준적인 전순서는 [[자연수의 정렬성|정렬 전순서]]이다.

보다 일반적으로, 임의의 순서수 <math>\alpha</math>보다 작은 [[순서수]]들의 집합
:<math>\alpha=\{\beta\in\operatorname{Ord}\colon\beta<\alpha\}</math>
는 정렬 전순서 집합이다. 모든 [[순서수]]의 [[고유 모임]] <math>\operatorname{Ord}</math> (또는 그 임의의 부분 모임)의 표준적인 전순서는 정렬 전순서이다. [[선택 공리]]를 가정할 경우, [[기수 (수학)|기수]]의 [[고유 모임]]의 표준적인 전순서 역시 정렬 전순서이며, 이 사실은 [[알레프 수]]의 정의의 기반을 이룬다.

=== 문자열 ===
[[원순서 집합]] <math>(\Sigma,\lesssim_\Sigma)</math> 위의 유한 문자열 집합 ([[클레이니 스타]]) <math>\Sigma^*</math> 위에 다음과 같은 '''부분 문자열 관계'''를 주자. 즉, <math>s=s_0s_1\cdots s_{m-1}</math>과 <math>t=t_0t_1\cdots t_{n-1}</math>에 대하여, <math>s\ll t</math>이라는 것은
:<math>s_i\lesssim_\Sigma t_{f(i)}</math>
가 되는 [[단사 함수|단사]] [[증가 함수]]
:<math>f\colon\{0,1,\dots,m-1\}\to\{0,1,\dots,n-1\}</math>
가 존재함을 뜻한다. 이는 [[원순서]]이며, 만약 <math>\lesssim_\Sigma</math>가 [[부분 순서]]라면 부분 문자열 관계는 [[부분 순서]]이다. '''히그먼 보조 정리'''({{llang|en|Higman’s lemma}})에 따르면, <math>(\Sigma^*,\ll)</math>는 정렬 원순서 집합을 이룬다.<ref name="Higman"/><ref name="Gallier">{{저널 인용|제목=What’s so special about Kruskal’s theorem and the ordinal Γ<sub>0</sub>? A survey of some results in proof theory|doi=10.1016/0168-0072(91)90022-E|이름=Jean H.|성=Gallier|저널=Annals of Pure and Applied Logic|권=53|호=3|날짜=1991-09-19|쪽=199–260|언어=en}}</ref>{{rp|204, Theorem 3.2}}

=== 그래프 ===
(무향) 유한 [[그래프]]들의 [[가산 무한 집합]]은 [[그래프 마이너]] 관계에 대하여 [[원순서 집합]]을 이룬다. '''로버트슨-시모어 정리'''({{llang|en|Robertson–Seymour theorem}})에 따르면, 이는 정렬 원순서 집합이다.<ref>{{저널 인용|제목=Graph minors XX. Wagner’s conjecture|저널=Journal of Combinatorial Theory Series B|이름=Neil|성=Robertson|이름2=P. D.|성2=Seymour|doi=10.1016/j.jctb.2004.08.001|날짜=2004-11|권=92|호=2|쪽=325–357|언어=en}}</ref>

=== 반례 ===
[[순서체]] <math>K</math>(예를 들어, [[유리수체]]나 [[실수체]])는 정렬 전순서 집합이 될 수 없다. 모든 순서체는 <math>\mathbb Z</math>를 부분환으로 포함하는데, 이 경우 <math>\mathbb Z</math> 전체는 최소 원소를 갖지 않기 때문이다. 마찬가지로, [[자명환]]이 아닌 [[순서환]]은 항상 정렬 전순서 집합이 될 수 없다.

[[순서체]] <math>K</math>에서, 음이 아닌 원소들의 [[전순서 집합]] <math>K_{\ge0}</math> 역시 정렬 전순서 집합이 될 수 없다. 이는 <math>K_{\ge0}</math>는 양의 유리수들의 집합 <math>\mathbb Q^+</math>을 포함하는데, 이는 [[최소 원소]]를 갖지 않기 때문이다.

양의 정수의 집합에 [[약수]] 관계 <math>(\mathbb Z^+,\mid)</math>를 부여하면, 이는 [[부분 순서 집합]]이지만 정렬 부분 순서 집합이 아니다. 이는 [[소수 (수론)|소수]]의 집합은 무한 [[반사슬]]을 이루기 때문이다.

== 역사 ==
정렬 전순서 집합({{llang|de|wohlgeordnete Menge|볼게오르드네테 멩게}})의 용어 및 개념은 1883년에 게오르크 칸토어가 [[순서수]]를 도입하기 위하여 정의하였다.<ref>{{저널 인용 | 이름=Georg |성=Cantor |저자링크=게오르크 칸토어| title=Ueber unendliche, lineare Punktmannichfaltigkeiten 5 | journal=Mathematische Annalen | volume=21 | number=4 | pages=545–591 | url=http://resolver.sub.uni-goettingen.de/purl?GDZPPN002247461 | 날짜=1883 | doi=10.1007/bf01446819 | jfm=15.0452.03 | 언어=de }}</ref>{{rp|548, §2}} [[게오르크 칸토어]]는 정렬 정리가 증명이 필요없을 정도로 자명한 "사고 법칙"({{llang|de|Denkgesetz|뎅크게제츠}})이라고  간주했지만, 이를 증명하지 않고 공리로 가정하였다. (칸토어는 [[선택 공리]]를 직접적으로 사용하지 않았다.) 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다.<ref name="Moore">{{서적 인용|last1=Moore|first1=Gregory H.|title=Zermelo’s axiom of choice: its origins, development, and influence|날짜=1982|isbn=978-0-486-48841-7|출판사=Springer-Verlag|총서=Studies in the History of Mathematics and Physical Sciences|권=8|issn=0172-570X|isbn=978-1-4613-9480-8|doi=10.1007/978-1-4613-9478-5|언어=en}}</ref>{{rp|Chapter 1}}

1904년 8월의 [[하이델베르크]] [[세계 수학자 대회]]에서 헝가리의 수학자 [[쾨니그 줄러]]({{llang|hu|Kőnig Gyula}})는 정렬 정리를 반증하였다고 발표하였다.<ref name="Moore"/>{{rp|86, §2.1}} 그러나 몇 주 뒤 [[펠릭스 하우스도르프]]가 이 "반증"의 오류를 지적하였다.

1904년에 [[에른스트 체르멜로]]는 [[선택 공리]]를 도입하였고, 이를 통해 정렬 정리를 증명하였다.<ref>{{저널 인용|이름=Ernst|성=Zermelo|저자링크=에른스트 체르멜로|제목=Beweis, daß jede Menge wohlgeordnet werden kann. (Aus einem an Herrn Hilbert gerichteten Briefe)|저널=Mathematische Annalen|권=59|호=4|쪽=514–516|날짜=1904|url=http://resolver.sub.uni-goettingen.de/purl?GDZPPN002260018|doi=10.1007/BF01445300|issn=0025-5831|jfm=35.0088.03|언어=de}}</ref>

1937년에 [[주로 쿠레파]]가 "부분 정렬 순서 집합"({{llang|fr|ensemble partiellement bien ordonné}})이라는 용어를 사용하였으나, 쿠레파는 무한 [[반사슬]]의 부재를 가정하지 않았다.<ref>{{저널 인용|이름=Georges|성=Kurepa|저자링크=주로 쿠레파|제목=Théorie des ensembles|저널=Comptes rendus hebdomadaires des séances de l’Académie des Sciences|권=205|날짜=1937-12-13|쪽=1196–1198|url=http://gallica.bnf.fr/ark:/12148/bpt6k3157c/f1195.item|zbl=63.0834.01|언어=fr}}</ref>{{rp|1197}}<ref name="Kruskal"/>{{rp|299}} 1952년에 그레이엄 히그먼({{llang|en|Graham Higman}})은 정렬 부분 순서와 동치인 개념을 "유한 기저 성질"({{llang|en|finite basis property}})이라는 이름으로 도입하였고, 히그먼 보조 정리를 증명하였다.<ref name="Higman">{{저널 인용|이름=Graham|성=Higman|제목=Ordering by divisibility in abstract algebras|저널=Proceedings of the London Mathematical Society|권=2|호=1|날짜=1952|쪽=326–336|doi=10.1112/plms/s3-2.1.326|zbl=0047.03402 |언어=en}}</ref><ref name="Kruskal"/>{{rp|300}} 같은 해에 [[에르되시 팔]]과 리하르트 라도({{llang|de|Richard Rado}}) 역시 한 논문에서 "부분 정렬 순서 집합"({{llang|en|partially well ordered set}})이라는 용어를 도입하였다.<ref>{{저널 인용|성=Erdös|이름=Paul|저자링크=에르되시 팔|성2=Rado|이름2=Richard|제목=Sets having a divisor property|저널=American Mathematical Monthly|권=59|쪽=255-257|날짜=1952-04|doi=10.2307/2306526|jstor=2306526|언어=en}}</ref>{{rp|256}}<ref name="Kruskal"/>{{rp|300}}

현재까지도, 많은 수학자들은 정렬 정리가 직관적이지 않다고 여긴다. 그러나 이와 [[동치]]인 [[선택 공리]]는 대체로 더 직관적이라고 여겨진다. 미국의 수학자 제리 로이드 보나({{llang|en|Jerry Lloyd Bona}}, 1945~)는 1977년에 이에 대하여 다음과 같이 농담하였다.
{{인용문2|[[선택 공리]]는 당연히 참이고, 정렬 정리는 당연히 거짓이고, [[초른 보조정리]]는 글쎄……?<br>
{{lang|en|The Axiom of Choice is obviously true; the Well Ordering principle is obviously false; and who can tell about Zorn’s lemma?}}|<ref>{{서적 인용|제목=Handbook of analysis and its foundations|이름=Eric|성=Schechter|url=http://www.math.vanderbilt.edu/~schectex/ccc/|doi=10.1016/B978-0-12-622760-4.50033-9|출판사=Academic Press|날짜=1997|zbl=0943.26001|언어=en|확인날짜=2016-07-14|보존url=https://web.archive.org/web/20150307061351/http://www.math.vanderbilt.edu/%7Eschectex/ccc/|보존날짜=2015-03-07|url-status=dead}}</ref>{{rp|145, §6.21}}}}

== 각주 ==
{{각주}}
* {{웹 인용|url=https://cel.archives-ouvertes.fr/cel-00727025v2/document|제목=Algorithmic aspects of WQO theory|이름=Sylvain|성=Schmitz|이름2=Philippe|성2=Schnoebelen|url=https://cel.archives-ouvertes.fr/cel-00727025/|날짜=2012|언어=en}}
* {{서적 인용|last=Herrlich |first=Horst|title=Axiom of Choice |publisher=Springer |날짜=2006 |총서=Lecture Notes in Mathematics|권= 1876 |isbn=3-540-30989-6|언어=en}}
* {{서적 인용|성=Howard|이름=Paul|공저자=Jean E. Rubin|title=Consequences of the axiom of choice|날짜=1998|publisher=American Mathematical Society|총서=Mathematical Surveys and Monographs|volume=59|isbn=9780821809778|언어=en}}

== 외부 링크 ==
* {{eom|title=Well-ordered set}}
* {{eom|title=Order type}}
* {{eom|title=Zermelo theorem}}
* {{eom|title=Well-founded relation}}
* {{eom|title=Partially ordered set}}
* {{매스월드|id=WellOrderedSet|title=Well ordered set}}
* {{매스월드|id=OrderType|title=Order type}}
* {{nlab|id=well-order|title=Well-order}}
* {{nlab|id=well-quasi-order|title=Well-quasi-order}}
* {{nlab|id=well-ordering theorem|title=Well-ordering theorem}}
* {{nlab|id=well-founded relation|title=Well-founded relation}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Well-Ordered_Set|제목=Definition: well-ordered set|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Well-Founded|제목=Definition: well-founded|웹사이트=ProofWiki|언어=en|확인날짜=2016-07-14|archive-date=2015-06-19|archive-url=https://web.archive.org/web/20150619163918/https://proofwiki.org/wiki/Definition:Well-Founded}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Well-Ordering|제목=Definition: well-ordering|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Foundational_Relation|제목=Definition: foundational relation|웹사이트=ProofWiki|언어=en}}

[[분류:기초관계]]
[[분류:순서론]]
[[분류:집합론]]