집합의 기본 성질 중 하나는 집합의 원소의 개수이다. 유한집합의 경우 원소의 개수를 자연수로 나타낼 수 있지만, 무한집합의 크기를 다루려면 더 정교한 개념이 필요하다. 칸토어는 19세기 말 무한의 크기를 체계적으로 연구하면서 기수와 서수라는 혁신적인 개념을 도입했다. 이것은 수학에서 무한을 다루는 방식을 완전히 바꾸어 놓았다.
기수(cardinal number)는 집합의 크기 또는 원소의 개수를 나타내는 개념이다. 두 집합 사이에 일대일대응이 존재하면 같은 기수를 가진다고 말한다. 이것은 유한집합뿐만 아니라 무한집합에도 적용되어, 서로 다른 크기의 무한이 존재함을 보여준다. 한편 서수(ordinal number)는 집합의 순서 구조를 나타내는 개념으로, 무한집합도 적절히 순서를 부여하면 그 순서 유형을 서수로 표현할 수 있다.
흥미롭게도 모든 자연수는 유한기수인 동시에 유한서수이다. 예를 들면, 자연수 \(3\)은 세 개의 원소를 가진 집합의 크기를 나타내는 기수이면서, 동시에 세 번째 위치까지의 순서를 나타내는 서수이기도 하다. 이 부에서는 먼저 집합을 사용하여 자연수를 구성하는 방법을 살펴본 후, 이것을 바탕으로 기수와 서수의 개념을 살펴본다.
앞 장까지는 자연수 집합 \(\mathbb{N}\)을 익숙한 수의 집합으로 사용하였다. 이 장에서는 자연수를 집합으로 구성하고, 자연수의 연산과 순서를 정의하며, 수학적 귀납법의 원리를 살펴본다. 이 과정에서 자연수 집합의 존재와 재귀적 정의에 필요한 집합론적 사실도 함께 명시한다.
1. 집합을 사용한 자연수의 정의
폰 노이만(von Neumann)의 방법을 따라 자연수를 구성해 보자. 먼저 \(0\)을 공집합으로 정의하고, 이미 만든 자연수 \(n\)에서 따름수 \(S(n)\)을 반복하여 다음 자연수를 만든다. 처음 몇 단계는 다음과 같다. \[\begin{aligned} 0 &= \varnothing = \{\},\\[3pt] 1 &= \{0\} = \{\varnothing\},\\[3pt] 2 &= \{0,\,1\} = \{\varnothing,\,\{\varnothing\}\},\\[3pt] 3 &= \{0,\,1,\,2\} = \{\varnothing,\,\{\varnothing\},\,\{\varnothing,\,\{\varnothing\}\}\},\\[3pt] &\vdots \end{aligned}\]
일반적으로, 자연수 \(n\)의 따름수(successor) \(S(n)\)을 다음과 같이 정의한다. \[S(n)=n\cup\{n\}.\] 직관적으로 \(S(n)\)은 \(n\)의 다음 수, 즉 \(n+1\)을 나타내는 것으로 생각해도 무방하다. 예를 들어,
- \(S(0)=\varnothing\cup\{\varnothing\}=\{\varnothing\}=1\),
- \(S(1)=\{0\}\cup\{\{0\}\}=\{0,\,1\}=2\),
- \(S(2)=\{0,\,1\}\cup\{\{0,\,1\}\}=\{0,\,1,\,2\}=3\).
각 단계에서 만들어지는 자연수는 자신보다 앞에서 만들어진 자연수들을 원소로 갖는다. 뒤의 순서 관계 절에서는 이를 이용하여 \(m<n\)을 \(m\in n\)으로 정의하고, \(m\le n\)과 부분집합 관계의 관계를 증명한다.
문제 6.1. 폰 노이만의 자연수 구성에 대하여 다음을 구하시오.
- \(4=S(3)\)과 \(5=S(4)\)를 \(0,\,1,\,2,\,3,\,4\)를 원소로 사용하여 나타내시오.
- 다음 각 명제의 참과 거짓을 판정하시오. \[ 0\in3,\quad 2\in3,\quad 3\in3,\quad 2\subseteq3,\quad 3\subseteq2. \]
- \(S(S(2))\)를 계산하고 \(4\)와 비교하시오.
- \(m,n\in\{0,\,1,\,2,\,3\}\)에 대하여 \(m\in n\)인 순서쌍 \((m,\,n)\)을 모두 구하시오.
집합 \(N\)이 다음 두 조건을 모두 만족시킬 때 \(N\)을 귀납적 집합이라고 부른다.
- \(0\in N\)이다.
- \(n\in N\)일 때마다 \(S(n)\in N\)이다.
문제 6.2. 다음 물음에 답하시오.
- \(\{0,\,1,\,2\}\)는 귀납적 집합인가? 그 이유를 설명하시오.
- \(\mathbb N\setminus\{2\}\)는 귀납적 집합인가? 그 이유를 설명하시오.
- \(N\)이 귀납적 집합이면 \(0,\,1,\,2,\,3,\,4\in N\)임을 따름수의 정의를 사용하여 보이시오.
이제 귀납적 집합이 적어도 하나 존재한다고 가정하자. 이 가정은 앞 장의 집합 연산만으로는 증명할 수 없으며, 공리적 집합론에서는 무한 공리로 보장된다. 귀납적 집합 하나를 \(I\)라 하고 \[\mathcal I=\{J\subseteq I\mid J\text{는 귀납적 집합}\}\] 로 두자. \(I\in\mathcal I\)이므로 \(\mathcal I\)는 공집합이 아니다. 이때 \[\mathbb N=\bigcap_{J\in\mathcal I}J\] 로 정의하고 이를 자연수 집합이라고 부른다. 또한 \(\omega\)로도 나타낸다. [초중등 교육과정에서는 \(1\) 이상인 정수를 자연수라고 부르지만 집합론에서는 \(0\) 이상인 정수를 자연수라고 부른다. 공리적 집합론에서 위 집합족을 실제 집합으로 만드는 과정에는 멱집합 공리와 분리 공리꼴이 사용된다.] 이 정의는 처음 택한 귀납적 집합 \(I\)에 의존하지 않는다. 즉 \(\mathbb N\)은 모든 귀납적 집합에 포함되는 가장 작은 귀납적 집합이다. 원소나열법으로 쓰면 \[\mathbb N=\{0,\,1,\,2,\,3,\,4,\,\ldots\}.\]
문제 6.3. 공집합이 아닌 귀납적 집합족의 교집합이 귀납적 집합임을 증명하시오. 이를 이용하여 위에서 정의한 \(\mathbb N\)이 귀납적 집합이고 모든 귀납적 집합에 포함됨을 보이시오.
2. 수학적 귀납법
다음 원리를 수학적 귀납법(mathematical induction)이라고 부른다.
정리 6.1. (수학적 귀납법)
자연수에 대한 명제 \(P(n)\)이 다음 두 조건을 만족시키면 모든 자연수 \(n\)에 대하여 \(P(n)\)이 성립한다.
- 기초 단계: \(P(0)\)이 성립한다.
- 귀납 단계: 임의의 자연수 \(k\)에 대하여 \(P(k)\)가 성립하면 \(P(S(k))\)도 성립한다.
문제 6.4. 자연수 집합이 가장 작은 귀납적 집합이라는 사실을 이용하여 정리 6.1을 증명하시오.
수학적 귀납법과 짝을 이루는 정의 원리를 재귀적 정의(recursive definition)라고 부른다. 재귀적으로 주어진 규칙이 실제로 하나의 함수를 정의한다는 사실은 별도의 정리를 필요로 한다.
정리 6.2. (자연수 위의 재귀 정리)
집합 \(A\), 원소 \(a\in A\), 함수 \(F\colon A\to A\)가 주어지면 \[f(0)=a,\quad f(S(n))=F(f(n))\] 을 모든 \(n\in\mathbb N\)에 대하여 만족시키는 함수 \(f\colon\mathbb N\to A\)가 유일하게 존재한다.
이 정리의 엄밀한 집합론적 증명은 여러 집합 존재 공리를 사용하므로 여기서는 증명 없이 사용한다. 아래의 덧셈, 곱셈, 거듭제곱은 모두 이 재귀 정리에 의해 존재성과 유일성이 보장된다.
문제 6.5. 자연수 위의 재귀 정리를 사용하여 정의되는 함수 \(f\colon\mathbb N\to\mathbb N\)이 \[ f(0)=1,\quad f(S(n))=S(S(f(n))) \] 을 만족시킨다고 하자.
- \(f(0),\,f(1),\,f(2),\,f(3),\,f(4)\)를 차례로 구하시오.
- 이 재귀식이 함수 \(f\)를 유일하게 정한다는 것을 정리 6.2에 맞추어 설명하시오.
자연수의 폰 노이만 구성에 관하여 다음 성질도 자주 사용한다.
보조정리 6.3. (자연수의 추이성과 자기 비소속)
모든 \(n\in\mathbb N\)에 대하여 \(n\)은 추이적 집합이다. 즉 \(x\in y\in n\)이면 \(x\in n\)이다. 또한 \(n\notin n\)이다.
증명 \(n\)에 대한 수학적 귀납법을 사용한다. \(n=0\)일 때 두 주장은 자명하다. \(n\)이 추이적이고 \(n\notin n\)이라고 가정하자. \(x\in y\in S(n)=n\cup\{n\}\)이면 \(y\in n\)이거나 \(y=n\)이다. 어느 경우에도 \(x\in n\subseteq S(n)\)이므로 \(S(n)\)은 추이적이다.
이제 \(S(n)\in S(n)\)이라고 가정하자. 그러면 \(S(n)\in n\)이거나 \(S(n)=n\)이다. 후자이면 \(n\in S(n)=n\)이 되어 모순이다. 전자이면 \(n\in S(n)\in n\)이고 \(n\)의 추이성에 의해 \(n\in n\)이 되어 역시 모순이다. 따라서 \(S(n)\notin S(n)\)이다.
3. 자연수의 덧셈
자연수의 덧셈을 재귀적으로 정의한다. 자연수 \(m\)을 고정시키면 정리 6.2를 \(a=m\), \(F=S\)에 적용할 수 있으므로, 임의의 자연수 \(n\)에 대하여 다음 두 식에 의하여 \(m+n\)이 유일하게 정해진다. \[\begin{aligned} m+0&=m,\\[3pt] m+S(n)&=S(m+n). \end{aligned}\]
예를 들어, \(2+2\)를 계산하면 다음과 같다. \[\begin{aligned} 2+2&=2+S(1) =S(2+1) =S(2+S(0))\\[3pt] &=S(S(2+0)) =S(S(2)) =S(3) =4. \end{aligned}\]
문제 6.6. 덧셈의 정의를 사용하여 다음을 계산하시오.
- \(3+2\)
- \(2+3\)
- \(4+1\)
- \(1+4\)
자주 사용하는 덧셈의 기본 성질은 다음과 같다.
정리 6.4. (자연수 덧셈의 기본 법칙)
자연수 \(m,\,n,\,p\)에 대하여 다음이 성립한다.
- 결합법칙: \((m+n)+p=m+(n+p)\)
- 교환법칙: \(m+n=n+m\)
- 소거법칙: \(m+p=n+p\)이면 \(m=n\)이다.
문제 6.7. 자연수 \(n,m,p\)에 대하여 다음이 성립함을 증명하시오. (7절의 내용을 참조하시오.)
- \((n+m)+p=n+(m+p)\)
- \(n+S(p)=S(n)+p\)
- \(p+0=0+p\)
- \(n+1=S(n)\)
- \(n+p=p+n\)
- \(n+p=m+p\)이면 \(n=m\)이다.
4. 자연수의 곱셈
자연수의 곱셈도 재귀적으로 정의한다. 자연수 \(m\)을 고정시키고 이미 정의한 덧셈을 사용하면, 정리 6.2와 다음 두 식에 의하여 \(m\cdot n\)이 유일하게 정해진다. \[\begin{aligned} m\cdot0&=0,\\[3pt] m\cdot S(n)&=m\cdot n+m. \end{aligned}\]
예를 들어, \(2\cdot3\)을 계산하면 다음과 같다. \[\begin{aligned} 2\cdot3&=2\cdot S(2) =2\cdot2+2\\[3pt] &=2\cdot S(1)+2 =(2\cdot1+2)+2\\[3pt] &=(2\cdot S(0)+2)+2 =((2\cdot0+2)+2)+2\\[3pt] &=(0+2)+2+2 =6. \end{aligned}\]
문제 6.8. 곱의 정의를 사용하여 다음을 계산하시오.
- \(3\cdot2\)
- \(4\cdot1\)
- \(1\cdot3\)
- \(3\cdot3\)
자주 사용하는 곱셈의 기본 성질은 다음과 같다.
정리 6.5. (자연수 곱셈의 기본 법칙)
자연수 \(m,n,p\)에 대하여 다음이 성립한다.
- 결합법칙: \((m\cdot n)\cdot p=m\cdot(n\cdot p)\)
- 교환법칙: \(m\cdot n=n\cdot m\)
- 분배법칙: \(m\cdot(n+p)=m\cdot n+m\cdot p\)이고 \((m+n)\cdot p=m\cdot p+n\cdot p\)이다.
- 항등원의 성질: \(m\cdot1=1\cdot m=m\)
- \(0\)의 성질: \(m\cdot0=0\cdot m=0\)
문제 6.9. 자연수 \(n\), \(m\), \(p\)에 대하여 다음이 성립함을 증명하시오.
- \(n\cdot1=n\)
- \(n\cdot(m+p)=n\cdot m+n\cdot p\)
- \((n\cdot m)\cdot p=n\cdot(m\cdot p)\)
- \(0\cdot p=0\)
- \(1\cdot p=p\)
- \((1+n)\cdot p=1\cdot p+n\cdot p\)
- \(n\cdot p=p\cdot n\)
- \((m+p)\cdot n=m\cdot n+p\cdot n\)
5. 자연수의 거듭제곱
자연수의 거듭제곱도 재귀적으로 정의한다. 자연수 \(m\)을 고정시키고 정리 6.2를 적용하면 다음 두 식에 의하여 \(m^n\)이 유일하게 정해진다. \[\begin{aligned} m^0&=1,\\[3pt] m^{S(n)}&=m^n\cdot m. \end{aligned}\]
특별히 \(0^0=1\)로 정의한다는 점에 주목하자. 이것은 조합론과 집합론에서 자연스러운 정의이다.
문제 6.10. 거듭제곱의 재귀적 정의만을 사용하여 다음을 계산하시오.
- \(2^3\)
- \(3^2\)
- \(0^0\)
- \(0^3\)
- \(1^4\)
자주 사용하는 거듭제곱의 기본 성질은 다음과 같다.
정리 6.6. (자연수 거듭제곱의 기본 법칙)
자연수 \(m,n,a,b\)에 대하여 다음이 성립한다.
- \(m^{a+b}=m^a\cdot m^b\)
- \((m^a)^b=m^{a\cdot b}\)
- \((m\cdot n)^a=m^a\cdot n^a\)
- \(1^n=1\)
- \(m^1=m\)
문제 6.11. 정리 6.6의 다섯 식을 자연수에 대한 귀납법으로 증명하시오.
3장에서 \(A^B\)는 \(B\)에서 \(A\)로 가는 함수들의 집합을 뜻하였다. 자연수 \(m,n\)도 집합이므로 이 표기와 산술적 거듭제곱 \(m^n\)이 같은 모양으로 나타나지만, 두 대상이 집합으로서 같다는 뜻은 아니다. 혼동을 피하기 위하여 \[\operatorname{Fun}(n,m)=\{f\mid f\colon n\to m\}\] 로 쓰자.
문제 6.12. 자연수 \(m,n\)에 대하여 \(\operatorname{Fun}(n,m)\)은 유한집합이고 \[|\operatorname{Fun}(n,m)|=m^n\] 임을 증명하시오. 오른쪽의 \(m^n\)은 이 절에서 재귀적으로 정의한 자연수의 거듭제곱이다.
문제 6.13. \(2=\{0,1\}\), \(3=\{0,1,2\}\)로 두자.
- 함수 \(f\colon2\to3\)를 순서쌍 \((f(0),f(1))\)로 나타내어 모두 나열하시오.
- \(|\operatorname{Fun}(2,3)|=3^2\)임을 직접 확인하시오.
- 일반적으로 \(n\)에서 \(m\)으로 가는 함수를 정할 때 각 입력값마다 몇 가지 선택이 있는지 설명하시오.
6. 페아노 공리
페아노 공리(Peano axioms)는 자연수의 본질적 성질을 설명하는 공리 체계이다. 집합 \(N\), 원소 \(0\in N\), 함수 \(S\colon N\to N\)이 다음을 만족시킬 때 페아노 공리를 만족시킨다고 말한다.
공리 6.7. (페아노 공리)
- \(0\in N\)이다.
- \(n\in N\)이면 \(S(n)\in N\)이다.
- 모든 \(n\in N\)에 대하여 \(S(n)\ne0\)이다.
- \(S(m)=S(n)\)이면 \(m=n\)이다.
- 귀납 공리: \(A\subseteq N\)이 \(0\in A\)이고 \(n\in A\)일 때마다 \(S(n)\in A\)를 만족시키면 \(A=N\)이다.
문제 6.14. 집합 \(N=\{0,1,2\}\)와 원소 \(0\)을 생각하자.
- 함수 \(S\colon N\to N\)을 \[ S(0)=1,\quad S(1)=2,\quad S(2)=2 \] 로 정의할 때, 페아노 공리의 다섯 조건 중 어느 것이 성립하고 어느 것이 성립하지 않는지 판정하시오.
- 함수 \(T\colon N\to N\)을 \[ T(0)=1,\quad T(1)=2,\quad T(2)=0 \] 로 정의할 때도 같은 질문에 답하시오.
- 위 두 예가 페아노 공리 전체를 만족시키지 못하는 이유를 설명하시오.
폰 노이만의 방법으로 구성한 \((\mathbb N,0,S)\)는 페아노 공리를 만족시킨다. 첫째와 둘째 공리는 \(\mathbb N\)이 귀납적 집합이라는 사실에서 따른다. 셋째는 \(S(n)=n\cup\{n\}\)가 공집합이 아니므로 성립한다. 넷째를 보이기 위하여 \(S(m)=S(n)\)이라고 하자. \(m\in S(m)=S(n)\)이고 \(n\in S(n)=S(m)\)이다. \(m\ne n\)이면 \(m\in n\)이고 \(n\in m\)이므로, 보조정리 6.3에 의해 \(n\in m\in n\)에서 \(n\in n\)이 되어 모순이다. 따라서 \(m=n\)이다. 마지막으로 \(A\subseteq\mathbb N\)이 귀납적이면 \(\mathbb N\)의 최소성에 의해 \(\mathbb N\subseteq A\)이고, 이미 \(A\subseteq\mathbb N\)이므로 \(A=\mathbb N\)이다.
7. 연산 법칙의 증명
자연수의 연산 법칙들은 수학적 귀납법을 사용하여 증명할 수 있다. 예를 들어, 덧셈의 결합법칙 \[(m+n)+p=m+(n+p)\] 는 \(p\)에 대한 수학적 귀납법을 사용하여 다음과 같이 증명할 수 있다.
- 기초 단계: \(p=0\)일 때, \((m+n)+0=m+n=m+(n+0)\).
- 귀납 단계: \((m+n)+p=m+(n+p)\)라고 가정하면, \[\begin{aligned} (m+n)+S(p)&=S((m+n)+p) &&\text{(덧셈의 정의)}\\[3pt] &=S(m+(n+p)) &&\text{(귀납 가정)}\\[3pt] &=m+S(n+p) &&\text{(덧셈의 정의)}\\[3pt] &=m+(n+S(p)). &&\text{(덧셈의 정의)} \end{aligned}\]
다른 법칙들도 유사한 방법으로 증명할 수 있다. 이러한 증명은 자연수의 귀납적 구조를 활용한다.
문제 6.15. 함수 \(T\colon\mathbb N\to\mathbb N\)을 \[ T(0)=0,\quad T(S(n))=T(n)+S(n) \] 으로 재귀적으로 정의하자.
- \(T(0),\,T(1),\,T(2),\,T(3),\,T(4)\)를 구하시오.
- 모든 \(n\in\mathbb N\)에 대하여 \[ 2\cdot T(n)=n\cdot S(n) \] 임을 수학적 귀납법을 사용하여 증명하시오.
8. 순서 관계
자연수 \(m,n\)에 대하여 \[m<n\quad\Longleftrightarrow\quad m\in n\] 으로 정의하고, \(m\le n\)은 \(m<n\) 또는 \(m=n\)이라는 뜻으로 사용한다. 폰 노이만 자연수에서는 이 순서가 부분집합 관계와 산술적 차이의 존재로도 표현된다.
정리 6.8. (자연수 순서의 성질)
자연수 \(m,n\)에 대하여 다음이 성립한다.
- \(m\le n\)일 필요충분조건은 \(m\subseteq n\)인 것이다.
- \(m<n\)일 필요충분조건은 어떤 \(k\in\mathbb N\setminus\{0\}\)에 대하여 \(m+k=n\)인 것이다.
- \(m<n\), \(m=n\), \(n<m\) 중 정확히 하나가 성립한다.
- 공집합이 아닌 \(\mathbb N\)의 부분집합은 최소원소를 가진다.
- \(n<S(n)\)이므로 \(\mathbb N\)에는 최대원소가 없다.
위 정리의 네 번째 성질을 정렬성(well-ordering property)이라고 한다. 마지막 성질은 단순히 자연수 집합에 최대원소가 없다는 뜻이며, 실수나 순서체에서 말하는 아르키메데스 성질과는 구별한다.
문제 6.16. 폰 노이만 자연수의 순서에 대하여 다음을 구하시오.
- \(1<4\), \(4<1\), \(2\le2\), \(3\le4\)의 참과 거짓을 각각 판정하고, 집합의 원소 관계 또는 부분집합 관계로 확인하시오.
- \(2<5\)를 \(2\in5\), \(2\subseteq5\), 그리고 \(2+k=5\)인 \(k\ne0\)의 존재라는 세 가지 방법으로 확인하시오.
- \(n<4\)를 만족시키는 자연수 \(n\)을 모두 구하시오. 또한 \(n\le4\)를 만족시키는 자연수 \(n\)을 모두 구하시오.
- 집합 \(\{5,\,2,\,8,\,3\}\)의 최소원소를 구하시오.
문제 6.17. 정리 6.8을 증명하시오. 특히 정렬성은 수학적 귀납법을 이용하여 증명하시오.
문제 6.18. \(\mathbb N\times\mathbb N\) 위의 관계 \(\sim\)를 \[(a,b)\sim(c,d)\quad\Longleftrightarrow\quad a+d=b+c\] 로 정의하자.
- \(\sim\)가 동치관계임을 보이시오.
- 몫집합 \(\mathbb Z=(\mathbb N\times\mathbb N)/\sim\)를 생각하자. 동치류 \([(a,b)]\)를 형식적인 차 \(a-b\)로 해석할 수 있음을 설명하시오.
- \(i\colon\mathbb N\to\mathbb Z\), \(i(n)=[(n,0)]\)이 일대일함수임을 보이시오.
- 다음 연산이 대표원의 선택과 무관하게 잘 정의됨을 보이시오. \[[(a,b)]+[(c,d)]=[(a+c,b+d)],\] \[[(a,b)]\cdot[(c,d)]=[(ac+bd,ad+bc)].\]