개요
수학적 귀납법(Mathematical induction)은 일반화된 명제의 증명 방법으로, 귀납법이란 이름을 달고 있지만 사실은 연역법이다. 고등학교 교육과정에선 수학적 귀납법의 원리를 이해할 수 있을 정도로 간단히 다루지만 대학교에서 수학 관련 전공에 진입하면 증명까지 다루게 된다.
진술
자연수의 집합이 정의역인 조건을 [math]\displaystyle{ P(n) }[/math]이라고 하자. 만약
- [math]\displaystyle{ P(0) }[/math]이 참이다.
- 임의의 [math]\displaystyle{ n\in \mathbb{N} }[/math]에 대해 [math]\displaystyle{ P(n) }[/math]이 참이면 [math]\displaystyle{ P(n+1) }[/math]도 참이다.
이면 임의의 [math]\displaystyle{ n\in \mathbb{N} }[/math]에 대해 [math]\displaystyle{ P(n) }[/math]은 참이다.
명제를 형식적으로 나타내면 다음과 같다.
- [math]\displaystyle{ P(0) \land \forall (k\in \mathbb{N})[P(k)\Rightarrow P(k+1)]\Rightarrow \forall (n\in \mathbb{N})P(n) }[/math]
증명
[math]\displaystyle{ n'\in \mathbb{N} }[/math]이 존재하여 [math]\displaystyle{ P(n') }[/math]이 거짓이라고 가정하자. 그리고 집합 S를 다음과 같이 정의하자.
- [math]\displaystyle{ S=\{n\in \mathbb{N}\vert \neg P(n)\} }[/math]
그러면 [math]\displaystyle{ \neg P(n') }[/math]이 참이므로 [math]\displaystyle{ n'\in S }[/math]이다. 따라서 S는 공집합이 아니고 [math]\displaystyle{ \mathbb{N} }[/math]의 부분집합이므로, 정렬순서공리에 의해 S의 최소원소가 존재한다. 이 원소를 [math]\displaystyle{ n_0 }[/math]라고 하자. 이때 [math]\displaystyle{ P(0) }[/math]은 참이므로, [math]\displaystyle{ n_0\ne 0 }[/math]이고 따라서 [math]\displaystyle{ n_0 \ge 1 }[/math]이다. 그러면 [math]\displaystyle{ n_0 -1 \ge 0 }[/math]인데, [math]\displaystyle{ n_0-1 }[/math]은 S의 최소원소가 아니므로 [math]\displaystyle{ n_0 -1\not\in S }[/math]이다. 따라서 [math]\displaystyle{ P(n_0 -1) }[/math]는 참이다. 그러면 가정에 의해 [math]\displaystyle{ P(n_0) }[/math]는 참이므로 [math]\displaystyle{ n_0\not\in S }[/math]이다. 그러면 [math]\displaystyle{ n_0\in S }[/math]이고 [math]\displaystyle{ n_0\not\in S }[/math]이므로 [math]\displaystyle{ n'\in \mathbb{N} }[/math]이 존재하여 [math]\displaystyle{ P(n') }[/math]이 거짓이라는 가정에 모순이다. 따라서 원하는 결론을 얻게 된다.
수학적 귀납법의 변형
완전귀납법
자연수의 집합이 정의역인 조건을 [math]\displaystyle{ P(n) }[/math]이라고 하자. 만약
- [math]\displaystyle{ P(0) }[/math]이 참이다.
- 임의의 [math]\displaystyle{ n\in \mathbb{N} }[/math]에 대해 [math]\displaystyle{ P(0),P(1),\cdots,P(n) }[/math]이 참이면 [math]\displaystyle{ P(n+1) }[/math]도 참이다.
이면 임의의 [math]\displaystyle{ n\in \mathbb{N} }[/math]에 대해 [math]\displaystyle{ P(n) }[/math]은 참이다.
완전귀납법의 증명은 간단하다. 조건 [math]\displaystyle{ Q(n) }[/math]를 "[math]\displaystyle{ P(0),P(1),\cdots,P(n) }[/math]는 참이다."로 설정하면 [math]\displaystyle{ Q(0)=P(0) }[/math]은 참이고 [math]\displaystyle{ P(0),P(1),\cdots,P(n) }[/math]이 참이면 가정에 의해 [math]\displaystyle{ P(n+1) }[/math]가 참이므로 결국 [math]\displaystyle{ P(0),P(1),\cdots,P(n+1) }[/math]가 참이다. 즉 [math]\displaystyle{ Q(n) }[/math]이 참이면 [math]\displaystyle{ Q(n+1) }[/math]이 참이다. 따라서 [math]\displaystyle{ Q(n) }[/math]은 귀납법 가정을 만족하므로 임의의 [math]\displaystyle{ n\in \mathbb{N} }[/math]에 대해 [math]\displaystyle{ Q(n) }[/math]은 참인데 [math]\displaystyle{ Q(n) }[/math]의 정의에 의해 [math]\displaystyle{ P(n) }[/math]은 참이다.
한편 완전귀납법으로 정렬순서공리를 증명할 수 있다. 이 말은 수학적 귀납법과 정렬순서공리가 동치라는 것을 의미한다.
수학적 귀납법을 가정하자. 그리고 [math]\displaystyle{ \mathbb{N} }[/math]의 부분집합이고 공집합이 아니며, 최소원소가 없는 집합 S가 존재한다고 가정하자. 만약 [math]\displaystyle{ 0\in S }[/math]이면, 임의의 [math]\displaystyle{ x\in S }[/math]에 대해 [math]\displaystyle{ 0\le x }[/math]이므로 n이 S의 최소원소가 된다. 따라서 [math]\displaystyle{ 0\not\in S }[/math]이다. [math]\displaystyle{ 0\not \in S, 1\not\in S, \cdots, n\not\in S }[/math]라고 하자. 만약 [math]\displaystyle{ n+1\in S }[/math]라면, 임의의 [math]\displaystyle{ x\in S }[/math]에 대해 [math]\displaystyle{ n+1\le x }[/math]이므로 [math]\displaystyle{ n+1 }[/math]이 최소원소가 되어 모순이다. 따라서 [math]\displaystyle{ n+1\in S }[/math]이다. 따라서 완전귀납법에 의해 임의의 [math]\displaystyle{ n\in \mathbb{N} }[/math]에 대해 [math]\displaystyle{ n\not\in S }[/math]이고 따라서 S는 공집합이다. 이것은 S가 공집합이 아니라는 가정과 모순이다. 따라서 [math]\displaystyle{ \mathbb{N} }[/math]의 부분집합이고 공집합이 아닌 집합 S는 반드시 최소원소를 가진다.
초한귀납법
[math]\displaystyle{ P(x) }[/math]를 순서수를 정의역으로 하는 조건이라 하자. 임의의 순서수 α에 대해, 다음 만약
- 임의의 [math]\displaystyle{ \beta \lt \alpha }[/math]에 대해 [math]\displaystyle{ P(\beta) }[/math]가 참이면, [math]\displaystyle{ P(\alpha) }[/math]는 참이다.
이면 임의의 순서수 α에 대해 [math]\displaystyle{ P(\alpha) }[/math]는 참이다.