정렬 원순서 집합

순서론과 집합론에서 **정렬 원순서 집합**(整列原順序集合, 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이자 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\ne\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는 정초 관계이다.언어=en116, Remark 5 (여기서 \downarrow는 하폐포를 뜻한다.) * 다음 두 조건이 성립한다.202, Lemma 2.4(2)언어=en298 ** X 속의 모든 반사슬은 유한 집합이다. ** (내림 사슬 조건) X 속의 모든 감소열 x_0\gtrsim x_1\gtrsim x_2\gtrsim\cdots에 대하여, 모든 i,j\ge N에 대하여 x_i\sim x_j가 되는 N\in\mathbb N이 존재한다. 여기서 x\sim y는 x\lesssim y\lesssim x를 뜻한다. 증명 첫 번째 조건 ⇒ 세 번째 조건: S\subseteq X가 공집합이 아니며, 극소 원소를 갖지 않는다고 가정하자. 극소 원소의 정의에 따라, :s_0>s_1>s_2>\cdots 인 무한 열 (s_i)_{i\in\mathbb N}\subseteq S가 존재한다. 이제, S\subseteq X가 공집합이 아니며, 극소 원소들의 동치류의 수가 무한하다고 하자. 그렇다면, 서로 동치가 아닌 가산 무한 개의 극소 원소 s_0,s_1,\dots\in S들을 고를 수 있다. 임의의 자연수 i에 대하여, s_i\nsim s_j이며, s_j가 극소 원소이므로 s_i\not\lesssim s_j이다. 세 번째 조건 ⇒ 다섯 번째 조건: 임의의 반사슬 S\subseteq X에 대하여, S의 모든 원소는 극소 원소이며, 서로 동치가 아니다. 가정에 따라, S는 유한 집합이다. 임의의 감소열 x_0\lesssim x_1\lesssim x_2\lesssim\cdots에 대하여, 가정에 따라 그 극소 원소 x_N이 존재하며, 이 경우 :x_N\sim x_{N+1}\sim\cdots 이다. 다섯 번째 조건 ⇒ 첫 번째 조건: 귀류법을 사용하여, 임의의 자연수 i에 대하여 x_i\not\lesssim x_j인 무한 열 (x_i)_{i\in\mathbb N}\subseteq X가 존재한다고 가정하자. :I=\\{i\in\mathbb N\colon\forall j>i\colon x_i\not\gtrsim x_j\\} 라고 하자. \\{x_i\\}_{i\in I}가 반사슬이며, i\mapsto x_i가 단사 함수이므로, I는 유한 집합이다. f(0)>\max I라고 하자. I의 정의에 따라, :x_{f(0)}\gtrsim x_{f(1)}\gtrsim x_{f(2)}\gtrsim\cdots :f(0) 인 함수 f\colon\mathbb N\to\mathbb N이 존재하며, 귀류법의 가정에 따라 :x_{f(0)}>x_{f(1)}>x_{f(2)}>\cdots 이다. 이는 모순이다. 첫 번째 조건 ⇒ 두 번째 조건: 임의의 무한 열 (x_i)_{i\in\mathbb N}\subseteq X이 주어졌다고 하자. :I=\\{i\in\mathbb N\colon\forall j>i\colon x_i\not\lesssim x_j\\} 라고 하자. 만약 I가 무한 집합이라면, \\{x_i\\}_{i\in I}가 무한 집합이거나, 어떤 x_i가 무한한 수의 i\in I에 대응한다. 어떤 경우에도, i이며 x_i\lesssim x_j인 i,j\in I가 존재하며, 이는 I의 정의와 모순이다. 따라서, I는 유한 집합이다. f(0)>\max I라고 하자. I의 정의에 따라, :x_{f(0)}\lesssim x_{f(1)}\lesssim x_{f(2)}\lesssim\cdots :f(0) 인 함수 f\colon\mathbb N\to\mathbb N이 존재한다. 두 번째 조건 ⇒ 첫 번째 조건: 자명하다. 첫 번째 조건 ⇒ 네 번째 조건: 만약 S_0>^*S_1>^*S_2>^*\cdots라면, :s_i\in S_i\setminus{\downarrow S_{i+1 인 무한 열 (s_i)_{i\in\mathbb N}를 고를 수 있다. 임의의 자연수 i에 대하여, s_i\not\in{\downarrow S_{i+1이며 {\downarrow S_{i+1\supseteq S_j이므로, s_i\not\lesssim s_j이다. 네 번째 조건 ⇒ 첫 번째 조건: 만약 임의의 자연수 i에 대하여 x_i\not\lesssim x_j인 무한 열 (x_i)_{i\in\mathbb N}\subseteq X가 존재한다면, :\\{x_0,x_1,x_2,\dots\\}>^*\\{x_1,x_2,\dots\\}>^*\cdots 이다. 증명 끝 정렬 원순서 집합인 부분 순서 집합을 **정렬 부분 순서 집합**(整列部分順序集合, well partially ordered set)이라고 한다. 정렬 원순서 집합인 전순서 집합을 **정렬 전순서 집합**(整列全順序集合, well totally ordered set) 또는 **정렬 집합**(well ordered set)이라고 한다. 즉, 전순서 집합 (X,\le)에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 전순서 집합을 **정렬 전순서 집합**이라고 한다. * 임의의 열 (x_i)_{i\in\mathbb N}\subseteq X에 대하여, i이자 x_i\le x_j인 i,j\in\mathbb N이 존재한다. * 임의의 열 (x_i)_{i\in\mathbb N}\subseteq X은 증가 부분열을 갖는다. * (최소 원소의 존재) 임의의 부분 집합 S\subseteq X에 대하여, 만약 S\ne\varnothing이라면, S는 최소 원소를 갖는다. * (내림 사슬 조건) X 속의 모든 감소열 x_0\ge x_1\ge x_2\ge\cdots에 대하여, 모든 i,j\ge 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)이라고 한다. 순서수는 각 순서형의 표준적인 대표원을 제공한다.
# 성질

## 함의 관계
다음과 같은 함의 관계가 성립한다. :{| | 정렬 전순서 집합 | colspan=5 | ⟹ ||정렬 원전순서 집합 |- |- | || ⇘ | colspan=3 | || ⇙ |- | || || 전순서 집합 || ⇒ || 원전순서 집합 |- | ⇓ || || ⇓ || || ⇓ || || ⇓ |- | || || 부분 순서 집합 || ⇒ || 원순서 집합 |- | || ⇗ | colspan=3 | || ⇖ |- | 정렬 부분 순서 집합 | colspan=5 | ⟹ ||정렬 원순서 집합 |}
## 정렬 전순서 집합
정렬 전순서 집합 (S,\le)의 부분 집합 A\subset S이 주어졌을 때, (A,\le) 역시 정렬 전순서 집합이다. 서로 동형인 두 정렬 전순서 집합은 같은 집합의 크기를 갖는다. 반대로, 집합의 크기가 같은 두 유한 정렬 전순서 집합은 서로 동형이다. 반면, 집합의 크기가 같지만 서로 다른 무한 정렬 전순서 집합이 존재한다. 예를 들어, 순서수 \omega에 대응하는 정렬 전순서 집합과 순서수 \omega+1에 대응하는 정렬 전순서 집합은 서로 동형이지 않다.
## 정렬 원순서 집합
정렬 원순서 집합들의 유한 족 (X_i,\lesssim_i)_{i=1}^n이 주어졌다고 하자. 그렇다면, 분리합집합 \textstyle\bigsqcup_{i=1}^nX_i 위에 순서 :x\lesssim y\iff\exists i\in\\{1,\dots,n\\}\colon(x\in X_i\land y\in X_i\land x\lesssim_iy) 를 줄 수 있다. 이 역시 정렬 원순서 집합이다. 정렬 원순서 집합들의 유한 족 (X_i,\lesssim_i)_{i=1}^n이 주어졌다고 하자. 그렇다면, 곱집합 \textstyle\prod_{i=1}^nX_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}^nX_i,\lesssim) 역시 정렬 원순서 집합이다 (**딕슨 보조 정리** Dickson’s lemma).언어=en203, 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,\le_A)\le(B,\le_B)는 A\subset B이며 또한 포함 사상 A\hookrightarrow B가 시뮬레이션인 것과 동치이다. 이에 따라 W(X)는 부분 순서 집합을 이룬다. W(X)의 임의의 사슬 \\{(X_i,\le_i)\\}_{i\in I}에 대하여, \textstyle\bigcup_{i\in I}X_i는 사슬의 상계이다. 따라서, W(X)의 모든 사슬은 상계를 갖는다. 따라서, 초른 보조정리에 따라 W(X)는 극대 원소 (\tilde X,\le_{\tilde X})\in W(X)를 갖는다. 귀류법을 사용하여, 만약 \tilde X\subsetneq X라고 하자. 그렇다면 x_0\in\tilde X\setminus X가 존재하는데, 이 경우 \tilde X\cup\\{x_0\\} 위에 다음과 같은 정렬 전순서를 줄 수 있다. :x\le y\iff(x,y\in\tilde X\land x\le_{\tilde X}y)\lor(y=x_0) 즉, x_0이 \tilde X의 모든 원소보다 더 크다. 이 정렬 전순서를 주었을 때, :\tilde X<\\{x_0\\}\cup\tilde X 이므로 \tilde X는 극대 원소일 수 없다. 즉, \tilde X=X이며, \le_{\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_0s_1\cdots s_{m-1}과 t=t_0t_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)는 정렬 원순서 집합을 이룬다.언어=en204, Theorem 3.2
## 그래프
(무향) 유한 그래프들의 가산 무한 집합은 그래프 마이너 관계에 대하여 원순서 집합을 이룬다. **로버트슨-시모어 정리**(Robertson–Seymour theorem)에 따르면, 이는 정렬 원순서 집합이다.언어=en
## 반례
순서체 K(예를 들어, 유리수체나 실수체)는 정렬 전순서 집합이 될 수 없다. 모든 순서체는 \mathbb Z를 부분환으로 포함하는데, 이 경우 \mathbb Z 전체는 최소 원소를 갖지 않기 때문이다. 마찬가지로, 자명환이 아닌 순서환은 항상 정렬 전순서 집합이 될 수 없다. 순서체 K에서, 음이 아닌 원소들의 전순서 집합 K_{\ge0} 역시 정렬 전순서 집합이 될 수 없다. 이는 K_{\ge0}는 양의 유리수들의 집합 \mathbb Q^+을 포함하는데, 이는 최소 원소를 갖지 않기 때문이다. 양의 정수의 집합에 약수 관계 (\mathbb Z^+,\mid)를 부여하면, 이는 부분 순서 집합이지만 정렬 부분 순서 집합이 아니다. 이는 소수의 집합은 무한 반사슬을 이루기 때문이다.
# 역사
정렬 전순서 집합(볼게오르드네테 멩게)의 용어 및 개념은 1883년에 게오르크 칸토어가 순서수를 도입하기 위하여 정의하였다.언어=de548, §2 게오르크 칸토어는 정렬 정리가 증명이 필요없을 정도로 자명한 "사고 법칙"(뎅크게제츠)이라고 간주했지만, 이를 증명하지 않고 공리로 가정하였다. (칸토어는 선택 공리를 직접적으로 사용하지 않았다.) 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다.언어=enChapter 1 1904년 8월의 하이델베르크 세계 수학자 대회에서 헝가리의 수학자 쾨니그 줄러(Kőnig Gyula)는 정렬 정리를 반증하였다고 발표하였다.86, §2.1 그러나 몇 주 뒤 펠릭스 하우스도르프가 이 "반증"의 오류를 지적하였다. 1904년에 에른스트 체르멜로는 선택 공리를 도입하였고, 이를 통해 정렬 정리를 증명하였다.언어=de 1937년에 주로 쿠레파가 "부분 정렬 순서 집합"(ensemble partiellement bien ordonné)이라는 용어를 사용하였으나, 쿠레파는 무한 반사슬의 부재를 가정하지 않았다.언어=fr1197299 1952년에 그레이엄 히그먼(Graham Higman)은 정렬 부분 순서와 동치인 개념을 "유한 기저 성질"(finite basis property)이라는 이름으로 도입하였고, 히그먼 보조 정리를 증명하였다.언어=en300 같은 해에 에르되시 팔과 리하르트 라도(Richard Rado) 역시 한 논문에서 "부분 정렬 순서 집합"(partially well ordered set)이라는 용어를 도입하였다.언어=en256300 현재까지도, 많은 수학자들은 정렬 정리가 직관적이지 않다고 여긴다. 그러나 이와 동치인 선택 공리는 대체로 더 직관적이라고 여겨진다. 미국의 수학자 제리 로이드 보나(Jerry Lloyd Bona, 1945~)는 1977년에 이에 대하여 다음과 같이 농담하였다. 145, §6.21