순서수

$\omega ^{\omega }$ 이하의 순서수들의 형상화

집합론에서 순서수(順序數, 영어: ordinal) 또는 서수(序數)는 정렬 전순서 집합들의 "길이"를 측정하는 수의 일종이다. 자연수를 확장하며, 자연수들의 정렬 전순서 집합과 같은 무한 정렬 전순서 집합들의 크기를 측정하는 무한 순서수들이 존재한다.

자연수는 집합의 크기를 표현하기 위해 사용되기도 하고, 열에서 원소의 위치를 나타내기 위해 사용되기도 한다. 이 두 쓰임새는 유한 집합의 경우 크게 다르지 않으나, 무한 집합의 경우에는 이 구분이 중요해진다. 전자를 확장한 것이 기수이고, 후자를 확장한 것이 순서수이다.

기수는 아무런 구조도 갖지 않는 집합에 대해서도 부여할 수 있지만, 순서수는 정렬 전순서 집합에 대해서만 정의되며, 정렬 전순서의 개념과 순서수의 개념에는 매우 밀접한 관련이 있다. 간단히 말해, 정렬 전순서란 무한히 감소하는 수열이 존재하지 않는 전순서를 말한다. (물론 무한히 증가하는 수열은 존재할 수 있다.) 임의의 전순서 집합에서 최소 원소를 0이라 하고 그 다음 원소를 1이라 하는 식으로 그 집합의 원소들을 순서수를 이용해 순서매길 수 있으며, 이 집합의 "길이"를 여기에서 집합의 원소에 대응되지 않는 가장 작은 순서수로 정의할 수 있다. 이 "길이"를 집합의 순서형이라고 한다.

정의

동치류를 이용한 정의

기수를 모든 집합의 전단사 함수에 대한 동치류로 정의할 수 있는 것처럼, 순서수는 모든 정렬 전순서 집합의 순서 동형에 대한 동치류로 정의할 수 있다. 그러나 이러한 정의에 따르면 각 순서수는 체르멜로-프렝켈 집합론에서는 집합이 아니며, 고유 모임이 되므로 기술적으로 문제가 있다. (예를 들어, 순서수의 모임 $\operatorname {Ord}$는 고유 모임들을 원소를 가져야 하므로 정의할 수 없다.)

유형 이론이나 윌러드 밴 오먼 콰인의 새 기초(New Foundations)등에서는 이 정의가 문제가 되지 않는다. 이 정의는 유형 이론을 사용하는 《수학 원리》에 등장한다.

폰 노이만 정의

집합론적 문제를 피하기 위해, 정렬 전순서 집합의 순서 동형 동치류의 대표원을 다음과 같이 고를 수 있다. 이 정의는 존 폰 노이만이 제시하였고, 오늘날 표준적인 정의다. 선택 공리를 추가한 체르멜로-프렝켈 집합론을 가정하면, 추이적 집합 $S$에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 추이적 집합을 순서수라고 한다.

• $(S,\subseteq )$는 전순서 집합을 이룬다. 즉, 임의의 $a,b\in S$에 대하여, $a\in b$이거나 $b\in a$이거나 $a=b$이다.
• $(S,\subseteq )$는 정렬 전순서 집합을 이룬다.^{:19, Definition 2.10}
• $S$의 모든 원소는 추이적 집합이다.

폰 노이만 정의에서는 순서수 $\alpha$와 $\beta$에 대하여 다음 두 조건이 서로 동치이다.

• $\alpha \in \beta$
• $\alpha \subsetneq \beta$

이를 $\alpha <\beta$로 표기하고, $\alpha \not <\beta$를 $\alpha \geq \beta$로 표기한다. 즉, 순서수 $\alpha$는 그보다 작은 모든 순서수들의 집합이다.

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

이 순서에 따라, 모든 순서수는 정렬 전순서 집합이며, 반대로 모든 정렬 전순서 집합이 정확히 하나의 순서수와 순서 동형이라는 것은 초한 귀납법을 이용해 보일 수 있다.

