서수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
수학 체계
기초

\mathbb{N}\sub\mathbb{Z}\sub\mathbb{Q}\sub\mathbb{R}\sub\mathbb{C}

복소수의 확장
기타

i 허수 단위 = \sqrt{-1}
\pi 원주율 ≈ 3.14159 26535 ...
e 자연로그의 밑 ≈ 2.71828 ( \notin \mathbb{Q})

주요 상수

π - e - √2 - √3 - γ -
φ - β* - δ - α - C2 -
M1 - B2 - B4 - Λ - K -
K - K - L - μ - EB -
Ω - β - λ - D(1) - λμ -
Cah. - Lap. - A-G - Λ - K-L -
Apr. - θ - Bac. - Prt. - Lb. -
Niv. - Sie. - Kin. - F - L

수학집합론에서 서수(序數)(ordinal)는 게오르크 칸토어1897년에 도입한 의 종류로, 자연수의 개념을 확장한 것이지만 정수기수와는 다르다. 서수의 개념을 이용해 순서 구조를 가진 집합들을 분류할 수 있다.

정렬순서수학적 귀납법을 확장한 초한귀납법이 적용될 수 있는 완전순서를 말하는데, 서수는 정렬순서들을 순서동형에 따라 분류했을 때의 동치류에 대응된다. 각 서수는 그보다 작은 서수들의 집합으로 정의되며, 크게 0과 따름서수(successor ordinal) 및 극한서수(limit ordinal)로 분류할 수 있다. 서수에는 자연스러운 위상이 주어진다.

자연수의 확장으로서의 서수[편집]

자연수는 집합의 크기를 표현하기 위해 사용되기도 하고, 순서대로 늘어선 수열에서 원소의 위치를 나타내기 위해 사용되기도 한다. 이 두 용도는 유한집합의 경우 크게 다르지 않으나, 무한집합의 경우에는 이 구분이 중요해진다. 전자 쪽을 확장한 것이 기수이고, 후자 쪽을 확장한 것이 이 글에서 다루는 서수이며, 이 두 개념은 전부 칸토어가 개발한 것이다.

기수는 아무런 구조도 갖지 않는 집합에 대해서도 부여할 수 있지만, 서수는 정렬순서가 주어진 집합에 대해서만 정의되며, 실제로 정렬순서의 개념과 서수의 개념에는 매우 밀접한 관련이 있다. 간단히 말해 정렬순서란 무한히 감소하는 수열이 존재하지 않는 완전순서(임의의 두 원소의 크기를 비교할 수 있는 순서)를 말한다. (물론 무한히 증가하는 수열은 존재할 수 있다.) 임의의 완전순서집합에 대해 가장 작은 원소를 0이라 하고 그 다음 원소를 1이라 하는 식으로 그 집합의 원소들을 서수를 이용해 순서매길 수 있으며, 또한 이 집합의 "길이"를 여기에서 집합의 원소에 대응되지 않는 가장 작은 서수로 정의할 수 있다. 이 "길이"를 집합의 순서형(order type)이라고 한다.

0은 가장 작은 서수이며 그 다음의 서수는 1,2,3 등으로 나아간다. 각 서수는 그보다 작은 서수들의 집합을 이용해 정의되는데, 예를 들어 서수 42는 집합 {0,1,2,…,41}의 순서형으로 정의할 수 있다. 혹은, 이 집합 '자체'를 42로 정의하는 경우도 많다.

여기까지 언급된 서수는 유한서수이며, 이들은 자연수와 차이가 없다. 가장 작은 무한서수는 자연수 집합 전체의 순서형이며, 기호로는 ω로 쓴다. (물론 정의에 따라 자연수 집합 자체가 ω라고 말할 수도 있다.)

서수 ω²을 그림으로 표현. 각 막대기는 적당한 자연수 m과 n에 대해 ω·m+n 형태의 서수에 대응된다.

서수의 구체적인 정의를 다루기 전에, 먼저 비교적 작은 서수들이 어떤 것이 있는지 알아보자. 위에 언급했듯이 가장 작은 서수는 자연수인 0,1,2,3,4,5,… 등등이 있다. '모든' 자연수들의 뒤에 등장하는 서수가 첫 무한서수인 ω이고, 그 뒤에는 ω+1, ω+2, ω+3 등으로 나아간다. (덧셈기호의 의미는 아래에서 보다 명확히 다룬다. 여기에서는 일단 "ω+1" 등이 서수를 나타내는 하나의 기호라고 생각할 것.) 이 뒤에 나타나는 서수는 ω·2로, 이는 ω+ω와 같다. 물론 그 뒤에는 ω·2+1, ω·2+2 등등으로 이어지고, 그 뒤에는 ω·3이 있다. 같은 방법으로 ω·4나 ω·5 등의 서수도 있음을 알 수 있다. 이와 같은 방법으로 만들어지는 모든 서수(즉, 자연수 m과 n에 대해 ω·m+n으로 나타낼 수 있는 서수)들의 집합의 순서형은 그 자체로 서수가 되며, 이를 ω2으로 나타낸다. 비슷한 방법으로 ω3이나 ω4도 정의되며, ωω나 ωω² 등을 정의할 수도 있고, 이렇게 한참 더 나아가면 ε0라는 서수가 등장한다. 여기까지 등장한 서수들은 비교적 굉장히 작은 것들이며, 이와 같은 방법으로 끝없이 서수를 정의하며 나아가는 것이 가능하다.

정의[편집]

정렬순서의 정의[편집]

