정렬 원순서 집합

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

정의

정렬 원순서 집합

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

• 임의의 무한 열 $(x_i{)}_{i\in \mathbb{N}}\subseteq X$에 대하여, $i<j$이자 $x_i\lesssim x_j$인 $i,j\in \mathbb{N}$이 존재한다.틀:Rp
• 임의의 무한 열은 무한 증가 부분열을 갖는다. 즉, $(x_i{)}_{i\in \mathbb{N}}\subseteq X$에 대하여, $x_{f(0)}\lesssim x_{f(1)}\lesssim x_{f(2)}\lesssim \cdots$가 되는 증가 함수 $f:\mathbb{N}\to \mathbb{N}$가 존재한다.틀:Rp틀:Rp
• (유한 개의 극소 원소의 존재) 임의의 부분 집합 $S\subseteq X$에 대하여, 만약 $S\ne \varnothing$이라면, $S$는 (하나 이상의) 극소 원소들을 가지며, $S$의 극소 원소들의 동치류의 수는 유한하다.
• $𝒫(X)$ 위의 원순서 $S{\lesssim }^{\star }T⟺S\subseteq \downarrow T$를 정의하였을 때, 이항 관계 $S{\prec }^{\star }T⟺S{\lesssim }^{\star }T{\lesssim ̸}^{\star ̸}S$는 정초 관계이다.틀:Rp (여기서 $\downarrow$는 하폐포를 뜻한다.)
• 다음 두 조건이 성립한다.틀:Rp틀:Rp
  • $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$를 뜻한다.

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

• 임의의 열 $(x_i{)}_{i\in \mathbb{N}}\subseteq X$에 대하여, $i<j$이자 $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)$ 사이의 시뮬레이션(틀:Llang) $f:S\to T$는 다음 성질들을 만족시키는 함수이다.

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

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

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

성질

함의 관계

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

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

정렬 전순서 집합

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

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

정렬 원순서 집합

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

$x\lesssim y⟺\mathrm{\exists }i\in \{1,\dots ,n\}:(x\in X_i\wedge y\in X_i\wedge x{\lesssim }_{i}y)$

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

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

$(x_1,x_2,\dots ,x_n)\lesssim (y_i,y_2,\dots ,y_n)⟺(\mathrm{\forall }i\in \{1,\dots ,n\}:x_i\lesssim y_i)$

를 준다면, $({\prod }_{i=1}^n{X}_i,\lesssim )$ 역시 정렬 원순서 집합이다 (딕슨 보조 정리 틀:Llang).틀:Rp

증명:

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

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

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

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

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

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

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

정렬 정리

정렬 정리(整列定理, 틀:Llang)에 따르면, 모든 집합은 적어도 하나 이상의 정렬 전순서를 갖는다. (다만, 이 정렬 전순서는 구체적으로 명시하지 못할 수 있다.) 다시 말해, 임의의 크기를 갖는 순서수가 존재한다. 이를 통해, 임의의 집합 위에 초한 귀납법을 적용할 수 있다. 사실, 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}$에 대하여, $\bigcup _{i\in I}{X}_i$는 사슬의 상계이다. 따라서, $W(X)$의 모든 사슬은 상계를 갖는다.

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

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

$x\le y⟺(x,y\in \tilde{X}\wedge x{\le }_{\tilde{X}}y)\vee (y=x_0)$

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

$\tilde{X}<\{x_0\}\cup \tilde{X}$

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

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

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

$\min :𝒮\to \bigcup 𝒮$

$\min :S\in 𝒮\mapsto \min S$

는 $𝒮$ 위의 선택 함수이므로, 선택 공리는 참이다.

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

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

예

정렬 전순서 집합

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

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

$\alpha =\{\beta \in \mathrm{Ord}:\beta <\alpha \}$

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

문자열

원순서 집합 $(\mathrm{\Sigma },{\lesssim }_{\mathrm{\Sigma }})$ 위의 유한 문자열 집합 (클레이니 스타) ${\mathrm{\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 }_{\mathrm{\Sigma }}{t}_{f(i)}$

가 되는 단사 증가 함수

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

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

그래프

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

반례

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

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

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

역사

정렬 전순서 집합(틀:Llang)의 용어 및 개념은 1883년에 게오르크 칸토어가 순서수를 도입하기 위하여 정의하였다.틀:Rp 게오르크 칸토어는 정렬 정리가 증명이 필요없을 정도로 자명한 "사고 법칙"(틀:Llang)이라고 간주했지만, 이를 증명하지 않고 공리로 가정하였다. (칸토어는 선택 공리를 직접적으로 사용하지 않았다.) 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다.틀:Rp

1904년 8월의 하이델베르크 세계 수학자 대회에서 헝가리의 수학자 쾨니그 줄러(틀:Llang)는 정렬 정리를 반증하였다고 발표하였다.틀:Rp 그러나 몇 주 뒤 펠릭스 하우스도르프가 이 "반증"의 오류를 지적하였다.

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

1937년에 주로 쿠레파가 "부분 정렬 순서 집합"(틀:Llang)이라는 용어를 사용하였으나, 쿠레파는 무한 반사슬의 부재를 가정하지 않았다.틀:Rp틀:Rp 1952년에 그레이엄 히그먼(틀:Llang)은 정렬 부분 순서와 동치인 개념을 "유한 기저 성질"(틀:Llang)이라는 이름으로 도입하였고, 히그먼 보조 정리를 증명하였다.틀:Rp 같은 해에 에르되시 팔과 리하르트 라도(틀:Llang) 역시 한 논문에서 "부분 정렬 순서 집합"(틀:Llang)이라는 용어를 도입하였다.틀:Rp틀:Rp

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

각주

• 틀:웹 인용
• 틀:서적 인용
• 틀:서적 인용

외부 링크

• 틀:Eom
• 틀:Eom
• 틀:Eom
• 틀:Eom
• 틀:Eom
• 틀:매스월드
• 틀:매스월드
• 틀:Nlab
• 틀:Nlab
• 틀:Nlab
• 틀:Nlab
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용