마찬가지로, 모든 순서수의 모임 $\operatorname {Ord}$는 정렬 전순서 모임을 이룬다. 이 덕분에 순서수에 대해 초한 귀납법을 자유로이 사용할 수 있다.

연산

순서수들에 대해 덧셈 · 곱셈 · 거듭제곱 연산을 정의하는 것이 가능하다. 각 연산은 연산 결과에 해당하는 정렬 전순서 집합을 직접 만들어내는 방법으로 정의할 수도 있고, 초한 귀납법을 이용해 정의할 수도 있다. 유한 순서수의 경우, 순서수로서의 연산은 기수로서의 연산 및 자연수로서의 연산과 일치한다. 무한 순서수의 경우, 순서수의 연산은 극한 기수로서의 연산과 현저히 다르다.

두 정렬 전순서 집합 $(S,\leq )$와 $(T,\leq )$가 주어졌다고 하고, $S$의 순서형이 $\alpha$, $T$의 순서형이 $\beta$라고 하자. (폰 노이만 정의에서는 $S=\alpha$, $T=\beta$로 놓을 수 있다.)

덧셈

서로소 합집합 $S\sqcup T$에 다음과 같은 정렬 순서를 주자.

$s\leq t\qquad \forall s\in S,\;t\in T$

그렇다면 순서수의 합 $\alpha +\beta$는 $S\sqcup T$의 순서형이다.

폰 노이만 정의에서, 순서수의 합은 마찬가지로 다음과 같이 초한 귀납법으로 정의할 수도 있다.^{:23, Definition 2.18}

• $\alpha +0=\alpha$
• $\alpha +(\beta +1)=(\alpha +\beta )+1$
• $\alpha +\beta =\bigcup _{\gamma <\beta }\alpha +\gamma$ ($\beta$는 0이 아닌 극한 순서수)

$(\operatorname {Ord} ,+)$는 "모노이드"를 이룬다. 즉, 덧셈의 결합 법칙이 성립하며, 양쪽 항등원 $0\in \operatorname {Ord}$이 존재한다. (물론, $\operatorname {Ord}$는 집합이 아니므로 엄밀히 말해 모노이드가 될 수 없다.)

• (결합 법칙) $(\alpha +\beta )+\gamma =\alpha +(\beta +\gamma )$
• (양쪽 항등원) $\alpha +0=0+\alpha =\alpha$

그러나 이는 "가환 모노이드"가 아니다. 즉, 덧셈의 교환 법칙을 만족시키지 않는다. 예를 들어,

$1+\omega =\omega <\omega +1$

이다.

곱셈

곱집합 $T\times S$에 사전식 순서를 주자. 그렇다면 순서수의 곱 $\alpha \beta$는 $T\times S$의 순서형이다.

폰 노이만 정의에서, 순서수의 곱은 마찬가지로 다음과 같이 초한 귀납법으로 정의할 수도 있다.^{:23, Definition 2.19}

• $\alpha 0=0$
• $\alpha (\beta +1)=\alpha \beta +\alpha$
• $\alpha \beta =\bigcup _{\gamma <\beta }\alpha \gamma$ ($\beta$는 0이 아닌 극한 순서수)

$(\operatorname {Ord} ,\cdot )$는 "모노이드"를 이룬다. 즉, 곱셈의 결합 법칙이 성립하며, 양쪽 항등원 $1\in \operatorname {Ord}$이 존재한다. (물론, $\operatorname {Ord}$는 집합이 아니므로 엄밀히 말해 모노이드가 될 수 없다.)

• (결합 법칙) $(\alpha \beta )\gamma =\alpha (\beta \gamma )$
• (양쪽 항등원) $1\alpha =\alpha 1=\alpha$

또한, 이 "모노이드"는 0을 가지며, 오른쪽 분배 법칙이 성립한다.

