| 수학기초론 Foundations of Mathematics | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 다루는 대상과 주요 토픽 | ||
| 수리논리학 | 논리 · 논증{귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문(조각적 정의) · 명제 논리(명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리(존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론 | ||
| 집합론 | 집합(원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계(동치관계 · 순서 관계) · 순서쌍(튜플) · 서수(하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC(선택공리) · 기수(초한기수) · 절대적 무한 · 모임 | ||
| 범주론 | 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 | ||
| 계산가능성 이론 | 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수 | ||
| 정리 | |||
| 드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리(괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리 | |||
| 기타 | |||
| 예비사항(약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학 | |||
| 틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | ||
1. 개요
서수(序數, ordinal) 또는 순서수(順序數)란, 집합의 원소에 순서를 "잘" 주기 위해서 고안된 개념이다. 예를 들어서, 총원 30명인 반이 있다고 해보자. 그럼 각 학생들에게 1번부터 30번까지 하나씩 번호가 주어질 것이다. 그러면 선생님은 이 번호를 가지고, 학생들을 순서대로 심부름을 시킨다든지, 발표를 시킨다든지 할 수 있을 것이다. 물론, 유한집합 또는 가산 무한집합에 순서를 주는 것은 자연수만으로도 충분하지만, 수학에는 원소가 자연수의 개수보다 많은 집합도 얼마든지 있으므로, 이들 집합의 원소에 순서를 주는 것은 자연수만으로는 부족하다. 따라서 자연수를 포괄하면서, 순서가 "잘" 주어진 어떤 수체계가 필요하다. 이를 서수라고 한다.서수는 게오르크 칸토어에 의해 처음 정의되었으며 현대 집합론에서는 보통 존 폰 노이만의 방식을 따라서 정의된다. 폰 노이만의 방식대로 정의하면 서수는 추이적(transitive) 집합이며, 포함 관계에 대해 정렬적인 집합이다. 모든 정렬적 집합은 이 서수 중 하나와 동형임이 증명되어있고 따라서 서수를 정렬 순서의 대표자로 사용할 수 있다.
2. 정의
순서를 "잘" 줬다는 것은, 물론 정렬 순서를 말한다. 아래의 두 성질:- 삼일률(三一律, trichotomy): 임의의 [math(x)], [math(y)]에 대하여 [math(x>y)], [math(x=y)], [math(x<y)] 중 어느 하나가 유일하게 반드시 만족한다.
- 추이율(推移律, transitivity): 임의의 [math(x)], [math(y)]에 대하여 [math(x<y)]이고 [math(y<z)]이면 [math(x<z)]
예를 들면, 자연수의 집합 [math(\N)]은 우리가 잘 아는 "[math(<)]"라는 순서 관계가 정의되어 있으며, 임의의 공집합이 아닌 부분집합을 잡아도 최소원소가 당연히 존재한다. 그런데 정수의 집합 [math(\Z)]를 생각해보면 [math(\{-1, -2, -3, \cdots\})]라는 부분집합을 선택했을 때 최소원소가 존재하지 않음을 알 수 있다. 따라서 [math(\N)]은 정렬적이지만 [math(\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\}\}, \{\empty, \{\empty\}, \{\empty, \{\empty\}\}\}\})] 같은 집합은 추이적 집합이다.[1]
어떤 집합 [math(\alpha)]가 추이적 집합이면서 동시에 관계 [math(\in)]에 대하여 정렬집합이면, [math(\alpha)]를 서수라고 한다.
3. 분류
3.1. 유한서수
유한서수는 원소의 개수가 유한한 서수이다. 아래의 몇가지 성질에 의해 유한서수를 찾을 수 있다.- 공집합 [math(\empty)]은, 정렬집합이면서 추이적집합이므로 서수이다. 원소가 없으므로 볼것도 없기 때문이다.[2]
- [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)))]은 서수이다.[3] 폰 노이만은 [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)]에 순서 위상을 부여할 때, 집적점을 지니지 않는다.
3.2. 초한서수
게오르그 칸토어가 절대적 무한(Absolute Infinite, 기호: Ω)과 구분하기 위해 상대적 무한(Relative Infinite, 기호: ω)에 붙인 이름이 바로 초한수(Transfinite number)다. Ω과 ω은 각각 오메가의 대문자와 소문자를 가리킨다.3.2.1. 가산 무한서수
두 정렬집합 [math(A,B)]에 대하여, 다음 세 가지 중 하나가 유일하게 항상 성립한다.- [math(A)]와 [math(B)]가 순서 동형이다.
- [math(A)]와 [math(\{x\in B|x<b\})]가 순서동형인 [math(b\in B)]가 유일하게 존재한다.
- [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)]가 된다는 점이다.[4]
3.2.2. 비가산 무한서수
모든 가산 무한 서수의 집합을 고려하자. 이 집합의 서수를 [math(\omega_{1})]라고 할 수 있는데, 대각선논법과 비슷한 논리를 통하면, 이 서수는 그 가산 무한 서수와 1대 1로 대응되지 않는다는 것을 보일 수 있다. 즉, [math(\omega_{1})]는 비가산 무한서수가 되며, 수학적으로 이 서수가 최소의 비가산 무한서수라는 것이 알려져 있다. 또한, [math(\omega_{1}=\aleph_{1})]이다.3.3. 극한서수
[math(\alpha=\beta+1)]를 만족하는 순서수 [math(\beta)]가 존재하지 않는 순서수 [math(\alpha)]가 극한서수다.그 외에도 여러가지 더 다양한 추가정의들이 있는데, 쉽게 말하자면, [math(0, \omega, \omega2, ...)] 처럼 따름서수들의 프로토타입들이 바로 극한서수다.
3.4. 따름서수
[math(\alpha=\beta+1)]를 만족하는 순서수 [math(\beta)]가 존재하는 순서수 [math(\alpha)]가 따름서수다.그 외에도 여러가지 더 다양한 추가정의들이 있는데, 쉽게 말하자면, [math(1, 2, ..., \omega+1, \omega+2, ..., \omega2+1, \omega2+2, ..., ...)] 처럼 극한서수로부터 정의되는 순서수가 따름서수다.
3.4.1. 홀순서수
[math(\alpha=2\beta+1)]를 만족하는 순서수 [math(\beta)]가 존재하는 순서수 [math(\alpha)]가 홀순서수다.그 외에도 여러가지 더 다양한 추가정의들이 있는데, 쉽게 말하자면, [math(1, 3, ..., \omega+1, \omega+3, ..., \omega2+1, \omega2+3, ..., ...)] 처럼 극한서수로부터 홀수번째로 따라오는 순서수가 홀순서수다.
3.4.2. 짝순서수
[math(\alpha=2\beta+1)]를 만족하는 순서수 [math(\beta)]가 존재하지 않는 순서수 [math(\alpha)]가 짝순서수다.그 외에도 여러가지 더 다양한 추가정의들이 있는데, 쉽게 말하자면, [math(2, 4, ..., \omega+2, \omega+4, ..., \omega2+2, \omega2+4, ..., ...)] 처럼 극한서수로부터 짝수번째로 따라오는 순서수가 짝순서수다.
4. 연산
기존의 덧셈, 곱셈, 지수는 초한서수를 다루도록 정의되어있지 않기 때문에, 연산도 다시 정의해주어야 한다. 이것이 중요한 이유는 초한서수에서는 교환법칙이 성립하지 않기 때문이다. 예를 들어, [math(5+\omega)]는 [math(\omega+5)]가 아닌 [math(\omega)]와 같다.4.1. 덧셈
1. [math(\alpha+0=\alpha)]2. [math(\alpha+1=\alpha\cup\{\alpha\})]
3. [math(\alpha+(\beta+1)=(\alpha+\beta)+1)]
4. [math(\alpha+\beta=\displaystyle\bigcup_{\gamma<\beta}(\alpha+\gamma))] ([math(\beta)]가 극한서수인 경우)
3번까지는 자연수에서의 덧셈과 정의가 같다. 또한 2번과 3번을 묶어 다음과 같이 나타낼 수도 있다.
- [math(\alpha+(\beta+1)=(\alpha+\beta)\cup\{\alpha+\beta\})]
예를 들면 [math(\omega^2+\omega^2)]는 [math(\{\omega^2,\omega^2+1,\omega^2+2,\cdots\}\cup\{\omega^2+\omega,\omega^2+\omega+1,\omega^2+\omega+2,\cdots\}\cup\{\omega^2+\omega2,\omega^2+\omega2+1,\omega^2+\omega2+2,\cdots\}\cup\cdots)]으로 정의된다. 그런데 이는 [math((\omega^2+\omega)\cup(\omega^2+\omega2)\cup(\omega^2+\omega3)\cup\cdots)]라고도 나타낼 수 있다.
위에서 예로 든 [math(5+\omega)]는 정의에 따라 [math(\{5+1,5+2,5+3,\cdots\})]이다. 그런데 이것은 [math(\omega=\{1,2,3,\cdots\})]에서 앞의 [math(1,2,3,4,5)]를 제외한 것일 뿐이다.[5] 유한 개의 원소가 빠진다 한들 모든 자연수 이후에 나온다는 순서는 변하지 않으므로 둘은 동일한 서수이다. 이와는 달리, [math(\omega+5)]는 모든 자연수가 나온 다음에도 5번을 더 가야 나오는 순서이므로 더 크다.
교환법칙과는 달리 결합법칙은 성립한다. 때문에 [math((\omega+1)+\omega=\omega+(1+\omega)=\omega+\omega)]가 성립한다.
4.2. 곱셈
4.3. 지수
[1] 체르멜로 방식의 자연수의 정의에 의하면, 이 집합은 [math(\{0,1,2,3\})]이다.[2] 이런 경우를 "공허하게 참(vacuous truth)" 이라고 한다.[3] 물론 이 집합의 존재성은 무한공리에 의해 보장된다. 자세한 것은 ZFC 공리계 참조.[4] 그런데 기수와 서수의 성질로 인해 [math(\aleph_0+1=\aleph_0)]이지만 [math(\omega+1>\omega)]라는 다소 직관과는 동떨어진 결론을 얻는다.[5] 또는 각 원소에 5를 더했다고도 해석할 수 있다. 둘이 같다는 것엔 변함없다.