수학적 귀납법은 정의역이 자연수 집합인 함수의 성질을 밝힐 때뿐만 아니라 정의역이 자연수 집합인 함수를 정의할 때도 사용된다. 예컨대 \(a\)가 \(0\)이 아닌 실수이고 \(n\)이 자연수일 때 \[a^0 = 0 ,\quad a^{n+1} = a^n \times a\] 라고 정의하면, 모든 자연수 \(n\)에 대하여 거듭제곱 \(a^n\)이 정의된다. 이와 같은 방법으로 정의된 함수를 귀납적으로 정의된 함수라고 부른다.
이 글에서는 귀납적으로 정의된 함수가 잘 정의된 함수임을 보장하는 정리를 살펴보자. 이 글에서 ‘자연수’는 \(0\) 이상인 정수를 이르는 것으로 약속한다.
정리 1. 귀납적으로 정의된 함수.
\(X\)가 집합이고 \(x_0 \in X\)이며, \(g:X\rightarrow X\)가 함수라고 하자. 그러면 두 조건
- \(f(0) = x_0\)
- 임의의 \(n\in\mathbb{N}\)에 대하여 \(f(n^+ ) = g(f(n))\)
을 모두 만족시키는 함수 \(f:\mathbb{N}\rightarrow X\)가 유일하게 존재한다.
\(n\in\mathbb{N}\)이라고 하자. 만약 함수 \(h:n\rightarrow X\)가 두 조건
- \(h_0 (0) = x_0\)
- \(0\in n\)일 때, \(m^+ \in n\)인 임의의 \(m\)에 대하여 \(h(m^+ ) = g(h(m))\)
을 모두 만족시키면 \(h\)를 ‘\(n\)-귀납적 함수’라고 부르자. 또한 임의의 \(n\)에 대하여 \(n\)-귀납적인 함수를 \(\mathbb{N}\)-귀납적 함수라고 부르자. 그러면 정리의 결론을 다음과 같이 바꾸어 쓸 수 있다.
\(\mathbb{N}\)-귀납적 함수 \(f : \mathbb{N} \rightarrow X\)가 존재한다.
이제 다섯 단계를 따라 정리 1을 증명한다.
명제 1. 임의의 \(n\in\mathbb{N}\)에 대하여, \(n\)-귀납적 함수가 존재한다.
증명
수학적 귀납법을 사용하자. \(n=0\)일 때는 자명하다.
이제 \(n\)이 자연수이고, \(n\)-귀납적 함수가 존재한다고 가정하자. 만약 \(n=0\)이라면 \(h(0)=x_0\)이라고 정의된 함수 \(h=\left\{ \langle 0,\,x_0 \rangle\right\}\)은 \(1\)-귀납적 함수이다. 만약 \(n\ne 0\)이면 적당한 \(k\)에 대하여 \(n=k^+\)이며 \(n\)-귀납적 함수 \(h\)가 존재한다. \(h ' = h\cup \left\{ \langle n ,\, g(h(k)) \rangle \right\}\)는 \((n^+)\)-귀납적 함수이다.
명제 2. \(h_1\)이 \(n_1\)-귀납적 함수이고 \(h_2\)가 \(n_2\)-귀납적 함수라고 하자. 만약 \(m\in n_1 \cap n_2\)이면 \(h_1 (m) = h_2 (m)\)이다.
증명
\(m\)에 대한 수학적 귀납법을 사용하자.
\(m=0\)이면 \(h_1 (0) = x_0 = h_2 (0)\)이다.
이제 자연수 \(m\)에 대하여 정리의 결론 부분이 성립한다고 가정하고, \(m^+ \in n_1 \cap n_2\)라고 하자. 그러면 귀납적 가정에 의하여 \[h_1 (m^+ ) = g(h_1 (m)) = g(h_2 (m)) = h_2 (m^+ )\] 가 성립한다.
명제 3. 각 자연수 \(n\)에 대하여, \(n\)-귀납적 함수가 유일하게 존재한다.
증명
명제 3에 의하여 자명하게 성립한다.
명제 4. \(\mathbb{N}\)-귀납적 함수가 존재한다면 그 함수는 유일하다.
증명
\(f_1\)과 \(f_2\)가 \(\mathbb{N}\)-귀납적 함수라고 하자. 각 \(n\)에 대하여, \(f_1\)의 정의역을 \(n\)으로 축소한 함수와 \(f_2\)의 정의역을 \(n\)으로 축소한 함수는 모두 \(n\)-귀납적 함수이다. 그러므로 \(f_1 = f_2\)이다. 여기서 \(n\)은 임의의 자연수이므로 \(f_1\)과 \(f_2\)는 \(\mathbb{N}\)에서 일치한다.
\(n\)-귀납적 함수는 \(\mathcal{P}(\mathbb{N}\times X)\)의 원소이다. 또한 \(\mathcal{P}(\mathbb{N}\times X)\)의 원소 중에서 적당한 \(n\)에 대하여 \(n\)-귀납적 함수인 것만 모아서 집합 \(N\)을 구성할 수 있다. \(N\)이 \(\langle k,\,\ell\rangle\) 꼴이 순서쌍들의 집합의 집합이므로, \[f=\bigcup N\] 은 순서쌍들의 집합이다. 즉 \(f\)는 \(\mathbb{N}\times X\)의 부분집합이다.
이와 같이 정의된 집합 \(f\)가 바로 우리가 바라는 함수가 된다.
명제 5. \(f\)는 \(\mathbb{N}\)-귀납적 함수이다.
증명
먼저 \(f\)가 \(\mathbb{N}\)으로부터 \(X\)로의 함수임을 보이자.
\(n\in\mathbb{N}\)이라고 하자. 그러면 \((n+1)\)-귀납적 함수 \(h\)가 존재하여 적당한 \(\langle n ,\,x\rangle \in \bigcup N\)에 대하여 \(x = h(n) \in X\)를 만족시킨다. 만약 \(\langle n ,\,x ' \rangle \in \bigcup N\)이면 \(n\in k\)인 적당한 \(k\)에 대하여 \(k\)-귀납적 함수 \(h ' \)이 존재하여 \(h ' (n) = x'\)을 만족시킨다. 여기서 명제 2에 의하여 \[x ' = h'(n) = h(n) = x\] 이다. 그러므로 \(f\)는 \(\mathbb{N}\)으로부터 \(X\)로의 함수이다.
이제 \(f\)가 \(\mathbb{N}\)-귀납적 함수임을 보이자. \(n\in\mathbb{N}\)이고 \(h:n^{++} \rightarrow X\)가 \(n^{++}\)-귀납적 함수라고 하자. 그러면 \(h(0) = x_0\)이고 \(f(0) = x_0\)이며 \[f(n^+) = h(n^+) = g(h(n)) = g(f(n))\] 이다. 따라서 \(f\)는 \(\mathbb{N}\)-귀납적 함수이다.
이로써 명제 5와 명제 4에 의하여 정리 1이 증명되었다.
따름정리 2. \(A\)와 \(X\)가 집합이고 \(h : A\rightarrow X\)와 \(g:A\times X \rightarrow X\)가 함수라고 하자. 그러면 두 조건
- 임의의 \(a\in A\)에 대하여 \(f(a,\,0) = h(a)\);
- 임의의 \(a\in A\)와 \(n\in\mathbb{N}\)에 대하여 \(f(a,\,n^+ ) = g(a,\,f(a,\,n))\)
을 모두 만족시키는 함수 \(f:A\times\mathbb{N} \rightarrow X\)가 유일하게 존재한다.
증명
각 \(a\in A\)에 대하여 정리 1을 적용한다. 즉 \(x_0 = h(a)\)라고 하고, \(g_a : X \rightarrow X\)를 \(g_a (x) = g(a,\,x)\)라고 정의한다. 그러면 정리 1에 의하여 \(f_a (0) = g(a)\)이고 각 \(n\in\mathbb{N}\)에 대하여 \(f_a ( n^+ ) = g_a ( f_a (n))\)인 함수 \(f_a : \mathbb{N} \rightarrow X\)가 유일하게 존재한다. 이제 함수 \(f:A\times\mathbb{N} \rightarrow X\)를 \(f(a,\,n) = f_a (n)\)으로 정의한다. 이와 같이 정의된 함수를 집합으로 나타내면 다음과 같다. \[f = \left\{ x\in (A\times \mathbb{N}) \times X \,\vert\, \exists a\in A \exists n\in\mathbb{N} \,:\, x=\langle\langle a,\,n\rangle ,\, f_a (n)\rangle \right\}.\] 명백히 \(f\)는 정리의 두 조건을 모두 만족시키는 함수이다.