• $\alpha 0=0\alpha =0$
• (우측 분배 법칙) $\alpha (\beta +\gamma )=\alpha \beta +\alpha \gamma$
• (영인자의 부재) $\alpha \beta =0$이라면 $\alpha =0$이거나 $\beta =0$이다.

그러나 교환 법칙 및 왼쪽 분배 법칙은 성립하지 않는다.

$2\omega =\omega <\omega 2$

$(\omega +1)2=\omega +1+\omega +1=\omega 2+1<\omega 2+2$

거듭제곱

직합

$S^{\oplus T}=\bigoplus _{t\in T}S$

에 사전식 순서를 주자. 그렇다면 순서수의 거듭제곱 $\alpha ^{\beta }$는 $S^{\oplus T}$의 순서형이다.

폰 노이만 정의에서, 순서수의 거듭제곱은 마찬가지로 다음과 같이 초한 귀납법으로 정의할 수도 있다.^{:23, Definition 2.20}

• $\alpha ^{0}=1$
• $\alpha ^{\beta +1}=\alpha ^{\beta }\alpha$
• $\alpha ^{\beta }=\bigcup _{\gamma <\beta }\alpha ^{\gamma }$ ($\beta \neq 0$은 극한 순서수)

임의의 순서수 $\alpha ,\beta ,\gamma$에 대하여 다음이 성립한다.

• $0^{\alpha }={\begin{cases}0&\alpha >0\\1&\alpha =0\end{cases}}$
• (거듭제곱의 분배 법칙) $\alpha ^{\beta +\gamma }=\alpha ^{\beta }\alpha ^{\gamma }$
• $\alpha ^{\beta \gamma }=(\alpha ^{\beta })^{\gamma }$

그러나 $(\alpha \beta )^{\gamma }\neq \alpha ^{\gamma }\beta ^{\gamma }$일 수 있다. 예를 들어,

$(\omega 2)^{2}=\omega 2\omega 2=\omega ^{2}2\neq \omega ^{2}4$

이다.

순서수의 거듭제곱은 기수의 거듭제곱과 현저히 다르다. 예를 들어, 순서수 연산에 대해서, 칸토어의 정리가 다음과 같이 성립하지 않는다.

$2^{\omega }=\omega$

순서 보존

임의의 서수 $\alpha$, $\beta$, $\gamma$에 대하여 다음이 성립한다.

• $\alpha +\beta <\alpha +\gamma$와 $\beta <\gamma$는 동치이다.
• $\alpha +\beta =\alpha +\gamma$와 $\beta =\gamma$는 동치이다.
• $\alpha +\gamma <\beta +\gamma$이면 $\alpha <\beta$이다.
• $\alpha <\beta$이면 $\alpha +\gamma \leq \beta +\gamma$이기만 하다.

비슷하게, 곱셈에 대하여 다음 성질들이 성립한다.

• $\alpha \beta <\alpha \gamma$와 $\beta <\gamma$ 또는 $\alpha =0$은 동치이다.
• $\alpha \beta =\alpha \gamma$와 $\beta =\gamma$ 또는 $\alpha =0$은 동치이다.
• $\alpha \gamma <\beta \gamma$이면 $\alpha <\beta$이다.
• $\alpha <\beta$이면 $\alpha \gamma \leq \beta \gamma$이기만 하다.

성질

폰 노이만 정의에서, 순서수 $\alpha$의 원소 $\beta \in \alpha$는 여전히 순서수이다.

순서수의 집합 $S\subset \operatorname {Ord}$에 대하여, 그 합집합 $\textstyle \bigcup S=\sup S$ 역시 순서수이며, 이는 $S$의 상한이다.

공집합이 아닌, 순서수의 모임 $\varnothing \neq C\subset \operatorname {Ord}$에 대하여, 그 교집합 $\textstyle \bigcap C=\min C$ 역시 순서수이며, 이는 $C$의 최소 원소이다.

순서수의 집합은 일반적으로 순서수가 아니다. 순서수의 모임 $\operatorname {Ord}$은 고유 모임이며, 따라서 순서수가 아니다. 이 사실을 부랄리포르티 역설이라고 한다.

