순서수(順序數, 영어: ordinal)는 집합론에서 정렬 전순서 집합들의 "길이"를 측정하는 수의 일종이다. 서수(序數)라고도 불린다. 자연수를 확장한 개념으로, 자연수들의 정렬 전순서 집합과 같은 무한 정렬 전순서 집합들의 크기를 측정하는 무한 순서수들이 존재한다.
자연수는 집합의 크기를 표현하기 위해 사용되기도 하고, 열에서 원소의 위치를 나타내기 위해 사용되기도 한다. 유한 집합의 경우 이 두 쓰임새는 크게 다르지 않으나, 무한 집합의 경우에는 이 구분이 중요해진다. 전자를 확장한 것이 기수(cardinal)이고, 후자를 확장한 것이 순서수이다.
기수는 아무런 구조도 갖지 않는 집합에 대해서도 부여할 수 있지만, 순서수는 정렬 전순서 집합에 대해서만 정의된다. 정렬 전순서란 무한히 감소하는 수열이 존재하지 않는 전순서를 말한다. 임의의 정렬 전순서 집합에서 최소 원소를 0이라 하고 그 다음 원소를 1이라 하는 식으로 그 집합의 원소들을 순서수를 이용해 순서매길 수 있으며, 이 집합의 "길이"를 여기에서 집합의 원소에 대응되지 않는 가장 작은 순서수로 정의할 수 있다. 이 "길이"를 집합의 순서형이라고 한다.
정의
순서수는 모든 정렬 전순서 집합의 순서 동형에 대한 동치류로 정의할 수 있다. 그러나 이러한 정의에 따르면 각 순서수는 체르멜로-프렝켈 집합론에서는 집합이 아니며 고유 모임이 되므로 기술적으로 문제가 있다. 이를 피하기 위해 존 폰 노이만이 제시한 정의가 오늘날 표준적으로 사용된다. 폰 노이만 정의에 따르면, 추이적 집합 S에 대하여 (S, ⊆)가 정렬 전순서 집합을 이루는 경우 S를 순서수라고 한다. 이 정의에서 순서수 α는 그보다 작은 모든 순서수들의 집합, 즉 α = {β ∈ Ord : β < α}로 나타내어진다.
연산
순서수들에 대해 덧셈, 곱셈, 거듭제곱 연산을 정의하는 것이 가능하다. 유한 순서수의 경우 순서수로서의 연산은 기수로서의 연산 및 자연수로서의 연산과 일치한다. 그러나 무한 순서수의 경우 순서수의 연산은 기수로서의 연산과 현저히 다르다. 예를 들어 순서수의 덧셈은 교환 법칙을 만족시키지 않으며, 1 + ω = ω < ω + 1이 성립한다. 마찬가지로 곱셈도 교환 법칙을 만족시키지 않아 2ω = ω < ω·2이다.
종류
순서수는 유한 순서수와 무한 순서수로 나뉜다. 유한 순서수들은 자연수(음이 아닌 정수)들과 대응된다. 가장 작은 무한 순서수 ω는 자연수 집합 전체의 순서형이며, 폰 노이만 정의에서는 자연수의 집합과 같다. 그 다음에는 ω+1, ω+2 등의 순서수들이 존재하며, ω, ω², ω³, …의 극한은 ω^ω이고, ω, ω^ω, ω^(ω^ω), …의 극한은 ε₀라고 한다. 모든 가산 무한 순서수들의 집합의 순서형은 가장 작은 비가산 무한 순서수 ω₁이다.
모든 순서수는 따름 순서수(successor ordinal) 또는 극한 순서수(limit ordinal)로 분류된다. 따름 순서수는 α = β + 1인 순서수 β가 존재하는 순서수이며, 극한 순서수는 그러한 β가 존재하지 않는 순서수이다. 예를 들어 1, 2, ω+1, ω+2는 따름 순서수이고, 0과 ω는 극한 순서수이다.
응용과 역사
순서수의 개념은 초한 귀납법을 사용할 때 필요하며, 이를 통해 무한한 구조를 귀납적으로 정의할 수 있다. 측도론에서 보렐 집합들은 어떤 기저로부터 생성되는 '생일'에 대응하는 순서수로 분류된다. 증명 이론에서는 주어진 수학 이론의 강력한 정도를 순서수로 측정하는 순서수 분석이 이루어진다.
순서수는 게오르크 칸토어가 1883년에 도입하였다. 원래 순서수의 동치류로서의 정의는 고유 모임이므로 집합론적인 결함이 있었으며, 1923년에 존 폰 노이만이 오늘날 쓰이는 정의를 도입하였다.
