정렬 원순서 집합

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

정의

정렬 원순서 집합

원순서 집합 $(X,\lesssim )$에 대하여 다음 다섯 조건들이 서로 동치이며, 이를 만족시키는 원순서 집합을 정렬 원순서 집합(整列原順序集合, 영어: well preordered set)이라고 한다.

• 임의의 무한 열 $(x_{i})_{i\in \mathbb {N} }\subseteq X$에 대하여, $i<j$이자 $x_{i}\lesssim x_{j}$인 $i,j\in \mathbb {N}$이 존재한다.^{:202, Definition 2.3}
• 임의의 무한 열은 무한 증가 부분열을 갖는다. 즉, $(x_{i})_{i\in \mathbb {N} }\subseteq X$에 대하여, $x_{f(0)}\lesssim x_{f(1)}\lesssim x_{f(2)}\lesssim \cdots$가 되는 증가 함수 $f\colon \mathbb {N} \to \mathbb {N}$가 존재한다.^{:Lemma 2.5(2):298}
• (유한 개의 극소 원소의 존재) 임의의 부분 집합 $S\subseteq X$에 대하여, 만약 $S\neq \varnothing$이라면, $S$는 (하나 이상의) 극소 원소들을 가지며, $S$의 극소 원소들의 동치류의 수는 유한하다.
• ${\mathcal {P}}(X)$ 위의 원순서 $S\lesssim ^{\star }T\iff S\subseteq \downarrow T$를 정의하였을 때, 이항 관계 $S\prec ^{\star }T\iff S\lesssim ^{\star }T\not \lesssim ^{\star }S$는 정초 관계이다.^{:116, Remark 5} (여기서 $\downarrow$는 하폐포를 뜻한다.)
• 다음 두 조건이 성립한다.^{:202, Lemma 2.4(2):298}
  • $X$ 속의 모든 반사슬은 유한 집합이다.
  • (내림 사슬 조건) $X$ 속의 모든 감소열 $x_{0}\gtrsim x_{1}\gtrsim x_{2}\gtrsim \cdots$에 대하여, 모든 $i,j\geq N$에 대하여 $x_{i}\sim x_{j}$가 되는 $N\in \mathbb {N}$이 존재한다.

여기서 $x\sim y$는 $x\lesssim y\lesssim x$를 뜻한다.

정렬 원순서 집합인 부분 순서 집합을 정렬 부분 순서 집합(整列部分順序集合, 영어: well partially ordered set)이라고 한다. 정렬 원순서 집합인 전순서 집합을 정렬 전순서 집합(整列全順序集合, 영어: well totally ordered set) 또는 정렬 집합(영어: well ordered set)이라고 한다. 즉, 전순서 집합 $(X,\leq )$에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 전순서 집합을 정렬 전순서 집합이라고 한다.

• 임의의 열 $(x_{i})_{i\in \mathbb {N} }\subseteq X$에 대하여, $i<j$이자 $x_{i}\leq x_{j}$인 $i,j\in \mathbb {N}$이 존재한다.
• 임의의 열 $(x_{i})_{i\in \mathbb {N} }\subseteq X$은 증가 부분열을 갖는다.
• (최소 원소의 존재) 임의의 부분 집합 $S\subseteq X$에 대하여, 만약 $S\neq \varnothing$이라면, $S$는 최소 원소를 갖는다.
• (내림 사슬 조건) $X$ 속의 모든 감소열 $x_{0}\geq x_{1}\geq x_{2}\geq \cdots$에 대하여, 모든 $i,j\geq N$에 대하여 $x_{i}\sim x_{j}$가 되는 $N\in \mathbb {N}$이 존재한다.
• 집합론적 나무를 이룬다.
• 어떤 순서수와 순서 동형이다.

시뮬레이션

두 정렬 원순서 집합 $(S,\lesssim _{S})$, $(T,\lesssim _{T})$ 사이의 시뮬레이션(영어: simulation) $f\colon S\to T$는 다음 성질들을 만족시키는 함수이다.

