Mathematical induction
수학에서 명제를 증명하는 방법 중 하나이다. 귀납법이란 이름과 달리 연역적인 형태를 띄지만, 수학자들은 관습적으로 이를 귀납법이라 부른다.
목차
1. 진술
2. 증명
3. 일반화
4. 영상
자연수에 대한 명제
P가 있다고 하자. 이 때
이면
P는 모든 자연수에 대해 참이다.
P가 참인 자연수의 집합을 S\in\Bbb N이라 하자. S\neq\Bbb N이면, \Bbb N-S\in\Bbb N, \Bbb N-S\neq\varnothing이므로 자연수의 정렬성의 원리에 의해 그 최소원소 m이 존재한다. 1\in S이므로 m>1이고, 따라서 m-1\in\Bbb N-S임에서 P(m-1)이다. 하지만 그렇다면 조건 2에 의해 P(m)이므로 m\not\in S에 모순. 따라서 S=\Bbb N이다.
수학적 귀납법은 초한 귀납법으로 일반화된다.
정렬집합
A에서의
P(x)가
\forall x\in A에 대한 모든
y<x에 대해
P(y)가 참이면 항상
P(x)도 참일 때,
\forall x\in A\ P(x)는 참이다. 흔히 다음을 증명하여 가정을 만족시킨다.
P(0)P(\alpha) \to P(\alpha+1)\forall \lambda<Λ\ P(\lambda) \to P(Λ)
위의
\alpha+1은 임의의
\alpha에 대한 따름서수이고,
Λ는 임의의 극한서수이다.