종류

유한 순서수

임의의 순서수 $\alpha$에 대하여, 다음 조건들이 서로 동치이며, 이를 만족시키는 순서수를 유한 순서수(영어: finite ordinal)라고 한다.

• $\alpha <\omega$이다.
• $\alpha$는 (폰 노이만 정의에 따라) 집합으로서 유한 집합이다. 즉, $|\alpha |<\aleph _{0}$이다.
• $(\alpha ,\leq )$의 역순서 $(\alpha ,\geq )$는 정렬 전순서이다. 즉, $\alpha$에서 공집합이 아닌 모든 부분 집합이 최대 원소를 갖는다.
• $\alpha$는 순서 위상을 부여하였을 때, 집적점을 갖지 않는다.

유한 순서수들은 자연수(음이 아닌 정수)들과 대응된다. 폰 노이만 정의에 따르면, 이들은

$0=\varnothing$

$1=\{0\}=\{\varnothing \}$

$2=\{0,1\}=\{0,\{0\}\}=\{\varnothing ,\{\varnothing \}\}$

등의 집합으로 정의된다.

가산 무한 순서수

순서수 $\omega ^{2}$의 형상화. $\omega$개의 $\omega$들이 모여 있다.

가장 작은 무한 순서수 $\omega$는 자연수 집합 전체의 순서형이며, 폰 노이만 정의에서는 이는 자연수의 집합과 같다.

$\omega =\mathbb {N} =\{0,1,2,\dots \}$

그 다음에는 $\omega +1$, $\omega +2$ 등의 순서수들이 존재한다.

$\omega +1=\{0,1,2,\dots ,\omega \}$

$\omega +2=\{0,1,2,\dots ,\omega ,\omega +1\}$

마찬가지로, $\omega +\omega =\omega \cdot 2$는 다음과 같다. (순서수의 곱셈은 가환하지 않으며, $2\omega =\omega \neq \omega \cdot 2$이다.)

$\omega \cdot 2=\{0,1,2\dots ,\omega ,\omega +1,\omega +2,\dots ,\}$

$\omega \cdot 2+1=\{0,1,2\dots ,\omega ,\omega +1,\omega +2,\dots ,\omega \cdot 2\}$

마찬가지로, $\omega \cdot 3,\omega \cdot 3+1,\dots$ 등이 존재한다. 이와 같은 방법으로 만들어지는 모든 순서수(즉, 자연수 $m$과 $n$에 대해 $\omega \cdot m+n$으로 나타낼 수 있는 순서수)들의 집합(의 순서형)은 그 자체로 순서수가 되며, 이는 $\omega ^{2}$이다. 비슷한 방법으로 $\omega ^{3},\omega ^{4},\dots$ 등이 존재한다.

$\omega ,\omega ^{2},\omega ^{3},\dots$의 극한은 $\omega ^{\omega }$이고, 마찬가지로 $\omega ^{\omega ^{\omega }}$ 등등이 존재한다.

$\omega ,\omega ^{\omega },\omega ^{\omega ^{\omega }},\dots$의 극한은 $\epsilon _{0}$라고 한다. 이 역시 가산 무한 순서수이다. 이는

$\omega ^{\epsilon _{0}}=\epsilon _{0}$

을 만족시킨다.

비가산 무한 순서수

모든 가산 무한 순서수들의 집합의 순서형은 가장 작은 비가산 무한 순서수 $\omega _{1}$이다. 이는 가장 작은 비가산 무한 기수 $\aleph _{1}$과 같다.

극한 순서수와 따름 순서수

모든 순서수들은 따름 순서수(-順序數, 영어: successor ordinal) 또는 극한 순서수(極限順序數, 영어: limit ordinal)로 분류된다. (일부 문헌에서는 0을 극한 순서수에서 제외하기도 한다.) 이들은 초한 귀납법을 적용할 때 보통 개별적으로 다룬다.

