이 글에서 ‘자연수’는 \(0\) 이상인 정수를 이르는 것으로 약속한다.
자연수 집합의 정의
정의 1.
자연수를 다음과 같은 집합으로 정의한다. \[\begin{aligned} 0 &= \varnothing, \\[5pt] 1 &= 0^+ = \left\{ 0 \right\} ,\\[5pt] 2 &= 1^+ = \left\{ 0,\,1 \right\} ,\\[5pt] 3 &= 2^+ = \left\{ 0 ,\,1,\,2 \right\} , \\[5pt] &\,\,\,\,\vdots \end{aligned}\]
정의 1에서 정의된 각 정수는 논리식으로 표현될 수 있다. 예컨대 \(1\)은 다음 논리식을 만족시키는 집합 \(x\)이다. \[\exists z ( \forall y ( \neg y \in z ) \wedge z \in x \wedge \forall w ( w \in x \rightarrow w = z ))\] \(2\)와 \(3\)도 마찬가지로 논리식으로 나타낼 수 있으나, 무척이나 긴 논리식이 된다.
\(n\)이 자연수이면 \(n\)은 원소의 개수가 \(n\)인 유한집합이다. 즉 자연수 각각은 집합이다. 하지만 자연수를 모두 모은 모임이 집합이 된다는 것은 아직 확신할 수 없다.
정의 2. \(x\)가 집합이라고 하자. 이때 \(x\cup \left\{ x \right\}\)를 \(x\)의 따름수(successor)라고 부르고 \(x^+\)로 나타낸다.
정의 3. \(x\)가 집합이라고 하자. 만약 \(x\)가 두 조건
- \(\varnothing \in x,\)
- \(y\in x\)일 때마다 \(y^+ \in x\)이다
를 모두 만족시키면, 즉 \(x\)가 따름수 연산에 대하여 닫혀 있으면, \(x\)를 귀납적 집합(inductive set)이라고 부른다.
ZF7. 무한 공리; Axiom of Infinity.
귀납적 집합이 존재한다.
정리 4. 임의의 귀납적 집합의 부분집합인 귀납적 집합이 유일하게 존재한다. 즉 두 조건
- \(N\)은 귀납적 집합이다,
- \(Y\)가 귀납적 집합이면 \(N \subseteq Y\)이다
를 모두 만족시키는 집합 \(N\)이 유일하게 존재한다.
증명
“\(x\)가 귀납적 집합이다”라는 진술을 \(\phi(x)\)로 나타내자. 그리고 \(X\)가 귀납적 집합 중 하나라고 하자(무한 공리에 의하여 귀납적 집합이 하나 이상 존재한다). \[N = \left\{ x \in X \,\vert\, \forall y ( \phi (y) \rightarrow x\in y )\right\}\] 라고 하자. 이제 \(N\)이 바라는 집합임을 보이자.
\(x\in N\)이라고 하자. 그리고 \(Y\)가 귀납적 집합이라고 하자. 그러면 \(N\)의 정의에 의하여 \(x\in Y\)이다. 여기서 \(Y\)가 귀납적 집합이므로 \(x^+ \in Y\)이다. 그런데 \(x\in X\)이므로 \(x^+ \in X\)이다. 그러므로 \(x^+ \in N\)이다. 즉 \(N\)은 귀납적 집합이다. 더욱이 이 증명 과정에서 \(N \subseteq Y\)라는 사실을 알 수 있다.
다음으로 \(N ' \)이 정리에서 제시한 두 조건에서 \(N\)을 \(N ' \)으로 바꾼 조건을 모두 만족시키는 또 다른 집합이라고 하자. 그러면 \(N ' \)이 귀납적 집합이므로 \(N \subseteq N ' \)이다. 두 집합의 역할을 바꾸면 \(N' \subseteq N\)을 얻는다. 그러므로 \(N=N'\)이다. 즉 정리의 두 조건을 만족시키는 집합 \(N\)은 유일하다.
정의 5. 임의의 귀납적 집합의 부분집합이 되는 귀납적 집합을 자연수 집합이라고 부르고 \(\mathbb{N}\)으로 나타낸다. 자연수 집합을 \(\omega\)로 나타내기도 한다.
자연수 집합 위에서의 순서관계
정리 6. 수학적 귀납법.
\(\phi (x)\)가 자연수 \(x\)에 대한 명제함수라고 하자. 만약 \(\phi\)가 두 조건
- \(\phi (0)\)이 성립한다,
- \(\phi (x)\)가 성립할 때마다 \(\phi ( x^+ )\)가 성립한다
를 모두 만족시키면, 임의의 \(x\in\mathbb{N}\)에 대하여 \(\phi (x)\)가 성립한다.
증명
\(\phi\)의 진리집합을 \(X\)라고 하자. 즉 \[X = \left\{ x\in \mathbb{N} \,\vert\, \phi(x)\right\}\] 라고 하자. 그러면 \(X\)는 귀납적 집합이므로 \(\mathbb{N} \subseteq X\)이다. 또한 \(X\)는 \(\mathbb{N}\)의 원소로 이루어진 집합이므로 \(X\subseteq\mathbb{N}\)이다. 그러므로 \(X=\mathbb{N}\)이다.
수학적 귀납법은 자연수 집합에서 정의된 관계나 함수, 또는 자연수의 연산과 관련된 성질을 증명할 때 사용된다.
정의 7. 자연수 집합에서 순서관계를 다음과 같이 정의한다. \[R_\le = \left\{ \langle n,\,m \rangle \in \mathbb{N} \times \mathbb{N} \,\vert\, (n\in m) \vee (n=m )\right\}.\]
편의상 \(\langle n,\,m \rangle \in R_\le\)를 \(n\le m\)으로 나타낸다.
정리 8. \(m\)과 \(n\)이 자연수라고 하자. 이때 \(m\le n\)이기 위한 필요충분조건은 \(m\subseteq n\)인 것이다.
증명
[\(\Rightarrow\)] \(\phi (n)\)을 “\(m\le n\)이면 \(m\subseteq n\)이다”라고 정의하자. 이제 수학적 귀납법을 이용하여 증명하자.
- \(n=0\)이라고 하자. 만약 \(m\le n\)이라면, \(m\in n\)이거나 \(m=n\)이다. 그러나 \(n=\varnothing\)이므로 \(m\in n\)은 불가능하다. 그러므로 \(m=n\) 즉 \(m\subseteq n\)이다. 따라서 \(\phi (0)\)이 성립한다.
- 다음으로 \(n\)이 자연수이고 \(\phi (n)\)이 성립한다고 가정하자. 또한 \(m\le n^+\)이라고 가정하자. 그러면 \(m=n^+\) 또는 \(m\in n^+\)가 성립한다. \(m=n^+\)인 경우 \(m\subseteq n^+\)이므로 \(m\in n^+ = n\cup \left\{ n \right\}\)이다. 그러므로 “\(m=n^+\) 또는 \(m\in n^+\)”라는 결과를 “\(m=n\) 또는 \(m\in n\)”으로 바꿀 수 있다. 따라서 순서관계의 정의에 의하여 \(m\le n\)을 얻으며, 귀납적 가정에 의하여 \(m\subseteq n\)을 얻는다. 그런데 \(m\subseteq n\subseteq n^+\)이므로 \(\phi ( n^+ )\)가 성립한다.
[\(\Leftarrow\)] \(\phi (n)\)을 “\(m\in\mathbb{N}\)이고 \(m\subseteq n\)이면, \(m\le n\)이다”라고 정의하자. 그리고 수학적 귀납법을 이용하여 증명하자.
- \(n=0,\) \(m\subseteq n\)이라고 가정하자. 그러면 \(m=0\)이므로 \(m=n\)이고 \(m\le n\)이다. 즉 \(\phi (0)\)이 성립한다.
- 이제 \(\phi (n)\)이 성립한다고 가정하자. 그리고 \(m\in\mathbb{N}\)이고 \(m\subseteq n^+\)라고 가정하자. 그러면 \(m\subseteq n\cup\left\{ n \right\}\)이다. 이제 두 가지 경우로 나누어 살펴보자.
먼저 \(n\notin m\)인 경우를 살펴보자. 그러면 \(m\subseteq n\)이므로 귀납적 가정에 의하여 \(m\le n\)이다. 즉 \(n=m\) 또는 \(m\in n\)이 성립하며, \(m\in n^+\)를 얻는다.
다음으로 \(n\in m\)인 경우를 살펴보자. 그러면 \(n\le m\)이며, [\(\Rightarrow\)]의 증명 결과에 따라 \(n\subseteq m\)이다. 따라서 \(n\in m\)이고 \(n\subseteq m \subseteq n\cup\left\{ n \right\}\)이다. 그러므로 \(m=n^+\)이다.
두 경우 모두 \(m\le n^+\)를 얻으므로, \(\phi (n^+ )\)가 성립한다.
정리 9. 관계 \(\le\)는 \(\mathbb{N}\) 위에서 반순서이다.
증명
\(m\)과 \(n\)이 자연수일 때, 정리 8에 의하여, \(m\le n\)이기 위한 필요충분조건은 \(m\subseteq n\)이다. 이 사실을 이용하자.
- 임의의 \(n\)에 대하여 \(n\subseteq n\)이다. 그러므로 \(\le\)는 반사적 관계이다.
- \(m\le n\)이면서 \(n\subseteq m\)이면, \(m\subseteq n\)이면서 \(n\subseteq m\)이므로 \(m=n\)이다. 그러므로 \(\le\)는 반대칭적 관계이다.
- \(\ell \le m\)이면서 \(m\le n\)이라고 가정하자. 그러면 \(\ell \subseteq m\)이면서 \(m\subseteq n\)이므로 \(\ell \subseteq n\) 즉 \(\ell \le n\)이다. 그러므로 \(\le\)는 추이적 관계이다.
정리 10. 순서관계 \(\le\)는 \(\mathbb{N}\)에서 전순서이다.
증명
\(n\)이 자연수일 때, “\(m\in \mathbb{N}\)이고 \(m\nleq n\)이면, \(n\le m\)이다”를 \(\phi (n)\)으로 나타내자. 이제 \(n\)에 대한 수학적 귀납법법을 사용하자.
- \(n=0\)일 때, 임의의 \(m\)에 대하여 \(0 = \varnothing \le m\)이다. 그러므로 \(\phi (0)\)이 성립한다.
- 다음으로, \(\phi (n)\)이 성립하고 \(m\in\mathbb{N}\)이며 \(m\nleq n^+\)라고 가정하자. 그러면 추이적 성질에 의하여 \(m\le n\)이며, 귀납적 가정에 의하여 \(n\le m\)이다. 그런데 \(m\ne n\)이므로 \(\le\)의 정의에 의하여 \(n\in m\)이다. 그러므로 \(n^+ \subseteq m\) 즉 \(n^+ \le m\)이다. 따라서 \(\phi ( n^+ )\)가 성립한다.
정리 11. \(n\)이 자연수라고 하자. 그러면 다음 중 하나가 성립하며, 하나만 성립한다.
- \(n=0.\)
- \(n=m^+\)인 \(m\)이 \(\mathbb{N}\)에 유일하게 존재한다.
증명
\(n\)이 자연수일 때, “\(n=0\) 또는 \((\exists m \in \mathbb{N})(n=m^+)\)”를 \(\phi (n)\)으로 나타내자. 여기에 \(n\)에 대한 수학적 귀납법을 사용하면, 임의의 \(n\)에 대하여 \(\phi(n)\)이 성립함을 보일 수 있다.
- \(n=0\)일 때 \(\phi (0)\)이 자명하게 성립한다.
- \(n\)이 자연수이고 \(\phi (n)\)이 성립한다고 가정하자. \(m=n\)이라고 하면 \(m^+ = n^+\)이므로 \(\phi(n^+ )\)가 성립한다.
이제 유일성을 증명하자. \(n = \ell^+ = m^+\)라고 가정하자. 그러면 \(\ell \cup \left\{ \ell \right\} = m\cup \left\{ m\right\}\)이므로, \(\ell \le m\)이고 \(m\le \ell\)이다. 그러므로 \(\ell =m\)이다.
정리 12. 강한 수학적 귀납법.
\(\phi (x)\)가 자연수 \(x\)에 대하여 정의된 명제함수라고 하자. 만약 임의의 \(n\in \mathbb{N}\)에 대하여 “[\(m\in \mathbb{N},\) \(m\in n\)일 때마다 \(\phi (m)\)이 참]이면 \(\phi(n)\)이 참이다”가 성립하면, 임의의 \(n\in\mathbb{N}\)에 대하여 \(\phi (n)\)이 성립한다.
증명
“\(m\in n\)이면 \(\phi (m)\)이 성립한다”를 \(\psi (n)\)으로 나타내자. 수학적 귀납법을 사용하여 임의의 \(n\)에 대하여 \(\psi (n)\)이 성립함을 보이자.
- 먼저 \(\psi (0)\)이 참이다. 왜냐하면 \(m\in 0\)인 \(m\)이 존재하지 않으므로 \(\psi (n)\)의 가정 부분이 거짓이 되기 때문이다.
- \(\psi (n)\)이 성립한다고 가정하자. 그러면 \(m\in n\)인 모든 \(m\)에 대하여 \(\phi (m)\)이 성립하므로 귀납적 가정에 의하여 \(\phi (n)\)이 성립한다. 그러므로 \(m\in n^+\)인 모든 \(m\)에 대하여 \(\phi (m)\)이 성립하므로, \(\psi (n^+ )\)가 성립한다.
다음 정리는 수학적 귀납법으로부터 얻어지는 자연수의 순서관계의 중요한 성질이다.
정리 13. 자연수 집합의 정렬성.
\(S\)가 \(\mathbb{N}\)의 부분집합이고 \(S\ne\varnothing\)이면, \(S\)는 최소원소를 가진다.
증명
\(S\)가 \(\mathbb{N}\)의 부분집합이라고 하자. 그리고 “\(n\notin S\)”를 \(\phi (n)\)으로 나타내자.
결론과는 반대로 \(S\)가 최소원소를 갖지 않는다고 가정하자.
- 명백히 \(0\notin S\)이므로 \(\phi (0)\)이 성립한다.
- 다음으로 \(m\in n\)인 모든 \(m\)에 대하여 \(\phi (m)\)이 성립한다고 가정하자. 그러면 \(m\in n\)인 모든 \(m\)에 대하여 \(m\notin S\)이다. 그러므로 \(n\notin S\)이다. 왜냐하면, 만약 \(n\in S\)라면 \(n\)이 \(S\)의 최소원소가 되기 때문이다. 그러므로 \(\phi (n)\)이 성립한다.
그러므로 강한 수학적 귀납법에 의하여 임의의 \(n\)에 대하여 \(\phi (n)\)이 성립한다. 이것은 \(S\)가 공집합임을 의미한다.
강한 수학적 귀납법과 자연수 집합의 정렬성은 서로 동치이다. 즉 정리 13을 사용하여 정리 12를 증명할 수 있다.
정리 13이 성립한다고 가정하자. 정리 12의 명제함수 \(\phi\)에 대하여\[S = \left\{ n\in\mathbb{N} \,\vert\, \neg\phi (n)\right\}\]이라고 하자. 그러면 정리 12의 가정에 의하여 \(S\)는 최소원소를 갖지 않는다. 즉 \(S\)는 공집합이다. 그러므로 임의의 \(n\)에 대하여 \(\phi (n)\)이 성립한다.
