순서수
집합론에서, 순서수(順序數, )는 정렬 전순서 집합들의 "길이"를 측정하는 수의 일종이다. 자연수를 확장하며, 자연수들의 정렬 전순서 집합과 같은 무한 정렬 전순서 집합들의 크기를 측정하는 무한 순서수들이 존재한다.
자연수는 집합의 크기를 표현하기 위해 사용되기도 하고, 열에서 원소의 위치를 나타내기 위해 사용되기도 한다. 이 두 쓰임새는 유한 집합의 경우 크게 다르지 않으나, 무한 집합의 경우에는 이 구분이 중요해진다. 전자를 확장한 것이 기수이고, 후자를 확장한 것이 순서수이다.
기수는 아무런 구조도 갖지 않는 집합에 대해서도 부여할 수 있지만, 순서수는 정렬 전순서 집합에 대해서만 정의되며, 정렬 전순서의 개념과 순서수의 개념에는 매우 밀접한 관련이 있다. 간단히 말해, 정렬 전순서란 무한히 감소하는 수열이 존재하지 않는 전순서를 말한다. (물론 무한히 증가하는 수열은 존재할 수 있다.) 임의의 전순서 집합에서 최소 원소를 0이라 하고 그 다음 원소를 1이라 하는 식으로 그 집합의 원소들을 순서수를 이용해 순서매길 수 있으며, 이 집합의 "길이"를 여기에서 집합의 원소에 대응되지 않는 가장 작은 순서수로 정의할 수 있다. 이 "길이"를 집합의 순서형이라고 한다.
기수를 모든 집합의 전단사 함수에 대한 동치류로 정의할 수 있는 것처럼, 순서수는 모든 정렬 전순서 집합의 순서 동형에 대한 동치류로 정의할 수 있다. 그러나 이러한 정의에 따르면 각 순서수는 체르멜로-프렝켈 집합론에서는 집합이 아니며, 고유 모임이 되므로 기술적으로 문제가 있다. (예를 들어, 순서수의 모임 formula_1는 고유 모임들을 원소를 가져야 하므로 정의할 수 없다.)
형 이론이나 윌러드 밴 오먼 콰인의 새 기초(New Foundations)등에서는 이 정의가 문제가 되지 않는다. 이 정의는 형 이론을 사용하는 《수학 원리》에 등장한다.
집합론적 문제를 피하기 위해, 정렬 전순서 집합의 순서 동형 동치류의 대표원을 다음과 같이 고를 수 있다. 이 정의는 존 폰 노이만이 제시하였고, 오늘날 표준적인 정의다. 선택 공리를 추가한 체르멜로-프렝켈 집합론을 가정하면, 추이적 집합 formula_2에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 추이적 집합을 순서수라고 한다.
폰 노이만 정의에서는 순서수 formula_10와 formula_11에 대하여 다음 두 조건이 서로 동치이다.
이를 formula_14로 표기하고, formula_15를 formula_16로 표기한다. 즉, 순서수 formula_10는 그보다 작은 모든 순서수들의 집합이다.
이 순서에 따라, 모든 순서수는 정렬 전순서 집합이며, 반대로 모든 정렬 전순서 집합이 정확히 하나의 순서수와 순서 동형이라는 것은 초한 귀납법을 이용해 보일 수 있다.
마찬가지로, 모든 순서수의 모임 formula_1는 정렬 전순서 모임을 이룬다. 이 덕분에 순서수에 대해 초한 귀납법을 자유로이 사용할 수 있다.
순서수들에 대해 덧셈 · 곱셈 · 거듭제곱 연산을 정의하는 것이 가능하다. 각 연산은 연산 결과에 해당하는 정렬 전순서 집합을 직접 만들어내는 방법으로 정의할 수도 있고, 초한 귀납법을 이용해 정의할 수도 있다. 유한 순서수의 경우, 순서수로서의 연산은 기수로서의 연산 및 자연수로서의 연산과 일치한다. 무한 순서수의 경우, 순서수의 연산은 극한 기수로서의 연산과 현저히 다르다.
두 정렬 전순서 집합 formula_20와 formula_21가 주어졌다고 하고, formula_2의 순서형이 formula_10, formula_24의 순서형이 formula_11라고 하자. (폰 노이만 정의에서는 formula_26, formula_27로 놓을 수 있다.)
서로소 합집합 formula_28에 다음과 같은 정렬 순서를 주자.
그렇다면 순서수의 합 formula_30는 formula_28의 순서형이다.
폰 노이만 정의에서, 순서수의 합은 마찬가지로 다음과 같이 초한 귀납법으로 정의할 수도 있다.
formula_36는 "모노이드"를 이룬다. 즉, 덧셈의 결합 법칙이 성립하며, 양쪽 항등원 formula_37이 존재한다. (물론, formula_1는 집합이 아니므로 엄밀히 말해 모노이드가 될 수 없다.)
그러나 이는 "가환 모노이드"가 아니다. 즉, 덧셈의 교환 법칙을 만족시키지 않는다. 예를 들어,
이다.
곱집합 formula_42에 사전식 순서를 주자. 그렇다면 순서수의 곱 formula_43는 formula_42의 순서형이다.
폰 노이만 정의에서, 순서수의 곱은 마찬가지로 다음과 같이 초한 귀납법으로 정의할 수도 있다.
formula_49는 "모노이드"를 이룬다. 즉, 곱셈의 결합 법칙이 성립하며, 양쪽 항등원 formula_50이 존재한다. (물론, formula_1는 집합이 아니므로 엄밀히 말해 모노이드가 될 수 없다.)
또한, 이 "모노이드"는 0을 가지며, 오른쪽 분배 법칙이 성립한다.
그러나 교환 법칙 및 왼쪽 분배 법칙은 성립하지 않는다.
직합
에 사전식 순서를 주자. 그렇다면 순서수의 거듭제곱 formula_62는 formula_63의 순서형이다.
폰 노이만 정의에서, 순서수의 거듭제곱은 마찬가지로 다음과 같이 초한 귀납법으로 정의할 수도 있다.
임의의 순서수 formula_68에 대하여 다음이 성립한다.
그러나 formula_72일 수 있다. 예를 들어,
이다.
순서수의 거듭제곱은 기수의 거듭제곱과 현저히 다르다. 예를 들어, 순서수 연산에 대해서, 칸토어의 정리가 다음과 같이 성립하지 않는다.
임의의 서수 formula_10, formula_11, formula_77에 대하여 다음이 성립한다.
비슷하게, 곱셈에 대하여 다음 성질들이 성립한다.
폰 노이만 정의에서, 순서수 formula_10의 원소 formula_97는 여전히 순서수이다.
순서수의 집합 formula_98에 대하여, 그 합집합 formula_99 역시 순서수이며, 이는 formula_2의 상한이다.
공집합이 아닌, 순서수의 모임 formula_101에 대하여, 그 교집합 formula_102 역시 순서수이며, 이는 formula_103의 최소 원소이다.
순서수의 집합은 일반적으로 순서수가 아니다. 순서수의 모임 formula_1은 고유 모임이며, 따라서 순서수가 아니다. 이 사실을 부랄리포르티 역설이라고 한다.
임의의 순서수 formula_10에 대하여, 다음 조건들이 서로 동치이며, 이를 만족시키는 순서수를 유한 순서수()라고 한다.
유한 순서수들은 자연수(음이 아닌 정수)들과 대응된다. 폰 노이만 정의에 따르면, 이들은
등의 집합으로 정의된다.
가장 작은 무한 순서수 formula_116는 자연수 집합 전체의 순서형이며, 폰 노이만 정의에서는 이는 자연수의 집합과 같다.
그 다음에는 formula_118, formula_119 등의 순서수들이 존재한다.
마찬가지로, formula_122는 다음과 같다. (순서수의 곱셈은 가환하지 않으며, formula_123이다.)
마찬가지로, formula_126 등이 존재한다.
이와 같은 방법으로 만들어지는 모든 순서수(즉, 자연수 formula_127과 formula_128에 대해 formula_129으로 나타낼 수 있는 순서수)들의 집합(의 순서형)은 그 자체로 순서수가 되며, 이는 formula_130이다. 비슷한 방법으로 formula_131 등이 존재한다.
formula_132의 극한은 formula_133이고, 마찬가지로 formula_134 등등이 존재한다.
formula_135의 극한은 formula_136라고 한다. 이 역시 가산 무한 순서수이다. 이는
을 만족시킨다.
모든 가산 무한 순서수들의 집합의 순서형은 가장 작은 비가산 무한 순서수 formula_138이다. 이는 가장 작은 비가산 무한 기수 formula_139과 같다.
모든 순서수들은 따름 순서수(-順序數, ) 또는 극한 순서수(極限順序數, )로 분류된다. (일부 문헌에서는 0을 극한 순서수에서 제외하기도 한다.) 이들은 초한 귀납법을 적용할 때 보통 개별적으로 다룬다.
순서수 formula_10에 대하여, 다음 조건들이 서로 동치이며, 이를 만족시키는 순서수를 극한 순서수라고 하며, 이를 만족시키지 않는 순서수를 따름 순서수라고 한다.
예를 들어, 순서수들
가운데, 1, 2와 formula_118, formula_119는 따름 순서수이며, 0과 formula_116는 극한 순서수이다.
임의의 순서수 formula_161가 주어졌다고 하자. 그렇다면, 모든 순서수 formula_10는 다음과 같은 꼴로 유일하게 나타내어진다.
이를 formula_10의 formula_167진 칸토어 표준형(formula_167進Cantor標準型, )이라고 한다. 진법 formula_167가 주어지지 않았을 때, 칸토어 표준형이란 formula_116진 칸토어 표준형을 뜻한다.
이를 재귀적으로 사용하여, 일부 순서수들을 양의 정수 및 기호 formula_116만으로 나타낼 수 있다. 예를 들어 다음과 같다.
이와 같이 나타낼 수 있는 순서수는 formula_136 이하이다. 여기서 순서수 formula_136는 다음과 같다.
즉, formula_136의 formula_116진 칸토어 표준형은 formula_178이므로 이는 자연수와 formula_116만으로 나타낼 수 없다.
모든 순서수는 짝순서수(-順序數, ) 또는 홀순서수(-順序數, )로 분류된다. 이는 자연수가 짝수와 홀수로 분류되는 것의 일반화이다. 이 개념은 다음과 같이 여러 가지로 정의될 수 있다.
순서수 formula_10에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 순서수를 짝순서수라고 한다.
짝순서수가 아닌 순서수를 홀순서수라고 한다.
순서수의 개념은 초한 귀납법을 사용할 때 필요하다. 이를 사용하여, 무한한 구조를 귀납적으로 손쉽게 정의할 수 있다. 예를 들어, 측도론에서 보렐 집합들은 어떤 기저로부터 생성되는 ‘생일’에 대응하는 순서수로 분류된다.
증명 이론에서는 주어진 수학 이론의 강력한 정도를 순서수로 측정하며, 이 이론을 순서수 분석이라고 한다. 순서수가 더 큰 이론은 순서수가 더 작은 이론의 무모순성을 증명할 수 있다.
게오르크 칸토어가 1883년에 도입하였다. 원래 순서수의 동치류로서의 정의는 고유 모임이므로 집합론적인 결함이 있었으며, 1923년에 존 폰 노이만이 오늘날 쓰이는 정의를 도입하였다.