순서수 $\alpha$에 대하여, 다음 조건들이 서로 동치이며, 이를 만족시키는 순서수를 극한 순서수라고 하며, 이를 만족시키지 않는 순서수를 따름 순서수라고 한다.

• $\alpha =\beta +1$인 순서수 $\beta$가 존재하지 않는다.
• $\sup\{\beta \in \operatorname {Ord} \colon \beta <\alpha \}=\alpha$이다. (물론 $\sup \varnothing =0$으로 놓는다.)
• $\operatorname {cf} \alpha \neq 1$이다. (여기서 $\operatorname {cf}$는 공종도이다.)
• 폰 노이만 정의에서, $\alpha$는 최대 원소를 갖지 않는다.
• $\alpha =\omega \beta$인 순서수 $\beta$가 존재한다.
• 폰 노이만 정의에서, 임의의 순서수 $\beta >\alpha$에 대하여 $\beta$에 순서 위상을 부여하였을 때, $\alpha \in \beta$는 $\beta$의 집적점이거나 $\alpha =0$이다. 즉, $\alpha \neq 0$라면 $\alpha$의 모든 근방은 무한 집합이다.
• 폰 노이만 정의에서, $\alpha$는 순서 위상을 부여하였을 때 콤팩트 공간이 아니거나 $\alpha =0$이다.

예를 들어, 순서수들

$0,1,2,\ldots ,\omega ,\omega +1,\omega +2$

가운데, 1, 2와 $\omega +1$, $\omega +2$는 따름 순서수이며, 0과 $\omega$는 극한 순서수이다.

칸토어 표준형

임의의 순서수 $\delta \geq 2$가 주어졌다고 하자. 그렇다면, 모든 순서수 $\alpha$는 다음과 같은 꼴로 유일하게 나타내어진다.

$\alpha =\delta ^{\beta _{1}}\gamma _{1}+\delta ^{\beta _{2}}\gamma _{2}+\cdots +\delta ^{\beta _{k}}\gamma _{k}$

$0\leq \beta _{1}<\beta _{2}<\cdots <\beta _{k}\in \operatorname {Ord}$

$\gamma _{1},\gamma _{2},\dots ,\gamma _{k}<\delta$

이를 $\alpha$의 $\delta$진 칸토어 표준형($\delta$進Cantor標準型, 영어: base-$\delta$ Cantor normal form)이라고 한다. 진법 $\delta$가 주어지지 않았을 때, 칸토어 표준형이란 $\omega$진 칸토어 표준형을 뜻한다.^{:24, Theorem 2.26}

이를 재귀적으로 사용하여, 일부 순서수들을 양의 정수 및 기호 $\omega$만으로 나타낼 수 있다. 예를 들어 다음과 같다.

$\omega ^{\omega ^{2}5+\omega ^{3}+\omega +2}+\omega ^{\omega ^{8}+\omega ^{2}}+\omega ^{0}34$

이와 같이 나타낼 수 있는 순서수는 $\epsilon _{0}$ 이하이다. 여기서 순서수 $\epsilon _{0}$는 다음과 같다.

$\epsilon _{0}=\min\{\alpha \in \operatorname {Ord} \colon \alpha =\omega ^{\alpha }\}=\sup\{\omega ,\omega ^{\omega },\omega ^{\omega ^{\omega }},\dots \}=\omega ^{\omega ^{\omega ^{\cdot ^{\cdot ^{\cdot }}}}}$

즉, $\epsilon _{0}$의 $\omega$진 칸토어 표준형은 $\epsilon _{0}=\omega ^{\epsilon _{0}}$이므로 이는 자연수와 $\omega$만으로 나타낼 수 없다.

짝순서수와 홀순서수

모든 순서수는 짝순서수(-順序數, 영어: even ordinal) 또는 홀순서수(-順序數, 영어: odd ordinal)로 분류된다. 이는 자연수가 짝수와 홀수로 분류되는 것의 일반화이다. 이 개념은 다음과 같이 여러 가지로 정의될 수 있다.