• (증가 함수) 만약 $s,s'\in S$에 대하여 $s\lesssim s'$라면, $f(s)\lesssim f(s')$이다.
• $f(S)\subseteq T$는 하집합이다. 즉, 임의의 $s\in S$ 및 $t\in T$에 대하여, 만약 $t\lesssim f(s)$라면 $f(s')=t$인 $s'\in S$가 존재한다.

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

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

성질

함의 관계

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

정렬 전순서 집합	⟹					정렬 원전순서 집합
	⇘				⇙
		전순서 집합	⇒	원전순서 집합
⇓		⇓		⇓		⇓
		부분 순서 집합	⇒	원순서 집합
	⇗				⇖
정렬 부분 순서 집합	⟹					정렬 원순서 집합

정렬 전순서 집합

정렬 전순서 집합 $(S,\leq )$의 부분 집합 $A\subset S$이 주어졌을 때, $(A,\leq )$ 역시 정렬 전순서 집합이다.

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

정렬 원순서 집합

정렬 원순서 집합들의 유한 족 $(X_{i},\lesssim _{i})_{i=1}^{n}$이 주어졌다고 하자. 그렇다면, 분리합집합 $\textstyle \bigsqcup _{i=1}^{n}X_{i}$ 위에 순서

$x\lesssim y\iff \exists i\in \{1,\dots ,n\}\colon (x\in X_{i}\land y\in X_{i}\land x\lesssim _{i}y)$

를 줄 수 있다. 이 역시 정렬 원순서 집합이다.

정렬 원순서 집합들의 유한 족 $(X_{i},\lesssim _{i})_{i=1}^{n}$이 주어졌다고 하자. 그렇다면, 곱집합 $\textstyle \prod _{i=1}^{n}X_{i}$ 위에 순서

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

를 준다면, $\textstyle (\prod _{i=1}^{n}X_{i},\lesssim )$ 역시 정렬 원순서 집합이다 (딕슨 보조 정리 영어: Dickson’s lemma).^{:203, Lemma 2.6}

증명:

수학적 귀납법을 통해 $n=2$인 경우를 증명하면 족하다. ($n=0$은 자명하다.) $X\times Y$ 속의 점렬 $(x_{k},y_{k})_{k=0}^{\infty }$이 주어졌다고 하자. 이제,

$(x_{f(k)})_{k=0}^{\infty }$

가 $(x_{k})_{k=0}^{\infty }$의 증가 부분열이라고 하자. 또한,

$(y_{f(g(k))})_{k=0}^{\infty }$

가 $(y_{f(k)})_{k=0}^{\infty }$의 증가 부분열이라고 하자. 그렇다면

$(x_{f(g(k))},y_{f(g(k))})_{k=0}^{\infty }$

는 $(x_{k},y_{k})_{k=0}^{\infty }$의 증가 부분열이다.

정렬 정리

정렬 정리(整列定理, 영어: well-ordering theorem)에 따르면, 모든 집합은 적어도 하나 이상의 정렬 전순서를 갖는다. (다만, 이 정렬 전순서는 구체적으로 명시하지 못할 수 있다.) 다시 말해, 임의의 크기를 갖는 순서수가 존재한다. 이를 통해, 임의의 집합 위에 초한 귀납법을 적용할 수 있다. 사실, 1차 논리의 체르멜로-프렝켈 집합론에서, 정렬 정리는 선택 공리 및 초른 보조정리와 서로 동치이다. 즉, 체르멜로-프렝켈 집합론의 공리들로, 이 셋 가운데 하나가 주어지면 나머지 둘을 증명할 수 있다.

증명 (초른 보조정리 ⇒ 정렬 정리):

임의의 집합 $X$가 주어졌다고 하자. $X$의 부분 집합들 위의 정렬 전순서 집합 $W(X)$를 생각하자. 여기에 다음과 같은 부분 순서를 주자.

• $(A,\leq _{A})\leq (B,\leq _{B})$는 $A\subset B$이며 또한 포함 사상 $A\hookrightarrow B$가 시뮬레이션인 것과 동치이다.

이에 따라 $W(X)$는 부분 순서 집합을 이룬다.

$W(X)$의 임의의 사슬 $\{(X_{i},\leq _{i})\}_{i\in I}$에 대하여, $\textstyle \bigcup _{i\in I}X_{i}$는 사슬의 상계이다. 따라서, $W(X)$의 모든 사슬은 상계를 갖는다.

따라서, 초른 보조정리에 따라 $W(X)$는 극대 원소 $({\tilde {X}},\leq _{\tilde {X}})\in W(X)$를 갖는다.

귀류법을 사용하여, 만약 ${\tilde {X}}\subsetneq X$라고 하자. 그렇다면 $x_{0}\in {\tilde {X}}\setminus X$가 존재하는데, 이 경우 ${\tilde {X}}\cup \{x_{0}\}$ 위에 다음과 같은 정렬 전순서를 줄 수 있다.

$x\leq y\iff (x,y\in {\tilde {X}}\land x\leq _{\tilde {X}}y)\lor (y=x_{0})$

즉, $x_{0}$이 ${\tilde {X}}$의 모든 원소보다 더 크다. 이 정렬 전순서를 주었을 때,

${\tilde {X}}<\{x_{0}\}\cup {\tilde {X}}$

이므로 ${\tilde {X}}$는 극대 원소일 수 없다. 즉, ${\tilde {X}}=X$이며, $\leq _{\tilde {X}}$는 $X$ 위의 정렬 전순서이다.

증명 (정렬 정리 ⇒ 선택 공리):

정렬 정리를 가정하자. 공집합이 아닌 집합들의 집합족 ${\mathcal {S}}$가 주어졌다고 하자. 정렬 정리를 사용하여, $\bigcup {\mathcal {S}}$에 정렬 전순서를 주자. 이 경우, 함수

$\min \colon {\mathcal {S}}\to \bigcup {\mathcal {S}}$

$\min \colon S\in {\mathcal {S}}\mapsto \min S$

는 ${\mathcal {S}}$ 위의 선택 함수이므로, 선택 공리는 참이다.

폰 노이만-베르나이스-괴델 집합론이나 모스-켈리 집합론과 같은, 모임을 다루는 이론에서는 모든 모임이 정렬 전순서를 갖는지에 대하여 생각할 수 있다. (선택 공리를 제외한) 이들 체계에서는 다음 두 조건이 서로 동치이다.

• 모든 모임은 정렬 전순서를 갖는다.
• (대역적 선택 공리 영어: axiom of global choice) 공집합이 아닌 집합들을 원소로 하는 모든 모임은 선택 함수를 갖는다.

예

정렬 전순서 집합

모든 유한 원순서 집합은 (자명하게) 정렬 원순서 집합을 이룬다.^:203 특히, 자연수 집합의 표준적인 전순서는 정렬 전순서이다.

보다 일반적으로, 임의의 순서수 $\alpha$보다 작은 순서수들의 집합

$\alpha =\{\beta \in \operatorname {Ord} \colon \beta <\alpha \}$

는 정렬 전순서 집합이다. 모든 순서수의 고유 모임 $\operatorname {Ord}$ (또는 그 임의의 부분 모임)의 표준적인 전순서는 정렬 전순서이다. 선택 공리를 가정할 경우, 기수의 고유 모임의 표준적인 전순서 역시 정렬 전순서이며, 이 사실은 알레프 수의 정의의 기반을 이룬다.

문자열

원순서 집합 $(\Sigma ,\lesssim _{\Sigma })$ 위의 유한 문자열 집합 (클레이니 스타) $\Sigma ^{*}$ 위에 다음과 같은 부분 문자열 관계를 주자. 즉, $s=s_{0}s_{1}\cdots s_{m-1}$과 $t=t_{0}t_{1}\cdots t_{n-1}$에 대하여, $s\ll t$이라는 것은

$s_{i}\lesssim _{\Sigma }t_{f(i)}$

가 되는 단사 증가 함수

$f\colon \{0,1,\dots ,m-1\}\to \{0,1,\dots ,n-1\}$

가 존재함을 뜻한다. 이는 원순서이며, 만약 $\lesssim _{\Sigma }$가 부분 순서라면 부분 문자열 관계는 부분 순서이다. 히그먼 보조 정리(영어: Higman’s lemma)에 따르면, $(\Sigma ^{*},\ll )$는 정렬 원순서 집합을 이룬다.^{:204, Theorem 3.2}

그래프

(무향) 유한 그래프들의 가산 무한 집합은 그래프 마이너 관계에 대하여 원순서 집합을 이룬다. 로버트슨-시모어 정리(영어: Robertson–Seymour theorem)에 따르면, 이는 정렬 원순서 집합이다.

반례

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

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

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

역사

정렬 전순서 집합(독일어: wohlgeordnete Menge 볼게오르드네테 멩게^[*])의 용어 및 개념은 1883년에 게오르크 칸토어가 순서수를 도입하기 위하여 정의하였다.^{:548, §2} 게오르크 칸토어는 정렬 정리가 증명이 필요없을 정도로 자명한 "사고 법칙"(독일어: Denkgesetz 뎅크게제츠^[*])이라고 간주했지만, 이를 증명하지 않고 공리로 가정하였다. (칸토어는 선택 공리를 직접적으로 사용하지 않았다.) 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다.^{:Chapter 1}

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

1904년에 에른스트 체르멜로는 선택 공리를 도입하였고, 이를 통해 정렬 정리를 증명하였다.

1937년에 주로 쿠레파가 "부분 정렬 순서 집합"(프랑스어: ensemble partiellement bien ordonné)이라는 용어를 사용하였으나, 쿠레파는 무한 반사슬의 부재를 가정하지 않았다.^:1197:299 1952년에 그레이엄 히그먼(영어: Graham Higman)은 정렬 부분 순서와 동치인 개념을 "유한 기저 성질"(영어: finite basis property)이라는 이름으로 도입하였고, 히그먼 보조 정리를 증명하였다.^:300 같은 해에 에르되시 팔과 리하르트 라도(독일어: Richard Rado) 역시 한 논문에서 "부분 정렬 순서 집합"(영어: partially well ordered set)이라는 용어를 도입하였다.^:256:300

현재까지도, 많은 수학자들은 정렬 정리가 직관적이지 않다고 여긴다. 그러나 이와 동치인 선택 공리는 대체로 더 직관적이라고 여겨진다. 미국의 수학자 제리 로이드 보나(영어: Jerry Lloyd Bona, 1945~)는 1977년에 이에 대하여 다음과 같이 농담하였다.

“	선택 공리는 당연히 참이고, 정렬 정리는 당연히 거짓이고, 초른 보조정리는 글쎄……? The Axiom of Choice is obviously true; the Well Ordering principle is obviously false; and who can tell about Zorn’s lemma?	”
	— :145, §6.21

각주

• Schmitz, Sylvain; Schnoebelen, Philippe (2012). “Algorithmic aspects of WQO theory” (영어). 
• Herrlich, Horst (2006). 《Axiom of Choice》. Lecture Notes in Mathematics (영어) 1876. Springer. ISBN 3-540-30989-6. 
• Howard, Paul; Jean E. Rubin (1998). 《Consequences of the axiom of choice》. Mathematical Surveys and Monographs (영어) 59. American Mathematical Society. ISBN 9780821809778. 

외부 링크

• “Well-ordered set”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Order type”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Zermelo theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Well-founded relation”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Partially ordered set”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Well ordered set”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Order type”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Well-order”. 《nLab》 (영어). 
• “Well-quasi-order”. 《nLab》 (영어). 
• “Well-ordering theorem”. 《nLab》 (영어). 
• “Well-founded relation”. 《nLab》 (영어). 
• “Definition: well-ordered set”. 《ProofWiki》 (영어). 
• “Definition: well-founded”. 《ProofWiki》 (영어). 2015년 6월 19일에 원본 문서에서 보존된 문서. 2016년 7월 14일에 확인함. 
• “Definition: well-ordering”. 《ProofWiki》 (영어). 
• “Definition: foundational relation”. 《ProofWiki》 (영어).