순서수

섬네일|right|<math>\omega^\omega</math> 이하의 순서수들의 형상화
집합론에서 **순서수**(順序數, ) 또는 **서수**(序數)는 정렬 전순서 집합들의 "길이"를 측정하는 수의 일종이다. 자연수를 확장하며, 자연수들의 정렬 전순서 집합과 같은 무한 정렬 전순서 집합들의 크기를 측정하는 무한 순서수들이 존재한다.

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

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

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

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

### 폰 노이만 정의
집합론적 문제를 피하기 위해, 정렬 전순서 집합의 순서 동형 동치류의 대표원을 다음과 같이 고를 수 있다. 이 정의는 존 폰 노이만이 제시하였고, 오늘날 표준적인 정의다. 선택 공리를 추가한 체르멜로-프렝켈 집합론을 가정하면, 추이적 집합 S에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 추이적 집합을 **순서수**라고 한다.
* (S,\subseteq)는 전순서 집합을 이룬다. 즉, 임의의 a,b\in S에 대하여, a\in b이거나 b\in a이거나 a=b이다.
* (S,\subseteq)는 정렬 전순서 집합을 이룬다.
* S의 모든 원소는 추이적 집합이다.
폰 노이만 정의에서는 순서수 \alpha와 \beta에 대하여 다음 두 조건이 서로 동치이다.
* \alpha\in\beta
* \alpha\subsetneq\beta
이를 \alpha로 표기하고, \alpha\not를 \alpha\ge\beta로 표기한다. 즉, 순서수 \alpha는 그보다 작은 모든 순서수들의 집합이다.
:\alpha=\{\beta\in\operatorname{Ord}\colon\beta
이 순서에 따라, 모든 순서수는 정렬 전순서 집합이며, 반대로 모든 정렬 전순서 집합이 정확히 하나의 순서수와 순서 동형이라는 것은 초한 귀납법을 이용해 보일 수 있다.

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

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

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

### 덧셈
서로소 합집합 S\sqcup T에 다음과 같은 정렬 순서를 주자.
:s\le t\qquad\forall s\in S,\;t\in T
그렇다면 순서수의 **합** \alpha+\beta는 S\sqcup T의 순서형이다.

폰 노이만 정의에서, 순서수의 합은 마찬가지로 다음과 같이 초한 귀납법으로 정의할 수도 있다.
* \alpha + 0 = \alpha
* \alpha + (\beta +1 )  = (\alpha + \beta ) + 1
* \alpha + \beta = \bigcup_{\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
이다.

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

폰 노이만 정의에서, 순서수의 곱은 마찬가지로 다음과 같이 초한 귀납법으로 정의할 수도 있다.
* \alpha 0 =0 
* \alpha(\beta +1 )  = \alpha\beta + \alpha
* \alpha\beta = \bigcup_{\gamma (\beta는 0이 아닌 극한 순서수)

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

또한, 이 "모노이드"는 0을 가지며, 오른쪽 분배 법칙이 성립한다.
* \alpha0=0\alpha=0
* (우측 분배 법칙) \alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma
* (영인자의 부재) \alpha\beta=0이라면 \alpha=0이거나 \beta=0이다.
그러나 교환 법칙 및 왼쪽 분배 법칙은 성립하지 않는다.
:2\omega=\omega
:(\omega+1)2=\omega+1+\omega+1=\omega2+1

### 거듭제곱
직합
:S^{\oplus T}=\bigoplus_{t\in T}S
에 사전식 순서를 주자. 그렇다면 순서수의 **거듭제곱** \alpha^\beta는 S^{\oplus T}의 순서형이다.

폰 노이만 정의에서, 순서수의 거듭제곱은 마찬가지로 다음과 같이 초한 귀납법으로 정의할 수도 있다.
* \alpha^0 =1
* \alpha^{\beta+1} = \alpha^\beta\alpha
* \alpha^\beta = \bigcup_{\gamma (\beta\ne0은 극한 순서수)

임의의 순서수 \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\ne\alpha^\gamma\beta^\gamma일 수 있다. 예를 들어,
:(\omega2)^2=\omega2\omega2=\omega^22\ne\omega^24
이다.

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

### 순서 보존
임의의 서수 \alpha, \beta, \gamma에 대하여 다음이 성립한다.
* \alpha+\beta와 \beta는 동치이다.
* \alpha+\beta=\alpha+\gamma와 \beta=\gamma는 동치이다.
* \alpha+\gamma이면 \alpha이다.
* \alpha이면 \alpha+\gamma\le\beta+\gamma이기만 하다.

비슷하게, 곱셈에 대하여 다음 성질들이 성립한다.
* \alpha\beta와 \beta 또는 \alpha=0은 동치이다.
* \alpha\beta=\alpha\gamma와 \beta=\gamma 또는 \alpha=0은 동치이다.
* \alpha\gamma이면 \alpha이다.
* \alpha이면 \alpha\gamma\le\beta\gamma이기만 하다.

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

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

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

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

## 종류
### 유한 순서수
임의의 순서수 \alpha에 대하여, 다음 조건들이 서로 동치이며, 이를 만족시키는 순서수를 **유한 순서수**()라고 한다.
* \alpha이다.
* \alpha는 (폰 노이만 정의에 따라) 집합으로서 유한 집합이다. 즉, |\alpha|이다.
* (\alpha,\le)의 역순서 (\alpha,\ge)는 정렬 전순서이다. 즉, \alpha에서 공집합이 아닌 모든 부분 집합이 최대 원소를 갖는다.
* \alpha는 순서 위상을 부여하였을 때, 집적점을 갖지 않는다.

유한 순서수들은 자연수(음이 아닌 정수)들과 대응된다. 폰 노이만 정의에 따르면, 이들은
:0=\varnothing
:1=\{0\}=\{\varnothing\}
:2=\{0,1\}=\{0,\{0\}\}=\{\varnothing,\{\varnothing\}\}
등의 집합으로 정의된다.

### 가산 무한 순서수
섬네일|right|순서수 <math>\omega^2</math>의 형상화. <math>\omega</math>개의 <math>\omega</math>들이 모여 있다.
가장 작은 무한 순서수 \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\cdot2는 다음과 같다. (순서수의 곱셈은 가환하지 않으며, 2\omega=\omega\ne\omega\cdot2이다.)
:\omega\cdot2=\{0,1,2\dots,\omega,\omega+1,\omega+2,\dots,\}
:\omega\cdot2+1=\{0,1,2\dots,\omega,\omega+1,\omega+2,\dots,\omega\cdot2\}
마찬가지로, \omega\cdot3,\omega\cdot3+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과 같다.

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

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

예를 들어, 순서수들
:0,1,2,\ldots,\omega,\omega+1,\omega+2
가운데, 1, 2와 \omega+1, \omega+2는 따름 순서수이며, 0과 \omega는 극한 순서수이다.

### 칸토어 표준형
임의의 순서수 \delta\ge2가 주어졌다고 하자. 그렇다면, 모든 순서수 \alpha는 다음과 같은 꼴로 유일하게 나타내어진다.
:\alpha=\delta^{\beta_1}\gamma_1+\delta^{\beta_2}\gamma_2+\cdots+\delta^{\beta_k}\gamma_k
:0\le\beta_1
:\gamma_1,\gamma_2,\dots,\gamma_k
이를 \alpha의 **<math>\delta</math>진 칸토어 표준형**(\delta進Cantor標準型, )이라고 한다. 진법 \delta가 주어지지 않았을 때, **칸토어 표준형**이란 \omega진 칸토어 표준형을 뜻한다.

이를 재귀적으로 사용하여, 일부 순서수들을 양의 정수 및 기호 \omega만으로 나타낼 수 있다. 예를 들어 다음과 같다.
:\omega^{\omega^25+\omega^3+\omega+2}+\omega^{\omega^8+\omega^2}+\omega^034
이와 같이 나타낼 수 있는 순서수는 \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만으로 나타낼 수 없다.

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

순서수 \alpha에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 순서수를 **짝순서수**라고 한다.
* \alpha가 극한 순서수이거나, 만약 \alpha=\beta+1이라면 \beta는 짝순서수가 아니다. (이는 재귀적인 정의이다.)
* 만약 \alpha=\lambda+n이며, \lambda가 극한 순서수, n이 유한 순서수라면, n은 짝수이다.
* \alpha=2\beta인 순서수 \beta가 존재한다.
* \alpha=2\beta+1인 순서수 \beta가 존재하지 않는다.
짝순서수가 아닌 순서수를 **홀순서수**라고 한다.

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

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

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

## 같이 보기
* 셈
* 순서 위상
* 초현실수

## 각주

* 
** 

## 외부 링크

* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
*