집합론 에서 순서수 (順序數, 영어 : ordinal ) 또는 서수 (序數)는 정렬 전순서 집합 들의 "길이"를 측정하는 수 의 일종이다. 자연수 를 확장하며, 자연수 들의 정렬 전순서 집합과 같은 무한 정렬 전순서 집합들의 크기를 측정하는 무한 순서수들이 존재한다.
ω
ω
{\displaystyle \omega ^{\omega }}
이하의 순서수들의 형상화
자연수 는 집합 의 크기 를 표현하기 위해 사용되기도 하고, 열 에서 원소의 위치를 나타내기 위해 사용되기도 한다. 이 두 쓰임새는 유한 집합 의 경우 크게 다르지 않으나, 무한 집합 의 경우에는 이 구분이 중요해진다. 전자를 확장한 것이 기수 이고, 후자를 확장한 것이 순서수이다.
기수는 아무런 구조도 갖지 않는 집합에 대해서도 부여할 수 있지만, 순서수는 정렬 전순서 집합 에 대해서만 정의되며, 정렬 전순서 의 개념과 순서수의 개념에는 매우 밀접한 관련이 있다. 간단히 말해, 정렬 전순서 란 무한히 감소하는 수열이 존재하지 않는 전순서 를 말한다. (물론 무한히 증가하는 수열은 존재할 수 있다.) 임의의 전순서 집합 에서 최소 원소 를 0이라 하고 그 다음 원소를 1이라 하는 식으로 그 집합의 원소들을 순서수를 이용해 순서매길 수 있으며, 이 집합의 "길이"를 여기에서 집합의 원소에 대응되지 않는 가장 작은 순서수로 정의할 수 있다. 이 "길이"를 집합의 순서형 이라고 한다.
폰 노이만 정의
집합론적 문제를 피하기 위해, 정렬 전순서 집합 의 순서 동형 동치류의 대표원을 다음과 같이 고를 수 있다. 이 정의는 존 폰 노이만 이 제시하였고,[1] 오늘날 표준적인 정의다. 선택 공리 를 추가한 체르멜로-프렝켈 집합론 을 가정하면, 추이적 집합
S
{\displaystyle S}
에 대하여 다음 조건들이 서로 동치 이며, 이를 만족시키는 추이적 집합 을 순서수 라고 한다.
(
S
,
⊆
)
{\displaystyle (S,\subseteq )}
는 전순서 집합 을 이룬다. 즉, 임의의
a
,
b
∈
S
{\displaystyle a,b\in S}
에 대하여,
a
∈
b
{\displaystyle a\in b}
이거나
b
∈
a
{\displaystyle b\in a}
이거나
a
=
b
{\displaystyle a=b}
이다.
(
S
,
⊆
)
{\displaystyle (S,\subseteq )}
는 정렬 전순서 집합 을 이룬다.[2] :19, Definition 2.10
S
{\displaystyle S}
의 모든 원소는 추이적 집합 이다.
폰 노이만 정의에서는 순서수
α
{\displaystyle \alpha }
와
β
{\displaystyle \beta }
에 대하여 다음 두 조건이 서로 동치 이다.
α
∈
β
{\displaystyle \alpha \in \beta }
α
⊊
β
{\displaystyle \alpha \subsetneq \beta }
이를
α
<
β
{\displaystyle \alpha <\beta }
로 표기하고,
α
≮
β
{\displaystyle \alpha \not <\beta }
를
α
≥
β
{\displaystyle \alpha \geq \beta }
로 표기한다. 즉, 순서수
α
{\displaystyle \alpha }
는 그보다 작은 모든 순서수들의 집합이다.
α
=
{
β
∈
Ord
:
β
<
α
}
{\displaystyle \alpha =\{\beta \in \operatorname {Ord} \colon \beta <\alpha \}}
이 순서에 따라, 모든 순서수 는 정렬 전순서 집합 이며, 반대로 모든 정렬 전순서 집합이 정확히 하나의 순서수와 순서 동형이라는 것은 초한 귀납법 을 이용해 보일 수 있다.
마찬가지로, 모든 순서수의 모임
Ord
{\displaystyle \operatorname {Ord} }
는 정렬 전순서 모임 을 이룬다. 이 덕분에 순서수에 대해 초한 귀납법을 자유로이 사용할 수 있다.
순서수들에 대해 덧셈 · 곱셈 · 거듭제곱 연산을 정의하는 것이 가능하다. 각 연산은 연산 결과에 해당하는 정렬 전순서 집합 을 직접 만들어내는 방법으로 정의할 수도 있고, 초한 귀납법 을 이용해 정의할 수도 있다. 유한 순서수의 경우, 순서수로서의 연산은 기수 로서의 연산 및 자연수 로서의 연산과 일치한다. 무한 순서수의 경우, 순서수의 연산은 극한 기수 로서의 연산과 현저히 다르다.
두 정렬 전순서 집합
(
S
,
≤
)
{\displaystyle (S,\leq )}
와
(
T
,
≤
)
{\displaystyle (T,\leq )}
가 주어졌다고 하고,
S
{\displaystyle S}
의 순서형이
α
{\displaystyle \alpha }
,
T
{\displaystyle T}
의 순서형이
β
{\displaystyle \beta }
라고 하자. (폰 노이만 정의에서는
S
=
α
{\displaystyle S=\alpha }
,
T
=
β
{\displaystyle T=\beta }
로 놓을 수 있다.)
덧셈
서로소 합집합
S
⊔
T
{\displaystyle S\sqcup T}
에 다음과 같은 정렬 순서 를 주자.
s
≤
t
∀
s
∈
S
,
t
∈
T
{\displaystyle s\leq t\qquad \forall s\in S,\;t\in T}
그렇다면 순서수의 합
α
+
β
{\displaystyle \alpha +\beta }
는
S
⊔
T
{\displaystyle S\sqcup T}
의 순서형이다.
폰 노이만 정의에서, 순서수의 합은 마찬가지로 다음과 같이 초한 귀납법 으로 정의할 수도 있다.[2] :23, Definition 2.18
α
+
0
=
α
{\displaystyle \alpha +0=\alpha }
α
+
(
β
+
1
)
=
(
α
+
β
)
+
1
{\displaystyle \alpha +(\beta +1)=(\alpha +\beta )+1}
α
+
β
=
⋃
γ
<
β
α
+
γ
{\displaystyle \alpha +\beta =\bigcup _{\gamma <\beta }\alpha +\gamma }
(
β
{\displaystyle \beta }
는 0이 아닌 극한 순서수)
(
Ord
,
+
)
{\displaystyle (\operatorname {Ord} ,+)}
는 "모노이드 "를 이룬다. 즉, 덧셈의 결합 법칙 이 성립하며, 양쪽 항등원
0
∈
Ord
{\displaystyle 0\in \operatorname {Ord} }
이 존재한다. (물론,
Ord
{\displaystyle \operatorname {Ord} }
는 집합이 아니므로 엄밀히 말해 모노이드 가 될 수 없다.)
(결합 법칙 )
(
α
+
β
)
+
γ
=
α
+
(
β
+
γ
)
{\displaystyle (\alpha +\beta )+\gamma =\alpha +(\beta +\gamma )}
(양쪽 항등원 )
α
+
0
=
0
+
α
=
α
{\displaystyle \alpha +0=0+\alpha =\alpha }
그러나 이는 "가환 모노이드 "가 아니다. 즉, 덧셈의 교환 법칙 을 만족시키지 않는다. 예를 들어,
1
+
ω
=
ω
<
ω
+
1
{\displaystyle 1+\omega =\omega <\omega +1}
이다.
유한 순서수
임의의 순서수
α
{\displaystyle \alpha }
에 대하여, 다음 조건들이 서로 동치 이며, 이를 만족시키는 순서수를 유한 순서수 (영어 : finite ordinal )라고 한다.
α
<
ω
{\displaystyle \alpha <\omega }
이다.
α
{\displaystyle \alpha }
는 (폰 노이만 정의에 따라) 집합으로서 유한 집합 이다. 즉,
|
α
|
<
ℵ
0
{\displaystyle |\alpha |<\aleph _{0}}
이다.
(
α
,
≤
)
{\displaystyle (\alpha ,\leq )}
의 역순서
(
α
,
≥
)
{\displaystyle (\alpha ,\geq )}
는 정렬 전순서 이다. 즉,
α
{\displaystyle \alpha }
에서 공집합 이 아닌 모든 부분 집합 이 최대 원소 를 갖는다.
α
{\displaystyle \alpha }
는 순서 위상 을 부여하였을 때, 집적점 을 갖지 않는다.
유한 순서수들은 자연수 (음이 아닌 정수)들과 대응된다. 폰 노이만 정의에 따르면, 이들은
0
=
∅
{\displaystyle 0=\varnothing }
1
=
{
0
}
=
{
∅
}
{\displaystyle 1=\{0\}=\{\varnothing \}}
2
=
{
0
,
1
}
=
{
0
,
{
0
}
}
=
{
∅
,
{
∅
}
}
{\displaystyle 2=\{0,1\}=\{0,\{0\}\}=\{\varnothing ,\{\varnothing \}\}}
등의 집합으로 정의된다.
가산 무한 순서수
순서수
ω
2
{\displaystyle \omega ^{2}}
의 형상화.
ω
{\displaystyle \omega }
개의
ω
{\displaystyle \omega }
들이 모여 있다.
가장 작은 무한 순서수
ω
{\displaystyle \omega }
는 자연수 집합 전체의 순서형이며, 폰 노이만 정의에서는 이는 자연수의 집합과 같다.
ω
=
N
=
{
0
,
1
,
2
,
…
}
{\displaystyle \omega =\mathbb {N} =\{0,1,2,\dots \}}
그 다음에는
ω
+
1
{\displaystyle \omega +1}
,
ω
+
2
{\displaystyle \omega +2}
등의 순서수들이 존재한다.
ω
+
1
=
{
0
,
1
,
2
,
…
,
ω
}
{\displaystyle \omega +1=\{0,1,2,\dots ,\omega \}}
ω
+
2
=
{
0
,
1
,
2
,
…
,
ω
,
ω
+
1
}
{\displaystyle \omega +2=\{0,1,2,\dots ,\omega ,\omega +1\}}
마찬가지로,
ω
+
ω
=
ω
⋅
2
{\displaystyle \omega +\omega =\omega \cdot 2}
는 다음과 같다. (순서수의 곱셈은 가환하지 않으며,
2
ω
=
ω
≠
ω
⋅
2
{\displaystyle 2\omega =\omega \neq \omega \cdot 2}
이다.)
ω
⋅
2
=
{
0
,
1
,
2
…
,
ω
,
ω
+
1
,
ω
+
2
,
…
,
}
{\displaystyle \omega \cdot 2=\{0,1,2\dots ,\omega ,\omega +1,\omega +2,\dots ,\}}
ω
⋅
2
+
1
=
{
0
,
1
,
2
…
,
ω
,
ω
+
1
,
ω
+
2
,
…
,
ω
⋅
2
}
{\displaystyle \omega \cdot 2+1=\{0,1,2\dots ,\omega ,\omega +1,\omega +2,\dots ,\omega \cdot 2\}}
마찬가지로,
ω
⋅
3
,
ω
⋅
3
+
1
,
…
{\displaystyle \omega \cdot 3,\omega \cdot 3+1,\dots }
등이 존재한다.
이와 같은 방법으로 만들어지는 모든 순서수(즉, 자연수
m
{\displaystyle m}
과
n
{\displaystyle n}
에 대해
ω
⋅
m
+
n
{\displaystyle \omega \cdot m+n}
으로 나타낼 수 있는 순서수)들의 집합(의 순서형)은 그 자체로 순서수가 되며, 이는
ω
2
{\displaystyle \omega ^{2}}
이다. 비슷한 방법으로
ω
3
,
ω
4
,
…
{\displaystyle \omega ^{3},\omega ^{4},\dots }
등이 존재한다.
ω
,
ω
2
,
ω
3
,
…
{\displaystyle \omega ,\omega ^{2},\omega ^{3},\dots }
의 극한은
ω
ω
{\displaystyle \omega ^{\omega }}
이고, 마찬가지로
ω
ω
ω
{\displaystyle \omega ^{\omega ^{\omega }}}
등등이 존재한다.
ω
,
ω
ω
,
ω
ω
ω
,
…
{\displaystyle \omega ,\omega ^{\omega },\omega ^{\omega ^{\omega }},\dots }
의 극한은
ϵ
0
{\displaystyle \epsilon _{0}}
라고 한다. 이 역시 가산 무한 순서수이다. 이는
ω
ϵ
0
=
ϵ
0
{\displaystyle \omega ^{\epsilon _{0}}=\epsilon _{0}}
을 만족시킨다.
비가산 무한 순서수
모든 가산 무한 순서수들의 집합의 순서형은 가장 작은 비가산 무한 순서수
ω
1
{\displaystyle \omega _{1}}
이다. 이는 가장 작은 비가산 무한 기수
ℵ
1
{\displaystyle \aleph _{1}}
과 같다.
극한 순서수와 따름 순서수
모든 순서수들은 따름 순서수 (-順序數, 영어 : successor ordinal ) 또는 극한 순서수 (極限順序數, 영어 : limit ordinal )로 분류된다. (일부 문헌에서는 0을 극한 순서수에서 제외하기도 한다.) 이들은 초한 귀납법 을 적용할 때 보통 개별적으로 다룬다.
순서수
α
{\displaystyle \alpha }
에 대하여, 다음 조건들이 서로 동치 이며, 이를 만족시키는 순서수를 극한 순서수 라고 하며, 이를 만족시키지 않는 순서수를 따름 순서수 라고 한다.
α
=
β
+
1
{\displaystyle \alpha =\beta +1}
인 순서수
β
{\displaystyle \beta }
가 존재하지 않는다.
sup
{
β
∈
Ord
:
β
<
α
}
=
α
{\displaystyle \sup\{\beta \in \operatorname {Ord} \colon \beta <\alpha \}=\alpha }
이다. (물론
sup
∅
=
0
{\displaystyle \sup \varnothing =0}
으로 놓는다.)
cf
α
≠
1
{\displaystyle \operatorname {cf} \alpha \neq 1}
이다. (여기서
cf
{\displaystyle \operatorname {cf} }
는 공종도 이다.)
폰 노이만 정의에서,
α
{\displaystyle \alpha }
는 최대 원소 를 갖지 않는다.
α
=
ω
β
{\displaystyle \alpha =\omega \beta }
인 순서수
β
{\displaystyle \beta }
가 존재한다.
폰 노이만 정의에서, 임의의 순서수
β
>
α
{\displaystyle \beta >\alpha }
에 대하여
β
{\displaystyle \beta }
에 순서 위상 을 부여하였을 때,
α
∈
β
{\displaystyle \alpha \in \beta }
는
β
{\displaystyle \beta }
의 집적점 이거나
α
=
0
{\displaystyle \alpha =0}
이다. 즉,
α
≠
0
{\displaystyle \alpha \neq 0}
라면
α
{\displaystyle \alpha }
의 모든 근방 은 무한 집합 이다.
폰 노이만 정의에서,
α
{\displaystyle \alpha }
는 순서 위상 을 부여하였을 때 콤팩트 공간 이 아니거나
α
=
0
{\displaystyle \alpha =0}
이다.
예를 들어, 순서수들
0
,
1
,
2
,
…
,
ω
,
ω
+
1
,
ω
+
2
{\displaystyle 0,1,2,\ldots ,\omega ,\omega +1,\omega +2}
가운데, 1, 2와
ω
+
1
{\displaystyle \omega +1}
,
ω
+
2
{\displaystyle \omega +2}
는 따름 순서수이며, 0과
ω
{\displaystyle \omega }
는 극한 순서수이다.
칸토어 표준형
임의의 순서수
δ
≥
2
{\displaystyle \delta \geq 2}
가 주어졌다고 하자. 그렇다면, 모든 순서수
α
{\displaystyle \alpha }
는 다음과 같은 꼴로 유일하게 나타내어진다.
α
=
δ
β
1
γ
1
+
δ
β
2
γ
2
+
⋯
+
δ
β
k
γ
k
{\displaystyle \alpha =\delta ^{\beta _{1}}\gamma _{1}+\delta ^{\beta _{2}}\gamma _{2}+\cdots +\delta ^{\beta _{k}}\gamma _{k}}
0
≤
β
1
<
β
2
<
⋯
<
β
k
∈
Ord
{\displaystyle 0\leq \beta _{1}<\beta _{2}<\cdots <\beta _{k}\in \operatorname {Ord} }
γ
1
,
γ
2
,
…
,
γ
k
<
δ
{\displaystyle \gamma _{1},\gamma _{2},\dots ,\gamma _{k}<\delta }
이를
α
{\displaystyle \alpha }
의
δ
{\displaystyle \delta }
진 칸토어 표준형 (
δ
{\displaystyle \delta }
進Cantor標準型, 영어 : base-
δ
{\displaystyle \delta }
Cantor normal form )이라고 한다. 진법
δ
{\displaystyle \delta }
가 주어지지 않았을 때, 칸토어 표준형 이란
ω
{\displaystyle \omega }
진 칸토어 표준형을 뜻한다.[2] :24, Theorem 2.26
이를 재귀적으로 사용하여, 일부 순서수들을 양의 정수 및 기호
ω
{\displaystyle \omega }
만으로 나타낼 수 있다. 예를 들어 다음과 같다.
ω
ω
2
5
+
ω
3
+
ω
+
2
+
ω
ω
8
+
ω
2
+
ω
0
34
{\displaystyle \omega ^{\omega ^{2}5+\omega ^{3}+\omega +2}+\omega ^{\omega ^{8}+\omega ^{2}}+\omega ^{0}34}
이와 같이 나타낼 수 있는 순서수는
ϵ
0
{\displaystyle \epsilon _{0}}
이하이다. 여기서 순서수
ϵ
0
{\displaystyle \epsilon _{0}}
는 다음과 같다.
ϵ
0
=
min
{
α
∈
Ord
:
α
=
ω
α
}
=
sup
{
ω
,
ω
ω
,
ω
ω
ω
,
…
}
=
ω
ω
ω
⋅
⋅
⋅
{\displaystyle \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 }}}}}}
즉,
ϵ
0
{\displaystyle \epsilon _{0}}
의
ω
{\displaystyle \omega }
진 칸토어 표준형은
ϵ
0
=
ω
ϵ
0
{\displaystyle \epsilon _{0}=\omega ^{\epsilon _{0}}}
이므로 이는 자연수와
ω
{\displaystyle \omega }
만으로 나타낼 수 없다.
순서수의 개념은 초한 귀납법 을 사용할 때 필요하다. 이를 사용하여, 무한한 구조를 귀납적으로 손쉽게 정의할 수 있다. 예를 들어, 측도론 에서 보렐 집합 들은 어떤 기저 로부터 생성되는 ‘생일’에 대응하는 순서수로 분류된다.
증명 이론 에서는 주어진 수학 이론의 강력한 정도를 순서수로 측정하며, 이 이론을 순서수 분석 이라고 한다. 순서수가 더 큰 이론은 순서수가 더 작은 이론의 무모순성을 증명할 수 있다.
게오르크 칸토어 가 1883년에 도입하였다.[4] 원래 순서수의 동치류 로서의 정의는 고유 모임 이므로 집합론적인 결함이 있었으며, 1923년에 존 폰 노이만 이 오늘날 쓰이는 정의를 도입하였다.[1]
“ 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》 (영어).