[include(틀:이산수학·수리논리학)] [목차][[분류:집합론]] == 개요 == '''서수'''([[序]][[數]], ordinal) 또는 '''순서수'''([[順]][[序]][[數]])란, 집합의 원소에 순서를 [[잘 정의됨|"잘" 주기 위해서]] 고안된 개념이다. 예를 들어서, 총원 30명인 반이 있다고 해보자. 그럼 각 학생들에게 1번부터 30번까지 하나씩 번호가 주어질 것이다. 그러면 선생님은 이 번호를 가지고, 학생들을 순서대로 심부름을 시킨다든지, 발표를 시킨다든지 할 수 있을 것이다. 물론, 유한집합 또는 가산 무한집합에 순서를 주는 것은 자연수만으로도 충분하지만, 수학에는 원소가 자연수의 개수보다 많은 집합도 얼마든지 있으므로, 이들 집합의 원소에 순서를 주는 것은 자연수만으로는 부족하다. 따라서 __자연수를 포괄하면서, 순서가 "잘" 주어진__ 어떤 수체계가 필요하다. 이를 서수라고 한다. 서수는 [[게오르크 칸토어]]에 의해 처음 정의되었으며 현대 집합론에서는 보통 [[존 폰 노이만]]의 방식을 따라서 정의된다. 폰 노이만의 방식대로 정의하면 서수는 추이적(transitive) 집합이며, 포함 관계에 대해 정렬적인 집합이다. 모든 정렬적 집합은 이 서수 중 하나와 동형임이 증명되어있고 따라서 서수를 정렬 순서의 대표자로 사용할 수 있다. == 정의 == 순서를 "잘" 줬다는 것은, 물론 정렬 순서를 말한다. 아래의 두 성질, 1. Trichotomi: 임의의 [math(x,\:y)]에 대하여, [math(x>y,\:x=y,\:y<x,)] 중에 어느 하나가 유일하게 반드시 만족한다. 1. Transitivity: 임의의 [math(x,\:y)]에 대하여, [math(x<y)]이고, [math(y<z)]이면 [math(x<z)] 을 모두 만족하는 순서관계를 '''전순서'''라고 하는데, 전순서가 주어진 집합에서, 공집합이 아닌 임의의 부분집합이 항상 최소 원소를 가지면, 그 집합을 '''정렬집합'''이라 하고 그 전순서를 '''정렬순서'''라고 한다. (기타 다른 순서에 대해서는 [[순서 관계]] 참조.) 예를 들면, 자연수의 집합 [math(\mathbb{N})] 은 우리가 잘 아는 [math(<)]라는 순서 관계가 정의되어 있으며 임의의 공집합이 아닌 부분집합을 잡아도 최소원소가 당연히 존재한다. 그런데 정수의 집합 [math(\mathbb{Z})]를 생각해보면 [math(\{-1, -2, -3,\cdots\})]라는 부분집합을 선택했을 때 최소원소가 존재하지 않음을 알 수 있다. 따라서 [math(\mathbb{N})]은 정렬적이지만 [math(\mathbb{Z})]는 정렬적이지 않다. '''추이적 집합'''이란, 원소의 모든 원소를 원소로 가지는 집합이다. 즉, 집합 [math(\alpha)]에 대해, [math(\beta\in \alpha)]이고, [math(\gamma\in \beta)]이면, [math(\gamma\in \alpha)] 이 성립하면, [math(\alpha)]를 추이적 집합이라고 한다. (이를 달리 쓰면, "[math(\beta\in \alpha)]이면 [math(\beta\subset \alpha)]" 라고도 할 수 있다.) 추이적 집합의 익숙한 예는 언뜻보면 안떠오를 수도 있다. 예를 들어서, [math(\{\empty,\{\empty\},\{\{\empty\}\},\{\{\{\empty\}\}\}\})] 같은 집합은 추이적 집합이다.[* 자연수를 [[체르멜로]]의 방식으로 정의에 의하면, 이 집합은 [math(\{0,1,2,3\})]이다.] 어떤 집합 [math(\alpha)]가 추이적 집합이면서, 동시에, 관계 [math(\in)]에 대하여 정렬집합이면, [math(\alpha)]를 '''서수'''라고 한다. == 분류 == === 유한서수 === '''유한서수'''는 원소의 갯수가 유한한 서수이다. 아래의 몇가지 성질에 의해 유한서수를 찾을 수 있다. 1. 공집합 [math(\empty)]은, 정렬집합이면서 추이적집합이므로 서수이다. 원소가 없으므로 볼것도 없기 때문이다.[* 이런 경우를 "공허하게 참(vacuous truth)" 이라고 한다.] 1. [math(\alpha)]가 서수이면 [math(S(\alpha)=\alpha\cup\{\alpha\})]도 서수이다. [math(x\in S(\alpha))]이면, [math(x=\alpha)]이거나, [math(x\in\alpha)]인데, 어느 쪽이든 [math(y\in x)]에 대하여 [math(y\in S(\alpha))]이기 때문이다. [math(S(\alpha))]를 [math(\alpha)]의 successor이라고 하며, [math(\beta=S(\alpha))]인 [math(\alpha)]가 존재하면 [math(\beta)]를 successor ordinal 이라고 한다. [math(\empty)]에 유한번 [math(S)]를 적용하여, 얻은 집합 [math(S(S(\cdots(S(\alpha))\cdots)))]은 서수이다.[* 물론 이 집합의 존재성은 무한공리에 의해 보장된다. 자세한 것은 [[ZFC 공리계#s-2.7]] 참조.] 폰 노이만은 [math(\empty)]를 0, [math(S(\empty))]를 1, [math(S(S(\empty)))]를 2,[math(S(S(S(\empty))))]를 3, 등으로 정의했다. 이 정의에 의하면, 자연수가 일종의 서수가 된다. 서수가, 어떤 자연수와 1:1 대응이 존재하면 '''유한 서수'''라고 한다. 그러면, 자연수가 아닌 유한 서수가 존재하는지에 대해 자동적으로 의문이 생길 것이다. 이에 대한 답은 물론 "없다"이다. 임의의 서수 [math(\alpha)]에 대하여, [math(\beta\in\alpha)]도 서수가 되기 때문이다. 구체적으로, 자연수가 아닌 유한 서수 중에 원소 수가 제일 작은 서수의 원소수를 [math(n)]이라고 하자. [math(\alpha)]를 원소의 갯수가 [math(n)]인 서수라고 하자. 그런데, 두 유한서수 [math(x,y)]에 대하여 [math(x\in y)]이면, [math(x\subsetneq y)]이므로, [math(x)]의 원소의 갯수가 [math(y)]보다 적다. 따라서, [math(\alpha)]의 원소는 [math(n-1)]이하의 자연수여야 한다. 그런데, 원소의 갯수가 모두 [math(n)]개이므로, [math(\alpha=\{0,1,\cdots,n-1\}=n)] 가 성립한다. 즉, 원소의 갯수가 [math(n)]개인 서수는 모두 같은 집합이 나오므로 가정에 모순이 된다. 그래서, 자연수는 유한 서수 그 자체이다. 서수로서의 자연수의 집합을 [math(\omega)]라고 쓴다. 물론, [math(\omega=\mathbb{N})]이지만, 서수로서의 성질이 중요할 때, [math(\mathbb{N})] 대신 [math(\omega)]을 쓰는 것이다. 다음 각 조건들은 어떤 서수[math(\alpha)]가 유한 서수일 필요충분 조건이다. * [math(\alpha<\omega)] * [math(\alpha)]를 서수로 갖는 집합을 [math(A)]라고 할 때, [math(\left|A\right|<\aleph_{0})]가 성립한다. 즉, 폰 노이만 정의에 의해 유한집합이다. * [math(\left(\alpha,\preceq\right))]의 역순서인 [math(\left(\alpha,\succeq\right))]가 어떤 부분집합을 취하더라도 최대원소를 지닌다. * 위상수학적으로 [math(\alpha)]에 순서 위상을 부여할 때, 집적점을 지니지 않는다. === 초한서수 === [[게오르그 칸토어]]가 [[절대적 무한]](Absolute Infinite, 기호: '''[[Ω]]''')과 구분하기 위해 상대적 무한(Relative Infinite, 기호: '''[[ω]]''')에 붙인 이름이 바로 초한수(Transfinite number)다. '''Ω'''과 '''ω'''은 각각 [[오메가]]의 대문자와 소문자를 가리킨다. ==== 가산 무한서수 ==== 두 정렬집합 [math(A,B)]에 대하여, 다음 세 가지 중 하나가 유일하게 항상 성립한다. 1. [math(A)]와 [math(B)]가 순서 동형이다. 1. [math(A)]와 [math(\{x\in B|x<b\})]가 순서동형인 [math(b\in B)]가 유일하게 존재한다. 1. [math(\{x\in A|x<a\})]와 [math(B)]가 순서동형인 [math(a\in A)]가 유일하게 존재한다. 따라서, 어떤 서수 [math(A)]가 무한집합이라면, 임의의 자연수 [math(n)]을 항상 포함하여야 한다. 자연수가 정렬집합이고, 무한집합에 원소가 더 많으므로 어떤 [math(\alpha \in A)]에 대하여, [math(\alpha\approx n)]이 성립하여야 하는데, 서수의 원소는 서수이고, 자연수 [math(n)]과 원소의 갯수가 같은 서수는 [math(n)] 밖에 없기 때문이다. 그런데, 서수로 이루어진 집합 [math(A)]가 임의의 원소 [math(\alpha\in A)]에 대하여, [math(\alpha\subset A)]이면 [math(A)]도 서수이다. 그래서, 가장 작은 가산 무한서수는 덜도 말고 더도 말고 자연수만을 포함하고 있는 자연수 집합인 [math(\omega)]이다. 즉, [math(\omega=\mathrm{Ord}\left(\mathbb{N}\right)=\mathrm{Ord}\left(\{1,2,3,4,...\}\right)=\mathrm{Ord}\left(\{0,1,2,3,...\}\right))] 역시 위의 과정처럼 [math(\omega+\alpha=\{0,1,2,3,...\}\cup\{\omega, \omega+1, \omega+2, ..., \omega+\left(\alpha-1\right)\})]로 확장할 수 있으며, 이 과정을 거쳐서 [math(\omega+\omega=\omega\cdot 2)]로 확장할 수 있다. 이 과정을 계속해서 거치는 것으로, [math(\omega+\omega+...=\omega\cdot\omega=\omega^{2})]까지 확장할 수 있는데, 이 서수는 [math(\omega\cdot m+n)]로 구성할 수 있는 모든 서수집합의 서수다. 여기서, [math(\omega)]나 [math(\omega^{2})]는 어떤 서수의 다음 수로 정의되는 다른 서수들과 달리 어떤 서수들의 극한으로 정의됨을 알 수 있다. 이러한 서수들을 극서수 (Limit ordinal)라고 한다. 역시 이 과정을 무한하게 반복할 수 있으며, [math(\omega^{\omega})], [math(\omega^{\omega^{\omega}})]. 이런 식으로 계속해서 순서수가 확장될 수 있으며, 이런 확장 한계 서수를 모은 집합의 극한값을 구할 수 있다. 즉, [math(\{\omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \omega^{\omega^{\omega^{\omega}}}...\})]의 극한값([math(\omega)] 위에 [math(\omega)]가 무한번 나열된 수)이며, 기호로는 [math(\epsilon_{0})]라고 표기한다. 또한, 이 극한값까지 오게 되면 [math(\omega^{\epsilon_{0}}=\epsilon_{0})]가 된다. 이것보다 더 큰 가산서수들도 존재한다. [[/큰 가산서수|큰 가산서수]] 참고. 기수와의 차이점은, 기수는 [math(2^{\aleph_{0}}>\aleph_{0})]지만, 서수는 [math(2^{\omega}=\omega)]가 된다. ==== 비가산 무한서수 ==== 모든 가산 무한 서수의 집합을 고려하자. 이 집합의 서수를 [math(\omega_{1})]라고 할 수 있는데, 대각선논법과 비슷한 논리를 통하면, 이 서수는 그 가산 무한 서수와 1대 1로 대응되지 않는다는 것을 보일 수 있다. 즉, [math(\omega_{1})]는 비가산 무한서수가 되며, 수학적으로 이 서수가 최소의 비가산 무한서수라는 것이 알려져 있다. 또한, [math(\omega_{1}=\aleph_{1})]이다. === 극한서수 === [math(\alpha=\beta+1)]를 만족하는 순서수 [math(\beta)]가 존재하지 않는 순서수 [math(\alpha)]가 극한서수다. 그 외에도 여러가지 더 다양한 추가정의들이 있는데, 쉽게 말하자면, [math(0, \omega, 2\omega, ...)] 처럼 따름서수들의 프로토타입들이 바로 극한서수다. === 따름서수 === [math(\alpha=\beta+1)]를 만족하는 순서수 [math(\beta)]가 존재하는 순서수 [math(\alpha)]가 따름서수다. 그 외에도 여러가지 더 다양한 추가정의들이 있는데, 쉽게 말하자면, [math(1, 2, ..., \omega+1, \omega+2, ..., 2\omega+1, 2\omega+2, ..., ...)] 처럼 극한서수로부터 정의되는 순서수가 따름서수다. ==== 홀순서수 ==== [math(\alpha=2\beta+1)]를 만족하는 순서수 [math(\beta)]가 존재하는 순서수 [math(\alpha)]가 홀순서수다. 그 외에도 여러가지 더 다양한 추가정의들이 있는데, 쉽게 말하자면, [math(1, 3, ..., \omega+1, \omega+3, ..., 2\omega+1, 2\omega+3, ..., ...)] 처럼 극한서수로부터 홀수번째로 따라오는 순서수가 홀순서수다. ==== 짝순서수 ==== [math(\alpha=2\beta+1)]를 만족하는 순서수 [math(\beta)]가 존재하지 않는 순서수 [math(\alpha)]가 짝순서수다. 그 외에도 여러가지 더 다양한 추가정의들이 있는데, 쉽게 말하자면, [math(2, 4, ..., \omega+2, \omega+4, ..., 2\omega+2, 2\omega+4, ..., ...)] 처럼 극한서수로부터 짝수번째로 따라오는 순서수가 짝순서수다. [각주]