순서수 $\alpha$에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 순서수를 짝순서수라고 한다.

• $\alpha$가 극한 순서수이거나, 만약 $\alpha =\beta +1$이라면 $\beta$는 짝순서수가 아니다. (이는 재귀적인 정의이다.)
• 만약 $\alpha =\lambda +n$이며, $\lambda$가 극한 순서수, $n$이 유한 순서수라면, $n$은 짝수이다.^{:296, §9.1}
• $\alpha =2\beta$인 순서수 $\beta$가 존재한다.
• $\alpha =2\beta +1$인 순서수 $\beta$가 존재하지 않는다.

짝순서수가 아닌 순서수를 홀순서수라고 한다.

응용

순서수의 개념은 초한 귀납법을 사용할 때 필요하다. 이를 사용하여, 무한한 구조를 귀납적으로 손쉽게 정의할 수 있다. 예를 들어, 측도론에서 보렐 집합들은 어떤 기저로부터 생성되는 ‘생일’에 대응하는 순서수로 분류된다.

증명 이론에서는 주어진 수학 이론의 강력한 정도를 순서수로 측정하며, 이 이론을 순서수 분석이라고 한다. 순서수가 더 큰 이론은 순서수가 더 작은 이론의 무모순성을 증명할 수 있다.

역사

게오르크 칸토어가 1883년에 도입하였다. 원래 순서수의 동치류로서의 정의는 고유 모임이므로 집합론적인 결함이 있었으며, 1923년에 존 폰 노이만이 오늘날 쓰이는 정의를 도입하였다.

같이 보기

• 셈
• 순서 위상
• 초현실수

각주

• 콘웨이, 존; 가이, 리처드 (2003). 《수의 바이블》. 이진주, 황용석 역. 한승. ISBN 978-89-86865-78-3. 2015년 9월 28일에 원본 문서에서 보존된 문서. 2014년 11월 26일에 확인함. 
  • Conway, John Horton; Guy, Richard K. (1996). 《The book of numbers》 (영어). Springer. doi:10.1007/978-1-4612-4072-3. ISBN 978-1-4612-8488-8. Zbl 0866.00001. 

외부 링크

• “Ordinal number” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Ordinal number” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Initial ordinal” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Ordinal addition” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Ordinal multiplication” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Ordinal exponentiation” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• “Ordinal number” (영어). 《nLab》. 
• “Countable ordinal” (영어). 《nLab》. 
• Hamkins, Joel David; Gitman, Victoria. “Ordinal numbers” (영어). 《Cantor’s Attic》. 2016년 7월 17일에 원본 문서에서 보존된 문서. 2016년 7월 18일에 확인함. 
• “Definition: ordinal” (영어). 《ProofWiki》. 2017년 12월 27일에 원본 문서에서 보존된 문서. 2016년 7월 18일에 확인함. 
• “Definition: finite ordinal” (영어). 《ProofWiki》. 2020년 9월 28일에 원본 문서에서 보존된 문서. 2016년 7월 18일에 확인함. 
• Baez, John Carlos (2006년 7월 26일). “Week 236” (영어). 《This Week’s Finds in Mathematical Physics》. 2016년 4월 11일에 원본 문서에서 보존된 문서. 2016년 7월 18일에 확인함. 
• Baez, John Carlos (2016년 6월 29일). “Large countable ordinals (part 1)” (영어). 《Azimuth》. 2016년 7월 19일에 원본 문서에서 보존된 문서. 2016년 7월 18일에 확인함. 
• Baez, John Carlos (2016년 7월 4일). “Large countable ordinals (part 2)” (영어). 《Azimuth》. 2016년 8월 20일에 원본 문서에서 보존된 문서. 2016년 7월 18일에 확인함. 
• Baez, John Carlos (2016년 7월 7일). “Large countable ordinals (part 3)” (영어). 《Azimuth》.