정렬순서는 모든 공집합이 아닌 부분집합이 최소원소를 갖는 순서를 말한다. (종속선택공리를 가정한 경우 이는 완전순서이고 무한히 감소하는 수열이 존재하지 않는다는 것과 동치이다.) 정렬순서의 중요성은 초한귀납법이 적용될 수 있다는 점에 있으며, 컴퓨터 프로그램이 가지는 상태들이 모든 단계가 그보다 "하위의" 단계에서 따라나오는 형태로 정렬되어있을 경우 그 프로그램은 언젠가 (계산을 마치고) 정지할 것임을 알 수 있다.

두 정렬순서집합에 대해, 만약 두 집합이 원소들의 이름만 다를 뿐 그 순서 구조에는 아무 차이가 없다면 둘을 구분하는 것은 큰 의미가 없을 것이다. 구체적으로는, 이는 두 집합의 원소들을 한 집합에서 어느 원소보다 작은 원소는 다른 집합에서도 작은 원소로 대응되도록 일대일대응시킬 수 있는 경우를 말한다. 이와 같은 일대일대응을 순서동형사상이라 하며, 이렇게 대응되는 두 정렬순서집합을 서로 순서동형이라고 한다. (이는 물론 동치관계가 된다.) 정렬순서집합들 사이의 순서동형사상은 존재할 경우 언제나 유일하며, 이 점에서도 순서동형인 집합들을 사실상 동일한 구조를 갖고 있음을 알 수 있고, 따라서 이들의 동치류를 자연스럽게 대표할 대상을 선택할 필요가 있다. 이 대상이 바로 서수이며, 이를 이용해 임의의 정렬순서집합의 원소들을 자연스럽게 순서매길 수도 있다.

여기에서, 각 순서집합에 대해 이와 동형인 집합들의 동치류가 지나치게 커서, 보통의 ZF 공리계에서는 집합이 될 수 없다는 부분에 기술적인 문제가 있다. 그러나 이는 심각한 문제는 아니며, 아래에 나올 폰 노이만의 정의를 이용하면 해결된다.

동치류를 이용한 서수의 정의[편집]

프린키피아 마테마티카(Principia Mathematica) 등에 등장하는 서수의 본래 정의는 정렬순서집합의 순서형을 그와 순서동형인 모든 정렬순서집합들의 집합으로 놓은 것이었다. 이는 ZF 공리계를 비롯한 관련 공리적 집합론 체계에서는 이것이 집합이 되기에 너무 크다는 문제가 있기에 사용할 수 없는 방법이다. 그러나 형 이론 (type theory)이나 콰인의 새기초(New Foundations) 및 관련 체계에서는 이 정의를 그대로 사용할 수 있다.

폰 노이만이 제시한 서수의 정의[편집]

위의 문제를 피하기 위해, 서수를 각 동치류를 자연스럽게 대표하는 정렬순서집합으로 정의하기도 한다. 즉, 여기에서 서수는 특별한 정렬순서집합으로, 임의의 정렬순서집합이 정확히 하나의 서수와 순서동형이어야 한다. 아래의 정의는 존 폰 노이만이 제시했으며 현재는 표준 정의로 받아들여지고 있다.

집합 S의 모든 원소가 동시에 S의 부분집합이고, 그 원소들 사이의 집합적 포함관계가 완전순서를 이룰 경우 S를 서수라고 한다.

위의 정의를 만족하는 집합 S는 정칙성공리(axiom of regularity)에 따라 자동적으로 정렬순서집합이 된다.

자연수들이 위의 정의를 만족함은 간단히 확인할 수 있다. 예로서 자연수 2 = {0,1}은 4 = {0,1,2,3}의 원소이며 동시에 부분집합이다.

모든 정렬순서집합이 정확히 하나의 서수와 순서동형이라는 것은 초한귀납법을 이용해 보일 수 있다.

각 서수의 원소들은 그 자체로 서수가 된다. S와 T가 서수일 때 S가 T의 원소일 필요충분조건은 S가 T의 진부분집합이라는 것이다. 또한 언제나 S가 T의 원소이거나, T가 S의 원소이거나, 혹은 둘이 동일한 집합이거나 세 가지 중에 하나가 성립하며, 따라서 임의의 서수들의 집합은 완전순서집합이 된다. 더 나아가서, 임의의 서수들의 집합은 정렬순서집합이기도 하다. 이 중요한 결과는 자연수 집합이 정렬순서집합이라는 것의 확장이며, 이 덕분에 서수에 대해 초한귀납법을 자유로이 사용할 수 있다.

또다른 중요한 결과는 모든 서수는 그보다 작은 서수들 전부로 이루어진 집합이다라는 것이다. 이것으로 서수의 집합적 구조는 그보다 작은 서수들에 의해 완전히 결정되며, 이를 이용해 서수에 대한 여러 정리를 증명할 수 있다. 그 예로는 임의의 서수들의 집합은 거기에 속하는 서수들 전부의 합집합을 상한으로 가진다는 것과 모든 서수들을 전부 모은 것은 집합이 아니다라는 것이 있다. 만약 모든 서수들을 전부 모은 것이 집합이라면, 이는 서수의 정의를 만족시키므로 따라서 자기 자신의 원소가 되고, 정칙성공리를 위반하게 되기 때문이다. (부랄리-포르티 역설 참고.) 모든 서수들을 전부 모은 모임을 "Ord", "ON", "∞" 등으로 표시하기도 한다.

서수가 유한집합일 필요충분조건은 역순서가 정렬순서라는 것이며, 이는 또다시 모든 부분집합이 최대원소를 갖는다는 것과 동치이다.

서수의 산술[편집]

서수들에 대해 덧셈, 곱셈, 지수 연산을 정의하는 것이 가능하다. 각 연산은 연산 결과에 해당하는 정렬순서집합을 직접 만들어내는 방법으로 정의할 수도 있고, 초한반복을 이용해 정의할 수도 있다.

함께 보기[편집]